E-voting

Introduction

Electronic voting is called e-voting, and it includes both electronic voting systems as well as electronic systems to verify one's vote.

Such systems can be divided into two categories: supervised systems at polling stations and systems that can be used to vote remotely. Representatives from the first category are, for example, electronic voting machines used in the USA, India and Brazil.

The second category consists of remote voting systems that allow users to vote outside the polling station, for example, via a mobile phone or a computer. Estonian e-voting is an example of such a system.

An electronic voting machine used in Brazil (source).

Security requirements

Modern elections in democratic societies rely on a few core principles. One of the most significant of these is the requirement for a secret ballot. Its goal is to provide the voter with a private environment to fill in the ballot. It was mainly designed to prevent vote-buying and coercion. While the practice has a long history, the modern secret ballot was introduced in Australia in the middle of the 19th century. In France, the requirement for a secret ballot was written into the legislation at the end of the 18th century. However, it had loopholes, which gave possibilities for third parties to see what was written on the ballot sheet.

In addition, it is crucial for fair elections that the ballots would be distributed uniformly between the eligible voters and that the cast votes would be correctly counted. There are multiple security requirements regarding the handling of ballots, but we could generalize many of them under the term integrity. By attacking the integrity of the ballots, the election result could be changed.

In the case of paper voting, the requirement for ballot secrecy is fulfilled with the help of a voting booth. However, individual voters are not able to check what happens with their vote once it has been dropped into the ballot box. This check is delegated to election observers. It is hoped that there are sufficiently many observers to monitor all the processes.

In the case of electronic voting, it is possible to build voting systems, which allow the voter to check whether the vote was included in the final tally. Such verification mechanisms provide a strong guarantee regarding the integrity of the election result. However, the downside lies in the fact that the strong verification mechanisms provide means for proving how the voter voted. It can be argued that this would violate ballot privacy and enable both coercion and vote-buying. In addition, the voting system has to be usable for an average voter, which means that exotic cryptography, together with complex anti-coercion measures, can not be used for general elections. Thus, it can be seen that there is an inherent conflict between the requirement for ballot privacy and the requirement for verifiability (integrity). To build a usable system, a balance has to be found between these requirements.

A fully verifiable voting system is called end-to-end verifiable. This means that anyone could verify the election result (it is universally verifiable), and individual voters could also follow and check their votes. One way to split the requirement is to state the following requirements:

• cast as intended - a voter can check that the vote represents their intent
• recorded as cast - a voter can check that the vote is correctly stored in the ballot box
• counted as recorded - anyone can check that the votes are correctly tallied, and the voter can check that the vote was included in the tally.

The first two requirements are categorized under individual verifiability, while the latter is categorized under universal verifiability.

I-voting in Estonia

In Estonia, e-voting means that a citizen can vote over the internet. Hence, it may also be called i-voting. I-voting has been available in Estonia since 2005.

What are the advantages of i-voting?

• allows voting from outside the polling station, e.g. at home or from abroad
• it could increase turnout (convenience: no need to go somewhere)
• decreases the amount of foul play (in case of a very well designed & secured voting system)
• tallying is both precise and fast

As statistics shows, i-voting has become more popular year after year:

What is needed for successful i-voting (in Estonia)?

• ID-card or mobile-ID for user authentication and digital signing
• I-voting legislation
• I-voting software
• I-voting support infrastructure (hardware, information security, network communications)
• Organizers
• Informed voters

In Estonia, ID-card is a compulsory document, so all voters are able to electronically authenticate themselves and issue digital signatures. Moreover, i-voting is recognized by legislation. Voting, including i-voting is overseen by the National Electoral Committee (Vabariigi Valimiskomisjon) and managed by State Electoral Office (Riigi valimisteenistus).

Architecture of Estonian i-voting system

How does the Estonian i-voting system work? First, we will describe the scope and the parties involved in the process:

Scope of i-voting. (Source: documentation of IVXV from 2017, newer documentation is in Estonian)

We could say that the i-voting system contains four main parties: voters, vote collecting servers, vote processing servers, vote tallying server.

The main parties of the Estonian i-voting system. (Source: documentation of IVXV from 2017, newer documentation is in Estonian)

Estonian i-voting system uses a so-called double envelope scheme. First, the voter encrypts his vote with the public key of the elections that comes from the election organizer, the National Electoral Committee (NEC). This encryption forms the first layer ("envelope") around the vote. Secondly, the encrypted vote is signed using the voter's private key, constituting the second layer. The signed and encrypted vote is sent to the election server.

