End-To-End Verifiable Internet Voting


End-To-End Verifiable Internet Voting (E2E-VIV)
For the Rest of Us
By Jim Soper
January 25, 2016
Abstract

A team of highly respected experts asked the question. what would a reliable Internet voting system look like?
The short answer is that it must be:

  • secure end-to-end, using cryptography (explained below);
  • easy to use, transparent, and totally checkable;
  • resilient – able to recover when things go wrong;
  • developed using the most rigorous development and testing techniques available;
  • proven to work very well in normal polling places before putting it on the Internet.

They also ask, is such a system doable? The short answer is: they don’t know. Several very difficult problems have no foreseeable solution.

The report also states that none of today’s Internet voting systems meet these requirements. They should not be used in government elections.

Note: “End-to-end” (E2E) voting means using a system that is “secure” (encrypted and checked) at every step, end-to-end. “Verifiable” (E2E-V) means that the voters and the public can check all phases of the election. E2E-VIV is E2E-Verifiable using Internet Voting. Details are below.


Links

https://www.usvotefoundation.org/e2e-viv/summary
https://www.usvotefoundation.org/E2E-VIV

Introduction

In December, 2013, the U.S. Vote Foundation (USVF) started the E2E-VIV Project to explore what a reliable Internet voting (IV) system should look like, and whether or not such a system is doable. In July, 2015. they published a 116 page report titled “The Future of Voting: End-To-End Verifiable Internet Voting, Specification and Feasibility Assessment Study”. The contributors include over a dozen world-class computer security and voting system experts, ten prominent public election officials, and recognized specialists in disability, usability, auditing, testing, and legal issues. The study was very extensive. It included both IV optimists, and skeptics. The report is extremely important, and thorough.

The E2E-VIV team has published a summary, and a series of more in-depth reports (links are above). This version attempts to digest many of the salient points of the complete report into a few pages, to explain what E2E-VIV means, and to highlight the its conclusions.

Throughout are 2 and 3 digit numbers or letters. For example “1.2.3”. These refer to section numbers in the full report. Also, there are often key words, such as “denial of service”, that you can use to search through the E2EVIV_full_report.pdf file to find more information on certain topics.

We start off by defining a few important terms. Then we explain what E2E-VIV means. Then comes a discussion of important problem areas. Towards the end are the requirements for an IV system, feasibility of getting there, recommendations, and conclusions.


Terms
Encryption

We shall start with “encryption”. This is the process of scrambling the letters in a “message”, such as a ballot, so as to make the message unreadable to anyone who does not know exactly how to unscramble it. Aside from knowing the steps involved, encryption usually requires a secret “key”, which works something like a password, only both the scrambler and the unscrambler both know what the key is. When you send information from your browser via a “secure” connection across the Internet to any website that uses the https protocol, the information is encrypted before your browser sends it, and unencrypted at the other end. This is the root concept of end-to-end security. Cryptography, BTW, is the study of how to do encryption. For more details, see Wikipedia, and Chapter 5 of the complete report, “CRYPTOGRAPHIC FOUNDATIONS“. That chapter starts off by saying that “No existing E2E-VIV system or E2E-V protocol fulfills the [cryptographic] requirements set forth in this report.

Malware

“Malware” is malicious, malevolent software, usually in the form of a virus, worm, trojan horse, spyware, etc. The program’s intent is to do something bad on and/or to your computer, usually without your knowing it.

Denial of Service (DoS) Attacks

There is another type of attack across the Internet that involves sending billions of requests towards a website, keeping it so busy that it cannot respond properly anymore to anybody. We call this a “denial of service” (DoS) attack. It would most likely be directed at an elections website, effectively making it impossible to vote using the Internet. Discussions of “deployment” and “availability” in chapters 6, 7 and 8 explore various ways of possibly mitigating this threat. Dr. Jefferson and colleagues are more skeptical: “all E2E-VIV systems are vulnerable to network attacks that can result in disenfranchising a large number voters with no way of even measuring how many were affected. There is no fundamental defense against DDoS attacks.” (A.2.4, pg 116)


End-To-End Voting Systems
End-to-End (E2E) Voting

End-to-end (E2E) voting means voting on a system that is “secure” (encrypted and checked) end-to-end. More precisely, E2E encompasses all the steps of voting, including the voter signing in, then receiving, filling out, and casting (sending) the encrypted ballot, and having it received, recorded, counted and reported correctly at the elections office. On the Internet, it means that the voter’s computer, the central election computer, and the transmission between them of data, including the digital ballot, must be secure. By “secure”, we do not mean that hacking can be prevented, but that if it happens, it will be detected. Fixing the damage is another difficult problem.

Note: Your smart phone is also a computer. Every time we refer to the voter’s “computer”, it may be a desktop, laptop, tablet, or smart phone. It is the average voter’s computer that is the most vulnerable part of the entire system, and is likely to remain so, as most computer users are not computer-security savvy (4.2.1).

End-to-End Verifiable (E2E-V) Voting

After the E2E, the report adds on a V, to get E2E-V. The V stands for “verifiable”.

