A case of the wrong technology applied incorrectly

In this week's Economist magazine, an article describes how the Swiss general election that was held on October 21 was to use quantum cryptography to protect the transmission of votes from the polling stations to the central tabulation centers. Quoting from the article:

The authorities will use quantum cryptography—a way to transmit information that detects eavesdroppers and errors almost immediately—to ensure not only that votes are kept secret but also that they are all counted.

I first became aware of this project when a New Scientist reporter sent me a note about it and asked for my opinion. I assumed that it was a joke or that the reporter had heard wrong. After all, protecting electronic transmissions is the one problem I can think of in all of this that is not really hard. Here are some of the problems in electronic voting that are hard:

• Ensuring that the software on the voting machines is the correct software. The proposed solution of having a library of hash values of the correct binaries of voting machine software and checking the voting machines does not work. There is no way to perform the check of the hash of the code that is running in the machines. In fact, any attempt to check that hash value would provide an opportunity for an attacker to change the code then and there.
  
  
• Ensuring that the software on the voting machines is not malicious.Even if the "correct" code is running on the voting machine, there is no deterministic way to determine that the code was not designed with a back door in it that could affect the outcome of the election.
  
  
• Ensuring that no unknown bugs in the voting machines can affect the outcome.Even if the "correct" code is running on the voting machine and even if there is no intentional malicious code in the machine, there is no way to ensure that the code does not contain inadvertent bugs or unexpected failure modes that could disrupt an election or cause the wrong result to be computed.
  

Quantum cryptography is a novel and very interesting topic. There are potentially many applications that could benefit from this technology, and I have always been a big fan. But, quantum cryptography does not address the problems in electronic voting that are actually difficult to solve. Transmitting the votes from the polls to the central tabulation center can be done with traditional cryptography. Authentication functions can provide tamper resistance and encryption can provide secrecy, assuming that secrecy is actually desirable here. I believe it is not, as every aspect of the process should be transparent, and I see no reason to keep the precinct results secret. Just the opposite is true - it is important for observers to see princinct level results.

I applaud the Swiss for pursuing innovation, but in this case, they are using the wrong tool to solve the wrong problem in an inappropriate way.

Holt's H.R. 811 is finally coming up for a vote

Congressman Rush Holt's bill requiring a voter verified paper trail is scheduled to come up for a vote tomorrow. I've been traveling out of town, and I just returned home this evening (to an overflowing inbox about this issue). I was planning on writing up my thoughts about H.R. 811, but I just noticed that Ed Felten did a great job of writing his up on his blog. I pretty much agree with everything he said, so no need to repeat it here.

I support Holt's bill. I know that many activists, including several who have contacted me today, are opposed to this bill because it does not entirely ban DREs. However, at the moment, I believe that we need this bill to pass. It would outlaw the voting systems used in places like Maryland and Georgia and, I believe, 13 other states that have entirely paperless voting.

What's sorely lacking right now are paper trails and mandatory audits. Holt provides these. I do hold out hope that some day we will be able to utilize the added benefits of end to end cryptographic systems. But right now, the Holt bill is the best measure I can foresee to have a realistic chance of eliminating the paperless DREs that I may have to vote on next November 4th.

Avi

The Virus Did It

I attended Crypto in Santa Barbara this past week, and I was talking to a colleague of mine from another university. He had served as an expert witness in an interesting case involving a man who had been accused of having illegal pornographic images on his computer. His defense was that his computer had been infected with a malware virus and that "the virus did it." This may seem a little far fetched. However, my friend is a top security expert, and he had disassembled and reverse engineered the virus code, and he showed that indeed the virus was designed to download pornographic images from the Web.

The "virus did it" defense is likely to become more popular as increasingly nefarious online activity is uncovered. In a society where you are innocent until proven guilty, the possibility that a virus performed a malicious action from someone's computer, and that the person was not aware of this, may be enough to provide plausible deniability of almost anything.

Consider the implications of this for electronic voting machines. While the Princeton team showed how a malicious virus could copy itself to infect a precinct full of voting machines, and whereas the California top to bottom review team showed how even a single infected voting machine or memory card can compromise a back end tabulating system, in light of "the virus did it" phenomenon, the attacker's job in disrupting an election is even simpler. All an attacker has to do is leave evidence that casts suspicion that there may have been a virus. If an election audit reveals signs of a possible virus, the results are thrown into doubt, and a losing candidate has a legitimate claim that a virus may have tampered with the results.

The evidence of a possible virus can be created anytime prior to the audit, even after the election is complete. In a computerized system such as a paperless DRE, it is much easier to concoct false evidence that raises suspicion than it is in a paper ballot or end to end cryptographic system.

