Voting: November 2008 Archives


November 23, 2008

The recount in the Coleman-Franken Minnesota Senate race is in full swing and so again as in Florida 2000, we get to observe the spectacle of voting officials trying to figure out just what the heck their fellow citizens were thinking when they marked their ballots. This election was run on optically scanned paper and Minnesota Public Radio has posted a whole set of challenged ballots and a quiz where you can make your own judgement about whether they should be accepted or not. As I've mentioned before, one of the nominal advantages of DRE systems (see for instance, this post by Ed Felten) is that when you do a recount you don't have to do this, or rather one should say you can't do this because the DRE just records whatever choice you think it made. It may be wrong, but it's (almost) never ambiguous. Unfortunately, DREs and opscan ballots are incomparable in a number of other ways so it's sort of hard to decide whether this particular feature is decisive. Instead, let's try a thought experiment. Consider the following four voting systems:

A. Ordinary Precinct Count Optical Scan Ballots
You mark your paper ballots and they're scanned in the precinct and then dropped in a box. The scanner detects under and overvotes and spits out your ballot if it thinks it's invalid, but you can't tell if it's misread your vote. The paper ballots are available for subsequent recounts as usual.

B. PCOS + Confirmation
This is just like system A, but before the system accepts your ballot it shows you a confirmation screen indicating its interpretation of how you voted. If you think it's wrong, you can start over again with a new ballot. This isn't a security feature, really: the machine can always lie; it just detects incorrect reads (assuming voters check the confirmation screen).

C. Disposable PCOS + Confirmation
This system is like system B, except where the ballot box would ordinarily be (underneath the scanner) there's a big crosscut shredder which destroys your ballot as soon as its been recorded. Thus, the only possible recount is re-exporting the vote data from the scanner and re-tabulating at election central.

D. Disposable PCOS + VVPAT
Finally, consider what happens if we take system C but fit it with a VVPAT printer, which records the systems's interpretation of your vote which you can then accept or reject as usual with DREs.

System A is roughly how PCOS elections are run now. As far as I know, System B doesn't exist anywhere You could imagine retrofitting any PCOS scanner with a big enough screen, but even the biggest screens, like those found on the Hart eScan, are pretty small. Systems C and D correspond roughly to DREs with and without VVPATs. The two main differences are that the UI is lousy and that whereas with a DRE it's not really possible to have an independent record of the intent of the voter,1 with systems C and D we had an independent record, but we systematically destroyed it in order to avoid the ambiguity of being able to go back and second-guess the machine later.

If you buy the argument that it's bad/embarassing/awkward to have people go back and try to revise the machine count, then you ought to think that systems C and D are better than systems A or B. The difficulty with this position is that we know that the scanners do make mistakes and this basically removes our ability to correct a large class of them. Now, you could argue that any scanner errors will be caught by the users in the confirmation phase, but we know that's not true [*], so we're left tolerating the machine error rate with no real way to correct it. The counterargument, here is that the recount has its own error rate, both in terms of ballot interpretation and in terms of ballot handling—it would be one thing if we all agreed on the set of ballots to be audited, but in actual practice the chain of custody of paper ballots can be fairly problematic, so it's not just a matter of deciding the contents of each ballot, but also of making sure you have all the ballots.

