November 24, 2024

Posts Comments

Researchers Show How to Forge Site Certificates

December 30, 2008 by

Today at the Chaos Computing Congress, a group of researchers (Alex Sotirov, Marc Stevens, Jake Appelbaum, Arjen Lenstra, Benne de Weger, and David Molnar) announced that they have found a way to forge website certificates that will be accepted as valid by most browsers. This means that they can successfully impersonate any website, even for secure connections.

Let me unpack that for non-experts.

One of the cornerstones of web security is the use of secure connections. When your browser makes a secure connection to (say) Amazon and gets a page to display, the browser displays in its address bar a URL like “https://www.amazon.com”. The “https” indicates that the secure (https) protocol was used, and the browser also displays a happy blue lock or key icon to tell you the connection was secured.

The browser cooperates with Amazon’s web server to secure the connection via a two-step process. First, the two computers negotiate a shared secret key that they can use to communicate privately, using crypto tricks that I won’t describe here. Second, your browser authenticates Amazon’s web server, that is, it assures itself that the party on the other end of the connection is the genuine Amazon.com server.

Amazon has a digital certificate that it sends to your browser, as part of proving its identity. The certificate is issued by a party called a certification authority or CA. Your browser comes pre-programmed with a list of CAs its trusts; you can change the list but hardly anyone does. If your browser makes an encrypted connection to “amazon.com”, and the party on the other end of the connection owns a certificate for the name “amazon.com”, and that certificate was issued by a CA that your browser trusts, then your browser will conclude that it has a secure connection to amazon.com.

Now we can understand what the researchers accomplished: they showed how to forge a certificate corresponding to any address on the Web. For example, they can forge a certificate that allows themselves, or you, or me, or anybody, to impersonate amazon.com, or freedom-to-tinker.com, or maybe even fbi.gov. That is supposed to be impossible, for obvious reasons.

The forged certificates will say they were issued by a CA called “Equifax Secure Global eBusiness”, which is trusted by the major browsers. The forged certificates will be perfectly valid; but they will have been made by forgers, not by the Equifax CA.

To do this, the researchers exploited a cryptographic weakness in one of the digital signature methods, “MD5 with RSA”, supported by the Equifax CA. The first step in this digital signature method is to compute the hash (strictly speaking, the cryptographic hash) of the certificate contents.

The hash is a short (128-bit) code that is supposed to be a kind of unique digest of the certificate contents. To be secure, the hash method has to have several properties, one of which is that it should be infeasible to find a collision, that is, to find two values A and B which have the same hash.

It was already known how to find collisions in MD5, but the researchers improved the existing collision-finding methods, so that they can now find two values R and F that have the same hash, where R is a “real” certificate that the CA will be willing to sign, and F is a forged certificate. This is deadly, because it means that a digital signature on R will also be a valid signature on F — so the attacker can ask the CA to sign the real certificate R, then copy the resulting signature onto F — putting a valid CA signature onto a certificate that the CA would never voluntarily sign.

To demonstrate this, the researchers created a forged certificate signed by the Equifax CA. For safety, they made the forged certificate expire in the past and point to a harmless site. But it’s clear from their description that they can forge a certificate for any site they want.

Whose fault is this? Partly it’s a consequence of problems with the MD5 hash method. It’s been known for a few years that MD5 is in the process of melting down, so prudent designers have been moving away from MD5, replacing it with newer, better hash methods. Similarly, prudent CAs should not be signing certificates that use MD5-based signature methods; instead they should insist on signature methods involving stronger hashes. The Equifax CA did not follow this precaution.

The problem can be fixed, for now, by having CAs refuse to create new MD5-based signatures. But this is a sobering reminder that the certification process that underlies web site authentication — a mechanism we all rely upon daily — is far from bulletproof.

Filed Under: Privacy & Security Tagged With: , ,

Security Seals on AVC Advantage Voting Machines are Easily Defeated

December 19, 2008 by

On September 2, 2008, I submitted a report to the New Jersey Superior Court, demonstrating that the DRE voting machines used in New Jersey are insecure: it is easy to replace the vote-counting program with one that fraudulently shifts votes from one candidate to another.

In Section 10 of my report, I explained that

  1. There are no security seals on New Jersey’s AVC Advantages
    that prevent removal of the circuit-board cover;

  2. Even if there were security seals, physical security seals are easily defeated and would not significantly increase the security of elections in New Jersey.
  3. And in conclusion, one cannot achieve trustworthy elections solely by trying to ensure that a particular computer program is installed in the voting machine.

