What's So Special about Voting?
March 13, 2004
U.S. voters express their preferences via five basic types of voting technology: hand-counted paper ballots, optically scanned paper ballots, punch-card ballots, 19th-century lever machines, and direct recording electronic machines. Researchers in one study found the highest rates of lost and mismarked ballots in counties that used punch cards or DRE machines. Photo by Carey James, Homer (Alaska) News.
Sara Robinson
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 or be coerced to vote in a certain way. Indeed, until secret ballots were introduced at the end of the 19th century, this form of voting fraud was rampant. An ideal voting system would thus be verifiable, yet anonymous-a seemingly impossible proposition.
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. In the U.S., Democratic and Republican party officials ensure that the ballot boxes start out empty, and then monitor both the voting and the counting processes. This does much to minimize outright fraud, although votes can be missed for many other reasons.
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, or to find all its flaws. Making matters worse, there is typically no completely separate record of the votes; if the counting process is compromised, the problem will likely go undetected.
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."
As described in this article, some computer scientists are beginning to do exactly that. Researchers in the Caltech/MIT Voting Technology Project, established after the 2000 presidential election in the U.S., have outlined one possible approach. Their key idea is to isolate and separately secure vote counting, the most sensitive step of the voting process. Another potential solution is mathematical. Some cryptography researchers are developing voting schemes that they say would enable people to verify that their votes were counted, but would preserve anonymity. These methods, which will be discussed in greater depth in a subsequent SIAM News article, are briefly introduced here.
First, though, a look at some of the failings of voting systems now in use will help put the current research into perspective.
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. And this is only one type of vote-counting error. 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. Punch-card technology, which produces the chads and dimples of 2000 fame, was cited as particularly prone to error: The study found that counties using punch cards had error rates double those of counties using other technologies. The study did not determine why so many DRE ballots are lost or mismarked. (Lever machines have other problems. A study by consultant Roy G. Saltman, for instance, found that the number 99 shows up more frequently than it should, suggesting that the machines often jam when rolling over to the next power of 10.)
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.
Diebold
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. The DES encryption key used to protect the integrity of voting data, for example, was hard-coded into the software. The report received widespread media attention and prompted Ohio and Maryland, then considering large-scale purchases of Diebold machines, to ask for independent reviews of the technology.
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.)
More 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. Once they knew the password, they were able to reinitialize a voter smart card to enable a voter to vote multiple times or to shut down the machine. The machines themselves consist of touch-screen terminals with locking bays. The second bay houses the on-off switch, a keyboard jack, and two PCMCIA card slots, one for a card with the ballot definitions and the other for a modem used to communicate preliminary results (final tallies are recorded on PCMCIA cards and transported by hand). The team discovered that the keys to the bays were identical for all the machines. Once they had access to the card slots, the team was able to insert cards that would, for instance, switch the candidates' names so that votes for one would be recorded for the other.
The server security was even worse. Procedures require that the server be disconnected from any network, but, as mentioned above, the machines are equipped with modems for sending unofficial tallies to the server during the election. 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, freely downloading and uploading files and modifying them. Given five minutes of physical access to the server, the group was also able to gain control by exploiting an enabled "autorun" feature.
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. In Mercuri's method, the DRE machine produces a paper ballot at the end of the voting process. The voter reads the ballot and, after verifying its accuracy, deposits it in a secure ballot box, as in the procedure for paper ballots now in use. With such a system, the voter gains the advantages of the touch-screen interface, and electronic tallies can be used to compute preliminary counts. But the final count is certified only after the paper ballots have been counted.
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. Meanwhile, bills wending their way through Congress would institute federal requirements. Some manufacturers already produce machines that can provide paper audit trails, and others say they will do so if the law requires it.
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.
Here's how it works: Each voter gets a frog, which the authors envision as a simple memory card that has been filled in with that voter's ballot information. The frog has read-write capability and can be locked or "frozen," after which its contents can no longer be easily changed. Frogs can be issued well in advance of election day. At some point, the voter fills in her ballot, using, say, a voting machine in her local Safeway. On election day, she is authenticated at the precinct and carries her filled-in frog ballot to a machine, the "vote caster," which is not connected to anything. The voter plugs in the frog, and the machine reads the vote and displays it on the screen. If the displayed information is correct, the voter pushes a button and the machine adds her vote to the tally. The frog is then frozen, digitally signed, and added to the ballot box. The expended frogs constitute the record of the election.
Because the output of the voting machines is checked by the vote caster, or any other device the voter wishes to use, the voting machines don't need to be secure; rather, the emphasis can be on fancy user-interfaces and other user-friendly features. All that matters is that the machines used be able to generate a filled-in ballot on a frog. The vote caster, on the other hand, does require heavy security, but such a machine can be kept so simple, the researchers say, that securing it is feasible. It can have a single-purpose operating system and run simple code that can be posted on the Internet and checked by all. Meanwhile, the frogs provide a back-up record in case the vote caster data is somehow corrupted.
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.
In Chaum's system, the privacy of a voter is assured jointly through the participation of n trustees, and the integrity of the election through the participation of the voting public and interested third parties.
Each voter leaves the polling place with a receipt, marked with a serial number, that contains his filled-in ballot. The ballot is digitally signed and encrypted in such a way that the collaboration of all n trustees is required to decrypt it. Third parties can use information on the receipt to check that it is valid. Once polls have closed, all receipts are posted on the Internet, and each voter can use his serial number to find the image of his receipt and make sure it matches the one he carries.
Meanwhile, each trustee, in turn, performs one step toward decrypting the receipts. During this process, the serial numbers are stripped off and the order of the receipts is shuffled so that they cannot be traced to individual voters.
Finally, the decrypted ballots are posted; voters can verify that the number of final ballots is the same as the number of receipts. Using additional posted information, third parties and sophisticated voters can verify that, with high probability, the one-to-one function that transforms receipts into ballots was correctly computed.
Chaum's system has not been published in full technical detail, and thus has not yet been fully peer reviewed, but several cryptography experts familiar with the work describe the method as "ingenious," and believe that the ideas will prove to be correct. Some researchers express skepticism as to whether the scheme is simple enough to be practical, yet laud Chaum's method as an important step.
At present, though we lack a "sure-fire" system for voting electronically, researchers are taking steps in that direction.
Sara Robinson is a freelance writer based in Pasadena, California.
