In an interview today with CNet, Michael Shamos talks about paper trails.  Shamos is a professor at CMU who has served as a voting system analyst for the Pennsylvania Secretary of State. In this article, a transcript of an interview conducted by Declan McCullagh, he spends a fair bit of time trashing paper trails, and by that, he’s referring to the “toilet paper roll” thermal printer attachments that are sold by the major U.S. voting system vendors.

He’s correct, to a limited extent.  He discusses a “20%” failure rate, which he probably gets from some problems in Ohio.  It’s certainly the case that these things are poorly engineered.  The ostensible reason for the continuous paper roll, as opposed to cutting the sheets individually, is that you’d have better reliability.  However, having the votes recorded in the order they were cast is a clear violation of voter privacy.  A more serious concern with paper trails is that it’s unclear whether voters will bother to double-check them at all.  I’ve pointed Freedom to Tinker readers at Sarah Everett’s PhD thesis before and it’s worth doing it again.  The punchline is that roughly two thirds of the test subjects didn’t notice when our homebrew DRE system was lying on its summary screen.  In fact, they gave our machine exceptionally high marks.  They loved it.

Shamos criticizes the EFF, VerifiedVoting, the League of Women voters, and anybody else he can think of because they advocate for paper trails.  The preferred solution that they generally advocate is hand-marked optical scan ballots.  These appear to have better accuracy, and paper ballots are, inherently, paper trails that give us an unfiltered window into the voters’ original intent.  Don’t interpret Shamos’s criticism of toilet-paper rolls as a criticism of hand-marked paper ballots.

Shamos goes on to make a flip comparison between “ATM technology” and voting systems, saying we could have reliable paper trails if we only spent 10x the cost.  This is a very strange argument.  ATMs are expensive because they have a safe full of cash inside.  It’s important that you can’t steal the cash, even if you’ve got time and tools at your disposal.  Voting systems (at least anywhere I’ll ever be likely to vote) don’t dispense money.  Building a reliable printer doesn’t need to be expensive.

Then Shamos gets into the meat of the argument for paper trails.

I’m not advocating that we blindly trust machines. We have to have a way to make sure the (record is correct). If anything happens to that piece of paper, if it gets substituted or lost, there’s absolutely no way to reconstruct the election. that’s unlike an electronic system, which is if one memory fails you have the other.

The security on ballot boxes is much lower than the security on voting machines themselves. In order to do anything with those pieces of paper, they have to be handled by people. What do you think happens?

If I want to screw up an election, all I have to do is modify five votes. Then we have to do a manual recount (which is vulnerable to tampering and ballot-stuffing).

This is completely false.  Paper records are redundant with the electronic records, and that’s a huge feature.  That means that you can compare them, either statistically in aggregate, or even one-to-one (assuming there are serial numbers, which could cause some privacy concerns, but maybe you can obscure those in barcodes).  It’s certainly the case that missing paper votes can be reconstructed from electronic records.  When you have both, you reconcile.  If there’s ambiguity, then you need to resolve that ambiguity.  You then have a forensic problem.  If all the tamper-evident stickers and locks on the paper ballot box were disturbed, maybe you’re more likely to trust the electronic parts.  If the totals are radically divergent, you can’t tell which is more authentic, and the election is tight, then maybe the proper answer (from a scientific perspective) is to throw your hands up and say that you cannot legitimately state who won the election as a result of fraud.  This is defensible, scientifically, but it could lead to a political crisis.  Nobody ever said election administration was easy.

Doing away with the paper only does away evidence that might help you discover fraud.  Even if you cannot come up with the proper answer, it’s better to at least know you were under attack.

The fundamental difficulty with paper trails is that they’re ridiculously kludgey. The problem is that once you mandate paper trails, it cuts off research. There would be no reason to use anything else because it would be illegal.

Speaking as somebody who does research in electronic voting, I don’t feel that laws mandating paper trails would stop me from studying alternatives.  The 2007 VVSG standards process includes an “innovation class” for how vendors can get funky fresh technologies certified for use.  The trick is to make sure that the innovation class isn’t a loophole that vendors can use for the current crop of insecure equipment.