In October 2008, the State of New Jersey (and Sequoia Voting Systems) reacted by installing new security seals on the circuit board cover of voting machines in New Jersey. That is, they reacted to point 1 and ignored points 2 and 3.

In December 2008 I submitted to the Court a new report, and a new video, demonstrating how New Jersey’s new security seals can be removed and replaced without leaving evidence of tampering. It took me about 7 minutes the first time I tried it; I estimate it would take less than half that time with practice.

The video available here is now available in a compressed mp4 format, though it still takes a while to load. not well compressed and takes forever to load over the Internet; sometime in the near future I hope to make available a better-compressed video.

Filed Under: Other Topics, Privacy & Security Tagged With: ,

On the future of voting technologies: simplicity vs. sophistication

December 3, 2008 by

Yesterday, I testified before a hearing of Colorado’s Election Reform Commission. I made a small plug, at the end of my testimony, for a future generation of electronic voting machines that would use crypto machinery for end-to-end / software independent verification. Normally, the politicos tend to ignore this and focus on the immediately actionable stuff (e.g., current-generation DREs are unacceptably insecure; optical-scan is the best thing presently on the market). Not this time. I got a bunch of questions asking me to explain how a crypto voting system can be verifiable, how you can prove that the machine is behaving properly, and so forth. Pretty amazing. What I realized, however, is that it’s really hard to explain crypto machinery to non-CS people. I did my best, but it was clear from conversations afterward that a few minutes of Q&A did little to give them any confidence that crypto voting machinery really works.

Another of the speakers, Neil McBurnett, was talking about doing variable sampling-rate audits (as a function of how close the tally is). Afterward, he lamented to me, privately, how hard it is to explain basic concepts like what it means for something to be “statistically significant.”

There’s a clear common theme here. How do we explain to the public the basic scientific theories that underly the problems that voting systems face? My written testimony (reused from an earlier hearing in Texas) includes links to papers, and some people will follow up. Others won’t. My big question is whether we have a research challenge to invent progressively simpler systems that still have the right security properties, or whether we have an education challenge to explain that a certain amount of complexity is worthwhile for the good properties that can be achieved. (Uglier question: is it a desirable goal to weaken the security properties in return for greater simplicity? What security properties would you sacrifice?)

Certainly, with our own VoteBox system, which uses a variation on Benaloh‘s voter-initiated ballot challenge mechanism, one of the big open questions is whether real voters, who just want to cast their votes and don’t care about the security mechanisms, will be tripped up by the extra question at the end that’s fundamental to the mechanism. We’re going to need to run human subject tests against these aspects of the machine design, and if they fail in practice, it’s going to be a trip back to the drawing board.

[Sidebar: I’m co-teaching a class on elections with Bob Stein (a political scientist) and Mike Byrne (a psychologist). The students are a mix of Rice undergrads, most of whom aren’t computer scientists. I experimentally built a lecture that began by teaching just enough number theory to explain how El Gamal cryptography works and how it allows for homomorphic vote tallying. Then I described how VoteBox uses this mechanism, and wrapped up with an explanation of how to do Benaloh-style challenges. I left out a lot of details, like how you generate large prime numbers, or how you construct NIZK proofs, but I seemed to have the class along with me for the lecture. If I can sell the idea of end-to-end cryptographic mechanisms to undergraduate non-science students, then there may yet be some hope.]

Filed Under: Uncategorized Tagged With: , , , , ,

Low Hit Rate Isn't the Problem with TSA Screening

November 20, 2008 by

The TSA, which oversees U.S. airport security, comes in for a lot of criticism — much of it deserved. But sometimes commentators let their dislike for the TSA get the better of them, and they offer critiques that don’t stand up logically.

A good example is yesterday’s USA Today article on TSA’s behavioral screening program, and the commentary that followed it. The TSA program trained screeners to look for nervous and suspicious behavior, and to subject travellers exhibiting such behavior to more stringent security measures such as pat-down searches or short interviews.

Commentators condemned the TSA program because fewer than 1% of the selected travellers were ultimately arrested. Is this a sensible objection? I think not, for reasons I’ll explain below.

Before I explain why, let’s take a minute to set aside our general opinions about the TSA. Forget the mandatory shoe removal and toiletry-container nitpicking. Forget that time the screener was rude to you. Forget the slippery answers to inconvenient Constitutional questions. Forget the hours you have spent waiting in line. Put on your blinders please, just for now. We’ll take them off later.