To visualize how scary this could be, let's take the example of Sarasota County, Florida in the 2006 election. Congressional District 13 was an extremely close race with the strange anomaly that an abnormally high number of undervotes were found in an important race. Several studies and audits were conducted, but the reason for the problem has never been conclusively determined. Now, imagine if an audit had turned up virus code on some of the voting machines. Even if no virus had ever executed or propagated, the mere existence of such code would have created chaos. Taking this idea a step further, imagine if such evidence were found in the Virginia Senate race in 2006. This extremely close race singlehandedly determined the party majority in the Senate.

When defending the use of DREs, vendors and some election officials argue that it would be very difficult to tamper with a voting machine in an undetectable way to change the outcome of the election. While I disagree with this statement, the truth is that it grossly overestimates the job of the attacker. All an attacker has to do is to create the impression that something went very wrong. The losing candidate will do the rest.

If in a future election we begin to suspect that "the virus did it," things are going to get very ugly.

Why nobody wants to buy Diebold Election Systems

In an Associated Press story today, Diebold confirms that they tried and failed to sell their voting technologies business. Given the recent reports in California and Florida, I imagine it will be even harder for them now. I think people, even within Diebold, are coming to the realization that DREs are the wrong model for voting systems. There are several reasons for this.

1. DREs are too complex. There are typically 50,000+ lines of code in a DRE, much of that involves user interface and audio capability, and providing the DRE interface and user experience is not worth the hit in complexity.
   
   
2. DREs serve as a bottleneck on election day. DREs are expensive, and so it is unlikely that precincts will have more than they need. Since voters typically spend several minutes voting, and I've observed as a poll worker that quite a few voters take more than 10 minutes, the potential for long lines is tremendous. Once a backlog of voters is created, it only gets worse, as the effect propagates much like the airline systems gets backed up in a positive feedback loop of delays once some flights are late.
   
   
3. DREs are non-transparent. The public justifiably does not trust them. They cannot be independently audited, despite the vendor's insincere claims to the contrary. Even DREs with a VVPAT cannot be properly audited because they just don't work as we would hope. Voters often do not check the paper. The paper rolls used by most vendors do not lend themselves to easy recounts, and the retrofitting of DREs with VVPAT has led to awkward and sometimes ill defined procedures, especially when a voter disputes the printout.
   
   
4. Finally, a much better model for voting systems exists, namely, paper ballots with optical scan precinct counting and ballot marking machines for disability access.
   

So, it is no surprise that Diebold can't sell their voting business. They'd be as likely to sell 8 track players instead of ipods.

Secretary Bowen's clever insight

On Monday, our NSF ACCURATE center held its second annual EVT conference. It was a smashing success with packed attendance and great papers. Today, we held our Principal Investigator (PI) meeting consisting of the PIs, graduate students and some of our advisors. To all of our amazement, Debra Bowen, the Secretary of State of California, who is on our advisory board, showed up for both days. This is particularly incredible given that last Friday she created a firestorm by decertifying most of the electronic voting machines in her state after the top to bottom review that she ordered showed tremendous flaws in the machines.

Secretary Bowen was an active participant in both our workshop and our PI meeting. Today on a panel of our advisors, she said something that really struck a chord with me. It was a simple comment, but it showed great insight into the computer software process as well as the election system certification process. Bowen's observation was that the certification process is not well suited to software. Most election officials defer to staffers or to academics such as us about technical issues, but Secretary Bowen sounded as much like a computer scientists as a state official this afternoon. She rattled off technical terms that she was completely comfortable with and made arguments based on a level of understanding of technology that I have never seen from a non-computer scientist. It is no wonder that she was able to put together the team led by David Wagner and Matt Bishop to study the machines and to appreciate their findings.

Back to Bowen's comment about software not being suitable for the way election equipment is certified. It is right on the mark. The current certification process may have been appropriate when a 900 lb lever voting machine was deployed. The machine could be tested every which way, and if it met the criteria, it could be certified because it was not likely to change. But software is different. The software lifecycle is dynamic. As an example, look at the way Apple distributes releases of the iPhone software. The first release was 1.0.0. Two minor version numbers. When the first serious flaw was discovered, they issued a patch and called it version 1.0.1. Apple knew that there would be many minor and some major releases because that is the nature of software. It's how the entire software industry operates.

So, you cannot certify an electronic voting machine the way you certify a lever machine. Once the voting machine goes through a lengthy and expensive certification process, any change to the software requires that it be certified all over again. What if a vulnerability is discovered a week before an election? What about a month before the election, or a week after it passes certification? Now the point is that we absolutely expect that vulnerabilities will be discovered all the time. That would be the case even if the vendors had a clue about security. Microsoft, which arguably has some of the best security specialists, processes and development techniques issues security patches all the time.

Software is designed to be upgraded, and patch management systems are the norm. A certification system that requires freezing a version in stone is doomed to failure because of the inherent nature of software. Since we cannot change the nature of software, the certification process for voting machines needs to be radically revamped. The dependence on software needs to be eliminated.

