Matt Blaze's
EXHAUSTIVE SEARCH
Science, Security, Curiosity
California voting systems code review now released
Almost as eagerly anticipated as the new Harry Potter book.

Readers of this blog may recall that for the last two months I've been part of a security review of the electronic voting systems used in California. Researchers from around the country (42 of us in all) worked in teams that examined source code and documents and performed "red team" penetration tests of election systems made by Diebold Election Systems, Hart InterCivic and Sequoia Voting Systems.

The red team reports were released by the California Secretary of State last week, and have been the subject of much attention in the nationwide press (and much criticism from the voting machine vendors in whose systems vulnerabilities were found). But there was more to the study than the red team exercises.

Today the three reports from the source code analysis teams were released. Because I was participating in that part of the study, I'd been unable to comment on the review before today. (Actually, there's still more to come. The documentation reviews haven't been released yet, for some reason.) Our reports can now be downloaded from http://www.sos.ca.gov/elections/elections_vsr.htm .

I led the group that reviewed the Sequoia system's code (that report is here [pdf link]).

The California study was, as far as I know, the most comprehensive independent security evaluation of electronic voting technologies ever conducted, covering products from three major vendors and investigating not only the voting machines themselves, but also the back-end systems that create ballots and tally votes. I believe our reports now constitute the most detailed published information available about how these systems work and the specific risks entailed by their use in elections.

My hats off to principal investigators Matt Bishop (of UC Davis) and David Wagner (of UC Berkeley) for their tireless skill in putting together and managing this complex, difficult -- and I think terribly important -- project.

By law, California Secretary of State Debra Bowen must decide by tomorrow (August 3rd, 2007) whether the reviewed systems will continue to be certified for use throughout the state in next year's elections, and, if so, whether to require special security procedures where they are deployed.

We found significant, deeply-rooted security weaknesses in all three vendors' software. Our newly-released source code analyses address many of the supposed shortcomings of the red team studies, which have been (quite unfairly, I think) criticized as being "unrealistic". It should now be clear that the red teams were successful not because they somehow "cheated," but rather because the built-in security mechanisms they were up against simply don't work properly. Reliably protecting these systems under operational conditions will likely be very hard.

The problems we found in the code were far more pervasive, and much more easily exploitable, than I had ever imagined they would be.

 


Our reports speak for themselves (and they do a lot of speaking, I'm afraid, with over 300 pages released so far), so I won't try to repeat what's in them here. What follows are strictly my own thoughts about what we learned and how we did what we did.

My group, which was based in Berkeley, looked at the source code of the Sequoia system. That system includes touch-screen and optical scan voting machines used at polling places and a back-end ballot preparation and vote tallying database at the elections headquarters. At over 800K lines of code, Sequoia's was the largest of the three codebases reviewed, and ours was the largest team in the project (Arel Cordero, Sophie Engle, Chris Karlof, Naveen Sastry, Micah Sherr, Till Stegers and Ka-Ping Yee -- a group of extraordinary talent and energy if ever there was one).

Reviewing that much code in less than two months was, to say the least, a huge undertaking. We spent our first week (while we were waiting for the code to arrive) setting up infrastructure, including a Trac Wiki on the internal network that proved invaluable for keeping everyone up to speed as we dug deeper and deeper into the system. By the end of the project, we were literally working around the clock. To protect the vendor's proprietary software, our lab was in a small room on the UC Berkeley campus equipped with a lock not on the building master key, a monitored alarm, a safe in which we stored our disk drives when no one was there and an air-gapped isolated network of dedicated workstations. The ventilation in our small windowless room never quite worked, and whenever anyone had a cold we'd all eventually catch it. (Not that I'm complaining; the minor physical discomforts and long hours were tiny prices to pay for the opportunity to study the inner workings of something rarely exposed to outside scrutiny, and yet so central to our democracy.)

Because of the way the project was organized we didn't have any actual voting machines at Berkeley, only source code. All the vendor hardware was in another secure room at the Secretary of State's office in Sacramento and was intended primarily for use by the penetration test red teams. We ended up collaborating closely with the red team (based at UC Santa Barbara) that was working on our system (and who issued their own report).

So what can we learn from all this?

In spite of the short time and other sub-optimal conditions, the project found deeply-rooted security weaknesses in the software of all three voting systems reviewed.

I was especially struck by the utter banality of most of the flaws we discovered. Exploitable vulnerabilities arose not so much from esoteric weaknesses that taxed our ingenuity, but rather from the garden-variety design and implementation blunders that plague any system not built with security as a central requirement. There was a pervasive lack of good security engineering across all three systems, and I'm at a loss to explain how any of them survived whatever process certified them as secure in the first place. Our hard work notwithstanding, unearthing exploitable deficiencies was surprisingly -- and disturbingly -- easy.

Much of the controversy around electronic voting concerns the possibility of hidden "backdoors" incorporated by a nefarious vendor. Properly obfuscated, such mischief would be almost impossible to detect. Yet our reports chronicle software weakened not by apparent malice but by a litany of elementary mistakes: static cryptographic keys, unsecured interfaces, poorly validated inputs, buffer overflows, and basic programming errors in security-critical modules. Deliberate backdoors in these systems, if any existed, would be largely superfluous.

Unfortunately, while finding many of the vulnerabilities may have been straightforward enough, fixing them won't be.

The root problems are architectural. All three reviewed products are, in effect, large-scale distributed systems that have many of their security-critical functions performed by equipment sent out into the field. In particular, the integrity of the vote tallies depends not only on the central computers at the county elections offices, but also on the voting machines (and software) at the polling places, removable media that pass through multiple hands, and complex human processes whose security implications may not be clear to the people who perform them. In other words, the designs of these systems expose generously wide "attack surfaces" to anyone who seeks to compromise them. And the defenses are dangerously fragile -- almost any bug, anywhere, has potential security implications.

This means that strengthening these systems will involve more than repairing a few programming errors. They need to be re-engineered from the ground up. No code review can ever hope to identify every bug, and so we can never be sure that the last one has been fixed. A high assurance of security requires robust designs where we don't need to find every bug, where the security doesn't depend on the quixotic goal of creating perfect software everywhere.

In the short term, election administrators will likely be looking for ways to salvage their equipment with beefed up physical security and procedural controls. That's a natural response, but I wish I could be more optimistic about their chances for success. Without radical changes to the software and architecture, it's not clear that a practical strategy that provides acceptable security even exists. There's just not a lot to work with.

I don't envy the officials who need to run elections next year.