end-to-end verifiable is defined as follows. First, every voter can check that his or her ballot is cast and recorded as he or she intended. Second, anyone can check that the system has accurately tallied all of the recorded ballots.

The intent here is for the public to be able to verify, or have verified (7.5.2), each of the steps in an election. This includes the eight steps shown in the curves on the left side of the report’s title page:

  • Set Up Election
  • Distribute Ballots
  • Cast Votes as Intended
  • Record Votes as Cast
  • Count Votes as Recorded
  • Verify Votes Recorded as Cast
  • Announce Results
  • Allow Public to Verify Tally

More briefly, we must be able to verify that the votes were “Cast as intended; recorded as cast; and counted as recorded.” The last point is important because it is not enough to show that a particular vote was recorded correctly, but that all the votes were recorded correctly, and that the totals are correct. A deficient system could report a vote accurately back to a specific voter, when asked, but do something else with it when it comes time to compute and report totals.

Usually, we check these eight steps with some kind of paper trail – mainly with paper ballots, and various kinds of audit logs (4.1.5). Computer scientists have created experimental voting systems that use cryptography to ensure that data passed from one step to the next did not change (3.3). Several of these E2E-V systems include a means for the voter, for example, to go to a website to confirm that their vote was recorded correctly by the central tabulator. The real trick here is to allow the voter to do so, while maintaining ballot secrecy, so they cannot show their boss or a vote buyer what their actual votes were (“coercion resistance”). The report calls this ballot secrecy “receipt freedom” (3.4.1, 4.1.1, 4.2.1, and page 45). We haven’t figured out how to do this securely: “No usable E2E-VIV protocol in existing scientific literature has receipt freedom when the voting computer is untrusted.

End-to-End Verifiable Internet Voting (E2E-VIV)

Onto the E2E-V we add Internet Voting (IV), to get E2E-VIV. The question becomes, how to we get a fully verifiable voting system onto the wild west that is the Internet? There are many challenges here; the most obvious of which is security. By connecting the system to the Internet, you not only expose it to hackers world wide, but you have the added problem that the voter’s computer is probably not secure (see “malware”). This exposes that computer to all kinds of hacks, including manipulation of the vote before it gets encrypted. Fake voting apps could appear to be doing the right thing, but behind the screen, something else is being sent to the central tabulator, or not at all.

Note: Using information collected about users over the Internet, a malware or denial of service (A.2.iii) attack can be targeted towards one group of unfavored voters’ computers, and not others.

Sections 3 and 4 explain E2E-VIV more in depth starting on page 18.


Problem Areas
Usability

We won’t go into detail here, but the additional steps involved in you checking that the system recorded your vote correctly are themselves complicated, making verification by the voter problematic, at least with current E2E-V systems. See 3.4.5, 4.1.2. 8.1.3, and the “Usability Study” report.

Dispute Resolution

Voters being able to check their vote leads to another rats’ nest of problems. If the voter claims that their vote was not correct, how do they prove it, if they can’t show how they voted? They could be trying to sabotage an unhappy election. Or there could really be a problem. In which case, how many “problems” have to occur before you overturn an election? One? Ten? A hundred? A thousand? For more on this question, see 3.4.3 and “dispute resolution”.

Error Detection (Software Independence)

There is an importance nuance in what we mean by end-to-end verifiable. Some E2E-V systems can only detect if the results are not correct:

A voting system is software independent if an undetected change or error in its software cannot cause an undetectable change or error in an election outcome.” In theory, software independent systems can detect an anomaly in the totals, but “E2E-VIV protocols do not prevent such errors“.
Error Recovery (Strong Software Independence)

The report insists that mere detection is not good enough for important elections. When things go wrong, we must be able to figure out what the actual results should be. I call this resilience. The report calls it “strong software independence”:

“A voting system is strongly software independent if, in addition to being software independent, it enables a detected change or error in an election to be corrected without re-running the entire election. A requirement contained in this report insists that any future E2E-VIV system must be strongly software independent.” (3.4.4) And again, “Vote tabulation must be strongly software independent; it must be possible to detect any compromise of the election system software that causes a change in the tally, and to reconstruct a correct tally from some record in the event of such a compromise.” (pg 35).

In other words, the system must know exactly what went wrong, which votes are incorrect, and how to correct the election. If you don’t, in some cases, you would have to redo the entire election.

Note: Correcting for bad results is difficult to do.

Public Verification

With the eighth step, the system must “Allow Public to Verify Tally“. Basically this means that officials must give members of the public all the raw data, the encrypted ballots, and the necessary steps, the algorithm, to convert those encrypted votes into checkable totals. Everything must match. No existing E2E system does this. See 7.5.2.

Rigorous Software Engineering

Chapter 7 notes that software for “aeronautics, avionics, biomedical, nuclear energy, and spacecraft applications, to name a few, must conform to stringent development and certification standards.” This is because the cost of failure can be catastrophic. “One might argue that election systems are at least as important, especially if they are to be used for national public elections.” With the fate of the government at stake, it becomes a national security issue. For this reason, chapter 7 goes into extensive detail about how to methodically develop “mission-critical” software that is much more secure and solid. This takes much more work, time, and money, but the alternative is to risk watching a Internet-based election systems fail spectacularly, taking important elections down with it. Current IV systems cut way too many corners, and will not hold up when the stakes are high.


Requirements and Recommendations
Requirements

The report lays out many requirements for an E2E-VIV voting system. Indeed, it uses the word “must” over 300 times. I’ve grouped some of their requirements into three categories.

Any voting system should:

  • use rigorous software engineering techniques, including extensive testing;
  • not be so complex that an elections department would have difficulty installing and using it securely (8.1.4 and 8.1.5);
  • prevent insertion of extra ballots into the system (3.4.2)
  • be usable and accessible to voters with disabilities using “universal design” techniques;
  • allow “open public review of the entire election system and its operation, including all documentation, source code, and system logs” (no commercial system does this);
  • allow anybody to test the entire election system, with no legal restrictions;
  • allow the public to check that all the ballots were recorded and counted correctly;
  • provide evidence that the running software actually corresponds to the open source code, and has not been corrupted after installation;

An E2E-Verifiable voting system must:

  • have strong software independence – problems are correctable;
  • allow the voter to easily check that their ballot was recorded and counted correctly (difficult);
  • … without being able to show thsir votes to anybody else: “coercion resistance” (difficult);
  • allow for large-scale “dispute resolution” when voters claim that the system got their vote wrong (difficult);

An E2E-Verifiable Internet Voting system must:

  • allow that only eligible voters to vote (difficult, especially without a digital ID system);
  • resist massive coordinated “denial of service” (DoS) attacks on the central system (difficult);
  • resist DoS attacks on voter’s computers (difficult, A.2.iii);
  • prevent viruses or fake voting software from manipulating or blocking votes on the voters’ computers without detection (difficult, A.2.iii);
  • run correctly and securely on a wide variety of computers and web browsers;

It should be clear that putting an E2E-V system on the Internet poses additional problems. “there are many open engineering issues associated with actually building, running, and maintaining an E2E-VIV system“. For more, see 9.2.2 and A.2.4.  Sections 8.1.1 and A.2.4 list some of the difficult issues noted above.

In addition, the report stresses that we should not even attempt to put E2E-Verifiable voting systems onto the Internet, until we can get them working very well in a normal polling place. Because of several difficult requirements, we’re not even close.

Feasibility

Chapter 8 asks the question – is an E2E-VIV system doable? It states that

All technical aspects—engineering for correctness and security, design and engineering for usability, availability, operational—are feasible, though difficult. Feasibility of the non-technical  [political, financial, legal, etc.] aspects ranges from unknown to entirely possible.

The report continues

The politics and public acceptance of Internet voting are open questions. We believe that only the disciplined, transparent, scientific, and practical pursuit of E2E-VIV can convince the public that E2E-VIV systems deserve their trust.

In other words, IF we commit the resources to do all of it right, such voting systems might be trustworthy.

Report Recommendations

“The five key recommendations of this report are:
1) Any public elections conducted over the Internet must be end-to-end verifiable.

2) No Internet voting system of any kind should be used for public elections before end-to-end verifiable in-person voting systems have been widely deployed and experience has been gained from their use.

3) End-to-end verifiable systems must be designed, constructed, verified, certified, operated, and supported according to the most rigorous engineering requirements of mission- and safety-critical systems.

4) E2E-VIV systems must be usable and accessible.

5) Many challenges remain in building a usable, reliable, and secure E2E-VIV system. They must be overcome before using Internet voting for public elections. Research and development efforts toward overcoming those challenges should continue.
It is currently unclear whether it is possible to construct an E2E-VIV system that fulfills the set of requirements contained in this report. Solving the remaining challenges, however, would have enormous impact on the world.”

Conclusions

Using the current untested and unverified systems opens the door to wholesale election manipulation or failure. Aggressive early adoption of election technology must be tempered by a clear understanding that voters’ trust in their elections is hard-won and easily lost.

Building a usable, reliable, and secure Internet voting system may be impossible. Solving the remaining challenges, however, would have enormous impact on the world. Continued research and development efforts must be conducted transparently, with all results and artifacts open to peer review. Internet voting systems, including E2E-VIV systems, must not be deployed in public elections before all the key security problems are resolved.


Further Reading

For more general discussions of Internet voting, you may want to look at:
https://www.verifiedvoting.org/resources/internet-voting/,
https://countedascast.org/internet-voting-risks/,
https://countedascast.org/internet-voting-risks/internet-voting-reading-list/,
and the more general
https://en.wikipedia.org/wiki/Electronic_voting

Author

The author of this article, Jim Soper, is a computer programmer and 11-year election integrity advocate. He has also lived abroad for 17 years, so remote voting is a personal issue for him. He would like to see IV happen, but only when it’s done right. The stakes are too high. You can reach him through his website, www.CountedAsCast.org.

%d bloggers like this: