Electronic voting and partial audits

On February 16th fellow CNET blogger Robert Vamosi wrote an item headlined "With improvements, e-voting could be good, says researcher." I think that e-voting is a very bad thing and that no "improvements" will ever convert it to a good thing. But I'm not an expert on the subject, so I asked Rebecca Mercuri, a specialist in computer security and electronic voting, if she would like to respond to the claim made by the "researcher" in question. Mercuri has appeared many times on the Personal Computer Show to discuss electronic voting, which is where our paths previously crossed. Her response is below.

Electronic Voting and Partial Audits -- Let's do the Math
Guest blogged by Rebecca Mercuri
www.notablesoftware.com

I did not attend ShmooCon 2008, but I found Robert Vamosi's synopsis of J. Alex Halderman's talk rather curious. I'm sorry to hear that Dr. Felten was ill, but it's dismaying to hear a report of yet another of his Princeton mentees extolling the praises of a hypothetical future crop of acceptable electronic balloting or counting machines.

Keep in mind, I'm actually a long-time Felten fan who stepped up to his defense a while back, when he was inappropriately trashed by an article in the Chronicle of Higher Education. Felten and his students are well known for their efforts over the years in exposing the vulnerabilities of electronic voting and tabulation equipment.

First, there was the now infamous 2003 report "Analysis of an Electronic Voting System" co-authored by Avi Rubin and Dan Wallach (both Ph.D. alums of Felten) with two of Avi's students (Felten grandchildren?) that blew open the security risks of the Diebold source code that had been leaked onto the Web. And then, Felten and two of his more recent students (Ariel Feldman and J. Alex Halderman) performed a further analysis of the Diebold AccuVote-TS during 2006 that augmented the earlier list of discovered weaknesses with even more shocking revelations.

The Feldman/Halderman/Felten paper noted the following main findings:

1. "Malicious software running on a single voting machine can steal votes with little if any risk of detection..."
2. "Anyone who has physical access to a voting machine, or to a memory card that will later be inserted into a machine, can install said malicious software..."
3. "...machines are susceptible to ... computer viruses that can spread malicious software automatically and invisibly from machine to machine..."

I know these findings were directed at the particular voting machine type that they had investigated. And yes, I know I've removed some of the wording of their findings that pertains to that particular voting machine to make these statements more general.

But the fact remains that the field of computer science has not changed significantly in the last two years, nor is it expected to change any time in the foreseeable future, such that the currently unsolvable problems in the field that underlie these findings for all electronic voting and tabulation systems will miraculously vanish.

The problems I am talking about are those that involve computational complexity of the sort that make it infeasible to determine whether any computer is really doing what it is supposed to do, doing it correctly, and doing nothing else. Combine these issues with the insider physical access to voting systems, plus the secrecy of the ballot that precludes end-to-end auditing, and you have a problem meritorious of the Nobel Prize in Computer Science (of which there currently isn't one awarded, but there should be if these matters are ever fully mitigated).

Seeing as how the complexity of the issue itself is not even known to be solvable (view my comments on this topic at Harvardmagazine.com/2004/11/voting-into-vapor.html), the idea that "once the e-voting vendors improve their systems" (even if they were willing to do so, of which we have seen no evidence yet) they will somehow be ready for prime time, is simply ludicrous.

But Halderman is not alone in his cloying defense of e-voting among Felten's illustrious descendants. I and many others abandoned the ballot-behind-glass paper add-ons (sometimes known as the "Mercuri Method") back in 2003 after observing (even despite personal protest) how the vendors inappropriately designed these products such that denial-of-service attacks could be masked within a preposterous failure rate of upwards to 10 percent. Yet Avi Rubin waited until 2007 before disavowing e-voting, saying (to a U.S. House Subcommittee) "I now believe that a DRE with a VVPAT is not a reasonable voting system."

Editors note: A DRE is a Direct Recording Electronic voting machine. Simply put, electronic voting. A VVPAT is a Voter Verified Paper Audit Trail. Simply put, the ballot printed by a electronic voting machine. It is not a receipt, that is, it is not something the voter takes with them.

Rubin went on to say that he was (finally) endorsing "paper ballots with ballot marking machines for accessibility and precinct optical scanners for counting--coupled with random audits." But we know from numerous recent studies of optical scanners (first in Florida by Hursti, then in California where Felten's team was involved, and later in Ohio) that the optical scanners are also riddled with the same software-based vulnerabilities that affect the DREs. At least with hand-prepared paper ballots there is something to manually count. Notice I said COUNT, not audit. And here's where Felten's clan gets it wrong again.

According to the Vamosi article, at the hackers event, Halderman apparently described a method whereby only 1,000 votes for the winning candidate needed to be audited in a million vote race where 1 percent of the votes decided the winner. Let's do the math: If the race is 50.5 percent to 49.5 percent and you need to change half of the difference (0.5 percent or a little more than 5,000 votes) from one candidate to another, then any randomly selected handful of votes of the winner would likely have about 1 percent bogus votes in it. So, using Halderman's example, out of 1,000 votes for the winner, you might then expect to find around 10 that should have gone to the loser. As it happens, 10 flipped votes is small enough to be shrugged off as a "clerical error" by the election officials (as we've observed in the recent New Hampshire primary recount, where hundreds of vote variations were detected).

Halderman's audit method (which I have not yet seen described other than in the CNET article, though it is likely similar to other proposed partial audit methods) becomes more dubious when you consider a real election scenario. There's typically a few third-party candidates and also the mysterious "undervote" rate that is usually explained away by "people choosing not to vote in that race" (sometimes in astonishing numbers, but typically about 5 percent of ballots cast). These undervotes are entirely indistinguishable from the vote counting system siphoning off a few votes here and there in order to achieve a desired result.

So let's factor this in as follows: one million votes, 465,000 to the winner, 455,000 to the first runner-up (1 percent of the votes decided the winner), 30,000 votes to the 3rd party candidates, and 50,000 undervotes (a 5 percent undervote rate). Now you have THREE places to bury votes--ones given to the winner that should have gone to the loser will count double (since they have to be subtracted from the winner as well as added to the loser), plus the 80,000 votes in the 3rd party candidate and undervote counts. Problem is, you don't know which ballots were counted as "undervotes" by the computer, where actually a legitimate vote had been recorded, without pulling all of the undervoted ballots out and seeing if their hand-counted total precisely matches the number of undervotes that the machines reported.

Basically, the likelihood of detecting 10 easily-dismissed, instances of vote tabulation fraud by counting only 1,000 of the winner's votes may be nil (especially if the thieved votes are mostly buried in the third party and undervote counts). You also have to consider the fact that the bogus votes are probably not going to be evenly distributed, but will likely clump up in particular precincts, thus making detection far less probable than what is typically theorized by many partial audit proponents. And we haven't even discussed the issue of county or municipality consolidation of vote totals, another highly vulnerable insider-managed process that requires independent reconciliation with the precinct counts.

What I'm saying is that VVPAT/DREs and partial audits (even of optically scanned ballots), despite the misplaced claims of some of Ed Felten's students, do not provide sufficient assurances to resolve the multitude of election integrity issues that we know are present with computerized voting and ballot counting.

Democracy is ill-served whenever quick-fixes are proposed that are not based on sound theoretical underpinnings combined with a decent understanding of election administration risks. If the inevitable answer is to publicly hand count all of the paper ballots on election night, then let's immediately start looking for ways to transparently apply good technology solutions to ensure that ballots and their subsequent vote totals are not damaged, altered, removed or replaced, along with instituting comprehensive security controls, rather than continuing to promote palliative shortcuts that run considerable risk of providing false validations of unjustified victories.

See a summary of all my Defensive Computing postings.