A Little Learning - Electronic Voting and the Software Profession

Over the last week, I've had occasion to ponder the expression that 'a little learning is a dangerous thing'.

Quite spontaneously, a number of people have posted on Facebook in opposition to the idea of electronic voting. One linked to a YouTube video which clearly demonstrated the problems with some of the voting machines used in the US. Others posted a link to a Guardian opinion piece that labeled electronic voting a "monumentally fatuous idea".

The YouTube video - actually, a full-length documentary from 2006 entitled "Hacking Democracy" - showcased a number of well-known problems with the voting machines used in the US. Touch-screen misalignment causing the wrong candidate to be selected, possible tampering with the contents of memory cards, problems with mark-sense readers, allegations of corruption in the awarding of contracts for voting machines - these have been known for some years.

The Guardian article fell back on claims that "we could not guarantee that it was built correctly, even with source code audits. . . Until humans get better at building software (check back in 50 years) . . . we should leave e-voting where it needs to be: on the trash-heap of bad ideas."

However, by exactly the same argument, online banking is also a "monumentally fatuous" idea, along with chip & PIN credit card transactions, online shopping, fly-by-wire airliners, etc.

Whenever I've suggested that, actually, electronic voting is not such an outlandish idea, I've met with vehement opposition, usually supported by an appeal to authority along the lines of "I used to be a sysadmin, and let me tell you . . ." or "I'm a software engineer and it's impossible to write foolproof software. . ."

There's an old saying among cryptographers, that every amateur cryptographer is capable of inventing a security system that he, himself, is unable to break. In this case, the author of the Guardian piece demonstrates the converse - that because he, himself, is unable to come up with a system that he can't break, he is certain the professionals can't either. 

I have to say, that's a novel form of arrogance; to be so sure that because electronic voting systems are beyond your own modest capacity, nobody else can do it, either.

Yes, we've all seen software projects that were near-disasters, we've known programmers whose code had to be thrown away and rewritten, and poor practices like the storage of passwords and credit-card numbers in unencrypted form. I watch students today 'throw' code into the Eclipse IDE then run it through the debugger to figure out what the code they've just written actually does, and then I think back to my days of careful, paper-and-pencil bench-checking of Algol code, and I cringe!.  But not every system is designed and implemented that way.

It's true that electronic voting is a difficult problem, but it's one that some very fine minds in the cryptographic and security communities have been working on for several decades now. The underlying cause of this difficulty is that a voting protocol must simultaneously preserve what, at first sight, are a number of conflicting security properties.

Most security people are familiar with the basic security properties we work to preserve in the information and systems in our care: confidentiality (also known as secrecy), integrity (correctness) and availability - the so-called "CIA triad". But there are many more, and some of them, at first glance contradict each other.

For example, anonymity is important in a democracy; no-one should be able to find out how you voted so that nobody should fear any form of reprisal. For an electronic voting system, this means that the vote cannot be associated with the voter's identity, whether represented as a login ID, an IP address, a public key or some other identifying information. But democracy also requires that only those who are entitled to vote being able to do so - in Australia that means registering on the electoral roll and identifying yourself at the polling place. This property is called eligibility.

At first glance, these requirements are mutually exclusive and contradictory - how can you identify yourself to claim eligibility, while at the same time remaining anonymous? In the physical world, the time and space between your identification, the booth where you mark your ballot paper, and the random placement of the ballot paper in a box all serve to provide anonymity. Fortunately there are cryptographic techniques that effectively do the same thing.

An example is the use of blind signatures, which were originally invented by David Chaum in 1983 [1], although I'll use a later scheme, made possible by the RSA public-key system's property of homomorphism under multiplication. There are three parties: Henry, who holds a document (e.g. a vote) which he wants Sally (our electoral registrar) to sign without knowing what it is that she is signing. Finally, there is Victor (the verifier and vote tabulator), who needs to verify that the document was signed by Sally.

I don't want to delve into the mathematics too deeply, and am constrained by the limited ability of this blogging platform to express mathematics - hence '=' in what follows should be read as 'is congruent to' in modular arithmetic, rather than the more common 'equals'. Henry obtains Sally's public key, which comprises a modulus, N, and a key, e. Henry then chooses an integer blinding factor, r, and uses this with the key, e and the modulus N, along with his vote message, v to calculate a ciphertext

c = m x r^e (mod N)

and sends this to Sally along with any required proof of his identity. If Sally determines that Henry is eligible to vote, she signs his encrypted vote by raising it to the power of her private key, d:

s' = c^d (mod N) = (m x r^e)^d (mod N)  = r x m^d (mod N) (since ed = 1 (mod N))

and returns this to Henry. Henry now removes the blinding factor to get the correct signature:

s = s' x r^-1 (mod N) = r x m^d x r^-1 = m^d

Henry can now send his vote message, m, off to Victor, along with the signature, s. Victor uses Sally's public key, d, to check whether

s^d = m (mod N)

If the two are equal (congruent, really) then the signature is correct, and Victor will count the vote. Notice that Henry does not identify himself to Victor, and Victor does not know who he is; he is willing to accept that he is an eligible voter because Sally has signed his vote message. And, very importantly, note that Sally does not know how Henry voted - she signed the blinded version of his vote message.