Note that while superficially system D seems a lot like system B: in both cases we have an electronic record plus a paper trail. But upon deeper inspection they're really quite different: in system D, what we have is a voter verifiable paper audit trail. I.e., the voter could in principle have checked the paper (though Everett et al.'s research suggests this is unlikely), but the paper just reflects the machine's opinion of the voter's intent. By contrast, in B we have a voter created paper audit trail (I don't think that VCPAT is standard term, but it should be), in which we can independently assess the voter's intent from the paper record. This issue becomes increasingly important the higher the probability that the machine will misrecord people's votes, whether through malice or malfunction.

1. I should qualify this a little bit. Obviously, we could just videotape the voter voting, but that would utterly destroy ballot secrecy, which is generally considered to be an invariant of such systems. Cordero and Wagner [*] have described a system for privacy preserving audits of DREs, where they record the UI inputs but engage in scrubbing to try to remove sensitive marks. It's not clear how well this works.


November 9, 2008

Sorry about the delay in completing this part of the series. Things got a bit crazy after the election. Anyway, when we left off I had just covered malicious failure modes in the polling place. Today we'll be talking about failures in the back office, aka election central. There's plenty of stuff to go wrong in the election preparation phase (ballot definition, device programming, etc.), but here I'm mostly interested in vote tabulation, which is done via the Election Management System (EMS).

Depending on the election system being used, tabulation can be performed in a number of ways:

  • In central count opscan systems, the ballots get shipped back to election central, so we have to actually scan them and then tabulate the results.
  • In DRE and precinct count opscan systems, pre-counted results come back from the precinct and simply need to be aggregated and the winners declared.

It's best to take each of these separately.

Central Count Optical Scan
Most plausible CCOS failures are non-malicious: it's pretty hard for an end-user to mount any kind of attack on the scanning system proper or than denial of service. Obviously, the attacker could tamper with their ballot (treat it with acid, glue, or somesuch) to damage the scanner, but it's not clear what this would buy you other than delaying the count. [This isn't to say that there isn't plenty of room for manipulating paper ballots, just that you would probably find it more profitable to do outside of election central, which is presumbly subject to fairly restricted access.]

On the other hand, plenty of stuff can still go wrong. First, ballots don't always scan correctly. If you're lucky, the scanner will just reject the ballot and then it will need to be manually counted. Often the voter's intent is clear, but if it's not, there's no real opportunity for the voter to correct it, and their vote just gets lost. Other than that, the sheet feeder in the scanner can mangle the ballot in various ways, causing inconvenience, manual counting, etc.

That said, if an attacker does manage to take control of the CCOS scanner, the consequences are fairly serious. As with any other piece of computerized election equipment, the attacker can cause it to return any result that he wants. On the other hand, the scanner very rarely needs to be connected to any other piece of computer equipment, so the risk can be minimized with proper controls.

With PCOS and DRE, results get communicated back from the field one of two ways: either on some sort of memory card or on summary results tapes. The big concern with memory cards is that they can serve as a vector for viral spread from compromised precinct machines. For instance, the TTBR Diebold report describes such an attack. As usual, if the EMS is compromised, the attacker can cause it to report any results it chooses. This includes, of course, misreporting any results fed into it from the central count optical scanner. An even more serious concern is that if the same EMS is used for ballot preparation and machine initialization then it can serve as a viral spread vector: the attacker infects a machine in the field, the virus spreads to the EMS, which then compromises every polling place machine. ([HRSW08] has a lot more discussion of this form of attack, as well as countermeasures.)

The data doesn't have to be sent back on memory cards, of course. DREs and opscans typically print out results/summary tapes with the vote totals. These can be manually keyed into the EMS. This mostly controls the viral threat, but now you have to worry about a whole array of errors on the paper tape. As this post by Ed Felten indicates, the quality of the results tapes is pretty low and when coupled with the usual human errors, there's a lot of possibility for the wrong data to end up in the EMS. (This isn't to say that there can't be errors on the memory cards as well, especially with the Premier system which uses some super-old tech; Sequoia and Hart use PCMCIA flash drives, which are just old tech.) In principle, this might get detected by comparison of the precinct-level results tapes, which (at least in Santa Clara County) get posted publicly elsewhere, but I don't know if anyone actually double checks that stuff in practice.

Of course, almost none of these issues are obvious to voters: you just vote, but you have no real way of knowing if your vote was counted or not (this is deliberate, for vote privacy reasons). And of course it's even harder to verify that any issues have been handled correctly.

Next: attack vectors.


November 4, 2008

Yesterday I wrote about non-malicious e-voting failure modes. In today's installment, we discuss malicious failure modes in polling place devices (tomorrow we talk about the back office).

The most powerful attack is if the attacker can gain actual control of the voting machine. There has been a lot of work on subverting polling place devices, but the bottom line is that it looks to me like an attacker with limited physical access can take control of pretty much any of the standard devices (I'll cover attack vectors later). Obviously, an attacker who controls a voting machine can make it do pretty much anything it's physically capable of, including simulating any non-malicious attack. However, there are also more subtle attacks that an attacker can mount. The TTBR and EVEREST reports provide extensive catalogs of the possible attacks, but I'll just cover some of the highlights here, focusing on attacks designed to alter the vote count.

Because the optical scan interface is so limited, it's extremely hard to distinguish malicious from non-malicious errors. However, an attacker who controls an optical scanner can cause selective failures of the optical scanner in several interesting ways. First, the scanner can explicitly reject ballots cast for particular candidates; for instance, it could claim that some fraction of ballots with Burr selected were undervoted or overvoted. It's not clear how powerful such an attack is, since presumably voters would keep trying and eventually either the ballots would be submitted for exceptional manual processing or the machine would be taken out of service. On the other hand, this could serve as a vote suppression attack for particular districts. A more sophisticated version of this attack would be to have the scanner count votes and if it detects that a lot of voters are voting Burr rather than Hamilton, it starts failing more frequently, suppressing votes in Burr precincts.

There are also invisible attacks: the scanner could simply record votes for Burr instead of Hamilton. As I noted previously, this would only get caught in an audit with a separate scanner or hand counting, since there's no display to the user of the scanned ballot. Even if there were, the scanner could display "Burr" but record "Hamilton", so there's no real way for the user to detect attack. Not all jurisdictions do audits and it's not clear that even where they are done, they're done in a powerful enough way to detect and correct this kind of tampering (more on auditing in a later post as well).

Even an attacker who doesn't control the machine can still perform a DoS attack: optical scanners and the sheet feed mechanisms inside are relatively easy to jam. If you're not worried about getting caught, you could clearly cover your ballot with glue and then shove it in the scanner. There are probably substances you could use that would dirty the scan heads enough to make votes hard to read. Could you do this selectively? Maybe. opscan ballots in Santa Clara are two column, but each race is a single column, so you can't prefer one candidate to another. But what you could potentially do, depending on the scanner, is dirty the section of the head over a given race thus suppressing votes for just that race, which would let you have a semi-selective effect. This would be an invisible attack unless the scanner is configured to report undervotes.

There's an enormous amount of room for attack with DREs. You could clearly mount a simple vote-flipping attack, simulating a flakey touchscreen and making the machine visibly shift votes from Hamilton to Burr. However, you can do far better than that. The attack that's most obvious—and has generated the most concern—is simply to have the machine record an entirely different set of votes than the voters are voting. [In the research community it's generally considered declasse to just stuff the ballot results with fake votes because at least in principle jurisdictions record the total number of votes and can compare them; intead you change users votes.] This isn't even noticeable to the voter, since the UI all looks right. It's just that a different vote is recorded. Without an independent record of your vote, there's no straightforward way to detect or correct this kind of attack.

If a VVPAT is in use (see the previous post for a description of a VVPAT), the attacker's job becomes a little harder. If he just creates totally phony records, then the electronic results won't match the results on the VVPAT. The obvious attack here is what's called a "presentation attack". The machine accepts the user's input but somewhere along the line it changes the vote. Maybe it does it on initial input but more likely it does it before the summary screen or just on the VVPAT. Studies show that users aren't very good at checking these and so mostly this will work. Even if the user catches it, the machine just lets them correct "their" mistake and then perhaps waits a while before attacking again. A really sophisticated machine might be able to monitor user behavior to try to pick out users who seemed uncertain about how to use the machine and attack them preferentially. The advantage of this kind of attack is that it makes the VVPAT and the electronic records line up, making audits much harder.

Other attacks are possible too: the attacker controls the printer, so perhaps he can print the VVPAT as normal and then when the voter casts their vote, he waits and then prints "VOID" or "REJECTED" (depending on how the machine would ordinarily display rejected ballots) and then prints his own votes of choice. This just looks like a bunch of extra printer activity and since voters don't have a lot of idea how the VVPAT is supposed to behave, it's not at all clear they would notice.

As with OPSCAN, there are also a broad variety of DoS and selective DoS attacks. The machines can be programmed to slow down or crash when you vote for specific candidates. They can fail to display specific races. For instance, if the attacker wants to influence a Senate race and it detects you voted for party A for president, then it could not show you the senate race, thus pushing the race toward party B. Again, you might not notice this in the VVPAT/summary screen. Even without full control of the machine, it's probably possible to crash it in various ways without getting blamed.

Malice, incompetence, etc.
I said at the beginning of this post that an attacker can simulate more or less any non-malicious failure--and has a real incentive to do so. However, as anyone who has worked with computers can tell you, they are perfectly capable of behaving in lots of surprising ways without any malicious activity at all. Any report of failure needs to be evaluated using Hanlon's Razor. We have plenty of evidence that voting machines in particular can do things that look like attacks even when it's pretty clear they are not (see this video, for instance), so while certainly we have to be wary of attack, it's probably a mistake to jump to the conclusion that there's been an attack just because you see something funny.

Next: Malicious failure modes at election central

UPDATE: Fixed cut and paste error.


November 2, 2008

Voting machines (DREs and optical scanners) are computers and like any piece of computer equipment, they can fail in a more or less unlimited number of exciting ways. In this post, we focus on non-malicious failures, i.e., those where no attacker is trying to induce failures. It's useful to divide failures into two categories: voter visible and voter invisible. DRE "Vote flipping" is a classic voter visible error. You plan to vote for Jefferson, but when you press the touchscreen, the checkbox appears next to Burr. But remember that your vote is just being recorded on some memory card and just because the screen says "Jefferson" (and the VVPAT says Jefferson, if there is one) doesn't mean the memory card doesn't say "Burr". That's an invisible error.

We can divide visible failures into two additional categories: vote recording errors and system failures. Both of the errors above are recording errors, but the system can also just fail in some more obvious and crude way. For instance, it might not turn on, or might not respond to input or might crash as soon as you try to cast your vote. This shouldn't surprise you; they're computers after all, and crashing is one of the things that computers do best. [The Diebold AV-TSX actually runs Windows CE, so I suppose there is some chance you could get a Blue Screen of Death.]

Most precinct count optical scanners are fairly opaque devices: you insert your ballot and either it accepts it or rejects it. If it detects an error (overvotes or undervotes, depending on programming), it will generally spit the ballot out with some sort of error message. Even within this range, a variety of visible errors are possible. The machine could accept invalid ballots (though this probably won't be noticed unless the voter deliberately does something wrong); it could reject valid ballots. It could also refuse to accept any ballots at all (i.e., not feed them into the scanner) or jam while processing a ballot. Finally, it could just flat out crash or stop working in some other gross way.

By contrast, vote recording errors with opscan systems tend to be silent, as long as they don't turn into an error that the machine is programmed to check. In principle, the optical scanner could display who you voted for and give you an opportunity to accept or reject, but as far as I can tell, none of the popular scanners actually do this. Indeed, the Sequoia Insight display looks to me to be too small to plausibly display your votes, so it's probably not just a matter of software to add a feature like this.

OurVoteLive's database of voting problems shows another, non-computerized, failure mode of opscan systems: bleeding pens.

DREs have a much fancier UI than opscan systems and so can freak out in a whole bunch of fun ways. The one that gets a lot of attention is "vote flipping", but there are actually a number of different ways in which the votes recorded can be inconsistent with the user's intent. A DRE has (at least) the following values:

  • The user's intended selection.
  • The UI gesture the user makes.
  • The option that the UI displays as selected.
  • The option selected in the summary screen.
  • The option selected in the VVPAT (if any).
  • The option recorded on the memory card.
There are plausible paths that could lead to effectively any combination of values here. The only one of these that voters are really likely to notice is that the option that the UI displays as selected doesn't match their intended vote [Everett reports that most users don't check the summary screen]. And of course, if the recording on the memory card is wrong, that's a silent failure. It's worth noting that the "vote flipping" people complain about seems much more likely to be a bug than an attack, since a plausible attacker would do something more subtle.

Of course, there are lots of kinds of system failures. Pretty much anything you've ever seen on your desktop computer can show up on a DRE. The computer can lock up, skip races on the ballot, crash, etc. One of the big failure modes seems to be the VVPAT printers: when I took Santa Clara county voter training they told us we would have three printers for our one lonely DRE, just in case some broke down.

It's worth mentioning that DRE breakdowns tend to be more serious in terms of impact on voting: if a precinct count scanner breaks down in an obvious way, you just move to paper ballots in a box and scan them later (though some failures, like preferential rejection of votes for certain candidates, may have more serious effects). By contrast, if the DREs break down, people can't vote and if you don't have enough emergency paper ballots on hand, it can actually stop people from voting, or at least create incredibly long lines if just some of them are broken.

Back Office Failures
There are also plenty of failures that can happen after the polls close, either at the precincts or in the back office. For instance, the memory cards used to carry the results can be corrupted. Most of these are recoverable at some level, since the machines print out paper receipts and of course you can recount the paper ballots and the VVPAT (if any). The tabulation software at election central can screw up as well, but that's independently checkable from the precinct tallies.

In addition, the central count scanners can fail in the same ways as the precinct count scanners can fail. Visible failures, like rejected ballots, can be dealt with by manual counting, but there can be invisible failures which can only be caught via audits and recounts, which generally only sample a small fraction of ballots.

Non-Technical Failures
The above partial catalog of technical failures isn't to say that there aren't a huge number of potential non-technical failures. A huge amount of our pollworker training was devoted to the various anomalies we might have to deal with, ranging from voter's address is wrong to voter is a convicted felon. I may get around to talking about those at some later point.

Next: Malicious failure modes.


November 1, 2008

Most elections in the US use what's called first past the post voting. This just means that whoever gets the most votes wins, regardless of if they get a majority of the votes. Some other countries use what's called Instant Runoff Voting (IRV). The idea behind IRV is that voters rank order their choices. Then, if no candidate has a majority of first place votes, the lowest ranked candidate is removed and you then take the highest ranked candidates from each voter who voted for that candidate. Gigabytes of material have been written about the virtues of IRV versus first past the post versus approval voting, and I don't propose to rehash that here. Instead, I want to talk about the impact of IRV on a voting system.

The issue is this: in a FPTP system, the machines can simply record the number of votes for any candidate, since this is sufficient to resolve the contest.1 In an IRV system you need to record the rankings. Here's an example of why:

Let's say we have an election with three candidates, which we'll call Alice, Bob, and Charlie, and denote A, B, C. We have five voters, numbered 1-5. Now, consider the following table of preferences:

A A B B C    --  A:2, B:2, C:1
C C C A B    --  A:1, B:1, C:3
B B A C A    --  A:2, B:2, C:1

In the first round, then A and B are tied, so we cross out C. This has no impact on voters 1-4, but voter 5 now votes for B, so now it's 3-2 for B and B wins.

Now consider the following table of preferences:

A A B B C     -- A:2, B:2, C:1
C B C C A     -- A:1, B:1, C:3
B C A A B     -- A:2, B:2, C:1

This has the same totals as before, but this time, when we cross off C, voter 5 votes for A and now it's 3-2 A and A wins. I.e., totals aren't enough to determine the winner of an IRV contest. (At this point I can hear the approval voting enthusiasts screaming that approval doesn't have this problem. That's true but irrelevant. Take it outside.)

In order to make IRV work, you need to report each voter's preferences. The difficulty here is that this represents a potential threat to voter privacy because it means that election central needs to have access to the voter's ballot information (this is true with central count optical scan, but not with precinct count or DREs). If there is some way to tie the ballot to a voter, you could know how a voter voted, which could be used for vote buying or coercion.

One standard technique for this sort of tying is what's called "pattern voting". The voter is instructed to vote for a specific set of candidates with one race being the one the vote buyer cares about and the other ones being used to encode the voter's identity. Then the attacker looks for that ballot in the reported ballot lists. One natural defense is to disaggregate the contests, so that while you keep the preferences for a given race, they are disconnected from other races. However, when IRV is used, you can encode your information in the ordering of the individual contests, typically without too much impact on the election. This works especially well in races with a large number of candidates, where it doesn't matter too much how big your effect is on the 29th and 30th candidate.

There has been some work on cryptographic techniques for IRV (e.g., [*]), but the uptake of cryptographic voting in general has been minimal.

1.Though it turns out that many DREs actually record the invididual vote results. See, for instance Issue 5.2.19 of the Premier Elections TTBR report.

Over the next week or so you're going to hear a lot of complaints about voting machine failures. Unfortunately, the signal to noise ratio tends to be fairly low, so it's hard to figure out what's going on. Over the next few days I'm going to post a bit about voting technology and what kind of things can go wrong. In this post, we provide an overview of the major kinds of voting system in use in the US.

The majority of voting systems in the US fall into one of two broad types:

Optically Scanned Paper Ballots (opscan)
These are pretty much what they sound like. You're issued a paper ballot (usually card stock, actually) and you fill in a bubble or arrow corresponding to the candidate you want to select. Here's an example. These ballots are then optically scanned and the votes are recorded.

Opscan ballots can be run in either a precinct count optical scan (PCOS) or a central count optical scan (CCOS) mode. In PCOS, the scanner is at the precinct; you mark up your ballot and then you feed it into the scanner. At the end of the election, the scanner outputs the results on a piece of paper or a memory card. The results then get carried back to election central where they can be aggregated to determine the final winner. The ballots also get sent back in case a recount is needed, but they're not used as part of the main count.

In CCOS, there is no scanner at the precinct. Voters just drop ballots into boxes and then they are counted on one big scanner (or maybe many) back at election central, where the votes are aggregated and the winner is determined. Some jurisdictions run hybrid systems where ballots cast at the polling place are PCOS counted but absentee and vote-by-mail ballots are counted centrally.

A PCOS system has two major advantages. First, because votes are scanned while the voter is still present, errors can be caught and the voter can correct his ballot onsite. Thus, the rate of errors is quite different ([*], citation due to Joe Hall). Second it creates a set of independent records that might be useful for detecting some ballot stuffing attacks. The big disadvantage of a PCOS system is that the scanner is out at the field and is potentially subject to attack by voters or pollworkers. An attacker who takes over the software of the PCOS system can make it return any results he wants, which won't be detected unless an audit or recount is run. By contrast, the central count scanner can be kept in a secured room and thus is harder for outsiders to attack.

The advantage of both types of systems is that there is a paper record, so in the worst case you can recount every single ballot with a new scanner or by hand. More on this later.

Direct Recording Electronic (DRE)
The other major type of voting system is what's technically called a Direct Recording Electronic (DRE). These are commonly called touchscreens but not all are. A DRE is just a computer where you enter your vote. The computer outputs the votes (or the vote totals), just like the PCOS scanner. They then get carried back to election central for aggregation and contest resolution. Most of these machines are in fact touchcreens, but older ones often used an array of buttons and the Hart system uses a clickwheel. One big advertised advantage of DREs is that they can be fitted with a variety of accessibility devices (audio, sip/puff, etc.)

Many states require independent paper records and so most DREs can be fitted with what's known as a voter verifiable paper audit trail (VVPAT) printer. A typical VVPAT is a reel-to-reel printer with the paper under glass. Here's a not so great picture of a Hart voting machine with a VVPAT fitted (on the left). The way the VVPAT works is that once you've entered your vote, the DRE prints out a summary on the tape. You can then either approve or reject it. If you approve it, the vote is cast. If you reject it, you can vote again. The idea hear is that the paper trail represents an independent check on the machine, since it can't just return any votes it wants; the results need to match the paper (at least if you run an audit). More on this later.

Electronic Ballot Markers (EBM)
There's one less commonly used system that's starting to get some traction, at least in terms of mindshare: electronic ballot markers. An EBM is basically a DRE which instead of recording the ballot results, prints out a paper ballot which can be fed into an optical scanner. The idea here is that there is built in error checking, since the computer can prevent invalid choices, but that the ballots can then be checked using central counting, so there is less of a security dependence on the machine. Also, like DREs, EBMs are more disabled-friendly.

Next: Non-malicious failure modes