XKCD: Voting software

Trust isn't just about engineering like it is for avionics or other high-reliability systems. It's also about independent verification, including by lay people. If it requires advanced cryptography or computer science knowledge to trust the election results.

I live in Canada where we do paper ballots everywhere. We also get same-night results on election day. They're just starting to experiment with vote tabulators, and this means that results come in faster now. In fact, in the latest Ontario provincial elections they had a declared winner 20 minutes after polls closed. Especially with tabulator machines I just don't get the point of electronic voting.

[0] Unless specialized designs are used explicitly in hardware and software, similar to those which are found in embedded industrial control systems, which removes these uncertainties to a large extent. But they are rarely used in practice because of its difficulties and cost.

As Bruce Schneier written in Cryptography Engineering,

One of the biggest differences between security systems and almost any other type of engineering is the adversarial setting. Most engineers have to contend with problems like storms, heat, and wear and tear. All of these factors affect designs, but their effect is fairly predictable to an experienced engineer. Not so in security systems. Our opponents are intelligent, clever, malicious, and devious; they’ll do things nobody had ever thought of before. They don’t play by the rules, and they are completely unpredictable. That is a much harder environment to work in.

Many of us remember the film in which the Tacoma Narrows suspension bridge wobbles and twists in a steady wind until it breaks and falls into the water [1]. It is a famous piece of film, and the collapse taught bridge engineers a valuable lesson. Slender suspension bridges can have a resonance mode in which a steady wind can cause the whole structure to oscillate, and finally break. How do they prevent the same thing from happening with newer bridges? Making the bridge significantly stronger to resist the oscillations would be too expensive. The most common technique used is to change the aerodynamics of the bridge. The deck is made thicker, which makes it much harder for the wind to push up and down on the deck. Sometimes railings are used as spoilers to make the bridge deck behave less like a wing that lifts up in the wind. This works because wind is fairly predictable, and does not change its behavior in an active attempt to destroy the bridge.

A security engineer has to take a malicious wind into account. What if the wind blows up and down instead of just from the side, and what if it changes directions at the right frequency for the bridge to resonate? Bridge engineers will dismiss this kind of talk out of hand: ‘‘Don’t be silly, the wind doesn’t blow that way.’’ That certainly makes the bridge engineers’ jobs much easier. Cryptographers don’t have that luxury. Security systems are attacked by clever and malicious attackers. We have to consider all types of attack.

[1] https://upload.wikimedia.org/wikipedia/commons/transcoded/f/...

Also, I am very sceptical of your claim that most of the problems belong to the last category. If it seems that way, I say that is because of observation bias. It's much easier to find evidence of voter intimidation than for fraudulent counting, even if both take place.

No, they don't, IME; many of the people most vocal about the vulnerability of voting machines are the exact same people active against voter intimidation and suppression.

Conversely, many of the people who have historically most backed moves to vulnerable voting machines are also the same people practicing voter intimidation and suppression.

Also, at least for national election, it's quite hard to manipulate such ballot wildly as there are heavily decentralized with a lot of individual polling places. It's quite hard to have a massive fraud on the ballot itself has you have fraud in hundreds of places.

Now with the voting machine, you have one or a few central points where it could be possible to take over the voting machines and manipulate the vote on a large scale.

Also, voting machine can be quite horrible. It's basically a computer that is only used once or twice a year. So it's likely that voting machines have a ton of CVE. Also, those are generally not very well made, with a lot of security holes, from physical attack to debug ports not removed, default passwords from the manufacturer not replace or bad configuration/lack of security in the software.

The only use case for a voting machine that I could see is the following:

Using a voting machine where when you cast your ballot, it prints a paper with the name of the candidate, after that you do it the 'old' way (envelope+ballot).

When counting it's now possible to compare the paper ballot and the electronic one and check if everything matches.

As a side effect, it reduces the quantity of paper required.

If by "most common" you mean "affecting most voters worldwide", it's possible a number of high-population countries with flagrant corruption in elections may bias this figure, but overall—particularly in, say, West Virginia (which I guess is what inspired this comic)—I would imagine the 3rd category would be the least prevalent, particularly as it's the easiest to detect.