If all that mathematics was a bit much, consider this simple analogy: if I want you to sign something for me without seeing what it is, I can fold up the paper I want to sign in such a way that the signature space is on top when the paper is placed in an envelope. I then insert a piece of carbon paper - the paper that's used in receipt books to make a second copy of a written receipt, and used to be used to make copies of typewritten documents - on top of the paper but inside the envelope. I then ask you to sign on the outside of the envelope, and the pressure of your pen will imprint your signature, via the carbon paper, to the unseen paper inside the envelope. Voila! You have blind-signed a document, which I can now extract from the envelope once alone.

My point is that cryptographers have, for many years known about, and had solutions for, the superficially contradictory requirements for eligibility and anonymity.

In practice, voting protocols have many more requirements:

• The voter must be registered or authorized to vote (elegibility)
• The voter must vote once only (uniqueness)
• The vote must be recorded confidentially (privacy) and cannot be associated with the voter's identity (anonymity)
• The vote must be recorded correctly (accuracy)
• The voter must be able to confirm that his vote was recorded correctly (verifiability)
• The voter must not be able to sell his vote
• No-one can be able to duplicate votes (unreusability)
• The vote must be unalterable after recording (integrity)
• The voter must not be vulnerable to coercion (uncoercibility) 
• The votes must not be revealed or tallied until the end of the election (fairness)
• The electoral authority - or everyone - must know who voted and who did not

But we still have more tools at our disposal, such as zero knowledge proofs, digests, signatures and, of course, conventional symmetric crypto which we can use to build more sophisticated protocols which do satisfy these security requirements. Some very fine minds indeed have been working on this for decades now, although obviously their work is not well known outside a relatively small community of cryptographers with an interest in voting.

When the NSW Electoral Commission were working on their iVote system, they asked several universities to get involved. They supplied the design documentation for iVote, including references to the various cryptographic protocols used (e.g. Schnorr's Protocol - a zero-knowledge proof based on the discrete logarithm problem). Both I and a team from UNSW independently wrote programs which took over 250,000 votes and validated them, in a ceremony attended by scrutineers of the various political parties.

The iVote system is quite sophisticated - it's an enhancement of what's called a "split central tabulating facility" design, with a third, separate verification server which allows voters to verify their votes via a phone interface, while the counting system itself is airgapped from everything else. The process I described above compared the votes from the counting system with the encrypted votes in the verification server. The voter can additionally obtain verification that their vote was decrypted correctly via the web interface.

It's true that researchers did find a vulnerability in the SSL/TLS library on one server in the system. I'm not familiar with that part of the system, but I'm pretty sure that even if that vulnerability was exploited in a man-in-the-middle attack, the attacker would not be able to manipulate the vote in that session as the votes are encrypted in the application protocol and do not rely on the transport layer encryption of TLS. However, the browser supports TLS anyway, so it's a good idea to use it as one more layer of a defence in depth - and an alert user would expect to see that padlock in the URL bar in any case, so it would be a mistake not to use it.


Prior to getting involved with the iVote project, I'd been somewhat cynical about the prospects for electronic voting. Although I knew something of the underlying principles, I felt it was still in the too hard basket. And reports of the problems with US voting machines didn't help, although a little investigation will reveal they are almost embarrassingly primitive and bear no resemblance to the protocols I am discussing here. But they still contribute to popular fear of electronic voting systems and pollute the overall climate. Watch the video above and you'll see what I mean.

However, I discovered that work on voting protocols was more advanced than I had thought, and the implementation of the iVote system was considerably more sophisticated than most people would imagine.

But what has surprised me is the negative attitude of software professionals. The (ISC)2 Code of Ethics [2] requires me, as a CISSP, to "Protect society, the commonwealth, and the infrastructure" and as part of that effort, to "Promote and preserve public trust and confidence in information and systems". And yes, it also requires me to "Discourage unsafe practice". At this point, I cannot say that the introduction of electronic voting is an unsafe practice - over 250,000 people used in our last State election - but it's hard to promote public trust and confidence when software professionals who ought to know better are so active in promoting distrust. There's a huge gap between the quality of code produced by a junior programmer working on a mobile app with time-to-market pressures and the careful design of a voting system based on decades of cryptographic research and development, and the fact that the former may be unreliable is not an indication that the latter is inevitably insecure.

Only a fool would guarantee that an electronic voting system is 100% secure and error-free - but then, only a fool would guarantee that paper-based voting systems are 100% secure and error-free. However, humans are better at writing software than the Guardian author suggests and electronic voting system are in use today, will increase in popularity and are very unlikely to result in the downfall of democracy.

References

[1] Chaum, David. “Blind Signatures for Untraceable Payments.” In Advances in Cryptology, edited by David Chaum, Ronald L. Rivest, and Alan T. Sherman, 199–203. Springer US, 1983. http://link.springer.com/chapter/10.1007/978-1-4757-0602-4_18.

[2] (ISC)2 Code of Ethics -  The Pursuit of Integrity, Honor and Trust in Information Security, International Information Systems Security Certification Consortium, 2010. Available online at https://www.isc2.org/uploadedfiles/(isc)2_public_content/code_of_ethics/isc2-code-of-ethics.pdf