In the server, the voter's ID is first checked by verifying the signature on the encrypted vote. The signature is then removed from the vote, and the encrypted vote is sent to another server, where the votes are decrypted using the private key of elections and then tallied. It is important to understand that the first server does not have access to the election's private key and hence cannot decrypt the vote. Only anonymous encrypted votes are sent to the second server, where they can be decrypted.

"Two envelope system" used in i-voting. The key pair belongs to the organizers of the i-voting; it is not the user key pair. (Source: documentation of IVXV from 2017, newer documentation is in Estonian)

IVXV: Updated version of the Estonian i-voting system (2017)

The i-voting system was upgraded in 2017 to increase the security level and overall trustworthiness.

The new system provides additional integrity guarantees for the submitted ballots. More specifically, the new system makes it possible for auditors to do cryptographic checks to verify that the voting servers did not add, modify, or remove ballots. For example, an external registration service (certificate authority) adds a digital signature for each encrypted ballot that is received by the voting system. Thus, the registration service keeps a log of all encrypted ballots that were sent to the voting system (it signs the hashes of these ballots and stores the corresponding signatures). This list has to match the list of encrypted votes received by the voting system. Thus, the registration service can be seen as a bulletin board, but it is not public to prevent coercion. However, external auditors can come and audit the signatures issued by the registration service to make sure that the election system recorded all received ballots and that no ballots were added and no valid ballots were removed.

In addition, the updated voting systems uses cryptographic measures to anonymise the votes before they are sent to the tally server. It used to be that the anonymisation was provided by server software which removed signatures from the encrypted votes. The previous solution worked but left a theoretical possibility to claim that the system could be attacked by malicious insiders who have access to the servers.

Now the voting system is using a mixnet to ensure that the ballots are anonymised before they are being decrypted. After the signatures are removed from the encrypted votes, the encrypted votes are mixed such that it is not possible to match the votes and signatures. In addition, a mathematical proof is generated, which makes it possible to verify that mixing was done correctly. If a mixnet is always used before decryption, an insider can not find out how the voters voted. In addition, external auditors can use the proof to verify that mixing did not modify the result and that all encrypted votes were included in the result.

IVXV is using ElGamal instead of RSA. This is needed to apply the mixnet as mixing requires that encryption of the votes is done with a homomorphic cryptosystem. ElGamal is homomorphic when considering the multiplication operation. This means that by multiplying two encrypted ElGamal ciphertexts, we get a ciphertext that is the multiplication of the corresponding plaintexts. I.e., ElGamal encryption has the following property: Enc(m1) * Enc(m2) = Enc(m1 * m2).

As the election private key can not be published, a method had to be created to make the decryption process transparent and auditable. Thus, the decryption process was improved so that a cryptographic proof of correct decryption is generated for each decrypted vote. By verifying these proofs it is possible to guarantee that the election result is calculated directly from the encrypted votes.

More information about the updates done in 2017 can be found from: General Framework of Electronic Voting and Implementation thereof at National Elections in Estonia (2017)

An overview of the achitecture of Estonian i-voting system used since 2017. (Image source: PhD thesis of Kristjan Krips. )

Estonian i-voting software

The server-side software for i-voting is open-sourced with the source code available on GitHub: https://github.com/vvk-ehk/ivxv. However, the i-voting client application is closed source and is downloadable from the election web site during the pre-election phase. The voting application lets the voter to browse the candidate list and cast a vote.

How to check the authenticity of the voting application?

1. Before downloading, verify that you are really on the official web site of the elections. Check that the web site uses HTTPS and study its certificate.
2. Check if the hash of the downloaded application coincides with the one published in media.

Voting instructions

Specific usage instructions for the voting application are published before the elections.

However, these are four main steps:

• user authentication (ID-card / mobile-ID)
• browsing candidate list and choosing a candidate
• confirming the vote by signing it (ID-card / mobile-ID)
• verifying if the vote reached the server (optional)

Vote verification

Vote verification should answer the voter's question What happens to my vote after it is cast? Among others, the following questions should be answered:

• Was the vote encrypted and signed correctly?
• Was the vote sent to the server correctly?
• Was the vote correctly received at the server?
• Was the vote correctly counted when tallying?
• Are all the valid votes taken into account in the tally?
• Are there any invalid (fake) votes included in the tally?

The vote verification application, used since 2011, helps to answer the first three questions from this list. The rest of the properties are provided by organizational means not verifiable by each individual voter (see also the list of known problems below). The property of a voting system that allows the individual voter to verify that his or her vote was correctly counted and also allows to verify that the voting system functioned as it was intended (e.g., did not add/remove votes) is called end-to-end verifiability.

