Friday, October 13, 2017

Designing A Tamper-Proof Electronic Voting System



India's Electronic Voting Machine (EVM)

India's Electronic Voting Machines (EVMs) have been in the news a lot lately, and not always for the right reasons. There have been complaints by some candidates that when voters pressed the button in their favour, another party's symbol lit up. Faced with accusations that the EVMs may have been hacked (especially with the string of electoral successes of the ruling Bharatiya Janata Party), India's Election Commission has begun to conduct elections with a Voter-Verifiable Paper Audit Trail (VVPAT), which prints out the details of the party/candidate that a voter selected, so they can verify that their vote was registered correctly.



An EVM unit with a printer to provide immediate paper verification to voters

As a systems architect, I'm afraid I have to say that may not be good enough. Let me explain why, and then suggest a more foolproof alternative.

First of all, my familiarity with IT security tells me never to believe that a hardware device has in-built safeguards. We have all heard about how backdoors can be built into hardware, with whispers about the Russian mafia or Chinese government having control of fabrication plants that produce integrated circuits, so we know it's at least theoretically possible for criminal elements to inject malicious logic right into the hardware of an electronic device.

At the same time, I believe it's being Luddite to advocate a return to entirely paper-based ballots. It's true that many Western countries stick to paper ballots for the sheer auditability of a poll (which electronic voting makes opaque), but India has had bad experiences with paper-based polls in the past, with uniquely Indian subversions of the system such as "booth-capturing", as well as more conventional forms of fraud like "ballot-stuffing".

No, there's no going back to purely paper-based ballots, but there are serious vulnerabilities with the electronic voting system, even with VVPAT.

Let me illustrate.

The basic EVM logic is as follows. The voter presses a button corresponding to their preferred party or candidate, and the machine confirms their selection by lighting up the corresponding election symbol (because many voters are illiterate and can't read). The choice is also recorded in the unit's memory. After the polls close, all the voting units are collected and connected to a central unit that tallies the votes in each. Once all units have uploaded their votes to the central unit, the results of that election can be announced, with the tallies of all parties and candidates available.



Now, based on voter complaints about the wrong symbol lighting up, here's what many people suspect happened. Somehow (never mind how) a hack was introduced into some of the units that recorded a selection of party A as a selection of party B.



This is actually a pretty amateurish hack, as I'll explain shortly. It's readily detectable by an alert voter. What the Election Commission is attempting to do with the Voter-Verifiable Paper Audit Trail (VVPAT) is to make the voter's selection more explicit, in the hope that more of them will be forced to verify that their choice was correctly recorded. It does not make the system more secure in the sense of being able to trap more subtle hacks.

Here's the schematic of the basic logic when things go well.

(Click to expand)

When faced with a simple hack like the suspected one above, the system will respond as below.

(Click to expand)

However, any hacker with a little more smarts will realise that their subversion will have to be less readily detectable. In other words, the hack would have to be placed in a slightly different place.


(Click to expand)

With this kind of hack, any mischief would be virtually undetectable. Both the lighted symbol and the paper printout would confirm to the voter that their choice was faithfully recorded, yet their vote would have been subtly hijacked in favour of another party.

The logic of the hack could be designed to be extremely subtle indeed. Instead of switching every single vote from party A to party B, it could be designed to apply a random function so that, on average, only 1 in N votes was switched across. In many marginal constituencies, even a small skimming of votes would be enough to tip the balance, so desired results could be achieved without any suspiciously large vote swings. There could even be a threshold below which the logic would not start to kick in, say a few thousand votes. That way, if the Election Commission conducted a few test runs to ensure that a unit was working correctly, it would not arouse suspicions.

Now all this seems depressing. Is there any way to combat this?

Yes, there is, but it's not purely in hardware and software. If it were, this post would have been titled "Designing A Tamper-Proof Electronic Voting Machine". The system that we design needs to incorporate electronic and manual elements.

What we need are not one but two printouts for every vote. One copy is for the voter's own records. The other is for the Election Commission. The voter must verify that both match their selection, then place the EC copy into a ballot box before they leave the booth, just like in a paper-based poll. However, this paper ballot will only be used for verification, not for the actual vote tally on counting day, otherwise we may as well go back to a purely manual vote count.

(Click to expand)

A number of statistical techniques may be used to sample and test the performance of voting machine units in various constituencies.

Under the most pessimistic scenario, the ballot boxes of every single booth will be tallied offline, and the counting may continue for weeks after the official results. Elections will only be rescinded if the manual tally grossly contradicts the electronic one (there will always be minor discrepancies due to voter or official error).

Under less pessimistic scenarios, a random sample of booths may be chosen for such manual verification. If gross discrepancies are detected in any booth, then all of the ballot boxes in that constituency will have to be manually tallied. If more than a certain number of constituencies show suspicious results, then the tally may be expanded to cover an entire state, and so on.

There can be further refinements, such as ensuring that the random sample of booths to be verified is drawn publicly, after the voting is completed, so as to afford no opportunity for malicious elements to know in advance which booths are "safe" from being audited.

In general, the design of the overall process is meant to detect subversions after the fact, so the technically accurate term is tamper-evident rather than tamper-proof. However, advertising the fact that such audits will be taking place may deter malicious elements from attempting these hacks in the first place. Hence, in a larger sense, the system consisting of the combined electronic and manual process, plus a widespread foreknowledge of an inevitable audit, may result in a tamper-proof system after all.

Democracy works because citizens have faith that their will is reflected in the results of elections. If citizens lose faith in the electoral process, it could cause a breakdown in society, with violent revolution in the worst case. That's why it's important to act quickly to restore faith in the process, even if this makes the process costlier.

As the quote commonly attributed to Thomas Jefferson goes, "Eternal vigilance is the price of freedom."