Now suppose that TSA head Kip Hawley came to you and asked you to submit voluntarily to a pat-down search the next time you travel. And suppose you knew, with complete certainty, that if you agreed to the search, this would magically give the TSA a 0.1% chance of stopping a deadly crime. You’d agree to the search, wouldn’t you? Any reasonable person would accept the search to save (by assumption) at least 0.001 lives. This hypothetical TSA program is reasonable, even though it only has a 0.1% arrest rate. (I’m assuming here that an attack would cost only one life. Attacks that killed more people would justify searches with an even smaller arrest rate.)

So the commentators’ critique is weak — but of course this doesn’t mean the TSA program should be seen as a success. The article says that the arrests the system generates are mostly for drug charges or carrying a false ID. Should a false-ID arrest be considered a success for the system? Certainly we don’t want to condone the use of false ID, but I’d bet most of these people are just trying to save money by flying on a ticket in another person’s name — which hardly makes them Public Enemy Number One. Is it really worth doing hundreds of searches to catch one such person? Are those searches really the best use of TSA screeners’ time? Probably not.

On the whole, I’m not sure I can say whether the behavioral screening program is a good idea. It apparently hasn’t caught any big fish yet, but it might have positive effects by deterring some serious crimes. We haven’t seen the data to support it, and we’ve learned to be skeptical of TSA claims that some security measure is necessary.

Now it’s time for the professor to call on one of the diehard civil libertarians in the class, who by this point are bouncing in their seats with both hands waving in the air. They’re dying to point out that our system, for good reason, doesn’t automatically accept claims by the authorities that searches or seizures are justified, and that our institutions are properly skeptical about expanding the scope of searches. They’re unhappy that the debate about this TSA program is happening after it was in place, rather than before it started. These are all good points.

The TSA’s behavioral screening is a rich topic for debate — but not because of its arrest rate.

Filed Under: National Security & Surveillance, Privacy & Security Tagged With: ,

Can Google Flu Trends Be Manipulated?

November 19, 2008 by

Last week researchers from Google and the Centers for Disease Control unveiled a cool new research result, showing that they could gauge the level of influenza infections in a region of the U.S. by seeing how often people in those regions did Google searches for certain terms related to the flu and flu symptoms. The search-based predictions correlate remarkably well with the medical data on flu rates — not everyone who searches for “cough medicine” has the flu, but enough do that an increase in flu cases correlates with an increase in searches for “cough medicine” and similar terms. The system is called Google Flu Trends.

Privacy groups have complained, but this use of search data seems benign — indeed, this level of flu detection requires only that search data be recorded per region, not per individual user. The legitimate privacy worry here is not about the flu project as it stands today but about other uses that Google or the government might find for search data later.

My concern today is whether Flu Trends can be manipulated. The system makes inferences from how people search, but people can change their search behavior. What if a person or a small group set out to convince Flu Trends that there was a flu outbreak this week?

An obvious approach would be for the conspirators to do lots of searches for likely flu-related terms, to inflate the count of flu-related searches. If all the searches came from a few computers, Flu Trends could presumably detect the anomalous pattern and the algorithm could reduce the influence of these few computers. Perhaps this is already being done; but I don’t think the research paper mentions it.

A more effective approach to spoofing Flu Trends would be to use a botnet — a large collection of hijacked computers — to send flu-related searches to Google from a larger number of computers. If the added searches were diffuse and well-randomized, they would be very hard to distinguish from legitimate searches, and the Flu Trends would probably be fooled.

This possibility is not discussed in the Flu Trends research paper. The paper conspicuously fails to identify any of the search terms that the system is looking for. Normally a paper would list the terms, or at least give examples, but none of the terms appear in the paper, and the Flu Trends web site gives only “flu” as an example search term. They might be withholding the search terms to make manipulation harder, but more likely they’re withholding the search terms for business reasons, perhaps because the terms have value in placing or selling ads.

Why would anyone want to manipulate Flu Trends? If flu rates affect the financial markets by moving the stock prices of certain drug or healthcare companies, then a manipulator can profit by sending false signals about flu rates.

The most interesting question about Flu Trends, though, is what other trends might be identifiable via search terms. Government might use similar methods to look for outbreaks of more virulent diseases, and businesses might look for cultural trends. In all of these cases, manipulation will be a risk.

There’s an interesting analogy to web linking behavior. When the web was young, people put links in their sites to point readers to other interesting sites. But when Google started inferring sites’ importance from their incoming links, manipulators started creating links for their Google-effect. The result was an ongoing cat-and-mouse game between search engines and manipulators. The more search behavior takes on commercial value, the more manipulators will want to change search behavior for commercial or cultural advantage.

Anything that is valuable to measure is probably, to someone, valuable to manipulate.

Filed Under: Privacy & Security Tagged With: , ,