Starting from the local government elections in 2017, all the previously mentioned properties should hold. The new system provides a higher security level, but some properties are verified by auditors. E.g., voters themselves are not able to verify that their votes were included in the final result. Thus, the Estonian i-voting system does not provide end-to-end verifiability.

Estonian individual vote verification system

The vote verification system allows the voter to verify if his vote reached the election organizers correctly. Such verification helps against attacks where malware in the voter's computer changes the vote before sending it to the server. The general idea of the verification system is archived here:

• description in English
• illustration in Estonian

The vote verification application works on iOS and Android devices that have a camera and internet connection. The verification must be carried out on a separate device independent from the voting device as the latter may be compromised. However, currently, it is not possible to vote with a smartphone and thus the requirement to have a separate verification device is fulfilled.

Vote verification:

1. After successful voting, a QR-code is shown on the computer screen
2. Voter installs the verification app in his smartphone or tablet
3. The smart device is used to read the QR-code, after which the device contacts the election server
4. The cast vote is shown on the smart device screen

If the vote shown on the screen does not match the cast vote, the election organizers should be contacted. More information can be found from the archived instructions.

A QR-code is shown after the vote is cast. (Source: VVK)

Can the vote verification increase vote-selling?

Isn't it discriminating if vote verification requires a smart device?

Starting from 2015, the vote verification system was also approved by legislation, and now it is possible to use it as an input to apply for revoking the voting results.

Security of the Estonian i-voting system

To simplify the security analysis of an i-voting system, the client-side and the server-side could be analyzed separately. Besides the client and the server, it is also important to focus on the security of the transport channel, but this can be secured with standard measures like TLS.

It is important that the behavior of the server could be audited. No single malicious party should be able to modify the election result. Thus, the new version of the Estonian voting system distributes the server-side tasks between two independent entities. The vote registration service is separate from the rest of the server-side software. The vote registration service registers the received encrypted and signed votes. Once the voting period ends, the signatures are removed, and the encrypted votes are sent through a re-encrypting mix-net, which removes the link between the encrypted vote and the signature. The mix-net also generates a cryptographic (mathematical) proof, which shows that all of the encrypted votes coming out of the mix-net are the same that were inserted into the mix-net (that were signed by eligible voters). The re-encrypted votes are decrypted in an air-gapped machine, and the decryption software generates a cryptographic proof, which can be used to check that the decrypted votes represent the encrypted votes. Thus, it can be checked that the software that performs decryption does not cheat. However, this check has to be done by an auditor.

The client-side of the voting system should provide the voter the means to encrypt the vote and verify the vote. However, as mentioned before, the voting systems have an inherent conflict between privacy and verifiability requirements. The Estonian system is optimized to be coercion resistant by allowing the voters to re-vote as many times as they wish. This is expected to stop both vote-buying and coercion. However, due to this requirement, the Estonian i-voting system does not have end-to-end verifiability. While end-to-end verifiability would give the voters a way to check themselves whether their vote was included in the tally, it would also give a possibility to prove to the coercer, or vote buyer which vote was cast. The downside is that the voters are probably not able to check if their computers are infected with malware. In addition, it is difficult to check if malware has abused their electronic identities to issue legally binding signatures. Thus, when voters can not trust their own computers, it is difficult to get a guarantee that their vote was not overwritten by malware. However, to change the election result, a large number of voters would have to be attacked. The bigger the attack, the more probable it is detected. In addition, the election organizers can detect anomalies from the server-side logs. For example, if the number of voters who re-vote increases significantly, it should be carefully checked if there is malicious activity involved. Thus, in case an attacker wants to change the election result, the attack should be stealthy. However, staying invisible is very difficult in case of a large scale attack. At the same time, an attack that targets only a few voters is unlikely to change the election result, and the same result could be achieved by cheaper means (bribing people and asking them to take a photo of the ballot in the voting booth).

• Voting on someone's behalf
  • Solution: it is possible to recast one's vote several times
  • Solution: voting by traditional means (on paper) overrides the electronic vote
• A malware changes the vote or does not cast a vote at all
  • Solution: a voter can verify if his vote reached the server
  • Solution: a massive attack would probably be detected, and the voting result is cancelled
• Sabotage of i-voting: diminishing the reputation of i-voting by spreading false information. This could result in cancelling the voting result.
  • Solution: i-voting process is transparent and verifiable
