Alex Halderman testifying before the Senate Intelligence Committee
This morning, my childhood best friend Alex Halderman testified before the US Senate about the proven ease of hacking electronic voting machines without leaving any record, the certainty that Russia has the technical capability to hack American elections, and the urgency of three commonsense (and cheap) countermeasures:
- a paper trail for every vote cast in every state,
- routine statistical sampling of the paper trail—enough to determine whether large-scale tampering occurred, and
- cybersecurity audits to instill general best practices (such as firewalling election systems).
You can watch Alex on C-SPAN here—his testimony begins at 2:16:13, and is followed by the Q&A period. You can also read Alex’s prepared testimony here, as well as his accompanying Washington Post editorial (joint with Justin Talbot-Zorn).
Alex’s testimony—its civic, nonpartisan nature, right down to Alex’s flourish of approvingly quoting President Trump in support of paper ballots—reflects a moving optimism that, even in these dark times for democracy, Congress can be prodded into doing the right thing merely because it’s clearly, overwhelmingly in the national interest. I wish I could say I shared that optimism. Nevertheless, when called to testify, what can one do but act on the assumption that such optimism is justified? Here’s hoping that Alex’s urgent message is heard and acted on.
Follow
Comment #1 June 21st, 2017 at 6:00 pm
Is there any organization lobbying for this kind of voting sanity on a consistent basis (rather than an op-ed which might just be forgotten about tomorrow)? I’ve been meaning to write my state legislator about this for a while, and I think it would be nice to include any information about something like that, so he would have someone to follow up with if he was interested in taking action on this.
Comment #2 June 21st, 2017 at 6:07 pm
Ah, I missed the link to the National Election Defense Coalition: https://www.electiondefense.org . I guess that’s close to what I’m looking for.
Comment #3 June 21st, 2017 at 6:09 pm
I remember when I heard Trump question whether the election results will be legitimate I thought this would have a chance of having a positive side-effect by increasing the amount of attention that people give to the problem of insecure voting machines. How much was that a factor in enabling Alex Halderman to make a statement before Congress about this issue? How much do you think that will influence how policymakers respond to his proposal?
Comment #4 June 21st, 2017 at 6:48 pm
In New Zealand, computers are controlled by input.
In Soviet America, computers are controlled by Putin.
Comment #5 June 21st, 2017 at 9:01 pm
Har har har! Only Americans can think of basing their voting system on electronic machines. After this Trump clown you have elected, you officially transitioned from a democracy to an idiocracy. I hope for you that you manage to kick The Clown out of office ASAP, change the voting system to paper and drop the majority vote for a proportional one. Then you’ll be back to Democracy. Good luck.
Comment #6 June 21st, 2017 at 9:13 pm
Itai #3: I don’t actually know how the experts who testify before Congressional subcommittees get chosen (does anyone here?). Those who currently control Congress lying awake at night, bothered by pangs of intellectual consistency, doesn’t rank high on my list of hypotheses. All the same, yes, the very fact that Alex was called to testify is a hopeful sign that there’s still some unextinguished spark of rationality somewhere in the bowels of the system.
Comment #7 June 22nd, 2017 at 5:05 pm
This is an excellent idea that could potentially instill some trust into our democratic institutions. Provided, of course, that it can be implemented in a non-partisan way.
Comment #8 June 23rd, 2017 at 1:20 am
But why is it so difficult to design and build a hack-proof system of EVMs?
I have no interest in this matter, but even just 10 minutes of pondering produced this solution:
A machine having a special processor of very very severly limited functionality; a very tiny OS which is so tiny that its entire functionality can be machine-verified 100%; input access to the OS (including for the task of preparing a machine for an election, candidates’ names, etc.) only via a single mechanical means which has independent non-electronic existence after programming—viz. special-purpose punch cards, output access only via one mechanical means (punching machine).
At least the booth EVM can this way be made fully secure. That’s what I believe. (Correct me if I am wrong.)
Hacking can now occur only at the stage of collection of results—say from the different booths to a county or from many counties to a state election seat, etc. However, if we adopt the principle that the only communication with any electronic machine (or from one machine to another machine) can only be made via only mechanical and persistent means (such as paper tapes), the system _can_ be made safe.
Systems become susceptible to attack only when they acquire a complexity of composition beyond a certain level. Purely mechanical production systems (before the age of robots and FMS) had been producing machines and cars for decades, without ever getting hacked. And, what is necessary for elections is a task less complex than that of a car assembly line.
Anyway, the solution that would work is so obvious that the only question which strikes me is this: what forces lead the responsible people from not adopting them—and, from computer engineers from advocating these simplest electro-mechanical sort of solutions.
Just 2 cents. As I said, the matter does not interest me. But as an ordinary citizen of a democratic country (India), I do appreciate the fact that engineers and scientists are highlighting these issues. That is important.
Best,
–Ajit
Comment #9 June 23rd, 2017 at 5:06 am
Hi Scott,
Given the current dire political predicament in the U.S., and the chasm within the electorate that has been (re?)discovered, what do you conjecture a post-Trump America (assuming one still exists, of course) will look like? Do you think it’s likely that the U.S. will continue its downward spiral until democracy no longer exists? Do you see any plausible road to recovery? Or do you think the country will eventually fall apart in some sense, as a result of the dramatic “cultural” divide within the populace?
P.S.: Long time lurker, first time commenter. The blog is awesome, you’re awesome, and I look forward to many more blog posts! 🙂
Comment #10 June 23rd, 2017 at 9:07 am
Ajit #8: My guess is that, if you spent more than 10 minutes thinking about it—as a bunch of smart people actually did—in order to make your minimalist EVM as truly hack-proof as possible, you’d end up reinventing the concept of the EVM printing out a paper receipt that’s then dropped into a box, which is exactly what’s being advocated here.
Note that even a special-purpose chip can be hacked in many ways, including by someone surreptitiously opening the voting machine and swapping it out for another chip (something Alex and his students demonstrated the ability to do in about 10 seconds with real voting machines). And in practice, the functionality that people want here—graphical user interfaces, ability to program the same machine with different races, etc.—is always pushing them toward Turing-universality. That leads us to the principle that the voter simply shouldn’t have to trust whatever’s in the machine: the machine can help them vote, but the security of the vote needs to be guaranteed by something visible and external to it.
Comment #11 June 23rd, 2017 at 9:21 am
WITCN #9: I’d rather not have to speculate about such matters. Even if one agrees that the dissolution of the US, a second Civil War, the replacement of our system by an explicit autocracy, etc. are still rather wild and remote possibilities for the foreseeable future, I think a reasonable person would have to say that the probabilities for all these events shot way up in the last two years—more sharply than the same reasonable person could likely have predicted beforehand. If you know Asimov’s Foundation series, Trump is the Mule. Unfortunately, the whole point of that series was to illustrate the futility of “scientifically” predicting the future! So it’s fortunate that, unless we’re completely pure utilitarians (which no one is or has ever been, in practice), we don’t need to know the future of civilization in order to know our own moral obligations right now.
Comment #12 June 23rd, 2017 at 10:27 am
Scott #10:
Thanks for responding.
Ummm… No. What you say in your reply #10 is not what I had in mind; it is not something I would advocate. For instance, I did indicate that no matter what the specifics of the design, at each stage, the input and output must exclusively be only mechanical, and that each stage should independently produce a persistent record (such as a punched card) of both its inputs and outputs for later verification (whether 100% or statistically sampled).
I seem to already have spent more than 10 minutes on it, haven’t I?… So, OK. Here’s my proposal.
Let me think more about it, and come up with a concrete design or two, and send some documentation about it by email directly to Alex, with a cc to you. I would do that if and only if Alex would take my suggestions seriously enough to go through the (brief) documentation, and try to think of all possible attacks it is susceptible to, and let me know. I will then revise it, and send the revision, though I will keep the revisions down to only a few iterations (say fewer than five, to get the proposal going). If that’s OK by you two, let me know, say by reply at this blog, and I will soon begin work on it (though can’t commit time-frames—am too busy, and this is not one of my primary fields of interest).
Speaking of right this moment, I am looking forward to having a delicious dinner, and so must drop this conversation right where it is, but before I sign off for the time being, here are a few further notings.
If a chip can be surreptitiously replaced within 10 seconds, why not dump the electronic circuit part of it into a block of cold-setting resin at the time of manufacture? say with a couple of sprinklings of that dust of RFID into the resin (circuit-wise completely independent) such that each block can be non-destructively proded for its identity any time you desire? … If the public wants a simple visual interface, why must it be a GUI (on a computer)? Why can’t it be a color printout stuck in a non-replaceable way (and with procedural checks thrown in to ensure that it was not replaced) on to the very voting module of the EV System itself? In India, since a lot of our population is illiterate, we manage to pull through our elections using even graphical symbols for parties/independent candidates. These are simply B&W printed lists that are stuck next to the EVM buttons. They work. And, coming to the American public, even if it insists on only a HD GUI on an electronic monitor/computer display, OK, fine. Give them that. Just make sure to physically isolate it completely (right from their immediate power-sources) from the EVM’s voting module proper. By EVM’s voting module, I mean a counter, really speaking. The punching machine to specify the vote on to a punching card would be mechanically and physically separate.
As to the electronic parts, my design would rely on the idea that whatever I program in C++, it can, in principle, be produced in pure hardware, without a single software component to it.
… Anyway, I realize I’ve begun getting into more details than can make sense to you (or anyone else). So let me stop here, and await Alex’s and your nod. If both of you—and particularly, Alex—agrees, I will write a documentation on a proposed system or two that is practical enough, and, of course, safe enough.
Thanks for highlighting this issue itself though.
Bye for now, and take care,
–Ajit
PS: I will check back tomorrow (say 24 hours later) or later. But, yes, I am willing to take this as a challenge—I mean, in a positive spirit. And I think as a good engineer (that’s what I imagine myself to be) I should be able to meet it—even if the first version or two may not be all that safe, in the sense, you know, it always helps to have another pair of eyes. And it would be beyond wonderful if those happen to come from groups like Alex’s (not to mention the general public at large). OK. Enough is enough. Bye, really, for now.
Comment #13 June 23rd, 2017 at 9:49 pm
Ajit #12: I think you’re trying to solve a political problem with a technical solution. This sometimes works, but only if you realize that the problem you have is a political one. I’m not very well informed about this stuff, but I think the problem is NOT coming up with a perfect design. The problem is that the current laws don’t mandate even the most basic precautions. There is no paper trail. The source code is secret. You have things like this this:
https://www.schneier.com/blog/archives/2015/04/an_incredibly_i.html
This was used in 3 presidential elections!
Comment #14 June 24th, 2017 at 1:14 am
Thanks Scott for posting about this. Paper trail is necessary, and Alex’s testimony is very important.
Here is an Israeli take on the electronic voting/paper trail issue, dating back to 2008. Eventually, the Israeli government ended up not switching to electronic voting, though of course for all the wrong reasons.
From the technical side, it should be mentioned that Cryptographers have been working on developing “End-to-End Verifiable” electronic voting systems for 3.5 decades now, combining paper trail with electronic means in order to achieve the “best of both worlds”. Here is an example of such a system that I have been involved in, together with Amnon Ta-Shma and others.
People tend to dismiss such systems due to their relative complexity, claiming that it makes the inner workings of the system too hard to comprehend by the public. However, for the system to be auditable it should arguably be sufficient that it is comprehensible to experts (which we can choose to trust, just as we entrust doctors with our health). Plus, it is not like the technology underlying current electronic commerce (and finance) is actually understood by laypeople. Just look at Bitcoin, which is gaining wide adoption by the public, while being significantly more complex than most proposed End-to-End verifiable voting systems (I am aware to the fact that the stakes of elections are of a different nature than those of monetary systems).
Comment #15 June 24th, 2017 at 2:28 pm
WITCN #9, Scott #11: I think the big picture is very clear. In one corner are the Republicans, who are remaking America into a plutocracy. In the other corner are a disorganized gaggle of Democrats, Independents, etc., who are trying to push things back toward the norm.
How did things come to this pass? Lot of things:
(1) Huge money invested in developing Rush Limbaugh types who are somewhat entertaining and keep up a group of lies and distortions for decades, and actually convince a large cohort that voting against their self interest is a good idea.
(2) Standard issue fear mongering, “us versus them” that has worked for right wing nuts since forever.
(3) Abortion. A single issue that has caused huge numbers to vote for the party that is screwing them.
(4) Racism.
There are also plenty of issues that are nuanced, and the Republicans did a good job of convincing people that they could help, when in reality they will screw everyone. Obamacare, for example.
Comment #16 June 26th, 2017 at 1:37 pm
Raoul #9, I don’t know why you think the Republicans will screw everyone Obamacare. I am not American but my impression is that a good number of people were rationally unhappy with having to buy more health insurance, not judging the extra coverage being worth the money they paid. Just abolishing Obamacare would please them, presumably. Of course Obamacare won’t be straightforwardly abolished, but I doubt that there won’t be measures to please at least some health consumers in whatever package is finally enacted.
Anyway, as a non-American my primary hope is that Americans won’t stop paying high drug prices, thereby subsidizing the development of drugs for the entire world.
Comment #17 June 26th, 2017 at 6:23 pm
Colorado provides a good example of a state that has been moving forward on election integrity for many years, toward “evidence-based elections”. We now have voter verifiable paper ballots in all counties. In November 2017 we’ll roll out risk-limiting audits statewide.
For more information, see my site on the Colorado Risk-Limiting Audit Project:
http://bcn.boulder.co.us/~neal/elections/corla/
Comment #18 June 26th, 2017 at 10:47 pm
Hi Scott, if P≠NP is proved would that show time travel to be logically impossible?
Comment #19 June 27th, 2017 at 12:55 am
Jr,
You are absolutely right that plenty of people were not happy about how Obamacare was set up. Include me in that. But at least Obama tried to give everyone a shot at medical care, imperfect as the system was and is.
On the other hand, there are two different Republican goals. The OFFICIAL goal is to not force everyone to buy insurance, which is reasonable. But the REAL goal is to transfer lots more money to the ultra rich by cutting out any aid to the poor. As for the millions left without medical care who will die, TOUGH SH!T, you should have been rich!
A few decades ago, only crazy Republicans officeholders wanted this. Now they mostly do, energized by the cheerleader for all things evil, TFI Trump.
Comment #20 June 27th, 2017 at 5:12 am
Jr,
My understanding is that it’s an accident of 20th century history that the US ended up with a mostly private healthcare system, where the rest of the developed world ended up with a mostly state controlled system. In short summary, during WWII the War Labor Board exempted employer-paid health benefits from wage controls and income tax. This tax advantage made employer based health insurance schemes very popular. Once established as a system those who benefit from it are very reluctant to give it up of course. The history of how US healthcare went from this point to where we are today is also very interesting but too long for this comment.
What is odd is that it has turned into a sort of religious belief in the US that healthcare shouldn’t be universal and that the costs shouldn’t come from general taxation despite all the evidence available in plain site from practically all European countries, for example.
I do like your idea that the US’s inflated drug prices are subsidizing the rest of the world’s health costs however.
Comment #21 June 28th, 2017 at 8:16 am
Harold #18,
No. The question of whether P=NP is rests on assumptions about what one’s underlying computing model acts like. If one has P != NP then that simply is a statement about how models of classical computers will behave. It is consistent with that that the universe we live in may or may not have time travel, and in fact Scott has written papers on what computer models would be reasonable if one had time travel (although I think he pulls the standard physicist routine of talking about closed, time-like curves to keep it respectable).
Comment #22 June 28th, 2017 at 5:20 pm
Even if you can make a perfectly secure purely electronic system, there’s something to be said for the simplicity of a paper receipt. Everyone can understand that.
Comment #23 July 2nd, 2017 at 5:29 pm
Unrelated, but hopefully sufficiently interesting — what do you think of the new paper by Denef, Douglas, and collaborators (1706.06430) or the similar one by Bousso and collaborators (1706.08503)?
Comment #24 July 4th, 2017 at 1:49 pm
Just an observation that an EVM which produces a paper output is equivalent to a really expensive pencil. And make sure to count the paper ballots by hand, in public, or else the problem of not trusting the software is just displaced to the electronic scanner/tabulator.
Comment #25 July 4th, 2017 at 7:27 pm
John #24: One of the technologies most preferred by the experts in this area is optical scan, where yes, you fill out the ballot with a pencil. But a lot of people prefer touchscreens—so the idea is basically that if you insist on that, then at least have a paper record.
And the counting of the paper ballots only needs to be a statistical sample, not exhaustive, to verify that machine counts weren’t tampered with in an outcome-changing way. But yes, I agree, the counting should be done by hand and in public.
Comment #26 July 5th, 2017 at 12:54 pm
Completely offtopic: Is it possible to have a problem which is in both BQP and in NP (or MA) but for which computing the witness is not in BQP? I.e. the quantum computer can solve the problem efficiently, but can’t find a witness efficiently.
Comment #27 July 5th, 2017 at 2:25 pm
RandomOracle #26: Very good question! Relative to a suitable oracle, sure we can get that. For example, take some BQP problem that’s not in NP, like the complement of Simon’s problem, Forrelation, etc. Then hide an NP witness in a part of the oracle where a BQP machine couldn’t possibly find it because of the BBBV Theorem.
Some of us have conjectured for years that the Childs et al. glued trees problem provides an interesting, natural example of what you’re asking for. I.e. if there are short paths from the Start to End vertex, then those paths themselves are witnesses of that fact, and a quantum walk can also get from Start to End in polynomial time (thereby proving that the paths exist), but it can’t efficiently produce any actual example of a path, because to do so would require measuring which path and thereby collapsing the state of the quantum walk (so no more interference). But the inability of a BQP algorithm to find a path remains to be proven, even in the query complexity setting.
In the “real” (non-oracle) world, the best candidate for what you want that I can offer is a promise problem, as follows. You’re given a classical circuit C, which you’re promised computes either a periodic function (with period at most 2n/2) or an injective function. Your goal is to output “no” in the former case and “yes” in the latter.
In the “yes” case, there’s an AM proof that the function is injective, which means that there’s also an NP proof under suitable derandomization assumptions. And a quantum computer can efficiently decide which case we’re in using period-finding. But I don’t see any easy way for a QC to prove that we’re in the “yes” case.
Comment #28 July 6th, 2017 at 5:26 am
I see, thanks! 😀
Is the AM protocol for the last problem: arthur evaluates the circuit on poly many random values and sends them to merlin to invert them? If he does it perfectly then whp the function is injective otherwise it’s not.
Comment #29 July 6th, 2017 at 5:37 am
RandomOracle #28: Right.
Comment #30 July 6th, 2017 at 4:49 pm
Curious: did Putin hack Michigan’s all-paper ballots?
Comment #31 July 6th, 2017 at 8:52 pm
Nathan #30: Neither Alex, nor any other serious person I know of, claims to have evidence that any ballots were actually hacked in 2016. The point, as I would’ve thought obvious, is that we should have a system in place where the choice of whether to hack the ballots or not isn’t Vladimir Putin’s.
Comment #32 July 7th, 2017 at 2:18 pm
Hi Scott:
Im already sorry to be posting such a light comment on such great blog but you are wrong, Trump is not the Mule he is A mule.
Just saying : – )
Comment #33 July 7th, 2017 at 2:25 pm
Me again, on a more serious note, it is terrible that 70 years after the beginning of the Cold War, the (at least perceived) enemy of the United States is still Russia.