California source code study results

The source code team reports for the California Top to Bottom review of Diebold, Hart and Sequoia's voting systems are now online. These reports are comprehensive and detailed and should mark the end of the use of these voting machines in public elections. From the executive summaries:

Diebold
Our analysis shows that the technological controls in the Diebold software do not provide sufficient security to guarantee a trustworthy election. The software contains serious design flaws that have led directly to specific vulnerabilities that attackers could exploit to affect election outcomes.

Hart
Many of these attacks can be mounted in a manner that makes them extremely hard to detect and correct. We expect that many of them could be carried out in the field by a single individual, without extensive effort, and without long-term access to the equipment.

Sequoia
We found significant security weaknesses throughout the Sequoia system. The nature of these weaknesses raises serious questions as to whether the Sequoia software can be relied upon to protect the integrity of elections. Every software mechanism for transmitting election results and every software mechanism for updating software lacks reliable measures to detect or prevent tampering.

I am most familiar with the Diebold system, and one thing that stands out is how every time there is another study of the Diebold code, more security problems come to light. Here are a few issues that this report identified:

The audit log does not adequately detect malicious tampering.

Buffer overflows in unchecked string operations allow arbitrary code execution.

Integer overflows in the vote counters are unchecked.

Multiple buffer overflows in .ins file handling allow arbitrary code execution on startup.

Setting a jumper on the motherboard enables a bootloader menu that allows the user to extract
or tamper with the contents of the internal flash memory.

Keys used to secure smart cards and election data are not adequately protected.