There exists a formidable body of study describing the practices and theory required to write knowably-correct software, but the software engineering industry treats these ideas with utter derision. Even lighter-weight methods for knowably preventing broad classes of errors(e.g. Haskell-like type systems) are considered niche and pretentious. These opinions are mirrored by many CS programs, so most engineers wouldn’t have the slightest clue how to apply these methods, or even know that they exist, should they decide they were necessary.

With that kind of culture, what can we expect?

It's a rare case of a system its main customer does want to be able to break.

Now, of course we can make things that work. Airplanes and elevators are computing devices too, after all. But a working software is as expensive as a working airplane. People don't want their word processor to cost millions of dollars. OpenOffice is free, MS word is a few bucks, what do you expect?

To use the analogy of the plane designer, it'd be equivalent to building a consumer airliner that can handle flying through a warzone.

It's maddening how preventable a lot of this stuff is, but you can't convince anyone to listen to you because rules and processes aren't fun.

In the meantime, a junior programmer on my team just got an assignment (while I was on holiday) to add a feature to an old project she'd never worked on. The feature was described in three sentences, with a budget of "at most two days" as that is what the work was sold to the customer for.

I mean, it's rather hubristic to compare ourselves to those industries, we're closer to the handyman you hire to create a new door in some wall without telling him where exactly, all that matters is that it's done fast.

If every state contracts a handful (some may even contract a single one) of suppliers to crude the voting software, a bad actor that could compromise only one of those systems would have an enormous impact on an election. Contrast that with paper ballots, where an adversary would have to compromise dozens or hundreds of precincts, in-person, in order to have the same effect.

In terms of economics, having each precinct implement its own voting software (or contract uniquely) is not cost effective, nor would I trust small municipalities to be able to judge security.

It’s just too risky all around. Maybe one day when our software systems are better understood, or there are different security mechanisms, electronic voting might work. But not today.

Why is this different for software than for civil engineering? Fundamentally it’s not, except that people are willing to spend money on a new design for every bridge, and generally there is a collective awareness of threat models for bridges.

In the recent regional election of South Korea, there was a district where the winner won by a single vote. The runner-up appealed the decision, took the ballots to the overseeing committee, and the committee re-examined individual contested ballots and decided one of the ballots previously considered invalid should count for the second person, making it a tie and (according to some tie-breaking rules) changing the winner.[1]

You can't get that kind of transparency with voting software. It's worse in every way.

[1] Link (in Korean): http://news.jtbc.joins.com/html/712/NB11663712.html

Voting is fundamentally simple. People have been doing this for thousands of years, and it's intuitive how it should work. People mark ballots (in private); people count ballots (and then other people count the same ballots); the ballots aren't destroyed until the vote is finished; everyone calls each other and figures out what the total is. The amazing thing is anyone can look at what goes on and say "yep, that looks right", or "hey, I don't think they're supposed to do that…".

The whole thing needs a pretty significant human effort, but, again, people have been doing this for a long time, and large numbers of those humans can easily be volunteers. Also, that human effort is how you build a democracy. It is not a problem that needs to be solved.

As soon as you add software, you've added hundreds of layers of complexity to what was a very simple problem. You've turned it from a democratic, easy to follow system, to something that very few people can have anything to do with. It's like replacing letter writing with Facebook. Sure, you've made the surface act of communicating easier, but to do that you've added an ocean of complexity that nobody understands.

After every airplane crash, there's a major post-mortem. The root causes are ferreted out, as deeply as possible, in a blame-free way - and the regulations are updated and followed by the entire industry, enforced by laws.

What happens when your system has a 30 minute downtime? There's a meeting, someone suggests running your code through a linter or bumping log levels or adding another unit test, everyone high-fives and you wait until the next downtime - and that institutional knowledge doesn't leave the company, sometimes not even the team. Sometimes, it barely registers with the team members, who then quit the company and go and write voting software.

Part of it is that our industry is still relatively young - although, not that much younger than the aviation industry. But a bigger part is that for the most part, it's very strongly segmented, and most of those segments aren't responsible for people's lives.

1. For any piece of software, a person in the right position should be able to sabotage it. Ken Thompson's Turing acceptance piece (Reflections on trusting trust) showed a trivial example of sabotage...

2. It is REALLY difficult to diagnose software while it is running.

3. Risk vs. Reward. Planes have tremendous performance characteristics versus boats or cars. Elevators provide a means for disabled people to get to different levels on a building. But in terms of voting we're trading the security of paper ballots (which humans have spent centuries putting safety measures on ballot stuffing) for convenience.

