Over the last few years, I have been involved in issues related to the use of computerization in voting. This has come about because of my concerns about computer security, privacy and reliability, and from my role as chair of the ACM U.S. Public Policy Committee (USACM). USACM has taken a strong position as regards use of computers as voting stations and voting over the internet.

Two recent items address the issue of voting over the Internet.

The first is a study released by NIST about the threats posed by internet voting. This is a well-written document describing problems that would be encountered with any online voting system. Their conclusion is that, for public elections, distribution of blank ballots (on paper) is the only reasonable improvement that we can make with current technology.

The second is a note from my colleague, Yvo Desmedt, one of the senior leaders in information security He has asked that I circulate this to a wider audience:

  IACR (the International Association for Cryptologic Research) has changed its bylaws to allow e-voting over the internet to elect its board members and other purposes. IACR will likely move towards internet e-voting. The IACR Board of Directors subcommittee on internet e-voting has published a list of requirements for such a system at: http://www.iacr.org/elections/eVoting/requirements.html This is evidently a first step and the question remains whether the system the International Association for Cryptologic Research will choose will be easy to hack or not. So, security experts should follow this development.

The problems that need to be addressed by any voting technology are mostly obvious: impersonation of the voter, impersonation of the voting system, disclosure of the ballot, multiple voting, loss of votes, denial of access, and a number of other issues. The problems are complicated by the requirements of a fair voting system, one of which is that of vote deniability—that the voter is able to deny (or claim) that her/his vote was cast a particular way. This is important to prevent vote buying, or more importantly, retribution against voters who do not cast ballots in a particular way. It isn’t difficult to find stories where voters have been beaten or killed because of how they voted (or were presumed to have intended to vote). Thus, the tried-and-true concept of providing a receipt (ala ATM machines) is not a workable solution.

My intent in making this post isn’t to discuss all the issues behind e-voting—that is well beyond the scope of a single posting, and is covered well many other places. My main goal is to give some wider circulation to Yvo’s statement. However, in light of the recent problem with certificate issuance, it is also worth noting that schemes requiring encryption to secure voting may have hidden vulnerabilities that could lead to compromise and/or failures in the future.   

In the end, it comes down to a tradeoff of risk/reward (as do all security choices): can we accurately quantify the risks with a particular approach, and are we willing to assume them? Do we have appropriate mechanisms to eliminate, mitigate or shift the risks? Are we willing to accept the risks associated with adopting a particular form of e-voting in return for the potential benefit of better access for remote voters? Or are accurate (fair) results all the time more important than complete results?

Note that one objection often raised to USACM as we argue these points is “There is no evidence there has ever been a failure or tampering with a vote.” In addition to being incorrect (there are numerous cases of computer-based voting failures), this misses two key issues:

 
• How do you tell if there is tampering if there are no safeguards that definitively disclose such tampering? That you have not detected something does not mean it has not occurred.
 
• The past does not predict the future in such a case. That no failure (accidental or otherwise) has occurred does not mean it will not occur in the future. Worse, a string of occurrences without a failure may help cloud a future discovered discrepancy!

In the case of IACR, it is obvious why this group of cryptography professionals would wish to adopt techniques that show confidence in cryptography. However, the example they set could be very damaging for other groups—and populations—if their confidence is misplaced. Given the long history of spectacular failures in cryptography—often going unannounced while being exploited—it is somewhat surprising that the IACR is not more explicit in their statement about the risks of technological failures.

There are several news stories now appearing (e.g., Security News) about a serious flaw in how certificates used in online authentication are validated. Ed Felten gives a nice summary of how this affects online WWW site authentication in his Freedom to Tinker blog posting. Brian Krebs also has his usual readable coverage of the problem in his Washington Post article. Steve Bellovin has some interesting commentary, too, about the legal climate.

Is there cause to be concerned? Yes, but not necessarily about what is being covered in the media. There are other lessons to be learned from this.

Short tutorial

First, for the non-geek reader, I’ll briefly explain certificates.

Think about how, online, I can assure myself that the party at the other end of a link is really who they claim to be. What proof can they offer, considering that I don’t have a direct link? Remember that an attacker can send any bits down the wire to me and may access to faster computers than I do.

I can’t base my decision on how the WWW pages appear, or embedded images. Phishing, for instance, succeeds because the phishers set up sites with names and graphics that look like the real banks and merchants, and users trust the visual appearance. This is a standard difficulty for people—understanding the difference between identity (claiming who I am) and authentication (proving who I am).

In the physical world, we do this by using identity tokens that are issued by trusted third parties. Drivers licenses and passports are two of the most common examples. To get one, we need to produce sufficient proof of identity to a third party to meet its standards of proof. Then, the third party issues a document that is very difficult to forge (almost nothing constructed is impossible to forge or duplicate—but some things require so much time and expenditure it isn’t worthwhile). Because the criteria for proof of identity and strength of construction of the document are known, various other parties will accept the document as “proof” of identity. Of course, other problems occur that I’m not going to address—this USACM whitepaper (of which I was principal author) touches on many of them.

Now, in the online world we cannot issue or see physical documents. Instead, we use certificates. We do this by putting together an electronic document that gives the information we want some entity to certify as true about us. The format of this certificate is generally fixed by standards, the most common one being the X.509 suite. This document is sent to an organization known as a Certificate Authority (CA), usually along with a fee. The certificate authority is presumably well-known, and performs a check (to their own standards) that the information in the document is correct, and it has the right form. The CA then calculate a digital hash value of the data, and creates a digital signature of that hash value. This is then added to the certificate and sent back to the user. This is the equivalent of putting a signature on a license and then sealing it in plastic. Any alteration of the data will change the digital hash, and a third party will find that the new hash and the hash value signed with the key of the CA don’t match. The reason this works is that the hash function and encryption algorithm used are presumed to be so computationally difficult to forge that it is basically not possible.

As an example of a certificate , if you visit “https://www.cerias.purdue.edu” you can click on the little padlock icon that appears somewhere in the browser window frame (this is browser dependent) to view details of the CERIAS SSL certificate.

You can get more details on all this by reading the referenced Wikipedia pages, and by reading chapters 5 & 7 in Web Security, Privacy and Commerce.

Back to the hack

In summary, some CAs have been negligent about updating their certificate signing mechanisms in the wake of news that MD5 is weak, published back in 2004. The result is that malicious parties can generate and obtain a certificate “authenticating” them as someone else. What makes it worse is that the root certificate of most of these CAs are “built in” to browser and application trust lists to simplify look-up of new certificates. Thus, most people using standard WWW browsers can be fooled into thinking they have connected to real, valid sites—even through they are connecting to rogue sites.

The approach is simple enough: a party constructs two certificates. One is for the false identity she wishes to claim, and the other is real. She crafts the contents of the certificate so that the MD5 hash of the two, in canonical format, is the same. She submits the real identity certificate to the authority, which verifies her bona fides, and returns the certificate with the MD5 hash signed with the CA private key. Our protagonist then copies that signature to the false certificate, which has the same MD5 hash value and thus the same digital signature, and proceeds with her impersonation!

What makes this worse is that the false key she crafts is for a secondary certificate authority. She can publish this in appropriate places, and is now able to mint as many false keys as she wishes—and they will all have signatures that verify in the chain of trust back to the issuer! She can even issue these new certificates using a stronger hash algorithm than MD5!

What makes this even worse is that it has been known for years that MD5 is weak, yet some CAs have continued to use it! Particularly unfortunate is the realization that Lenstra, Wang and de Weger described how this could be done back in 2005. Methinks that may be grounds for some negligence lawsuits if anyone gets really burned by this….

And adding to the complexity of all this is the issue of certificates in use for other purposes. For example, certificates are used with encrypted S/MIME email to digitally sign messages. Certificates are used to sign ActiveX controls for Microsoft software. Certificates are used to verify the information on many identity cards, including (I believe) government-issued Common Access Cards (CAC). Certificates also provide identification for secured instant messaging sessions (e.g., iChat). There may be many other sensitive uses because certificates are a “known” mechanism. Cloud computing services , software updates, and more may be based on these same assumptions. Some of these services may accept and/or use certificates issued by these deficient CAs.

Fixes

Fixing this is not trivial. Certainly, all CAs need to start issuing certificates based on other message digests, such as SHA-1. However, this will take time and effort, and may not take effect before this problem can be exploited by attackers. Responsible vendors will cease to issue certificates until they get this fixed, but that has an economic impact some many not wish to incur.

We can try to educate end-users about this, but the problem is so complicated with technical details, the average person won’t know how to actually make a determination about valid certificates. It might even cause more harm by leading people to distrust valid certificates by mistake!

It is not possible to simply say that all existing applications will no longer accept certificates rooted at those CAs, or will not accept certificates based on MD5: there are too many extant, valid certificates in place to do that. Eventually, those certificates will expire, and be replaced. That will eventually take care of the problem—perhaps within the space of the next 18 months or so (most certificates are issued for only a year at a time, in part for reasons such as this).

Vendors of applications, and especially WWW browsers, need to give careful thought about updates to their software to flag MD5-based certificates as deserving of special attention. This may or may not be a worthwhile approach, for the reason given above: even with a warning, too few people will be able to know what to do.

Bigger issue

We base a huge amount of trust on certificates and encryption. History has shown how easy it is to get implementations and details wrong. History has also shown how quickly things can be destabilized with advances in technology.

In particular, too many people and organizations take for granted the assumptions on which this vast certificate system is based. For instance, we assume that the hash/digest functions in use are computationally difficult to reverse or cause collisions. We also assume that certain mathematical functions underlying public/private key encryption are too difficult to reverse or “brute force.” However, all it takes is some new insight or analysis, or maybe new, affordable technology (e.g., practical quantum computing, or massively parallel computing) to violate those assumptions.

If you look at the way our systems are constructed, too little thought is given to what happens to existing infrastructure when something breaks. Designs can include compensating and recovery code, but doing so requires some cost in space or time. However, all too often people are willing to avoid the investment by putting off the danger to “if and when that happens.” Thus, we instance such as the Y2K problems and the issues here with potentially rogue CAs.

(I’ll note as an aside, that when I designed the original version of Tripwire and what became the Signacert product, I specifically included simultaneous use of several different message digest functions in different families for this very reason. I knew it was a matter of time before one or two were broken. I still believe that it is beyond reason to find files that will match multiple, different algorithms simultaneously.)

Another issue is the whole question of who we trust, and for what. As noted in the USACM whitepaper, authentication is always relative to a third party. How much do we trust those third parties? How much trust have we invested in the companies and agencies issuing certificates? Are they properly verifying identities? How good is there internal security? How do we know, and how much is at risk from our trust in those entities?

Let me leave you with a final thought. How do we know that this problem has not already been quietly exploited? The basic concept has been in the open literature for years. The general nature of this attack on certificates has been known for well over a decade, if not two. Given the technical and infrastructure resources available to national agencies and organized criminals, and given the motivation to use this hack selectively and quietly, how can we know that it is not already being used?

[Added 12/31/2008]: A follow-up post to this one is available in the blog.