Microsoft Proposes Fix For E-Voting Attack 111
Trailrunner7 writes "Microsoft Research has proposed mitigation for a known potential attack against verifiable electronic voting machines that could help prevent insiders from being able to alter votes after the fact. The countermeasure to the 'trash attack' involves adding a cryptographic hash to the receipts that voters receive (PDF). Many verifiable voting systems already include hashes on the receipts, but that hash is typically made from the ballot data for each specific voter. The idea proposed by Microsoft Research involves using a running hash that would add a hash of the previous voter's receipt to each person's receipt, ideally preventing a privileged insider from using discarded receipts to alter votes. The trash attack that the mitigation is designed to address involves election workers or others who might be motivated to change votes gathering discarded receipts and then altering those votes."
Re:Microsoft Research (Score:4, Interesting)
They actually do a lot of great stuff there, which is not too surprising as they have many intelligent people working in Research. Just wish much more of their stuff would see daylight.
Can't say there's much of a market outside of Microsoft for a chair which will bounce.
This doesn't work (Score:5, Interesting)
I worked on an electronic voting system a few years back. What I did got accepted for use in a local academic department, and I even gave a WIP on it at a LISA conference once, and then I ran into the constraints of the real world when I tried to build it into something useful for a wider audience. They include the following:
1) You must not provide to a voter any form of receipt that can be used to determine how that voter voted. This is to prevent voter intimidation that has apparently turned into a major issue in places that did not abide by this constraint. If a hash can be used to verify that a vote was correct, it can be used to verify that a vote was what was required. I attempted to get around this by pre-seeding the vote results with a good number of copies of every possible result (which would cancel each other out), so you could take with you a vote receipt matching what you were required to do, but I couldn't come up with a way to make this idea scale, especially when any form of ranked voting was used.
Microsoft could get around this by giving only the hash, and not the vote record, with the receipt, but then you have no way to prove that your vote was recorded the way you input it -- the system could just as well record something else, and give you the hash matching that something else.
2) Even if you don't care about voter intimidation, and you give out receipts, not enough voters care enough to check that their votes were counted or registered correctly for crowdsourced verification to be all that useful. I remember an election irregularity report on one of the very few properly-done electronic voting systems -- backed by a printout under glass that could go either to the permanent record or the wastebin, and the UI directed the voter to carefully compare what was on the screen with the printout before accepting the vote. There was a malfunction at a station where the printer was completely nonfunctional. It wasn't even reported until an absurd amount of time after the poll opened (I can't remember the details, but many hours, and who knows how many voters). The Microsoft technique of using a running hash to prevent insertions, deletions, or alterations to a vote that is known will never be verified is nifty, but the odds are good that none of the votes in the last few hours of the day will ever be verified just because the verification count is so low, so you simply pick a spot and alter thereafter.
3) Even if a voter triggered an irregularity report by noting that the hash didn't match, there is no political will to invalidate an election. Almost no elections go by without irregularities. Some elections go through with absurd irregularities, things that obviously had the potential to change the result, or even things that definitely would have changed the result, and the result is let stand.
Discovery of the above three points made me give up on electronic voting as a solvable problem. The counted ballot has to be on a media not easily tamperable, and it must be independently verifiable by the interested parties, which, taken from a purely historical standpoint, do not appear to include the voters. Microsoft's bright idea (and I will give credit, it's not a bad thought when your only context is "how do I let a small sample detect tampering"), actually exacerbates problem #3 very badly by leading into #4:
4) Elections are expensive. You cannot build a system that lends itself to repeated invalidation. If you could ignore #1 through #3, a straight hash would still be of value, because you would only invalidate if enough people brought back signed hashes that did not match the published counted values, and a few forged receipts would not throw out all of the real resuls. Unfortunately, using a running hash over the course of the entire voting period means that the ability to tamper with a vote early in the day means you can invalidate *every vote that follows*, even if your technique was something that would only normally work on a single vote. This me