Does that mean you’re suggesting that we should be voting from insecure home computers even if they’re running Windows 98?
Shamos: I can point you to a mechanism (in a paper by Avi Rubin and Dan Wallach) that would allow secure voting on insecure terminals. The notion that the Internet is just not secure enough to do anything important is just wrong. It’s not insurmountable. The right people aren’t thinking about it because you gotta have a paper trail.

Really?  A recent paper that I just submitted to a workshop talked about how Internet voting might work, by virtue of having remote precincts set up in places like embassies and consulates, and using dedicated voting machines.  You could send the results home over the Internet.  Voting on dedicated voting machines with an Internet connection might be workable.  Voting on Windows 98 PCs would be an unmitigated disaster.  Botnets control literally millions of computers out there.  What if you’re voting from a botnet-infested computer?  Could the botnet modify your vote?  Why not?  For these sorts of reasons, the authors of the SERVE Report, including Avi Rubin, recommended strongly against voting on generic PCs.  Shamos says that Avi and I would support secure voting on insecure terminals?  Sure.  We’ll probably be beaten by the bioengineers working on flying pigs.

Update: in private email, Shamos states that he was citing our 2003 workshop paper, “Authentication for Remote Voting“.  That paper discusses how to do bidirectional remote authentication, which would certainly be applicable to an Internet-based remote voting system.  That paper, however, offers no technique that could allow for secure voting on insecure home computers.

I say, and the advocates are forced to admit it, that there’s never been any evidence that a DRE machine has been tampered with in an election. They say that doesn’t mean it never happened. I agree with that. But I believe deeply that if people were out there trying to hack elections we would see evidence of failed attempts.

Indeed, there’s no evidence to support a lack of tampering, but that’s meaningless.  A better way to look at this is that the incredibly poor security of modern paperless electronic voting systems makes it cheaper than it ever has been before to manipulate votes.  The cost per vote for electronic manipulation is almost nill, particularly if you allow for viral attacks, where one corrupt DRE can take out the entire tabulation system (a vulnerably shown to apply to Hart InterCivic and Diebold as part of the California Top to Bottom reports from last summer).  Regardless of whether somebody has attempted an attack like this, it’s dirt cheap – cheaper than with paper, because manipulating paper takes more time and more labor.  The economic incentives are clearly in play for electronic election fraud.  The big question is whether it’s more cost effective to manipulate voters through other means (e.g., dubious television advertising, robotic phone calls, etc.).

When a bridge collapses, do we outlaw bridges or do we inspect bridges of similar design? If the design itself is fundamentally flawed, then those bridges are going to have to be taken out of service and rebuilt. If there’s a fix, however, you can add a bracing member.

Excellent point.  DRE systems from all the major vendors have been conclusively shown to be fundamentally flawed in their design.  Even if and when the vendors patch their software, the time delay to push those patches through the certification process guarantees they won’t be ready for November.  Optically scanned paper ballots are available today and they work quite well (despite known security vulnerabilities in the tabulators).  Likewise, junky toilet-paper roll printers are available today, despite known problems with their ability to print and with voter’s ability to catch mistakes.

One last point:

Please don’t use the term “paperless.” It’s a construction of the advocates and it’s false and misleading. They’re not paperless. They just don’t produce a contemporaneous paper that the voter can view.

The word “paperless” is really insidious. The word “less” is meant to imply that they’re thereby missing something. Whoever decided to come up with the term “paperless” deserves a left-handed prize for their imagination. It’s wonderful for them. Paperless.

Yes, “paperless.”  It’s a fine word.  I’ve been using it for years.  It concisely captures the lack of redundancy, the reliance on poorly engineered software, and the risky nature of using paperless DRE voting systems for something as important as a national election.

