What's So Special About Voting?
Volume 37, Number 2, March 2004
Late in January, four computer scientists released a report urging the Pentagon to scrap a program that would allow overseas military personnel and civilians to vote via the Internet. As described in a front-page story in The New York Times, the report concludes that any such system would be vulnerable to attacks and viruses, and would thus compromise American democracy. Two weeks later, the program was cancelled.
Appearing in the midst of a flurry of media events highlighting the hazards of computerized voting, the report prompted Times columnist Paul Krugman to summarize the failings of electronic voting machines. He called for a solution favored by many security experts: to limit electronic voting to methods that produce a voter-verified paper record, subject to audits. Responding two days later in a letter-to-the-editor, Michael S. Smith of Brooklyn wrote that he didn't consider paperless voting a threat.
"My bank does a pretty good job of counting every cent of my money with computers. My phone company dutifully counts the minutes I use on my cell phone," Smith wrote. "In a country where a vote is supposed to be more important than a dollar or cell phone minutes, can't we come up with a sure-fire way to count votes electronically?"
Smith's letter cuts to the core of the issue. It is true that most people believe computers to be secure enough for sensitive financial transactions.
What's so special about voting?
The Voting Problem: A Mathematical Perspective
What makes voting tricky is that a voting system must satisfy opposing demands. With an electronic financial transaction, security comes from the separate receipts or documentation that participants can use to prove that the transaction occurred. With voting, however, standard receipts cannot be issued. If a voter could prove to a third party how he voted, he could sell his vote ...
In practice, the solution has been to choose anonymity and forsake verifiability. No individual can verify that her vote was included in the final totals, but a second-best measure is in place: Officials secure the process by making use of the opposing interests of the major political parties. ...
With the advent of electronic voting machines, the security of this carefully developed system is disappearing. As designers strive above all else for user-friendliness, electronic voting machines are running complex software with hundreds of thousands of lines of code. Thus, it's nearly impossible to know exactly what the code does ...
This is why many computer security researchers are pushing for the "voter-verified paper audit trail" advocated by Krugman. If electronic machines are backed up by separate all-paper records, the security measures of the established system, at least, are still in place. Nonetheless, many researchers agree with Smith of Brooklyn that information technology should make possible a safe, all-electronic solution that does a better job of counting votes than the current system.
"As we move forward, it's important to expand what we can do with electronics, though we have to be cautious, too," says Ron Rivest, Viterbi Professor of Computer Science at the Massachusetts Institute of Technology.
Douglas W. Jones, a professor of computer science at the University of Iowa and a member of the Iowa Board of Examiners for Voting Machines and Electronic Voting Systems, points out that even the most technologically advanced systems in place today are still based on the notion of a ballot box. "All voting vendors have the same model of how voting machines look and how to use computers to run an election," he says. "Thinking outside the box really seems applicable here."
How Votes on Paper Get Lost
In recent times, election margins have tended to be large enough to keep the public largely unaware of counting glitches. It took a statistical tie in Florida in 2000 to bring the flaws in the process to the attention of observers worldwide.
What those observers learned is that a surprisingly large fraction of ballots go uncounted. In a study of more than 2700 U.S. counties and municipalities across the last four presidential elections, the Caltech/MIT project found that 2% of ballots, on average, were mismarked or unmarked. ... After estimating the effects of long lines at polling stations and inaccuracies in the registration database, project researchers concluded that as many as six million votes (6%) nationwide, and up to 10% of the votes in some Florida counties, may have been lost in the 2000 election. (Bush eventually won Florida by an official margin of 537 votes.)
The researchers also found the number of voting errors to be technology-dependent. The U.S. uses five basic types of voting technology: hand-counted paper ballots, optically scanned paper ballots, punch-card ballots, 19th-century lever machines, and electronic voting machines (known as direct recording electronic voting machines, or DREs). The project found much higher rates of lost and mismarked ballots in counties that used punch cards or DREs than in those using other technologies, even when the researchers controlled for confounding factors. ...
Some researchers draw different conclusions from the data collected in the study. Jones, for instance, points out that the spread between different counties using the same technology was actually wider than the spread between technologies. "In many cases, non-technological factors, like bad ballot design, explain the problems more effectively than the technology used," he says. More information on this study can be found on the Web page of the voting project: http://www.vote.caltech.edu/.
Following the study, Caltech/MIT project participants recommended to Congress that the U.S. invest in improved voter-registration practices, with all punch cards and lever machines to be replaced by more modern technology. The eventual outcome was the 2002 Help America Vote Act, which authorizes a $3.8 billion budget for improving voting technology. The act also mandates the creation of a list of standards that new voting technology must meet, but Congress has yet to fund any of the research or standards-development activities mandated by HAVA, Jones says. Meanwhile, spurred by court rulings requiring a complete phase-out of the notorious punch-card systems, states are rushing to spend HAVA funds to replace their voting systems in time for the 2004 elections. The replacement technology of choice is proving to be DRE machines.
Asked why DRE machines are so popular with election officials, despite their many problems, Jones cites several factors. First, he explains, the machines look "cool" and modern. Second, election administrators dislike paper ballots: They are expensive---both to print, because large numbers of each ballot style often need to be stocked, and to store securely after the elections. DRE systems have high up-front costs, but each election does not require a large expenditure. Finally, Jones says, advocates for the handicapped (understandably) lobby hard for touch-screen machines, which enable many handicapped people to vote unassisted.
The Perils of DRE
In January, records from a special election in Broward County, Florida, showed that in a precinct using DREs, 134 more voters signed in than cast votes. As it turned out, that election was decided by only 12 votes, which triggered Florida's law requiring recounts in close elections. It wasn't clear how the DRE tally could be recounted, however. The record of the votes was the memory card from the machine; no separate record was available. A congressman from the region has filed a lawsuit against state election officials charging that the machines in place in Florida do not enable the state to fulfill the requirements of the law.
This and similar cases illustrate the greatest pitfall of DRE systems: There is no way to make them completely secure and thereby ensure that they provide accurate counts. As with any computer system, moreover, problems can typically be exploited on a large scale, making manipulation of an election conceivable.
Given the nature of the threat, computer security experts have become alarmed. Many have become e-voting activists, seeking out and widely publicizing DRE security flaws. Machines built by an Ohio-based company called Diebold, used in 37 states, have become a focus of attention.
Last summer, on receiving a copy of Diebold's source code, Johns Hopkins professor Avi Rubin immediately began to analyze it; working with him were two students, Tadayoshi Kohno and Adam Stubblefield, and Dan S. Wallach, a professor at Rice University. Not long afterward, the researchers summarized their findings in "the Hopkins report," which was posted on the Internet and released to the press.
The group's evaluation was scathing, citing dozens of design criticisms and security flaws that could allow an attacker to change the results of an election. ...
Diebold responded with a point-by-point rebuttal, asserting that almost all of the researchers' concerns were mitigated by the security of the election procedures themselves. (For links to the Hopkins report and rebuttals and a detailed summary of the Diebold story, see Jones's write-up at http://www.cs.uiowa.edu/~jones/voting/dieboldftp.html.)
recently, the independent reviews demanded by Ohio and Maryland were released. All found significant flaws in systems from Diebold and other vendors. A recent follow-up evaluation, conducted by Raba Technologies on behalf of the state of Maryland, has an interesting twist: On January 19, to address the security of Diebold systems in combination with Maryland election procedures, Raba convened a small group of its employees, along with software programmers and professors of computer science. The group, called "the Red team," was asked to try to hack the machines, their associated smart cards, and the server that collects the tallies. Here are some highlights:
First, the team discovered that the smart cards were password-protected only, and with an easily guessed password. ... The machines themselves consist of touch-screen terminals with locking bays. ... The team discovered that the keys to the bays were identical for all the machines. ...
The server security was even worse. ... The Red team was easily able to dial in to the server, which runs Microsoft Windows NT. Using readily available software to exploit a well-known NT vulnerability, they gained total control over the machine ...
The Raba report concluded that a paper audit trail and a software rewrite would ultimately be necessary to fix the Diebold flaws. In the meantime, it suggested some mitigating steps to defend against these specific attacks in time for the March elections, and "strongly" urged Diebold to take further steps to improve its security by November. The full Raba report is available at http://www.raba.com/press/TA_Report_AccuVote.pdf.
A Voter-Verified Audit Trail
Given the extent of the problem, security experts have banded together to urge lawmakers and election officials to adopt a relatively simple, short-term fix: a requirement that all voting technology be able to create a separate record of the votes that can be verified by the voters and then not easily changed. This separate record would then serve as the actual count of the votes, taking precedence over electronic records.
Computer scientist Rebecca Mercuri, in her 2000 dissertation at the University of Pennsylvania, described one way that DRE machines could supply such an audit trail. ...
Security experts and lawmakers like paper audit trails because they completely bypass the need to trust the security of the machine, yet the mechanism is simple to understand and relatively easy to implement. New laws mandating DRE paper trails have been passed in California, Illinois, and Nevada, and the secretaries of state in New Hampshire and Washington have endorsed such a requirement. ...
A resolution in support of voter-verified audit trails (with thousands of signatures) can be accessed on a Web site run by David Dill, a professor of computer science at Stanford University and an e-voting activist. (See http://verifiedvoting.org/.)
An Electronic Audit Trail
In a paper titled "A Modular Voting Architecture," Shuki Bruck, David Jefferson, and Rivest, all participants in the Caltech/MIT Voting Technology Project, describe an all-electronic voting architecture that they say could be made reasonably secure. The voting system is called the "Frog method." (Frog is not an acronym, the authors say; rather, it was chosen as "a neutral term with convenient clip-art for slides.")
The Frog method shares an essential feature with the Mercuri method: It separates the vote-generation process from the vote-counting process. Unlike Mercuri's method, however, it doesn't necessarily resort to paper.
Frogs should ultimately be cheaper than paper ballots, the authors suggest, because unused frogs can be held over for subsequent elections, and the ballot on each frog can be customized at the precinct level. For more information on the Frog method, see the Caltech/MIT voting project Web site: http://www.vote.caltech.edu/.
A Mathematically Verifiable Vote
The Mercuri and Frog methods manage to combine some of the advantages of computer voting with the reassurance of a paper audit trail. Yet even these methods leave open the possibility that votes will not be counted or that the system will otherwise be compromised. David Chaum, an independent cryptographer, and C. Andrew Neff of VoteHere, Inc. have independently devised systems that they claim will keep votes anonymous, yet enable all voters to ensure that their votes were correctly included in the final tally. The systems differ in the way they defend against dishonest voting machines and in their use of cryptography to protect privacy; still, the methods have similar overall structures.
Chaum's and Neff's methods will be discussed in an upcoming issue of SIAM News. Meanwhile, a quick overview of one of them will give readers an idea of how such a system is designed to work.
Sara Robinson is a freelance writer based in Pasadena, California.
©2003, Society for Industrial and Applied Mathematics