Let’s continue our discussion (1; 2) of Rivest’s ThreeBallot voting system. I’ve criticized ThreeBallot’s apparent inability to handle write-in votes. More detailed critiques have come from Charlie Strauss (1; 2) and Andrew Appel. Their analysis (especially Charlie’s) is too extensive to repeat here, so I’ll focus on just one of Charlie’s ideas.
Recall that ThreeBallot requires each voter to mark three ballots. Each candidate must be marked on at least one ballot (call this the mandatory mark); and the voter can vote for a candidate by marking that candidate on a second ballot. I call these rules (each candidate gets either one or two marks, and at most one candidate per race gets two marks) the Constraints. Because of the Constraints, we can recover the number of votes cast for a candidate by taking the total number of marks made for that candidate, and subtracting off the number of mandatory marks (which equals the number of voters).
ThreeBallot uses optical scan technology: the voter marks paper ballots that can be read by a machine. A voter’s three ballots are initially attached together. After filling out the ballots, the voter runs them through a checker machine that verifies the Constraints. If the ballots meet the Constraints, the checker puts a red stripe onto the ballots to denote that they have been checked, separates the three ballots, and gives the voter a copy of one ballot (the voter chooses which) to take home. The voter then deposits the three red-striped ballots into a ballot box, where they will eventually be counted by a tabulator machine.
Charlie Strauss points out there is a window of vulnerability from the time the ballots are checked until they’re put in the ballot box. During this time, the voter might add marks for his desired candidate, or erase marks for undesired candidates, or just put one of the ballots in his pocket and leave. These tactics are tantamount to stuffing the ballot box.
This kind of problem, where a system checks whether some condition is true, and then later relies on that assumption still being true even though things may have changed in the meantime, is a common cause of security problems. Security folks, with our usual tin ear for terminology, call these “time of check to time of use” or TOCTTOU bugs. (Some people even try to pronounce the acronym.) Here, the problem is the (unwarranted) assumption that if the Constraints hold when the ballots are put into the checker, they will still hold when the ballots are later tabulated.
One way to address this problem is to arrange for the same machine that checks the ballots to also tabulate them, so there is no window of vulnerability. But ThreeBallot’s security depends on the checker being dumb and stateless, so that it can’t remember the ballot-sets of individual voters. The tabulator is more complicated and remembers things, but it only sees the ballots after they are separated and mixed together with other voters’ ballots. Rivest makes clear that the checker and the tabulator must be separate mechanisms.
We might try to fix the problem by having the checker spit out the checked ballots into a sealed, glass-sided chute with a ballot box at the bottom, so the voter never gets to touch the ballots after they are checked. This might seem to eliminate the window of vulnerability.
But there’s still a problem, because the ballots are scanned by two separate scanner devices, one in the checker and one in the tabulator. Inevitably the two scanners will be calibrated differently, so there are some borderline cases that look like a mark to one scanner but not to the other. This means that ballot-triples that meet the Constraints according to one scanner won’t necessarily meet them according to the other scanner. A clever voter can exploit these differences, regardless of which scanner is more permissive, to inflate the influence of his ballots. He can make his mandatory marks for disfavored candidates faint, so that the checker just barely detects them, in the hope that the tabulator will miss them. And he can add a third mark for his favored candidate, just barely too faint for the checker to see, in the hope that the tabulator will count it. If either of these hopes is fulfilled, the final vote count will be wrong.
This is just a small sample of Charlie Strauss’s critique of ThreeBallot. If you want to read more, check out Charlie’s reports (1; 2), or Andrew Appel’s.
I jotted down some of my thoughts on ThreeBallot as well, at Usable Security. You might be interested in the comment i added to that post, which suggests a defense against alteration of the ballot between checking and collection.
The idea is to have the checker re-print the ballot with a change: it prints a solid white box over bubbles that it detects as empty, and prints a checkered black box over bubbles it detects as filled. The checkered pattern is hard to draw convincingly and hard to erase because it’s printed in ink, so any voter’s attempt to change the ballot after checking would be easily detectable. Also, the re-printed ballot gives the voter feedback on what the checker has detected, and should virtually eliminate scanning ambiguities.
What do you think?
Of course, we all know which “M”anufacturer is the most likely source of off-the-shelf software that proves insecure, though, don’t we? 😉
“M” stands for “manufacturer,” and “COTS” for “Commercial Off-the-Shelf.” The EAC’s Voluntary Voting System Guidelines (“VVSG”) exempt COTS software and equipment from most inspection and testing, as do most “open source” proposals. But an attacker could use this exemption to inject malware into a system. For example, an attacker could modify a voting machine’s COTS BIOS to replace a critical portion of the voting application, as I explained in section 3.1.2 of this paper: http://infolab.stanford.edu/pub/keller/2005/Shamos-rebuttal.pdf .
“M”, of course, standing for “Microsoft”? 🙂
(“COTS”?)
Quote:
——
For the second problem, that of coordination between the checker and the scanner, simply requiring that separate organizations build and operate each device, or having a second independently designed scanner at a separate location… with alarms and a manual recount where ballots didn’t match… would make this extremely unlikely. Any conspiracy that is so widespread that it can attack two or three independantly designed and operated devices in multiple locations would find manipulating the slate and voter access long before the actual polls a much more fruitful approach.
——
I think faith in “independently designed…devices” is misplaced. Nothing prevents vendor A from buying vendor B, or parent X from buying vendors A, B and C after the “indendently designed” devices are deployed. And nothing prevents vendors A, B, and C from unintentionally using malware-containing “COTS” software and/or hardware from common supplier M.
Also, global software attacks are likely to be the most fruitful large-scale attacks, because they need involve only a few people per vendor or supplier, yet they can corrupt large numbers of votes. See the Brennan Center’s report on voting system security for more about the “number of conspirators” metric. http://brennancenter.org/programs/downloads/Full%20Report.pdf . Local attacks are still, of course, important, especially in local elections.
Quote:
——
Rivest’s paper covers your scenario of adding marks after checking, and suggests to add a barcode checksum in addition to the red stripe. It doesn’t have to be very complicated, most people won’t be able to adjust the barcode according with a pen.
——
I think you’re referring to my attack. If so, it is not a manual attack that can be prevented by adding a checksum. It is a software-based attack that can corrupt the checksum. Indeed, the checksum itself is a fine place to hide the “copied bit.” Also the attack does not add tally marks; it only adds the “copied bit.” The scanner then cheats at its discretion by mis-scanning ballots not bearing the “copied bit.”
“Charlie Strauss points out there is a window of vulnerability from the time the ballots are checked until they’re put in the ballot box. During this time, the voter might add marks for his desired candidate, or erase marks for undesired candidates, or just put one of the ballots in his pocket and leave. These tactics are tantamount to stuffing the ballot box.”
As other people have noted, the checker can encode data on the ballot. That data can include a checksum of the data on each strip, in a form that is not amenable to human tampering. It doesn’t need to be steganography,
For the second problem, that of coordination between the checker and the scanner, simply requiring that separate organizations build and operate each device, or having a second independently designed scanner at a separate location… with alarms and a manual recount where ballots didn’t match… would make this extremely unlikely. Any conspiracy that is so widespread that it can attack two or three independantly designed and operated devices in multiple locations would find manipulating the slate and voter access long before the actual polls a much more fruitful approach.
Rivest’s paper covers your scenario of adding marks after checking, and suggests to add a barcode checksum in addition to the red stripe. It doesn’t have to be very complicated, most people won’t be able to adjust the barcode according with a pen.
Unfortunately, this doesn’t solve the problem, but for a different reason than you state: The votes which are have been tampered with will have to be rejected. This means your remaining two ballots can give *negative* votes. Example:
Alice: * o o
Bob: * * o
Carl: o o *
Here we’re voting for Bob (1-2-1). However, if we tamper with ballot 1, it will be discarded, and Alice will essentially lose a vote (0-1-1). If we tamper with ballot 2, the remainder is a blank vote (1-1-1). Tampering with ballot 3 has the most effect, it gives Carl a negative vote while still allowing us to prioritise Alice and Bob (1-2-0).
Rivest suggests that the “mandatory” column for each candidate is randomly prefilled. This will both ease the user interface (IMHO) and severely limit the potential for the above attack. We will be able to tell the amount of tampering, and can give a worst case estimate on its influence on the result.
How about this for a fresh new voting system?
On your ballot, you don’t mark an X by your favored candidate’s name. Instead, you cross out your least favored candidate’s name. The candidate with the fewest votes wins. 🙂
(This might make a real difference in areas where three or more candidates run for the same office, which means just about everywhere except the United States with its two-party system and the various one-party sham democracies out there.)
//Now vote-by-mail can be made a bit more secret if there’s a way for a voter, in secret, to show up at any voting station (not a specific one, which could be watched) at any time (not just election day) and say, “I want to cancel my mail-in ballot and do a real secret ballot here.â€//
I’d like to see a state require that mail-in ballots be cast at, sealed, and mailed by a notary public; notaries public would be required to provide such services free of charge as a condition of licensure. That would restore the secret ballot and also limit some types of fraud.
The problem of marginally-shaded ovals is easy to fix. Program the checker to reject (return to voter) any ballot in which any oval is between 10% and 90% shaded. Program the tabulator to reject (separate for hand inspection) any ballot in which any oval is between 30% and 70% shaded (accepting those in which none are within that range, even if some are between 10% and 30%, or between 70% and 90%).
On the other hand, the threeballot system does seem overcomplicated. Two things I’d like to see which wouldn’t add much complexity from a voter’s perspective, but would improve security nonetheless:
-1- Have a “no candidate selected” space on the ballot for each race and/or a place for the voter to indicate how many races have been left blank. If a ballot is inserted with the latter space not filled in, the machine would reject it and inform the voter what should be marked there. If the ballot is inserted and the count is wrong, the voter would be instructed to spoil the ballot and take another. Once the ballot is accepted, the addition of any marks would be detectable as fraud.
-2- Once all ballots are cast, they should be run through a tabulating machine in random order which should record the contents and mark each ballot with a one unique identifier for each race thereon (portions of the identifiers may be shared to save space). A database should be produced and published for each race with all the identifiers and associated votes.
It should then be possible for interested parties to arbitrarily select ballots and confirm that the paper ballots match the computer records. Note that it’s necessary to select the ballot by ID and then locate the paper record (which shouldn’t be too hard if the system logs (but does not publish) the order in which the ballots were scanned. Picking a paper ballot at random and checking its computer record would not detect a malfeasant system that sometimes assigned duplicate IDs to ballots that happened to be identical and then created records for imaginary ballots. Unless one happened to randomly pick two ballots that had the same ID, the duplicates would go unnoticed and undetectable.
Sadly, Ron’s system is too complicated for its goal. I say sadly because I do believe secret ballot is important. However, most voting systems have abandoned secret ballot in the name of voter convenience. That’s because they all have absentee voting by mail as an option, which eliminates secret ballot for those who wish to eliminate it, which is not much different than eliminating it entirely — as has been done in Oregon where all votes all mail-in.
Once you understand that the voters will not accept inconvience in order to get secret ballot, you realize that designing systems with any complexity to get it won’t go very far. The 3-ballot design has to add the sentence “And there is no vote by mail.” Then see how much people like it.
Now vote-by-mail can be made a bit more secret if there’s a way for a voter, in secret, to show up at any voting station (not a specific one, which could be watched) at any time (not just election day) and say, “I want to cancel my mail-in ballot and do a real secret ballot here.” But that’s pretty hard to do, though not impossible. (You have to allow this before election day because the vote buyer can say, “you had better be out of town, or at work all day, on election day.)
We gave up secret ballot long ago for convenience. We’ll only get it back if we somehow make things simpler at the polls, not more complex.
If they don’t try to pronounce the acronym, it’s not an acronym. In either case, however, it’s an initialism. (Most, but not all, acronyms are initialisms–cf. bit, Nazi).
I begin to wonder whether we’re not all losing sight of the goal here. The idea behind electronic voting with a voter-verified audit trail is not to close all possible avenues of fraud. Rather, it is to provide two different counting mechanisms – having different failure modes – in the hopes of making fraud detection easier.
I don’t personally believe that there will ever be a system, for instance, that cannot be defeated by collusion among a sufficiently great number of poll workers. If a system has descended into a sufficient level of corruption, the remaining two of the four boxes must be employed. (The four boxes are soap, ballot, jury, and ammunition. They should be used in order.)
Charlie Strauss wrote:
——
Rivest’s system should be praised on three accounts…3) it allows the use of dumb, resource starved, stateless equipment, it separates functions, and it does not allow the equiment to communicate….
——
But it does. The checker both reads the voter’s marks and prints a “these ballots have been checked” stripe (and possibly other information) on the ballots. As I noted above, the checker’s ability to write upon the ballots permits it to cheat by using the ballots to communicate with a cooperating tabulator.
Rivest’s system should be praised on three accounts 1) it works with paper without need of a computer for the encryption 2) it very cleverly seems to avoid the achiles heel of all other encrytped receipts: the need to contol access to the encryption keys to prevetn secret ballot compromise 3) it allows the use of dumb, resource starved, stateless equipment, it separates functions, and it does not allow the equiment to communicate.
Many of the proposed fixes so far on this commentary and previous days threads tend to involve adding layers of mechaincal or compuational sophistication, and violating one of the above tenets. For example, the checker and counter should not only have no way to communicate but it should be plainly obvious that this is so. Some plans involve making the systems “smart” enough to store state information–that will open up a whole can of worms of evil-software attacks, so we want to stay away from solutions like that.
Josh, in response to your crack. It’s a good iline of thought–in essence you are trying to invent a means for the checker and counter to communicate and thus collude. The specific proposals you make however assumes that the counter is not resource starved. In most practical counters today there are simple read-heads and threshold level detectors. there is not the resource of a machine vision system. (note some new scanners like those from Hart, acually are imaging systems and we want to avoid those for the reasons you site). Thus adding marks that as a means to communicate would be techincally difficult to implement on a system with just three fixed scan heads. And the resource enrichment needed to make mark based collusion possible would be noticable as a change in the machine’s physical characteristics.
So continue that line of thought, but be aware one of the best aspects of rivest system is that it intentionally is designed to allow dumb equipment to be so very dumb that it’s easy to determine if it actually has the computational resources to cheat. This is why proposals that propose to fix the holes, that themselves increase the brains of the machine, go against this principle and make validtiation of the machines “dumbness” increasingly difficult.
Also I’d advise having a look at the two papers of mine Ed links to. There’s a lot more to fix. In particular the encryption itself is surprisingly prone to cracking and vote selling. Some of the proposed solutions actually make these other problems worse.
how about this:
instead of making the checker and reader read the /same/ data, make the checker /duplicate/ the three ballots (and use the duplication to confirm to the voter that his ballot was read correctly), and shred the two original ballots that the user doesn’t want to keep – that way, it doesn’t matter how the machines are calibrated, because you’re guaranteed that the counter will read the ballot the same way as the checker read it. And then give the voter a copy of his receipt ballot.
Vorn
I have found an attack that voids ThreeBallot’s counted-as-cast guarantee. This attack operates against the integrated checker machine/copier and the tabulator, and would most easily be conducted by a vendor’s employee. When the voter presses the button to choose which ballot to copy, the checker operates as expected except that it steganographically encodes a bit onto that ballot indicating that the voter has copied it. Depending upon the particular sequence of operations, it might even be able to encode it into the red stripe. In any case the “copied bit” (which, for robustness, should be accompanied by another few bits of error-correction information) is little enough data that no voter should be able to detect its presence, let alone determine its purpose.
The tabulator, which also has been attacked, eventually scans the ballots. It honestly scans all ballots bearing the “copied bit,” and falsifies such of the others as suit the attacker’s purpose.
This attack can be caught by an appropriate manual audit, and its effects corrected by a full manual recount, but both the audit and the recount require approximately three times the effort of the corresponding ordinary (“OneBallot”) paper ballot audit or recount. I have not worked out the probabilities, but I think that the audit is even more expensive because at least 1/3rd of the ballots (the copied ones) are guaranteed to be scanned correctly.
Well, what if we use the same optical scanning head, but change what it’s wired into, while still retaining a secure path for the ballot from verification to tabulation?
Basically I’m envisioning a big plexiglass box (with one opaque panel to prevent people from seeing the ballot’s face) where you slip your whole ballot in, see it go through the scanning head (which is visibly wired only to the verifier), and either get rejected through the same opening, or accepted and moved to a secure temporary storage pont. There, the voter pulls one of three levers, which a) chooses a ballot portion to keep, b) seperates the portions, c) visibly changes the wiring from the verifier to the tabulator, d) visibly changes the ballot path so that it will go to the collection box, e) releases the chosen portion of the ballot, and f) runs the rollers in reverse to send the remaining portions back through the scanning head (now visibly wired only to the tabulator), and thence through the new path into the box.
The idea of pulling a lever is one that’s been around in voting machines for a while, so it probably won’t be too difficult to grasp. Now the only calibration risk is that the read head will go out of whack in a few seconds during a vote casting. This is still a real risk, but probably pretty low. There are also some mechanical parts that can go wrong, but we seem to manage making reliable copiers and printers with the ability to change and reverse feed paths, so this ought to be surmountable too.
If everyone gets to produce their own digital ballot slip, and knows that they can retrieve it along with everyone else’s slips anywhere on the planet, and knows that all digital ballots will at some point be semi-revealed to permit counting, then eveyone can count ALL the votes themselves. 300 million PCs, 300 million slips. At say 10K per slip that’s 3×10^12 bytes or 3,000 gigabytes. If enough people dedicate even 1 gigabyte of hard disk space to distributed vote storage, that’s massive redundancy.
It’s also very dangerous to permit the people to take control of the democratic process…
Perhaps I’m just a bit naive here and not seeing the whole picture, but, two thoughts:
1) What if the checker, upon determining a ballot to be valid, made permanent marks on the ballot to indicate what it interpreted the voter’s vote to be. If the voter believes the checker was wrong, they can discard the ballot and try again. Otherwise, the marks the checker makes are what the scanner reads to tabulate the votes, with the marks the voter made serving as a guide in case it’s necessary to go back and confirm that the checkers were operating properly.
2) As an extension on the idea above, why is it necessary for the voter to touch the ballot in the first place? Granted, this adds a step, and thus, a complication and a point of failure, but if a data-entry tool generates the ThreeBallot, which is securely passed to the checker (behind a glass window so the voter can see the process, but not interfere with it), and upon validation, the ThreeBallot is split up and deposited into the ballot box to be counted by the scanner, then there’s no chance of the voter doing something to the ballot that might cause a difference of opinions in the checker and scanner.