Paper-voted (and why I did so)

(This entry is written mostly for my non-cryptographer friends who wonder why I am always criticizing Estonian e-voting scheme, but it may also be interesting for cryptographers all around the globe. All opinions are my own.)

Many people probably already know that Estonia has had Internet voting since 2005. Over the years, the number of voters has increased. In the parliamentary elections this week, more than 10% of the whole population (which means even larger percentage of the population who can vote – and probably quite a large percentage of the people who actually go to vote) used Internet voting.

I paper voted.

Why? First of all, as a cryptographer, it is my job not to support insecure systems. Given the current situation in Estonia, paper-voting is the only thing that I can do, but I hope things will improve rapidly.

Here’s a short description of Estonian Internet voting protocol:

One vote attempt:
You as a voter either use an ActiveX control (or a downloadable application if you use a wrong browser/…) to log in to a secure webpage. To authenticate yourself you use an ID card (those have been obligatory in Estonia for quite a few years). After logging in, you use the GUI to select the candidate. After that, the voter computer encrypts your vote by using RSA and the key of a tallier. The result is also signed by using your private key (which is again stored in your ID card). Your computer now sends the signed & encrypted vote to the vote collector server.

Revoting:
You can always revote by using exactly the same procedure. The VCS only stores the latest vote by every voter. (This step was introduced to combat vote coercion/family voting — note that if everything else fails, you can go to the voting station and revoke your electronic vote by paper-voting.)

Vote counting:
After the election period ends, the VCS will take the latest encrypted votes of all voters and send them to the second server that is behind a firewall. The second server removes all the signatures. It then ‘burns’ all the unsigned encrypted votes to a CD. Now, a number of trusted people (including observers) take this CD and bring it to a separate room, which is well guarded. That room contains the third server, the tallier who is *not* connected to Internet at all. The CD is input to the tallier. The tallier reads all encrypted votes. Since it knows the decryption keys, it can decrypt all votes. After that it outputs the number of votes given for every candidate.

This whole process also contains a number of organizational steps (like transfer of the CD to the tallier, or general auditing), but cryptographically that’s it.

So what’s wrong with it? For a cryptographer it’s a rhetoric question but let me reiterate some points. Basically, an e-voting system can be attacked by attacking voter computers, Internet connection or voting servers. Signing/encryption mostly takes care of fraudulent Internet (they do not obviously protect you against DDOS attacks and the like).

Voter computers are an obvious problem: most of the people are computer illiterate, and are not able to check if their computers are not infected. Even if they have the newest antivirus (which we can’t be sure of), that antivirus itself might not be able to detect a piece of new malware that has been written specifically for *that* election and is unleashed just before it. (Note: in Estonia e-voting lasts for 3 days.) That malware could do a lot of damage, like hijack the connection between you and the ID card (basically letting the ID card to sign wrong votes), between the GUI and what actually happens inside the computer, etc. I would *not* be surprised if such a piece of software was written by a high-school kid.

Vote servers are another problem: they can attacked by a hostile (but yet invisible) takeover, or by an insider (software provider, hardware provider, they guy with a gun meant to protect the servers, cleaning lady…). To be completely certain nothing like that happens, one should use either 100% trusted providers etc, etc (which is somewhat unlikely if an interested foreign powers invests a few million euros to bribe everybody), or one should use cryptography. But first, why does it matter? Can’t we trust the election office? Rhetorically I could ask: do we trust politicians in general? Do we? Less rhetorically, there are so many potential threats here.

Given all this, when Internet voting process started in Norway, the government officials clearly stated they want strong cryptography, and probable security in general. In particular, they do not want to only avoid attacks. They want to be able to prove that no attacks happened. Moreover, they want to be able to prove that the e-voting system is so secure that no attacks are possible at all. (Or at least, the number of possible attacks is strongly limited.) If the e-voting system satisfies that property, they can in particular prove that they did *not* cheat. That means, at least some kittens in Norway will have a good night sleep. And people’s trust in the governance will increase.

