Thursday, June 25, 2009

Exporting Democracy II

Okay. So what we want to do is design a voting system, suitable for a large national election, that resists clandestine tampering by an attacker with serious resources (possibly the same people running the election), and at the same time is transparent enough that the voters have confidence in the system. Let's get started! :D

Crowdsourced verification

The core element of the system I'm proposing is a live printed display of cast votes. The votes would be displayed so that you could tell who the vote was for, and include a bit of other data such that the person who cast the ballot could see that it was theirs (a random number or picture shown to them after their ballot is cast would work), but should otherwise be completely anonymous. The votes are printed on the top half of a long roll of paper, which slides by after votes are printed on it. The top half of the paper is under glass, so that people can see it but not mess with it; the bottom half is available for people to write on. They would be allowed to write anything they want - a signature, a message, a random drawing, whatever. People would be encouraged to take pictures of the ballot roll at this stage, and take the pictures home with them. (In poorer countries, where people wouldn't have cameras necessarily, a few digital cameras and printers could be provided there.)

After the election, the vote totals would be counted by other means. The printed record, created solely for recounts and verification, would be made public - either by posting high resolution images of it online, in a country where the vast majority of citizens have internet access, or by posting copies in public places. We now have a very strong method of verification. No part of the ballot record could be modified after the election, because people could be holding photographs of any part of it, allowing people to easily prove electoral fraud. If the computer numbers are questioned, recounts are possible, because a full record of all votes cast is available. Even if the numbers aren't questioned, I fully expect suspicious people to recount some ballots in their own region anyway.

Furthermore, the system so far still preserves the secrecy of individual ballots, assuming closed voting booths. An attacker that wants to target people voting for a certain candidate could monitor the printed votes as they go by, but this is both obvious and imprecise, and can be countered by adding an unpredictable delay of a few minutes before the vote is actually printed. An attacker could also hide tiny cameras in all the voting booths. This is harder to counter, but can be mitigated by making the voting booths closed on all sides, and as spare as possible on the inside. Overall, though, this provides a very robust method of verification.

Voting Machines

With a strong verification system, you could really use any old voting machines for the electronic vote count. Even a Diebold or PES machine might be good enough. On the other hand, having just one layer of security is no fun - let's go ahead and make bulletproof voting machines too.

The TPM is usually understood to be a device to protect copyrights or some nonsense, by preventing tampering with some DRM scheme. This is largely because of a lack of imagination on all sides. There are several very general security problems in computing which a TPM can address. Malicious hardware added by an enemy is difficult to detect, but a TPM can remotely attest to the hardware in a machine. It's nigh-impossible to prevent people from running modified versions of software, so if somebody joins your network with a malicious version of your code, you either have to design a Byzantine fault-tolerant protocol (which is difficult and can be computationally expensive), or give up. A TPM can prevent unsigned software from running, on the other hand, and remotely attest to the software's validity. A TPM can also provide secure storage, through hardware-based encryption. Yes, all of these things can be used to restrict what you can do with a computer, but that's kind of the point.

Let's look at what this gives you in a voting machine.

Initially, you have a set of private keys, which are kept separate from each other and secured individually. Every device used in an election would have its built-in public key signed by all these keys, and hold those signatures. When the machines are networked together for an election, any device can recognize and verify any other device, by requesting its public key and the signatures, along with a remote attestation. (Devices aren't just restricted to the voting machines themselves - you also need to authenticate the printers, for example, or an attacker could use modified ones that print whatever.) In this way you can verify that every device used in an election isn't tampered with in various ways.

Each vote would be recorded, along with the machine it's taken on and the time of day, in a secure encrypted file, and distributed to all the other machines in the polling place. Recording extra data allows for data analysis if the result of the election is called into question (this machine only recorded votes for this candidate? this machine was active during times when the polling place should have been closed? HMM); distributing the results to other machines provides insurance in case of hardware failure. A gossip protocol could be used here, so that putting two machines on the same network would automatically have them exchange votes. This could be applied over a network to automatically send votes to a central location, or if there's no network connectivity, the votes could be sent on a burned CD, or a flash drive, or whatever. Having the votes signed by the individual machines means that transmission over an untrusted medium isn't a problem, as long as they're signed in aggregate and not individually. (Would it be problematic to have every machine store potentially every vote for the whole election? Assume 32 bits for a timestamp, 32 bits for a unique machine ID, and 32 bits for the vote itself - twelve bytes to record a vote. A few hundred million votes would fit comfortably on a large flash drive, even if you add in cryptographic signatures of the votes from each machine.)

Gossip protocols are neat. Let's designate one machine as the master machine; it will collect the final tally. (I say one, but there's no reason it can't be a set of machines, for fault tolerance.) Once it receives all the votes from a given machine through the gossip protocol, it can send back a notification through the same gossip protocol saying "the master machine has received all these votes from X". When X receives that message, it knows that all the votes recorded on it are included in the final tally, and can turn on a light or something to let poll workers know. (I'm assuming, obviously, that all messages are signed and encrypted; it would be extremely silly for them not to be.)


I think this system is pretty good, but no system is perfect. Even though we have two parallel counts going on which support each other - the documented paper count, and the signed electronic count - I'll count something as a vulnerability even if it could only affect either of these in isolation. After all, sticking vulnerabilities together is easy.

This sort of system is only really useful in places that actually profess to be democratic - if some despot insists on staging an election, but still wants to fake the results, all this system will do is prove what everybody already knows. It'd be nice to put together a system that generates accurate vote totals in the face of open electoral fraud, but I'm far from convinced that that's even possible. Again, if the attacker is sufficiently motivated and doesn't care about appearing democratic, they could just post armed guards inside every voting booth.

Letting people write on the running sheet of votes is important, since it makes the whole sheet significantly harder to later reprint and fake, but it also introduces a vulnerability: vandals could simply destroy the printout, in which case we'd be dependent on the electronic tally. More generally, if somebody wants to wreck the polling place, a strategically-placed bomb could halt voting in a given location. This issue is better addressed by law enforcement.

The electronic security of this system depends on how much you trust your hardware manufacturer, especially the people making the TPM chips. This can be mitigated by purchasing from different manufacturers, making sure that the distribution of hardware between machines is random, and then analyzing the final results for correlations between hardware components and voting patterns. This type of analysis is well-understood in data mining.

It's possible to correlate tapes from security cameras near or inside the polling place with the public vote record, and get a pretty good (but inexact) idea of who voted for whom. Um, this one is tricky. No idea how to mitigate this, if we want to maintain a public aggregate ballot.


Kiriska said...

Hm. I find the idea of a printout incredibly cumbersome, especially if some poor bastards need to scan that roll at the end of the day. It seems like a lot of supplies (paper, printer, cameras, etc) and physical labor (guards to prevent vandalism, theft or destruction) and trouble to go through for the sake of having a backup plan, though I can see why the backup plan in itself would be a good thing to have.

The personalization (so to speak) of the printed record also doesn't necessarily guarantee that people will go back and verify it online or wherever -- that takes effort and in the States, at least, people are lazy as hell. It was hard enough making it to the polling station, come on. Having a printed record also wouldn't prevent sabotagers from inserting new pieces, would it? Each voter might know their portion of the printed sheet, but it would be impossible for anyone to say, "Hey, that part wasn't there!"

I do like the assigning of random numbers to voters to have them verify their votes online later though.

P. Static said...

It may seem like a lot of effort, but I don't think it's that much compared to current punchcard systems. It'd be nice if we could get a measure of transparency without requiring people to do anything more than go and cast their ballot and then leave, like they do now, but I'm not sure that's possible. The current voting process is basically a black box, and we have to make some changes to it if we want to change that.

In general, sure, very few people will actually go online or whatever to check the printed record. If there's any reason at all to suspect the result, though, I think a lot of people will. Also, with good enough photo coverage it's impossible to add ballots, since people don't photograph just their own printed votes. There might be some spots that aren't covered, and ballots could be added there, but an attacker doesn't know where they are. So, even if we don't have full coverage, there's no way to alter the record and be confident that it won't be discovered.

I only intended the random numbers to be used to verify the votes in the record right after you vote, not after the fact online. XD If you have to keep the numbers globally unique, then they have to be a lot longer, and harder to remember. Plus, there should be no way to prove to others that you voted a certain way.

Frank Church said...

I should comment on your blog again! Sorry I haven't recently. Anyway, I like your voting system, though I can't help but spare a bit of sympathy for the poor trees that would die for it.

Of course, just because you've designed a good voting system doesn't mean that anyone will ever use it. :( The countries that need reliable voting systems the most (Iran!) are the least likely to use them. Unless under force, but...who supplies the force? The UN, I suppose, but the UN has plenty of countries that have funny elections. They wouldn't want to set a precedent.

Might as well mention another problem with voting: the location of voting booths. That's not what you're concerned with, but that's probably the other great problem with elections (at least in the US). Also make sure to have enough paper in the voting booth. Oh yeah, and voter registration too. That's the third great problem.

P. Static said...

You shouldn't assume that only countries with dubious records when it comes to democracy could benefit from this. Just look at the US, for example - how much confidence do you *really* have in the results of the last election? There are well-documented flaws with our voting machines which could easily lead to electoral fraud, but somehow we've convinced ourselves that that can't really happen. I, for one, don't think our democratic process should be something that we just have blind faith in.