The machine does not adequately protect the supervisor PIN. (This same problem was identified in this week's Florida report)

Votes can be swapped or neutralized by modifying the defined candidate voting coordinates
stored on the memory card.

OpenSSL is not initialized with adequate entropy

...

And the list goes on. Dozens of such vulnerabilities are identified; I just picked a few at random from the list. This is the code that Diebold produced after they claimed to have fixed the vulnerabilities we found in 2003 and that Ed Felten's group identified last year. The backend GEMS system has its own serious problems as well. It is clear that they are simply not qualified to build these kinds of machines.

As I read the three new reports, I could not help but marvel at the fact that so many places in the US are using these machines. When it comes to perscription medications, we perform extensive tests before drugs hit the market. When it comes to aviation, planes are held to standards and tested before people fly on them. But, it seems that the voting machines we are using are even more poorly designed and poorly implemented than I had realized.

The more these machines are studied, the worse they look.

Florida SAIT report highlights more Diebold problems

The Florida Secretary of State has just released a report from the Security and Assurance in Information Technology Laboratory (SAIT) at Florida State University titled "Software Review and Security Analysis of the Diebold Voting Machine Software". This report is the output of a study that Florida commissioned to determine whether flaws reported in previous studies of voting systems, including my group's study, had been fixed yet. I was a reviewer of this report, and my graduate student, Ryan Gardner, played a key role in the study. The group was led by Alec Yasinsac who led the previous FSU study on voting machine security for Florida.

I am pleased to see that there are so many studies of voting systems being performed. In this past year, Connecticut, California, and now Florida have conducted thorough reviews, and all of them have highlighted serious problems with the voting systems. All this is happening as the House is considering federal legislation to improve the auditability of voting equipment.

Once again this new report shows serious, serious problems with Diebold, and that they clearly have not fixed some of the most egregious problems. One of the weaknesses that our report in 2003 pointed out was that Diebold used a single, fixed encryption key for all encryption in the system. Diebold has moved from using DES to AES. However, the key management is just as bad as before, and possibly worse. Here is an excerpt from the new report released today.

The system key is generated by computing an MD5 hash of the machine serial number. Its value is never changed after generation. Since the machine serial number is public, the system key is also essentially public. Anyone who knows this procedure can generate the system key and can access anything it protects, including the data encryption key and anything that it is used to encrypt.

This is arguably worse than having a fixed static key in all of the machines. Because with knowledge of the machine's serial number, anyone can calculate all of the secret keys. Whereas before, someone would have needed access to the source code or the binary in the machine.

Other attacks mentioned in the report include swapping two candidate vote counters and many other vote switching attacks. The supervisor PIN is protected with weak cryptography, and once again Diebold has shown that they do not have even a basic understanding of how to apply cryptographic mechanisms. Quoting once again:

The supervisor PIN is now stored on supervisor smart cards as a keyed hash of the actual PIN. Specifically, the PIN is concatenated with part of the data encryption key (the first 64 bits), and an MD5 sum is computed over the resulting string. The first 4 bytes of the MD5 are stored on the smart card. The most significant weakness of this approach again concerns the key management of the data encryption key as described in Section 3.7.1.1. The key can be compromised by an adversary with sufficient access to a voting terminal, and an adversary with it can find the PIN using a simple brute force computation. Again, the act of using the same key for more than one purpose is generally considered poor practice within the cryptographic community. Moreover, the input to the hash function is 64 bits of the 128-bit data encryption key. Using only 64 bits of the 128-bit AES key in this manner may allow an adversary to recover the data encryption key significantly faster than exhaustive search.

So, Diebold is doing some things better than they did before when they had absolutely no security, but they have yet to do them right. Anyone taking any of our cryptography classes at Johns Hopkins, for example, would do a better job applying cryptography. If you read the SAIT report, this theme repeats throughout.

In my opinion, in his letter to Diebold the Secretary of State of Florida, Kurt Browning downplays the severity of this report.

A toast to Peter Honeyman

My former Ph.D. advisor, Peter Honeyman won the prestigious Lifetime Achievement Award from the USENIX Association. I first heard about this from Matt Blaze of the USENIX board and a former colleague of mine at AT&T, and I was absolutely thrilled. I can think of nobody more deserving. As the recipient of his mentorship, I am delighted that he was called out for his role mentoring students for this honor. From the USENIX web site:

Dr. Peter Honeyman has had a profound and lasting impact on the field of computer science. While many know Peter for his seminal contributions to computing systems, such as Honey DanBer UUCP and Disconnected AFS, it is his efforts as a mentor that we wish to honor with the USENIX Lifetime Achievement Award. Peter's often highly unconventional stewardship of the countless students, researchers, and advisees he has touched is the stuff of graduate student legend. His penetratingly insightful (and potentially hazardous) questions and comments, combined with a paradoxically unflinching loyalty, consistently have led those under his tutelage to the pinnacle of achievement in security, systems, and networking. Peter's questioning during conferences and doctoral defenses, although sometimes frightening, always demanded better from those of us who attempt to advance science.

Peter has a page with some pictures of the event. I was unable to attend the ceremony when he received his award because I was on vacation with my family in Israel, but I made a video tribute for him that was shown at the conference.

Debunking the "laboratory" defense

Yesterday, there was a hearing in California about the e-voting machines that were studied in the top to bottom review. I watched some of the proceedings that were broadcast on the web, and I read some of the press coverage, such as this article in the San Jose Mercury News. I'm struck (although not surprised) by the way the vendors attack the study results. As the top to bottom review concluded that the systems were highly vulnerable to all kinds of attacks, the vendors stand to lose business and revenue if the machines are decertified, so you would expect them to attack the study with everything they have.

Reading the news coverage of the hearing, it is clear that there is a common theme in the attacks on the study. Quoting the article:

Sequoia Voting Systems, which is used in Alameda, Santa Clara and Santa Cruz counties, called the review an "unrealistic, worst-case scenario" performed in a laboratory environment by computer security experts with unfettered access to the machines.

Several other people use the term "laboratory environment" in criticizing the study. I think these criticisms miss the point. Most, if not all of the vulnerabilities identified in the studies are weaknesses that are well known in the security literature and which can be avoided with proper design and implementation. The source code reviews have not been published yet, so I cannot comment on what was found there, but looking at the red team reviews, I can say that we know how to design systems that avoid the problems that were found there. So, regardless of whether these were broken in a laboratory or in a polling station, the fact is that vendors are not utilizing well-known security technology in designing their systems.

Rather than using technology provided by incompetent vendors who don't bother to hire real security experts to build voting systems, we should insist that these machines be scrapped. The debate should focus on whether or not the machines utilize the best available security, rather than on whether the proof that they are insecure was identified in a lab or somewhere else. If the vendors focused as many resources on improving the security of their systems as they do in criticizing the studies, then they wouldn't have to point out that the studies were done in a laboratory because studies that embarrass them would be less likely to exist.

More on California Top to Bottom

I should point out that only the red team reports have been released so far. (As the SoS web site states, "The document review teams and source code review teams submitted their reports on schedule. Their reports will be posted as soon as the Secretary of State ensures the reports do not inadvertently disclose security-sensitive information.") The red teams are groups of talented white hat hackers who approach the system as though they were mailicious parties looking to disrupt the election. These reports do not take into account flaws in the source code. The source code analysis reports, which are akin to the study that my research team performed in 2003 about Diebold, will be very revealing because they will shed light on how Diebold responded to the flaws that we found four years ago. Considering that I had two (very talented) graduated students looking at the code for about a week, I fully expect that this team of professionals who spent a month will uncover much more serious problems.

It's important to keep in mind, as the California report states, that any security problems reported by them constitute a lower bound on the problems that exist. The reason is that they were limited in both time and in the information available to them. Some of the material they needed was given to them only a couple of weeks before their final deadline. Furthermore, in a real world scenario, hackers would not have a month to do the analysis and produce a report. They would probably skip the report and could spend many months developing their attacks.