Paperless electronic voting systems can be made better, using tricks like Benaloh’s challenge mechanism, which can catch a machine, in the act, while it might otherwise be trying to corrupt the vote.  We used a variant on his mechanism in our research prototype (paper to appear this summer at Usenix Security).  Nonetheless, I really like the term “paperless” when hooked to “electronic voting machine” because it creates a burden of proof for the system designer.  You want to go paperless?  Fine.  Prove to us that your system is secure.  Without paper, we’ll assume it’s insecure until proven otherwise.

Today was the last day of early voting in Texas’s primary election. Historically, I have never voted in a primary election. I’ve never felt I identified enough with a particular political party to want to have a say in selecting their candidates. Once I started working on voting security, I discovered that this also allowed me to make a legitimate claim to being “non-partisan.” (While some election officials, political scientists, and others who you might perhaps prefer to be non-partisan do have explicit partisan views, many more make a point of similarly obscuring their partisan preferences like I do.)

In Texas, you are not required to register with a party in order to vote in their primary. Instead, you just show up and ask for their primary ballot. In the big city of Houston, any registered voter can go to any of 35 early voting locations over the two weeks of early voting. Alternately, they may vote in their home, local precinct (there are almost a thousand of these) on the day of the election. There have been stories of long lines over the past two weeks. My wife wanted to vote, but procrastinating, we went on the final night to a gigantic supermarket near campus. Arriving at 5:50pm or so, she didn’t reach the head of the queue until 8pm. Meanwhile, I took care of our daughter and tried to figure out the causes of the queue.

There were maybe twenty electronic voting machines, consistently operating at between 50-70% utilization (i.e., as many as half of the voting machines were unused at any given time). Yet the queue was huge. How could this be? Turns out there were four people at the desk in front dealing with the sign-in procedure. In a traditional, local precinct, this is nothing fancier than flipping open a paper printout to the page with your name. You sign next to it, and then you go vote. Simple as can be. Early voting is a different can of worms. They can’t feasibly keep a printout with over a million names of it in each of 35 early voting centers. That means they need computers. Our county’s computers had some kind of web interface that they could use to verify the voter’s registration. They then print a sticker with your name on it, you sign it, and it goes into a book. If a voter happens to present their voter registration card (my wife happened to have hers with her), the process is over in a hurry. Otherwise, things slow down, particularly if, say, your driver’s license doesn’t match up with the computer. “What was your previous address?” Unsurprisingly, the voter registration / sign-in table was the bottleneck. I’ve seen similar effects beforehand when voting early.

How could you solve this problem? You could have an explicit “fast path” for voters who match quickly versus a “slow path” with a secondary queue for more complicated voters. You can have more registration terminals. You could have roving helpers with PDAs and battery-powered printers that try to get further back into the queue and help voters reconcile themselves with their “true” identity. There’s no lack of creativity that’s been applied to solving this class of problems outside of the domain of election management.

Now, these voter registration systems are not subject to any of the verification and testing procedures that apply to the electronic voting machines themselves. Any vendor can sell pretty much anything and the state government doesn’t have much to say about it. That’s both good and bad. It’s clearly bad because any vetting process might have tried to consider these queueing issues and would have issued requirements on how to address the problem. On the flip side, one of the benefits of the lack of regulation is that the vendor(s) could ostensibly fix their software. Quickly.

To the extent there’s a moral to this story, it’s that the whole system matters. For the most part, we computer security folks have largely ignored voter registration as being somebody else’s problem. Maybe there’s a market for some crack programmer to crank out a superior solution in the time it took to read this blog post and get us out of the queue and into the voting booth.

(Sidebar: Turns out, the Texas Democratic Party has both a primary election and a caucus. Any voter who casts a vote in the primary is elgible to caucus with the party. The caucus locations are the same as the local polling places, with caucusing starting 15 minutes after the close of the polls. Expect stories about crowding, confusion, and chaos, particularly given the crowded, small precinct rooms and relatively few people with experience in the caucusing process. Wikipedia has some details about the complex process by which the state’s delegates are ultimately selected. There may or may not be lawsuits over the process as well.)