4. The potential number bad actors with voting is high. While the number of people that want to alter a plane or elevator for nefarious reasons is hopefully limited.

5. Political legitimacy is a very important concept for governments. In democracies, their legitimacy is largely based on ballots. It is really bad for citizens to question the outcome of an election.

Voting software needs to solve adversarial distributed trust across hundreds of thousands of polling stations. That's way harder than distributing control across three cooperating, redundant avionics packages. Really, it's an unsolved problem in computer science, but that doesn't stop people from selling solutions...

Number 2 is the cost of failure.

The worst case scenario for avionics software is a plane crashes and everyone on the plane very publicly dies. An engineer is unlikely to be motivated to cause this on purpose, and if they do then everyone knows about it immediately.

The worst case scenario for voting software is a single engineer gets control over the political direction of the entire country, and nobody notices, ever. There's a ton of motivation to do this.

But In a vote, not everybody wants the same. As a mayor / senator / etc., I want as many votes as possible, and so do my opponents. You can't trust anybody, as the expected outcome is different for everyone.

You cannot do that with voting software. To verify the result of a software-based election, you would have to compare the vote counts the software reports with the actual vote counts. But if you knew the vote counts, you wouldn't need the software anymore.

There a proposals to get around this issue by storing each voter's decision so they can verify that their vote was counted properly. That would abolish the secret ballot, making it a horrible idea.

Even if there were a software-based voting system that could be verified by experts, it would almost certainly be too complicated to be verified by the general public.

But how do you trust they are reliable? How do you verify them? How do you verify the surrounding systems? It is a dead giveaway if planes start falling out of the sky that something is wrong. Not so when someone steals an election.

If you want a good password hash you don't go for a fast hash that can be implemented in hardware. You go for a really slow hash that is hard to compute. I think this worse is better approach applies with voting systems. You really don't want them to be efficient. Optimising for efficiency takes away some of their other good properties. Paper voting is incredibly inefficient compared with machines and that is why it is so appropriate.

Planes and elevators are not connected to an internet, unlike most voting machines, making them harder to hack into.

Also, when people hack into planes/elevators the hack will quickly get noticed and thus the exploit will get fixed pretty soon. With electronic voting machines the hack could remain undiscovered for years since there's no clear visible sign that the machine has been hacked.

In the case of a voting machine, who are you trusting? The state governments and some random government contractor. What are their incentives? What is their track record?

This is conjecture on my part, since real lives aren't on the line, I would also imagine that error checking isn't held up to to the same standards.

The algorithms required to do it have been invented, so in a sense technical problem and has already been solved. Look up "end to end verifiable voting". Turns out that Ken Thompson's "reflections on trust" don't apply to these systems: you can run them on utterly untrusted hardware. They use cryptography or course, and like a lot of cryptography (eg, zero knowledge proofs) it first looks magic, but when you take the time to understand it it's just very clever.

Which leads you to the first difficulty: we are talking something more more complex than public key encryption. It adds steps and costs. Inventing a user interface usable by ordinary voters that masks the underlying complexity is major challenge involving the both a lot of new software and new hardware. Still, it has been done. https://arxiv.org/abs/1504.07098

Which leads to the next difficulty. It's not at all obvious to the layman how those extra steps and costs these systems require solve the problem. In fact unless you have an analytical engineering type mind, understanding it may well be beyond you. Which is a problem, at least in Australia, because the people who run the electoral systems are bureaucrats who expertise lies in building a system out of 1000's of unreliable newbies in an unfamiliar role that somehow reliably and incorruptibly counts and collates votes to deliver a timely poll outcome. When you reflect on it, it's an amazing feat of human engineering. These people seem to be acutely aware of sorts of ways humans can go wrong and working around it. Unfortunately they are bloody hopeless at understanding how computer systems go wrong.

It worth reflecting on the difference. Human voting systems are most vulnerable to what computer people call "retail failures". Retail failure occur at or near the ballot box - people voting twice, ballot box stuffing, boxes going missing. It requires many small interventions involving many people. Once the boxes get to the counting room there are so many people watching the process fraud becomes much less likely. Computers remove that central oversight - the thing that does the counting becomes an opaque box. Failures at the back end are called a "wholesale failures" to use the voting lingo. If you aren't very careful, a wholesale failure can mean a single person (a programmer) changes a couple of lines of code to in a way that Ken Thompson's reflects of trust tells us can be undetectable, to alter the outcome of an election. Wholesale failures look completely different to retail failures, but can be even more damaging that rampant ballot box stuffing.

The voting systems developed in Australia weren't a technical failure. They were used in real elections, and did work. But they failed nonetheless because in the end they weren't deployed beyond a few test runs. The reason they weren't deployed is the people who ran the elections where given two choices - one by a commercials companies and the one I've described which was developed by cryptographers and engineers in conjunction which disability groups. The first was very pretty, had a slick UI, and came with ironclad commercial guarantees about their robustness from the suppler. The second was more complex, cost more, wasn't so pretty, and came with a through cryptanalysis done by experts which spelt out all the failure modes and their likelihood. If you are a bureaucrat used to working with people is used to making reliable systems by accumulating interlocking promises from said people and utterly unfamiliar with making systems reliable with mathematical proofs - which would you choose?

So they chose the commercial system for mass deployment (I think there were all from US suppliers), and of course in doing so utterly pissed off the very clever academics and engineers who built the home grown system. They were so pissed off that they broke the commercial system on the first night with a wholesale attack - not literally, but demonstrated how they could have hacked it to obtain any outcome they wanted, without the bureaucrats in charge knowing. https://theconversation.com/thousands-of-nsw-election-online... The bureaucrats responded to this activism by labelling it "great marketing" and threatening to prosecute the academics and engineers who proved the commercial system was insecure.

The process is very simple, and hard to manipulate, because the observers (from all sides) ensure it.

In aerospace or elevators, the experts say that what we have is really quite safe, although a determined adversary could potentially cause harm.

In voting machines, the experts say that what we have is fundamentally UNSAFE, and that a half-hearted effort from a bright college student could bring it to its knees.

That difference should DEEPLY concern the people who run elections.

The most important one (in my opinion) is the problem that the companies that sell voting machines aren't making enough money and their profits would be improved if enough county election boards were convinced (or required, though state or national legislation) to buy new systems.

Another very significant problem that electronic voting is attempting to address is that election officials are evaluated (to some extent) by the public based on what appears in the newspaper on just one or two days per year -- and THAT depends largely on how quickly results are reported. So a tool that takes 2 hours to report results will look much better for election officials than a tool that takes 48 hours, even if the second produces elections that are more trustworthy and there are 2-3 months before the new candidates actually need to take office.

Another problem is that existing methods using paper look "old-fashioned". A fancy system that takes video images of the voter's face to identify them and then allows them to vote from overseas using a cell phone may not be as reliable or secure as mailing in a paper ballot, but it sure FEELS modern.

I guess my point is that there are definitely reasons these machines are being used, but "improved security" or "transparence and thus confidence in the reported results" are not the motivating forces.

Not really sure about that.

The way I understand, most of the inefficiencies in paper-based voting are actually features, that make the process a) verifiable and trustworthy to anyone with most basic education, and b) prohibitively expensive to attack at scale. All voting machines seem to do is to reduce either of those. I obviously cannot prove it, but I strongly suspect that the paper implementation is overall cheaper than any alternative electronic implementation comparable in trustworthiness and security guarantees.

Maybe when we'll have a colony in the Alpha Centauri system, then we can revisit electronic voting. Right now, there's no need for it.

Fundamentally, voting is a hard problem that looks like an easy problem precisely because the incentives to break it are so high.

In the past various forms of "vote for X or I will shoot" have happened. By having anonymous votes we ensure that everybody can say "I voted for X", and nobody will know they voted for Y.

Think about the development of heavier-than-air flight. It was a thing for 50 years or so before commercial flights became common, and they had the collective world's genius spurred on by 2 World Wars to advance the field.

Entrusting something as critical and nigh-sacred as our elections to such a provably immature and insecure as modern voting machines, and there's little impulse to remedy the situation right now.

He's an ex-NASA engineer, so he's perfectly aware of that.

> Writing robust software is possible, but nobody wants to pay for it when it isn't safety-critical.

That's the core reason why the field of software engineering is bad at what it does, while aviation isn't. Somehow, aviation can get people to pay for doing the job right, while software cannot.