• It is not possible to verify if all votes are correctly included in the tally
  • Partial solution: it is possible to observe the tallying process.
  • Solution: in 2017, the voting system was upgraded such that cryptographic proofs are generated, which can be used to verify whether the votes that were cast were also correctly counted. In case multiple votes were cast by the same voter, then only the last vote will be valid. The proof can only be verified by an auditor, and thus the end-user can not check if his/her choice was tallied.

Security analysis of the old version of the Estonian i-voting system (2014)

The following information is kept for historical reasons as the current server-side software is significantly improved and uses cryptographic means to prove the integrity of the results. However, the security analysis of the old system is still an interesting read, although the majority of the issues are not relevant anymore.

In spring 2014, a group of recognized i-voting researchers published a report on Estonian i-voting. The report showed that election organizers have problems with organizational security. Researchers noticed that many procedural rules were not followed correctly or they were lacking altogether. Following such rules is very important to avoid creating any weaknesses in the system. For example, the voting software was developed using developers' personal computers rather than special computers meant for just this task. The most important failure to follow procedural rules took place in 2013 when the vote counting server was unable to write the result to a DVD. As a quick alternative, someone's personal USB stick was used to transport the votes. Using a personal USB stick for this purpose makes it theoretically possible to alter the tally by infecting the server with malware.

Secondly, the researchers demonstrated a proof-of-concept attack on their own test system that might have allowed to change the voting outcome by infecting one of the organizers' computers with malware. The attack was carried out by infecting the DVD that was to be used to install the operating system on the servers. It was possible to infect the DVD so that the modification went undetected. The researchers disclosed the vulnerability before the elections, and this attack is no longer possible. The attack was based on the idea that you always have to trust something and it is almost impossible to create a system that is not based on trusting some components. For example, people have to trust that the software is built correctly, i.e., that the compilers that compile code are not under the control of an attacker. Also, one has to trust the operating system and that the hardware of the computer is not backdoored. An overview of the trust issue is given by Ken Thompson in his famous speech: Reflections on Trusting Trust.

Finally, the researchers pointed out a known problem that user's computers cannot be trusted as they can be infected by malware. For example, it is possible to infect user's computer with a malware that saves the ID-card PIN codes and uses these later to recast the vote. It is difficult for an end-user to detect such malware, especially if the attacker is a large nation-state with advanced cyber offense capabilities. The vote verification application does not provide protection against this attack as the malware can easily recast the vote after the allowed verification period (provided that the ID-card is in the card reader). Estonian i-voting system allows to recast one's vote an infinite number of times and does not notify the voter about the vote being cast again. If the system would notify the voter, then it would be easier to buy and sell votes as the notification could be a proof of re-voting & changing the sold vote. However, this attack is only possible when the voter is using a regular ID-card reader. If the voter uses a pin-pad based ID-card reader, then the attacker is not able to access the PIN codes as the PIN codes do not go through the operating system. This attack also does not work when the voter uses Mobile-ID for vote casting.

Documents

1. Press release of the security researcher, May 12, 2014
2. Reply by the National Electoral Committee, May 13, 2014
3. E-voting is (too) secure, Anto Veldre, CERT-EE (in Estonian)
4. Researcher's reply to NEC
5. Published research paper, November 2014

Extra reading

• Papers relevant to the Estonian i-voting system
  • Practical Security Analysis of E-Voting Systems (2007)
  • The Application of I-voting for Estonian Parliamentary Elections of 2011 (2011)
  • Verifiable Internet Voting in Estonia (2014)
  • Security Analysis of the Estonian Internet Voting System (2014)
  • Log Analysis of Estonian Internet Voting 2013–2015 (2015)
  • Improving the verifiability of the Estonian Internet Voting scheme (2016)
  • Estonian Voting Verification Mechanism Revisited Again (2017)
  • On practical aspects of coercion-resistant remote voting systems (2019)
  • Planning the next steps for Estonian Internet voting (2020)
• Description of Estonian i-voting system
  • Internet voting in Estonia
  • General Framework of Electronic Voting and Implementation thereof at National Elections in Estonia (2017)
  • Statistics about Internet Voting in Estonia
  • Source code
• Verification report from the E2E-VIV project
  • The Future of Voting - End-To-End Verifiable Internet Voting (Complete Report, 2015)
  • Report for Non-technical Audiences
  • Expert Statements
• Other
  • European Union Members Share Advice on Cyber Security of Elections
    • Compendium on Cyber Security of Election Technology (2018)