Voting: August 2010 Archives

The second major attack described by Prasad et al. is a clip-on memory manipulator. The device in question is a small microcrontroller attached to a clip-on connector. You open the control unit, clip the device onto the memory storage chip, rewrite the votes, and disconnect it. There are a number of countermeasures we could consider here.

Physical Countermeasures
We've already discussed seals, but one obvious countermeasure is to encase the entire memory chip in plastic/epoxy. This would make it dramatically harder to access the memory chip. One concern I have about this is heat: were these chips designed to operate without any cooling. That seems like a question that could be experimentally answered. I think you'd want to use transparent epoxy here, to prevent an attacker from drilling in, access the memory chip, and covering it over, maybe with a small piece of plastic to permit future access. I also had an anonymous correspondent suggest encasing the entire unit in epoxy, but at most this would be the circuit board, since the device has buttons and the like; this would of course make the heat problem worse.

Cryptographic Countermeasures
Another possibility would be to extend the cryptographic checksum technique I suggested to deal with the dishonest display. At the end of the election when the totals are recorded the CPU writes a MAC into the memory over all the votes (however recorded) as well as writing a MAC over the totals. It then erases the per-election key from memory (by overwriting it with zeros). This makes post-election rewriting attacks much harder—the attacker would need to also know the per-election key (which requires either insider information or access to the machine between setup and the election) and the per-machine key, which requires extensive physical access. I think it's plausible to argue that the machine can be secured at least during the election and potentially before it. Note that this system could be made much more secure by having a dedicated memory built into the CPU for storage of the per-unit key, but that would involve a lot more reengineering than I'm suggesting here.

In their paper on Indian EVMs, Prasad et al. demonstrate that you can easily pry off the LED segment display module and replace it with a malicious display. At a high level, it's important to realize that no computer system can be made secure if the attacker is able to replace arbitrary components, since in the limit he can just swap everything out with lookalike components.

The two basic defenses here to use anti-counterfeiting techniques and to use cryptography with hardware security modules. Most of the proposals for fixing this problem (and the memory overwriting problem) are of the anti-counterfeiting variety; you seal everything up with tamper-evident seals and make it very hard to get/make the seals. Then any attacker who wants to swap components needs to break the seals, which is in theory obvious. Unfortunately, it's very hard to make seals that resist a dedicated attacker. In addition, sealing requires good seal procedures in terms of placing them and checking them with this many machines in the field it's going to be quite hard to actually do that in a substantially better way than we are doing now.

The other main defense is to use cryptography. The idea is that you embed all your sensitive stuff in a hardware security module (one per device). That module has an embedded cryptographic key and is designed so that if anyone tampers with the module it erases the key. When you want to make sure that a device is legitimate, you challenge the module to prove it knows the key. That way, even if an attacker creates a lookalike module, it can't generate the appropriate proof and so the substitution doesn't work. Obviously, this means that anything you need to trust needs to be cryptographically verified (i.e., signed) as well. Periodically one does see the suggestion of rearchitecting DRE-style voting machines to be HSM-based, but this seems like a pretty big change for India, both in terms of hardware and in terms of procedures for managing the keying material, verifying the signatures, etc.

However, there is an intermediate approach which would make a Prasad-style attack substantially harder without anywhere near as much effort. The idea is that each machine would be programmed by the Election Commission of India with a unique cryptographic key. This could be done at the same time as it was programmed for the election to minimize logistical hassle. Then at the same time that the vote totals are read out, the machine also reads out a MAC (checksum) of the results computed using that key. That MAC is reported along with the totals and if it doesn't verify, that machine is investigated. Even though the malicious display can show anything the attacker wants, the attacker cannot compute the MAC and therefore can't generate a valid report of vote totals. The MAC can be quite short, even 4 decimal digits reduces the chance of successful attack on a machine to 1/10000.

This approach is significantly less secure than a real HSM, since an attacker who recovers the key for a given machine can program a display for that machine. But it means that the window of opportunity for that attack is much shorter; if the key is reprogrammed for each election then you need to remount the attack between programming time and election time, instead of attacking the machine once and leaving the display in place indefinitely. It's also worth asking if we could make it harder to recover the key; if it's just in the machine memory, then it's not going to be hard to read out using the same technique that Prasad et al. demonstrate for rewriting vote totals. However, you could make the key harder to read by, for instance, having two keys, one of which is burned into the machine at manufacture time in the unreadable (hard to read) firmware which is already a part of each machine and another which is reprogrammed at each election. The MAC would be computed using both keys. This would require the attacker to attack both the firmware on the machine (once) and the main memory (before each election).

Clearly, this isn't an ideal solution but as I said at the beginning of this series, the idea is to improve things without doing too much violence to the existing design. Other approaches welcome.

As I mentioned earlier, Prasad et al.'s research clearly demonstrates that there are attacks on the election machines used in India. On the other hand, during the panel at EVT/WOTE the Indian election officials argued that there were serious fraud problems (especially ballot box stuffing) with the paper ballot-based system they used before the introduction of the EVMs, so there's going to be a huge amount of resistance to just going back to paper ballots. Without taking a position on paper versus machines, it's worth asking whether it's possible to build a better version of the existing EVMs (bearing in mind that there are something like a million of these machines out there, so change isn't going to be easy.)

Prasad et al. have three major complaints about the EVMs:

• It's possible to replace the display, causing it to show any vote totals the attacker chooses.
• It's possible to rewrite the memory chip that stores the vote totals.
• The firmware on the devices is secret and the the devices are designed so that the firmware cannot be read off. This makes it difficult to determine whether the devices have malware (either installed at manufacture time or later.)

These are obviously real problems, though how serious they are of course depends on whatever procedural controls are used with the machines. Obviously, it would be better to have a machine without those problems. In DC I asked the panel to assume that they were stuck with something like the existing DREs (this isn't hard for Indiresan and Shukla, of course) and consider how they would improve them. I didn't get much of an answer, but I still think it's worth considering.

Over the next few days, I'll be talking a bit about how to address some of these issues.

I've held off on writing much about EVT/WOTE because I've been waiting for the A/V recordings to be posted. Most of them are up now, including an unfortunately partial recording of the most dramatic part of the conference, the panel on Indian EVMs. (There's some other good stuff like the rump session that's not up or only partially up.)

As background, Indian elections are conducted on a relatively simple hardware-based DRE machine, I.e., a small handset with buttons for each candidate; votes are recorded in memory and then totals read out on a control module. Hari Prasad, Alex Halderman, Rop Gonggrijp, Scott Wolchock, Eric Wustrow, Arun Kankipati, Sal Sakhamuri, and Vasavya Yagati got ahold of one of the machines and managed to demonstrate some attacks on it (see their analysis here). This naturally provoked a lot of controversy, and we decided this made a good topic for a panel. The panelists were:

• P.V. Indiresan, Former Director, IIT-Madras
• G.V.L Narasimha Rao, Citizens for Verifiability, Transparency, and Accountability in Elections, VeTA
• Alok Shukla, Election Commission of India
• J. Alex Halderman, University of Michigan

Unsurprisingly, the panel was extremely contentious, with Joseph Lorenzo Hall doing a great job of keeping the various strong personalities to the agreed upon format. It's definitely worth watching for yourself: we have complete audio and video for the last hour or so.

You may have heard that Hari Prasad has been arrested. This has obviously raised some very strong feelings, but I don't think it really bears one way or another on the arguments about whether EVMs are a good choice or not. The issues here aren't really that technical; the attacks reported by Prasad at all are straightforward, as are the attacks that the representatives of the Election Commission of India report were common on paper ballot systems before the introduction of EVMs. It's definitely worth watching/listening to this panel and making your own assessment.

I spent the first half of this week at at the 2010 Electronic Voting Technology/Workshop on Trustworthy Elections (EVT/WOTE) workshop. I only had one paper this time, a collaboration with Kai Wang, Hovav Shacham, and Serge Belongie called OpenScan. The basic idea behind OpenScan is really simple: in conventional optical scan systems the ballots are read by a single scanner operated by the election officials and there's no direct way for a third party to verify that the scanner is reading the ballots accurately. For all you know, the scanner (which after all is a computer) has been totally reprogrammed by some attacker.

There have been two major lines of development designed to provide some third-party verifiability for opscan systems. The first is a hand-counted audit, in which you randomly draw a sample of ballots, hand count them, and use statistical techniques to determine whether the results provide convincing evidence that the original count was correct. Audits require considerable statistical sophistication and have some other logistical drawbacks, so uptake has been a bit slow. The second approach, exemplified by the Humboldt Election Transparency Project, involved rescanning all the ballots and publishing images so that anyone can verify the count themselves. The problem with ETP-style approaches is that it's not practical to have everyone scan independently, so you're still at the mercy of the scanner. In principle, you now have two independent scans but of course the people who are allowed to do their own scan necessarily have a special relationship with election officials, so this doesn't create as high a level of assurance as you might like. (You can find my discussion of this issue here).

OpenScan takes the ETP to its logical conclusion by allowing an arbitrary number of independent scans. The basic idea is that instead of using a scanner, you have a mechanical paper transport and then use video cameras to record the ballots as they go by. You can then use computer vision techniques to isolate the individual frames corresponding to each ballot, rectify them so they're square, and then merge them into a singel image suitable for processing with standard optical scan processing software. Because the system works even when the camera doesn't have a head-on view, you can support multiple cameras, which means that a large number of independent observers can bring their own cameras, thus verifying the election without needing to trust the scanner (aside from that it will feed the ballots correctly). The nice thing about this design is that in principle you can build your own ballot processing framework completely independently out of commodity components (though this is a lot of work), so you don't really need to trust anything but that your generic camera and generic PC are behaving correctly. This means that election officials can allow third-party verifiability just be staging a single event where they run all the ballots through the sheet feeding apparatus and letting people video them. Note that like ETP this has privacy implications, so we would need to do some cost/benefit analysis before deploying such a system.

It turns out that this idea isn't original to us, as we unfortunately learned right after the camera-ready deadline. Anwar Adi suggested the same concept in 2006 and built a prototype, but it's quite a bit less capable than ours: it requires you to manually identify a single video frame for each ballot, doesn't produce ballot images (it uses simple edge detection algorithms to process the ballots itself) and won't work with the standard kind of opscan ballots in widespread use.

We (by which I mean Kai) have built a prototype of the system and it works pretty well. With the limited number of ballots we're processing, we get extremely good quality output; our test set of 50 ballots (600 opscan targets) produced no errors. The major drawback is performance: it takes about 10 seconds to process a single frame, so the system operates quite a bit slower than real-time with respect to the video camera. This can of course be dealt with by throwing hardware at the problem (we estimate that you would need something like 3-5 8-core machines to process at 30 ballots/minute, which is already pretty reasonable), but we've been working on faster algorithms and hope to be able to at least lower the required amount of hardware. Once we get this figured out, we're hoping to release an open source version of the software.