We can imagine all kind of attacks (and motivations behind those attacks) against Internet voting. A party would like to gain a few more votes. A script kiddie is angry at a politician whose daughter doesn’t like him. A foreign power wants their favorite party to gain a few more votes. A foreign power attacks e-voting process just so that it will be clear that somebody attacked and thus the results can’t be trusted. Etc. Etc. Script kiddie might spend a few days to write a virus that works on user computers. A foreign power might spend $10M to develop Stuxnet+.

How can we protect Internet voting then? Fortunately, there *are* very well-known (at least in the cryptographic community) protocols for that. It is known how to get security in the case when a minority of voting servers is malicious. Under some conditions, it just suffices to have one uncorrupted voting server. Developing such protocols means that there is a need for additional computing power (and time, to implement the cryptographic protocols). Deploying such protocols is invisible to the voters.

Protecting against corrupted voter computers is more difficult. There are quite many ways to do it, but most of the ways requires the voters to perform some additional operations. As an example, Norway will use a scheme where every voter receives (by post) a codesheet that has the names of all candidates and corresponding check codes. (The codes are unique for every voter.) Voting proceeds as usual, by using computer and your favorite GUI, but afterwards you will receive by SMS a single code. The voter can now just verify if this is the same code that was written on the codesheet under his or her favorite candidate. If it is not, he can revote electronically (or go and paper-vote).

There are a number of good things about the Norwegian system. First of all, receiving the codesheet and checking your codes is not obligatory — you just have to do it when you are paranoid or just security-conscious (or just geeky). Thus, Internet voting still rules in the sense of convenience. On the other hand, interested voters can verify that their votes were counted for by following a relatively small number of steps.

Another thing that I like about the Norwegian solution is that by using their own words, the underlying math is simple enough to be understood by high school students — and they plan to start teaching the protocol at high schools. (See the slides here.) Which is nice, since cryptography is not everything — for complete trust there have to be enough people to understand the system. And it’s always nice to teach people new math. 🙂

The Norwegian system is not ideal, but it can be improved upon. There are also many other, somewhat similar (or completely different) techniques to protect Internet voting schemes against corrupted user computers. Unfortunately, dwelling into them would take quite a lot of time and this margin here is too short.

Advertisements

8 Responses to “Paper-voted (and why I did so)”

  1. Uwe Riisenberg Says:

    For the clarity let it be said that an Estonian identification card has been obligatory since 1st January 2002 and e-voting last on current Estonian parliamentary election from 24th February until 2nd March.

  2. HillarP Says:

    How Norway can ensure secrecy of election?

  3. helger Says:

    One typo: probable security => provable security

    Interestingly enough, just a few days after this post, a second-year history student (I wrote: “I would *not* be surprised if such a piece of software was written by a high-school kid”) in Estonia came up with a claimed attack. What will exactly happen next, remains to be seen.

    @HillarP: Norway does not ensure secrecy in the case you can’t trust your computer. Yes, this means that the computer can not send your vote to the servers if it is not happy with your choice, but you will notice it since you won’t get a code back. There are some weaknesses left (family voting: your father can see whom you voter for, but this can be alleviated by revoting by using different computer or going to paper-vote — and obviously the case when political parties will start repressing people who vote for their opponents; but in this case I wouldn’t trust e-voting at all). Secrecy against voter computer can be achieved by using say code voting (a very well known concept since at least 2001), where the coder also inputs a code to the computer, and gets back a different check code. However this means voters MUST get the codesheets. In Norway it was felt it’s better to have an option for that. But In Estonia, we can obviously implement code voting.

    Second issue is secrecy against voting servers. Norwegian protocol guarantees secrecy against any single voting server. (The same is true also in Estonia.) However, differently from Estonian solution, it is very simple to add servers in Norway, and to scale the protocol so as it will be secure against coalitions of say 3 and more servers. As I said in my main post, making e-voting secure against voting servers is a solved problem in cryptography, the main problem is security against voter computers.

  4. HillarP Says:

    There is some miss understanding, let me explain.

    If there is table of codes, where each code correspond to candidate and each code is unique then voting commission have to know from who you voted for. Other vise they cant send you the code corresponding to your table. Yes, it can be done automatically, but those tables must be stored somewhere (for a quite long period) and voting servers are under control of voting commission.

    Also there is weaknesses in those codesheets moving paths. First this table of codes have to be printed – in Estonia nearly 1 million sheets. So there have to be some printing house (first untrusted party). Those sheets have to delivered to voters. So there have to be some delivery company (second untrusted party). And when this code will send back via SMS there have to be some telco (third untrusted party). In my opinion securing all those party’s aren’t trivial task.

  5. Ando Says:

    Why would somebody spend $10 000 000 for developing something like styxnet when you can buy the biggest political party in estonia for mearly $4 000 000. Paper votes help for sure aganist such action…

  6. helger Says:

    @HillarP:

    In Oct 2010, I gave this presentation for young computer scientists: http://home.lu.lv/~df/tdays/lipmaa-slides.pdf

    It was meant to introduce the Norwegian system for people who study CS but are not specialists in cryptography (though in a few places I had to use magic words since I only had 30 minutes). The slides also point out to two papers, one by us (me and Sven Heiberg from Cybernetica AS & Filip Laenen from Computas AS, Norway), and then second one by Gjøsteen from NTNU, Norway. The second protocol is actually going to be used in Norway.

    TL;DR: the voting commission doesn’t get to know, unless all voting servers collaborate. The beauty of the system is that you can add more and more servers, and thus distribute the trust. There’s no such possibility in Estonian system. Moreover, Estonian system does neither provide voter verifiability (I can check that my vote was counted correctly) or universal verifiability (given all encrypted/signed votes, everybody can verify whether the final tally is correct). Norwegian protocol does, under reasonable assumptions.

    The basic idea is that I send encrypted vote to the voting servers, who execute some algorithm on the *ciphertext* so that it transforms to the *ciphertext* of your check code, in a *verifiable* manner (Gjøsteen’s paper is more specific about verifiability, in our paper we mentioned it just can be achieved). It is not a completely trivial process, but as shown in the mentioned two papers, it can be done.

    About moving paths: no, there is no basic weakness. The paths are an *additional* security measure to make the process verifiable. If your computer is insecure and you can trust the paths, you get to know that the computer (actually, a peace of malware on it…) has mangled with it.

    If your computer is secure and you can’t trust the paths, then something bad can only happen when the attacker attacks both the postal system and SMS in a consistent way. I am 100% certain this is much more difficult to do undetectably than attacking voter computers. Moreover, we can duplicate the channels, by for example sending the verification code to you by using both the SMS and the post — and by all means, storying it on a webpage that you can access by using a different computer. (Again, there are different security issues here, but I suppose I do not have to explain them all.) Even if the attacker succeeds in attacking both paths, then you just get a false alarm that your vote did not reach the voting centers: the attacker of paths cannot change your vote (assuming that the voter computer is secure!). In this case, you can just revote electronically or on paper.

    The final case is when the attacker can attack all three things: your computer, the postal system and the SMS. I again argue that this is *much* more difficult to do (undetectably) than just attacking your computer. It doesn’t only require creating a well-timed malware (a la Stuxnet), it requires the attacker to take over or bribe off a lot of other systems as well.

  7. Game Key Says:

    Game Key…

    […]Paper-voted (and why I did so) « Who groks in beauty?[…]…

  8. Report on the Estonian Internet Voting System | Verified Voting Says:

    […] 3. The voters’ computers are vulnerable to election rigging malware. There are many examples of very clever viruses and worms, such as the Zeus virus, that have successfully stolen large sums of money from, for example, users’ on-line bank accounts. Specially modified versions of Zeus are even available on the black market. It would be relatively straightforward to modify Zeus to steal an election. As Estonian cryptographer Helger Lipmaa says in his blog: […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: