October 19, 2017

Blockchains and voting

I’ve been asked about a number of ideas lately involving voting systems and blockchains. This blog piece talks about all the security properties that a voting system needs to have, where blockchains help, and where they don’t.

Let’s start off a decade ago, when Daniel Sandler and I first wrote a paper saying blockchains would be useful for voting systems. We observed that voting machines running on modern computers have overwhelming amounts of CPU and storage, so let’s use it in a serious way. Let’s place a copy of every vote on every machine and let’s use timeline entanglement (Maniatis and Baker 2002), so every machine’s history is protected by hashes stored on other machines. We even built a prototype voting system called VoteBox that used all of this, and many of the same ideas now appear in a design called STAR-Vote, which we hope could someday be used by real voters in real elections.

What is a blockchain good for? Fundamentally, it’s about having a tamper-evident history of events. In the context of a voting system, this means that a blockchain is a great place to store ballots to protect their integrity. STAR-Vote and many other “end-to-end” voting systems have a concept of a “public bulletin board” where encrypted votes go, and a blockchain is the obvious way to implement the public bulletin board. Every STAR-Vote voter leaves the polling place with a “receipt” which is really just the hash of their encrypted ballot, which in turn has the hash of the previous ballot. In other words, STAR-Vote voters all leave the polling place with a pointer into the blockchain which can be independently verified.

So great, blockchain for the win, right? Not so fast. Turns out, voting systems need many additional security properties before they can be meaningfully secure. Here’s a simplified list with some typical vocabulary used for these security properties.

  • Cast as intended. A voter is looking at a computer of some sort and indicates “Alice for President!”, and our computer handily indicates this with a checkbox or some highlighting, but evil malware inside the computer can silently record the vote as “Bob for President!” instead. Any voting system needs a mechanism to defeat malware that might try to compromise the integrity of the vote. One common approach is to have printed paper ballots (and/or hand-marked paper ballots) which can be statistically compared to the electronic ballots. Another approach is to have a process whereby the machine can be “challenged” to prove that it correctly encrypted the ballot (Benaloh 2006, Benaloh 2007).
  • Vote privacy. It’s important that there is no way to identify a particular voter with how they voted. To understand the importance of vote privacy, consider a hypothetical alternate where all votes were published, in the newspaper, with the voter’s name next to each vote. At that point, you could trivially bribe or coerce people to vote in a particular way. The modern secret ballot, also called the Australian ballot, ensures that votes are secret, with various measures taken to make it hard or impossible for voters to violate this secrecy. When you wish to maintain a privacy property in the face of voting computers, that means you have to prevent the computer from retaining state (i.e., keeping a private list of the plaintext votes in the order cast) and you have to ensure that the ciphertext votes, published to the blockchain, aren’t quietly leaking information about their plaintext through various subliminal channels.
  • Counted as cast. If we have voters taking home a receipt of some sort that identifies their ciphertext vote in the blockchain, then they also want to have some sort of cryptographic proof that the final vote tally includes their specific vote. This turns out to be a straightforward application of homomorphic cryptographic primitives and/or mixnets.

If you look at these three properties, you’ll notice that the blockchain doesn’t do much to help with the first two, although they are very useful for the third.

Achieving a “cast as intended” property requires a variety of mechanisms ranging from paper ballots and spot challenges of machines. The blockchain protects the integrity of the recorded vote, but has nothing to say about its fidelity to the intent of the voter.

Achieving a “vote privacy” property requires locking down the software on the voting platform, and for that matter locking down the entire computer. And how can that lock-down property be verified? We need strong attestations that can be independently verified. We also need to ensure that the user cannot be spoofed into running a fake voting application. We can almost imagine how we can achieve this in the context of electronic voting machines which are used exclusively for voting purposes. We can centrally deploy a cryptographic key infrastructure and place physical controls over the motion of the machines. But for mobile phones and personal computers? We simply don’t have the infrastructure in place today, and we probably won’t have it for years to come.

To make matters worse, a commonly expressed desire is to vote from home. It’s convenient! It increases turnout! (Maybe.) Well, it also makes it exceptionally easy for your spouse or your boss or your neighbor to watch over your shoulder and “help” you vote the way they want you to vote.

Blockchains do turn out to be incredibly helpful for verifying a “counted as cast” property, because they force everybody to agree on the exact set of ballots being tabulated. If an election official needs to disqualify a ballot for whatever reason, that fact needs to be public and everybody needs to know that a specific ballot, right there in the blockchain, needs to be discounted, otherwise the cryptographic math won’t add up.

Wrapping up, it’s easy to see how blockchains are an exceptionally useful primitive that can help build voting systems, with particular value in verifying that the final tally is consistent with the cast ballot records. However, a good voting system needs to satisfy many additional properties which a blockchain cannot provide. While there’s an intellectual seduction to pretend that casting votes is no different than moving coins around on a blockchain, the reality of the problem is a good bit more complicated.

Security against Election Hacking – Part 2: Cyberoffense is not the best cyberdefense!

State and county election officials across the country employ thousands of computers in election administration, most of them are connected (from time to time) to the internet (or exchange data cartridges with machines that are connected).  In my previous post I explained how we must audit elections independently of the computers, so we can trust the results even if the computers are hacked.

Still, if state and county election computers were hacked, it would be an enormous headache and it would certainly cast a shadow on the legitimacy of the election.  So, should the DHS designate election computers as “critical cyber infrastructure?”

This question betrays a fundamental misunderstanding of how computer security really works.  You as an individual buy your computers and operating systems from reputable vendors (Apple, Microsoft, IBM, Google/Samsung, HP, Dell, etc.).  Businesses and banks (and the Democratic National Committee, and the Republican National Committee) buy their computers and software from the same vendors.  Your security, and the security of all the businesses you deal with, is improved when these hardware and software vendors build products without security bugs in them.   Election administrators use computers that run Windows (or MacOS, or Linux) bought from the same vendors.

Parts of the U.S. government, particularly inside the NSA, have “cyberdefense” teams that analyze widely used software for security vulnerabilities.  The best thing they could do to enhance our security is notify the vendors immediately about vulnerabilities, so the vendors can fix the bugs (and learn their lessons).   Unfortunately, the NSA also has “cyberoffense” teams that like to save up these vulnerabilities, keep them secret, and use them as weak points to break into their adversaries’ computers.  They think they’re so smart that the Russkies, or the Chinese, will never be able to figure out the same vulnerabilities and use them to break into the computers of American businesses, individuals, the DNC or RNC, or American election administrators.  There’s even an acronym for this fallacy: NOBUS.  “NObody But US” will be able to figure out this attack.

Vulnerability lists accumulated by the NSA and DHS probably don’t include a lot of vote-counting software: those lists (probably) focus on widely used operating systems, office and word-processing, network routers, phone apps, and so on.  But vote-counting software typically runs on widely used operating systems, uses PDF-handling software for ballot printing, network routers for vote aggregation.  Improvements in these components would improve election security.

So, the “cyberdefense” experts in the U.S. Government could improve everyone’s security, including election administrators, by promptly warning Microsoft, Apple, IBM, and so on about security bugs.  But their hands are often tied by the “cyberoffense” hackers who want to keep the bugs secret—and unfixed.  For years, independent cybersecurity experts have advocated that the NSA’s cyberdefense and cyberoffense teams be split up into two separate organizations, so that the offense hackers can’t deliberately keep us all insecure.   Unfortunately, in February 2016 the NSA did just the opposite: it merged its offense and defense teams together.

Some in the government talk as if “national cyberdefense” is some kind of “national guard” that they can send in to protect a selected set of computers.  But it doesn’t work that way.  Our computers are secure because of the software we purchase and install; we can choose vendors such as Apple, IBM, Microsoft, HP, or others based on their track record or based on their use of open-source software that we can inspect.  The DHS’s cybersecurity squad is not really in that process, except as they help the vendors improve the security of their products.  (See also:  “The vulnerabilities equities process.”)

Yes, it’s certainly helpful that the Secretary of Homeland Security has offered “assistance in helping state officials manage risks to voting systems in each state’s jurisdiction.”  But it’s too close to the election to be fiddling with the election software—election officials (understandably) don’t want to break anything.

But really we should ask: Should the FBI and the NSA be hacking us or defending us?  To defend us, they must stop hoarding secret vulnerabilities, and instead get those bugs fixed by the vendors.

Security against Election Hacking – Part 1: Software Independence

There’s been a lot of discussion of whether the November 2016 U.S. election can be hacked.  Should the U.S. Government designate all the states’ and counties’ election computers as “critical cyber infrastructure” and prioritize the “cyberdefense” of these systems?  Will it make any difference to activate those buzzwords with less than 3 months until the election?

First, let me explain what can and can’t be hacked.  Election administrators use computers in (at least) three ways:

  1. To maintain voter registration databases and to prepare the “pollbooks” used at every polling place to list who’s a registered voter (for that precinct); to prepare the “ballot definitions” telling the voting machines who are the candidates in each race.
  2. Inside the voting machines themselves, the optical-scan counters or touch-screen machines that the voter interacts with directly.
  3. When the polls close, the vote totals from all the different precincts are gathered (this is called “canvassing”) and aggregated together to make statewide totals for each candidate (or district-wide totals for congressional candidates).

Any of these computers could be hacked.  What defenses do we have?  Could we seal off the internet so the Russians can’t hack us?  Clearly not; and anyway, maybe the hacker isn’t the Russians—what if it’s someone in your opponent’s political party?  What if it’s a rogue election administrator?

The best defenses are ways to audit the election and count the votes outside of, independent of the hackable computers.  For example,

[Read more…]