Schneier on Security
A blog covering security and security technology.
« Code Talking for the Dumb |
| "Safe Bedside Table" »
August 21, 2007
Another E-Voting Problem: Not-Secret Ballots
Ohio law permits anyone to walk into a county election office and obtain two crucial documents: a list of voters in the order they voted, and a time-stamped list of the actual votes. "We simply take the two pieces of paper together, merge them, and then we have which voter voted and in which way," said James Moyer, a longtime privacy activist and poll worker who lives in Columbus, Ohio.
EDITED TO ADD (9/13): Commentary by Ed Felton.
Posted on August 21, 2007 at 7:01 AM
• 56 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
How about we simply prohibit this data correlation by law? I heard that's supposed to work. Really.
Privacy, security, transparentness; pick two.
That's fine if you are willing to assume that no one is willing to break the law to get a list of voters and how they voted... I wouldn't make that assumption.
What's the exposure of scrambling the order in which voters voted? That should be enough to solve the problem at hand
"Privacy, security, transparentness; pick two."
This is not as E-Voting problem, it is a poor system design.
Brazilian e-vote system changes the order of its log entries to avoid the disclose of the vote. I think this is a obvious security feature for any e-vote machine.
has more on this story. It turns out that not just the ES&S e-voting system, but the three that were tested in California all have this same flaw because it is possible via date stamps or other methods to order the votes by time. It's not just an Ohio problem either; other states have similar systems.
Most depressing part of the story: the e-voting companies are just shrugging this off as no big deal ...
Woo is being sarcastic.
@syberghost, good point.
There's a fundamental conflict between privacy/anonymity and security/accountability in voting.
Think about it, if there's no way to connect each vote cast with the voter who cast it, how can it possibly be proved that the final totals counted accurately portray the collective will of the voters who cast ballots?
The only way is to create checks and balances and secure protocols around the handling and counting of the votes.
That's hard enough with paper ballots, and it just gets worse with electronic voting because there are no intrinsic physical artifacts produced.
While it's clearly a problem, I don't think it's quite as serious as the researchers seem to be claiming. Some people dither over a ballot, while others will be in and out in seconds. If there's only one voter every few minutes, then it'll be obvious who they voted for; if there's one every few seconds (which is more likely; a quick calculation with VERY rough numbers* suggests that the average would be perhaps 25-30 people a minute, if these are figures from the county as a whole?), then while they might be able to have a decent guess, they'd be a long way from certainty.
* Assuming polls open for 12 hours a day, average county population 50,000, of whom 20,000 vote, and a equal distribution across the entire day, which is obviously not the case in reality. I'm a Brit, and don't know so much about American electoral behaviour or law.
Extra reliability can be built into this attack by sending known parties in at set times and having them vote for a particular, unusual candidate.
That way, you get something like:
Bush, Gore, Gore, Bush, Schneier, Bush, Gore, Bush, Gore, Schneier...
which you can match up with the other log:
(four regular people), shill, (four more regular people), shill
There's a name for this in computer science, but i don't feel like looking it up right now.
Why worry about seeding or randomization?
Why not just use the machine to print the paper ballot and keep a running total?
Why keep logs at the machine?
For all of those who believe that privacy, security and transparency are mutually exclusive, consider the following design.
Each voter picks a one-time password at the time that they vote.
We publish a list of (hash(password), vote) pairs.
Anyone can count the "vote" parts to determine that votes were correctly counted.
Each voter can determine that their vote is present and correctly recorded by calculating hash(password).
With current mechanisms used to prevent double-voting, I hope this example illustrates that it might be possible to achieve all three aims; even if it might be flawed itself.
Basic flaw with your analysis:
While the total number of people who vote within a county may be 20,000, you won't have all 20,000 people using the same machine, or voting at the same venue. The paper trail is "per voting machine".
It's also possible that someone could figure out which machines were placed in which parts of the voting venue. Take this with the placement of the ballot lists (especially if they're grouped by name - say A-F, G-M, N-S, T-Z), and you may be able to hazard a guess which group of voting machines was used by which alphabetic groups of names.
I too am guessing (I'm from Australia), but I'm pretty sure they all don't use the same voting machine. :D
You make a good point. I was a polling place volunteer during the US mid-term elections last year (giving instructions to voters on how to use the voting machines). I would guess that the mean "time at voting machine" was around 2-3 minutes, but that the range was from 1 minute to 8 minutes. At this polling place, we had 4 machines working simultaneously. In aggregate, with maybe 50 machines across a county, it would be near-impossible to exactly match voter to vote with these two lists. The process did not record which voter voted at which machine.
I'm sure the voting machine manufacturer's love this: "What do you mean we don't offer voter verified paper trails (not that we need them)?"
@Toby: "publish a list of (hash(password), vote)"
This way, you could prove to an external party that you voted in a certain way by giving them the password.
==> Vote buying...
Maybe, do not hash the password and publish (password, vote) instead. This way, you cannot prove to someone that a certain vote is yours.
In my district in Brooklyn NY, there were several registration books divided by last names. But there was only a single voting machine for our district. So four people coming in at the same time could each register at the same time, but depending on how long they spent there, they could hit the voting machine in a different order.
If there's a lot of people, you might get some correlation between registration and voting, but it's not going to be perfect by any means.
It's clearly impossible to simultaneously have verifiable accurate vote counting and anonymous voting. Consider, for example, the case of a single voter.
Honestly, I think voter anonymity is overvalued anyway, and, for example, the hash(password) approach above has some merit.
Hmmm.... doesn't the fact that a paper trail printed on a continuous roll preserve the voting order and cause the same problem?
This could be solved by cutting the paper and letting it fall into a ballot box semi-randomly, but the machine I voted on last time didn't do this.
> maybe publish (password, vote)
Doesn't help. Whoever you sell your vote to tells you which password to use. If you don't use it with the right candidate, you don't get paid (or do get beaten up, investigated for anti-Party activity, or whatever).
There are schemes with better properties (where "Consider, for example, the case of a single voter" gives you a single voter who can check his vote was correctly counted, but can't prove that he was that one voter to anyone else from published information), but they aren't simple enough to be transparent to non-technical voters. See Bruce's books for more....
> > maybe publish (password, vote)
> Doesn't help. (...)
OK, did not think far enough (yet ;-))...
I personally like the 3 vote system suggested by Rivest. Its not perfect, see (Google: 3 vote system rivest) for more details.
But it seems we should strive for all 3, that is privacy, security and transparency. It should be possible.
It has been said that the 3 vote system is perhaps to complex. Well if that is to complex, what are we suggesting about the voters, in which case why do we need any of the above assurances. Since we have for all reasonable purposes defined the voters to be incapable of making any kind of reasonable choice and the weak link will "lie" elsewhere.
How about everybody put a mark on a piece of paper, and then in a public place stick it in a jar. The jar would be watched by members of all interested political parties and some private citizens drawn by lot. At the end of the day, a similar group would open the jar and subgroups (say 3 at a time) could count the ballots then add them up and publicly announce the final figure.
Secure, anonymous and transparent (transparency of the jar itself is optional). The technology may be too expensive for immediate roll-out, but we could try something less 22nd century, like shards of pottery as a low-cost transition to paper.
Why do we go over this every time?
This has already been solved for paper ballots. So use paper ballots. If you need a machine, then the machine does nothing more than tally the votes cast at it and print the paper ballots.
Don't over-think the problem. The more complex your "solution" the more likely it is that you've introduced a new weakness.
How about we get a big book of paper and number each page. We pluck of a page and give it to each voter. We sort the paper by number, avoiding duplicates, and count up the votes when the voting ends.
What's the beef with 'puters? I heard they can be broken into 'n stuff. And Kevin Mitnick could probably do a special whistle at the computer and make Bush win again, or something.
I'd suggest using a system like Punchscan ( http://punchscan.org/ ) or ThreeBallot (though Threeballot does have a known security flaw, it's still light-years ahead of anything Diebold or ES&S has produced. See http://people.csail.mit.edu/rivest/... )
The problem is that I don't think our politicians and election officials are selecting voting systems based on their security, transparency and verifiability. They choose these systems for their obfuscatability, vulnerability to undetectable attacks and ability to impress the ignorant with touch screens and blinkenlights.
Who, me? Cynical?
Once again, why? Why pushcan? Why anything other than a random jury out of the local voting pool and reps from any party that wants to be there?
Is everyone supposed to be corrupted? Or is it that we fantasize that it's impossible to have clean transparent elections, so we make up impossible, complex systems to guarantee that transparency and fairness are impossible, like some kind of schizophrenics?
Damn it. It's easy. It gets done in third world countries. Paper, Eyes and Eductaion. It gets done quickly. The only way to cheat is to completely corrupt the entire local government, in which case no technological innovation could possible overcome that - only folks fighting back can handle those cases.
It's like trying to find a technological solution or magical "method" to child raising. The only reason to even bring it up is as an avoidance tactic of actually doing the hard work.
Punchscan and ThreeBallot attack the problem of proving to an individual voter that their vote counted.
But these systems aren't designed to allow a third party to decide whether or not the election was conducted fairly.
Historically, where certain communities have been disenfranchised, all the local people know that it ain't fair. Indeed, some of the rawer forms of voter intimidation just won't work unless the affected community knows what's going on. The hard part is getting a newspaper in some far away city to tell their readers that it's time to start marching.
"This is not as E-Voting problem, it is a poor system design."
Except that it is very hard to do this with a voting system which uses physical ballot papers. But rather trivial to add (including by malware) to any "E-Voting" system.
"if there's no way to connect each vote cast with the voter who cast it, how can it possibly be proved that the final totals counted accurately portray the collective will of the voters who cast ballots?"
Well, we manage it alright in Canada. It works because we use paper ballots, see...
Each voter signs in, receives a ballot with a serial number on a tear-off strip (name and number are noted), fills it in privately, folds it over, and brings it back to the poll workers. The tear-off strip goes in one box, the now-anonymized ballot goes in another.
At the end of the day, every strip in the one box can be tied to a voter who signed in, and the number of ballots must exactly match the number of strips.
You can spoil your ballot by deliberately filling it out wrong, or you can decline your ballot, but destroying a ballot once you've received it, so the two pieces can't go into the two boxes is a crime.
Am I missing something? 1) there is more than one machine in each voting area, which means it is impossible to do better than a 1 in (number of machines) correlation, probably worse. 2) VVPT means that we don't need to match up people and votes, on the number of people and the number of votes. 3) If necessary, we could build a level of annonymity into the system by having the voters given random numbers on the 'list of voters', or by randomizing the list... Of course, if a vote is subsequently found to be invalid, there would be no way to remove it from the system, which is just fine by me...
I like the Canadian system (if it's still in use): 1. Voters mark paper ballots. 2. Each party counts the votes. If the counts don't agree, everyone counts again until they agree. (I assume there is some miniscule margin of error that is acceptable, though.)
@DBH - actually, it's impossible to do _worse_ than one in N, where N is the number of machines.
assuming the machines' clocks are in sync, you can easily turn the ballots from each machine into a time-sorted list of ballots.
Where ballots from all N different machines are very close in time, you will have N different possibilities for each of N voters. That's the worst case.
In the best case, the timestamps will be distant enough that you can reliably place one voter at one machine.
But that's plenty good enough for voter coercion. If I tell my employees that they'd better vote for my candidate or else start looking for another job, I can make good on my threats and they know it. The only way one of my workers can vote how they want with secrecy is if they know for sure that they are casting their vote within a couple of seconds of someone else at another machine who is going to vote for the boss's candidate.
The risk is probably too great for them to take - what if the old codger is a secret ?
Sorry - meant to say - what if the old codger is a secret KKK man, not the stolid Republican he makes himself out to be
What safeguards are there so ballots don't vanish or get added during step 2?
I have an idea! Lets poke preperfed holes out of cardboard with stylii under supervision of humans and then count them with a cardreader! Waaayy less possibilty for fraud (not "no" possibilities for fraud; just a small subset of whats available with evoting). Better for the environment too, no greenhouse gases caused by generating electricity for the machines.
As I described earlier - each ballot has a tear-off strip with a serial number. The serial number gets recorded along with the voter who receives the ballot. When the votes are placed, the strip with the serial number is torn off and put in one box, and the completed ballot in another.
By the end of the day, you can map from each serial number to a voter, but only from the total number of votes cast to the total number of voters.
Can we talk Ohio into seceding from the Union?
Punchscan was designed from the beginning to be audited, and in fact has a cryptographic protocol designed to enable both pre-election and post-election audits and cryptographically prove election integrity, while still preserving things like the secret ballot.
The genius of Punchscan is that while it does have some complex cryptography, it loads it all on the back end, so only the election authority and auditors need to know about it. The voters just need to fill out a variation of an optical scan ballot, then they can take half the ballot home (which isn't enough to prove who they voted for,) and they can go on the election web site and verify their vote was recorded correctly.
"As I described earlier - each ballot has a tear-off strip with a serial number."
I believe they were asking what's to stop someone from invalidating all the votes at that location by adding fake ballots WITHOUT including the opposite piece.
Either too many ballots or too many tear-off strips.
And the answer to that is ... the other parties' people.
Anyone who wants to can sit down and watch the process. And each party with a stake in the election SHOULD have at least one person watching each ballot box at any given moment.
Send two so they can alternate bathroom breaks.
The question should NOT be "how to secure the votes." That's easy.
The question should be "how do reduce the voter fraud to an insignificant level". How do I know that the guy who's voting here hasn't voted at 20 other locations already today?
And by "insignificant" I mean "below the level that it would change the outcome of the election".
1. All electrically operated voting machines are not Tempest certified. IE, anybody with a computer rigged to listen will know how you voted.
So votes are secret from you (and elections are fixed) but public to the government (so they know who to punish).
2. Our government is restrained by the fact that we have large numbers of armed citizens in close proximity to the munitions factories that supply ammunition and spare parts to the US military.
Meldroc at August 21, 2007 03:49 PM
'does have some complex cryptography,"
Haven't read about this system. How do we know that it hasn't been compromised itself?
[Disclosure: I'm for HCPB]
wkwillis at August 21, 2007 04:59 PM
“...electrically operated voting machines are not Tempest certified. IE, anybody with a computer rigged to listen will know how you voted.��?
And as far as I know, no Federal standard has ever mentioned this...
A Dutch vote integrity team has publically demonstrated a TEMPEST attack, tuning in on voters using a NEDAP DRE design which handles Dutch elections - and shows it on YouTube...
BTW, it appears that these machines are related to Liberty systems used in Ireland and some US jurisdictions.
For voting precincts without heavy voter turnout, it would after some elections be possible to connect most or all voters to their respective votes; even for precincts with heavy turnouts, some voter-to-vote connecting might be possible for slow periods of the voting day. Even if there were to be some overlapping voting sessions, which is likely, with some resulting uncertainty as to how specific voters voted, a party with an interest in an election's outcome might act based upon strong suspicion. Retribution based upon suspicion can be as bad as retribution based upon proven fact.
The possibility that a voter's vote might be discovered might make some voters more vulnerable to vote buying or to being intimidated to vote a certain way.
There should be no possibility that voter names on a voting order list can be be connected with votes by comparing times. Making the voter order list inaccessible to the public would not be good enough. A voting order list is unnecessary. Voter sign-in cards can be filed alphabetically or by voter registration number.
As has been pointed out, sound paper voting systems maintain secret voting successfully.
"Each voter picks a one-time password at the time that they vote."
You just excluded the 95% of voters who will read that sentence and say "a what-time what?". Not to mention the fact that most of the rest will pick from the same 20 passwords.
And for those of you saying "it works in Canada because we use paper ballots"; we have states with about as many people as your entire country, and you've got massive election fraud problems in your country that are the same things we're trying to address by going to electronic ballots.
The fact we aren't doing a very good job of it doesn't mean paper is the right solution. Every time a human being touches votes, you have the potential for fraud and errors, and you have to put checks in place. Electronic voting, done correctly, gives you fewer places you need to put checks (because humans touch the process less) and makes the errors if not necessarily less frequent, at least less personal. Silicon chips don't have subconscious biases, waning attention spans, or addictions to caffeiene and/or nicotine.
What's the purpose of keeping a "a list of voters in the order they voted"? What possible purpose could there be to keeping the order, except to make the votes public at some point? It sounds to me like the people of Ohio want their voting rigged, e-voting or not.
Please explain your comment "you've got massive election fraud problems in your country". I hadn't noticed them, what are they?
Bruce didn't mention it but this is a simple and clear example of a point he's made before.
Put two security protocols together, and you don't get double the security. You can even introduce problems. In this case the record of who's voted, a security measure to prevent duplicate votes, combines with the voter-verified paper trail to destroy ballot secrecy, another key security property.
Please explain your comment "you've got massive election fraud problems in your country". I hadn't noticed them, what are they?
A quick google turns up some shenanigans in Edmonton Centre with people registering at offices, non-existent addresses, etc. plus some official ballots being used in classroom exercises. The second one needs a firm source, but the first evidently spawned some legislation:
Hardly 'widespread' like about a million disenfranchised from Ohio, Florida, New Mexico, etc.
I don't get it. We have a well-known problem with a well-known, tested, solution (paper ballots, manual counting), used in most countries (not just Canada), that works.
Introducing a computer into this process accomplishes nothing and introduces a lot of complexity, and therefore the possibility (some would say certainty) of security holes.
Computerized voting is pretty much "broken" from the start. Why do so many people want to replace a good solution with a broken non-solution?
(Apart from companies that make voting computers, politicians who want to rig ballots, etc?)
"Computerized voting is pretty much "broken" from the start. Why do so many people want to replace a good solution with a broken non-solution?"
Read through the comments here.
When all you have is a hammer, everything looks like a nail.
Computers and computer networks have a very important place in the voting process. But it is NOT in the voting booth. We should be using them to validate the person voting.
Instead, we see the fans of computers arguing about how to "secure" them "cryptographically" so that they can be used as the voting device. And because (as you noted) the fundamental system is flawed, they keep piling "security" processes on top of each other. Hoping that, eventually, the system will be "safe".
Paper ballots are the best.
Humans counting paper ballots is the best.
Humans watching other humans to make sure they are correctly counting the ballots is the best.
@Brandioch There are many more controls in Canadian Elections that dragonfrog did not mention.
The voter gets their ballot from the poll workers (Deputy Return Officer and Poll Clerk). It's folded several times and initialled on the backside/outside. The voter votes behind a screen and returns the ballot folded with the initials showing and votes not showing. The DRO/PC inspect the ballot (initial) and deposit the ballot while the voter watches. Only initialled ballots go into the box. Any ballots in the box that aren't initialled indicate a problem/breach of protocol. The boxes are sealed and the seals initialled. Seals are changed at certain key steps.
There is a procedure for a voter to exchange and void a spolied ballot.
At the end of the day, the poll is closed and the DRO&PC open the box and do the count. Official observers are allowed but must sit back and cannot touch. I recall that observers sign somewhere as witnesses.
The balance tracks the number of ballots issued to the poll, the number remaining, cast, spolied, declined, and per candidate totals. Everything (cast ballets, stubbs, unused ballots, voter turnout log, etc.) gets separately bagged, labelled, boxed, sealed, and initialled. The balance is cross-tallied to detect errors. The balance/tally info is dual signed and stays out.
The Returning Officer's (an RO is in charge of a Riding = 1 candidate) staff collects boxes and balances from DRO/PC. They insure seals are ok. They check balances and can quickly detect problems in balance and can track errors for recount if needed.
When I worked for an RO, we knew the totals and had a very good idea exactly what the totals and the margin of error were. We could often detect when the printer had misbound a book of votes.
If I recall correctly there is an official count with the RO & Riding Clerk undertaken starting the next day.
- Extra or too few ballots will be detected.
- Walk offs (with ballot) get detected.
- Subsitute ballots will be detected unless there is collusion. Even then unused ballots are tracked.
- Count errors will be detected.
- Attempts to vote twice or as someone else will be detected.
- Votes remain private.
- Opportunities for election fraud are reduced.
- Counts are verified.
- It's highly auditable.
- All election materials are retained by the Chief Election Officer for a period mandated by law.
Frankly, IMO e-voting can't match this system. Not even close. Could it? Maybe, but a great deal of work is needed. And a great deal more transparency.
BTW. A typicall urban Riding will have about 200-300 polls of under 400 voters each. Polling stations are typically in groups with an experienced DRO. The RO is neutral and can only vote in a tie.
If you want this to ever be done right you are going to have to form a PAC, and wade hip deep into this. Rivest voting protocol proposal goes a long way toward solving many of these problems American politicians seem intent on rediscovering, every several months.
Seriously how do I give you money to build this PAC.
There is no Constitutional protection for the privacy of ballots -- that's rather a 20th century idea. In the old days, people used to be given ballots by their employers, or by other interest groups, pre-printed on colored paper. Candidate A had yellow paper, Candidate B had green paper -- paid poll watchers could tell for whom one voted simply by noting the color of the paper put into the box.
As a pragmatic matter, who would use the voting information? Most often it would be Karl Rove wannabes, who would try to predict who would vote for their candidate, and then make sure those people got to the polls. That's ward heeler, retail politics, isn't it? It's no great threat to privacy.
A greater threat (here we go weighing comparative risks) is the danger of computers screwing up vote totals. The totals are more important chunks of information, for almost everyone concerned. Let's get those accurate first.
there is nothing new here.
where i live in new jersey, voters sign a by-district register for each election, and then sign a numbered slip of paper. we then must use a specific voting machine for the district, IN SEQUENCE. this is verified by a poll attendant, who captures the numbered slips - in sequence.
ANY sequential log of votes kept by the machine, with or without time stamps, when correlated with the slips of paper, provides a perfect record of votes.
we are led to believe that mechanical voting machines are safe from vote tracking because they supposedly do not ahve any kind of vote-sequence recording capabilities, and merely can total votes. i've never been able to look; who among us has?
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.