Two Ohio researchers have discovered that some of the state’s e-voting machines put a timestamp on each ballot, which severely erodes the secrecy of ballots. The researchers, James Moyer and Jim Cropcho, used the state’s open records law to get access to ballot records, according to Declan McCullagh’s story at news.com. The pair say they have reconstructed the individual ballots for a county tax referendum in Delaware County, Ohio.
Timestamped ballots are a problem because polling-place procedures often record the time or sequence of voter’s arrivals. For example, at my polling place in New Jersey, each voter is given a sequence number which is recorded next to the voter’s name in the poll book records and is recorded in notebooks by Republican and Democratic poll watchers. If I’m the 74th voter using the machine today, and the recorded ballots on that machine are timestamped or kept in order, then anyone with access to the records can figure out how I voted. That, of course, violates the secret ballot and opens the door to coercion and vote-buying.
Most e-voting systems that have been examined get this wrong. In the recent California top-to-bottom review, researchers found that the Diebold system stores the ballots in the order they were cast and with timestamps (report pp. 49-50), and the Hart (report pp. 59) and Sequoia (report p. 64) systems “randomize” stored ballots in an easily reversible fashion. Add in the newly discovered ES&S system, and the vendors are 0-for-4 in protecting ballot secrecy.
You’d expect the vendors to hurry up and fix these problems, but instead they’re just shrugging them off.
An ES&S spokeswoman at the Fleishman-Hillard public relations firm downplayed concerns about vote linking. “It’s very difficult to make a direct correlation between the order of the sign-in and the timestamp in the unit,” said Jill Friedman-Wilson.
This is baloney. If you know the order of sign-ins, and you can put the ballots in order by timestamp, you’ll be able to connect them most of the time. You might make occasional mistakes, but that won’t reassure voters who want secrecy.
You know things are bad when questions about a technical matter like security are answered by a public-relations firm. Companies that respond constructively to security problems are those that see them not merely as a PR (public relations) problem but as a technology problem with PR implications. The constructive response in these situations is to say, “We take all security issues seriously and we’re investigating this report.”
Diebold, amazingly, claims that they don’t timestamp ballots – even though they do:
Other suppliers of electronic voting machines say they do not include time stamps in their products that provide voter-verified paper audit trails…. A spokesman for Diebold Election Systems (now Premier Election Solutions), said they don’t for security and privacy reasons: “We’re very sensitive to the integrity of the process.”
You have to wonder why e-voting vendors are so much worse at responding to security flaw reports than makers of other products. Most software vendors will admit problems when they’re real, will work constructively with the problems’ discoverers, and will issue patches promptly. Companies might try PR bluster once or twice, but they learn that bluster doesn’t work and they’re just driving away customers. The e-voting companies seem to make the same mistakes over and over.
i dont think our vote counts anymoore as with john carry but i think clinton should not get office she new her husband signed that bill to let our companys move out of this country this country needs jobs to stay afloat but it all comes down to the allmighty dollar i think presidents should have more degrees in goverment to qualify im not the smartest person but come on we need some one thats not gona rob the goverment or take the tax dollars from this country we need to build it up we give up jobs we are realy commiting treason to our own country
The only downside of absentee ballots is that close elections cannot be called for some time after election day since ballots can be mailed up to midnight on election day.
There are many downsides to absentee ballots:
-1- No current implementations prevent a voter from showing his ballot to someone else immediately before mailing it, or even giving the signed ballot to someone else before mailing it (or even filling it in!) Voter confidentiality is thus non-existent.
-2- There is no meaningful chain of custody with absentee ballots between the time they are sent out and the time they are received back.
-3- In Washington state, there’s often no meaningful chain of custody even after the ballots are received back.
-4- With polling-place voting, someone who votes multiple times at a precinct is likely to get caught. Someone who wants to vote multiple times must get registered at multiple precincts; this generally requires being able to receive mail at multiple addresses. Probably not hard on a onesy-twosy basis, but hard to do in bulk. With mail ballots, someone can register (and vote for) himself, three cats, two dogs, and a goldfish all at his same address and nobody will be the wiser.
In Washington State most voting is done by absentee ballot. This implies paper ballots and a paper trail. Paper ballots are great. I can fill in my ballot, which looks a lot like an SAT answer sheet, and send it off in a double envelope, the inner envelope being anonymous. If the state went back to voting booths, we’d have a massive drop off in voting, especially in my county which is a rural county and there is already a problem with voting in the more remote areas.
The only downside of absentee ballots is that close elections cannot be called for some time after election day since ballots can be mailed up to midnight on election day. The last gubernatorial race was a squeaker and it hinged completely on absentee ballots and Republican vote suppression efforts.
Slight addendum: if, within reasonable bounds, cost weren’t an issue, I think I’d most like to see votes recorded on a mechanical system with one roll of counterfeit-resistant paper tape per candidate, plus one for ‘no-candidate’ in each race. The system would, in front of a viewing window, advance the tape for each selected candidate (or the ‘no candidate selected’ one) and then punch a hole in it. The total number of holes punched for a race should equal the total number of people voting for it. If election judges from both parties supervise the installation of the tapes and mark them with counterfeit-resistant seals, the system should be relatively immune to tampering and yet retain voter secrecy.
If it is necessary to record what combinations of candidates are selected, it’s not possible to keep ballots in sorted order without having to repeatedly rewrite old ballots as new ones are cast. While there would be means of ensuring data coherency even while such rewriting is being performed, they would greatly complicate the system and increase the plausibility of something going wrong.
If it is not necessary to keep that information, setting aside the matter of handling write-in ballots, one could for each race allocate a bunch of EPROM/flash: (number of candidates plus two) times (maximum number of voters). Regard the memory as having one ‘column’ per candidate, plus a column marked ‘total’ and one marked ‘none’.
To cast a vote, program a bit in the ‘total’ column and then either program a bit in one of the candidate columns, or in the ‘none’ column if no candidate was selected for that race. In the event of a power failure, check the number of bits in the ‘total’ column against the total number of bits in the other columns. If there is one extra bit in ‘total’, allow the voter to remake his selection for that race, since it was not recorded. If ‘write-once’ media are used, a vote once cast cannot be altered without indelibly throwing off the totals.
If things are done that way, there’s no way the output format can encode any information about the voter. Not a bad approach, but the storage requirement could be excessive in races with many candidates. Further, I’m not convinced that’s necessary. If one trusts a voting machine to be running legitimate code, and if examination of that legitimate code reveals that it effectively stores ballots in random order, there is no need to worry about compromised vote secrecy. If one doesn’t trust a voting machine to be running legitimate code, or if one cannot inspect the code well enough to ensure that it preserves secrecy, then there probably isn’t much basis for trusting that it will record votes correctly either.
One advantage of sorting is that you can inspect the sorted output and verify that it is indeed in sorted order. But you can’t look at randomly-shuffled output and verify that it was really put in random order (and not some random-looking but really information-conveying order).
(Sorting isn’t the only way to reorder so that an inspector can verify that the ordering doesn’t covertly signal information about the original order. There’ s a small research literature about this problem.)
Of course —thinking about it a little bit— sorting on the contents of the ballot requires the sorting process to access information from the ballot. Thus the sort must be unobserved. (Otherwise the sorting process may leak voter identity information).
In an analagous vein, pre-computing a random sequence requires that process of serializing the ballots remain unobserved.
Both of those options require somewhat more complexity than seems desirable or necessary.
Randomization is better than sorting for this application, because it can be handled before the ballots are cast.
If there is a limit of, e.g., 10000 ballots per election, the machine could easily use an algorithm like:
– Assume ballot_array(0..9999) of ballot records and ballot_status(0..9999) of bytes; initialize all arrays to $FF (assuming flash or EPROM-style storage)
– Pick a number between 0 and 9999-ballots_cast
– Loop that many times with variable i:
– – Advance ‘i’ until ballot_status(i) equals $FF
– Store $FE into ballot_status(i)
– Store ballot into ballot_array(i)
– Store $FC into ballot_status(i)
The selection of each ballot spot will be entirely independent of the number of ballots cast or where they ended up. At no time will the system have any information about the position other than the current ballot being stored; maintaining storage coherency should not be a problem. On power-up, the system should look for any ballot_status entry holding $FE; if one exists, it should store indicate that the last ballot cast was not recorded. Once that is acknowledged, it should store $FA there resume operation.
Ping,
Whether you chunk and label the step in the process “randomization”, “sorting”, or “addition”, the core necessary abstraction is injecting informational entropy.
(I’m not really disagreeing with what you said, instead I’m just restating your “independent” of the initial sequence criterion.)
The trick is to ‘erase’ or ‘forget’ some information, while providing assurance that the integrity of another class of information is maintained.
This is an argument for computer-aided composition of the ballot, but not for anything else.
Let people use a machine in a booth to compose their ballot and print it. Then the printed ballot is placed by hand into a slot in a ballot box in the same manner as in a fully non-mechanized election. If the machine is tampered with, the ballot comes out different from what the voter intended and the voter can immediately see that something is wrong. Unlike “VVPT” machines the voter isn’t encouraged to just ignore the printed output or even to ignore a serious problem like a too-faint and illegible printout; the ballot is no good if it comes out illegible and the voter has to handle and look at it in order to complete the process. Signage can be used in the polling stations to encourage voters to quickly double-check the printed ballot for anything anomalous — the things they care most about, such as who the next president should be, should certainly be quick and easy for them to double-check. If they picked Gore and it showed Bush on the ballot they’d immediately see that something was wrong and could report it to a poll worker immediately. And have the option of submitting a hand-filled ballot, at greater risk of it being spoiled of course.
Ima asks when a “computerphile” will stand up and say paper is the answer.
Several such computerphiles have said variations on this. The devil, as always, is in the details. It matters how the paper is counted. It matters how many contests are on the paper. It matters how complex those contests are. Accessibility matters. The ease of ballot stuffing matters.
If you have a simple “Alice vs. Bob” election (i.e., just two candidates running for one office), then paper works great. Counting the ballots is nothing more than making two stacks. (For example, this is roughly how French parliamentary elections work.)
On the other hand, if you’ve got the Australian single transferable vote system (where voters can either select their party’s preferences, or must precisely specify a permutation of about seventy candidates — any error and the ballot is spoiled), or if you’ve got something like the recent California gubernatorial recall election (where Schwarzenegger competed with over a hundred other candidates with the order of the names on the ballot randomized), then it’s not intuitively obvious that hand-marked and hand-counted paper ballots are the optimal answer, given the unavoidability of human error.
My own feeling is that computerized voting machines can be done exceptionally. The present generation of products, however, fail to live up to this promise.
P.S. Returning to the original point of this article, vote randomness in ES&S iVotronic systems, it’s worth pointing out that Florida commissioned a source-code study of its iVotronic systems in the wake of the Sarasota ’06 problems. While the main focus of the study was whether some aspect of the source code contributed to Sarasota’s undervotes, the study also detailed other security vulnerabilities in ES&S’s iVotronic product. One of the (sadly) redacted appendices is tantalizingly titled Anonymization of cast vote records in the ES&S iVotronic 8.0.1.2 firmware. Presumably, if there wasn’t a problem, the section wouldn’t have been redacted.
When I noticed the reference to the Republican and Democratic poll watchers, I thought that with electoral districts nicely shared by the two half parties (better than just One, eh), what difference does it matter that the ballots are sorted? Call me cynical, but there must be a reason why the voter turnout is about 50%. Now, all those problems can be easily fixed if we either call for UN observers, or get a voter turnout like in Sarpy County, Nebraska (November 2004) – 139%.
When is a computerphile going to step up and say, “For some things, paper is the perfect technology.” As a society, we have found a way to resolve disputes by stuffing ballots into boxes instead of stuffing bodies into foxholes.
What is wrong with paper?
Tamen: Actually, with a lexicographic (“alphabetical”) sort, you really can’t reconstruct the order.
sorted(“This is a simple example.”) âž” ” .Taaeeehiiillmmppsssx”
Ping: Well, if the sorting algorithm is known it isn’t very difficult to run it in reverse and recreate the original order.
Spudz: There’s no need to use hash codes or rely on the randomness of a random number generator (which we know to be a tricky problem). Simply sort the ballot records. Then the order of the records will be strictly determined by their content. As long as the contents of each record are independent of the time when it was cast, no reconstruction will be possible.
As pointed out before, perfect reconstruction of the vote is not required. Suspicion beyond some level of doubt is sufficient.
It’s like with any other behind-doors suspicion and judgement. For somebody who prefers to think ill of you it is enough to just imagine you did something; if there is evidence the incident happened and it plausibly could have been you, so much the better.
The time stamp issue is going off the deep end. We have devolved into a society where solutions can not be implement because of “problems”. No system is perfect. I love the Royal Bank of Scotland commercial where the guy is sinking in quicksand and his compatriots just talk about options to save him but never do anything. Of course there is that one guy who took some initiative to save him.
While I favor electronic voting, I agree that these companies are 1. selling defective equipment and 2. ripping the taxpayer off.
I can see the logic behind the ES&S spokeswoman’s statement — at a busy polling place with more than one voting machine, the sign-ins tell you what order people arrive in but not which machine they went to or even what order they did so in (given five people coming in, maybe two queued for one machine while the other three went to separate machines, with varying delays before casting their votes). You could probably get some statistic answer (“one of these three people probably voted for X”), but you won’t be able to tell for sure.
At non-busy times or when there’s only one voting machine, of course, then what you said is true — almost all votes will be easily reconstructable.
In general though I agree with supercat.
I would like to see voting machines implemented with open-source software run on simple computers built from common off-the-shelf chips. Code and ballots should be stored on flash or OTP cartridges with a read-only port and a read-write port; the cartridges should be constructed so that the latter may be closed using physical seals. The machines should be constructed so that code may only be run from the cartridge directly; code execution from RAM is forbidden.
Operational protocol: immediately prior to the election, both poll judges seal the code cartridge to prevent write access, and then each uses his own reader to compare the contents against the official copy. Each then, under the watchful eye of the other, uses the reader to confirm that the ballot cartridge contains an official blank ballot.
The cartridges should then be inserted into the voting machine, which is then sealed by both judges. Immediately after the election, the ballot cartridge should be sealed by both judges, and then both the ballot and code cartridges should be read by both judges (each with his own reader) and each judge should give the other a signed copy of the readouts.
What possibilities of fraud would exist under such a system if AT LEAST ONE judge is honest?
They could solve several problems at a stroke by using Java, and using it well. To begin with Java is inherently free of the most common source of security vulnerabilities: buffer overrun bugs. Its large and rich standard library also mitigates against reinventing the wheel, and possibly doing it badly, and potentially introducing bugs thereby (including security holes). Finally, given the use of Java, randomizing the stored records so as to destroy any information about the order in which the votes were cast is easy: a) you don’t include any kind of timestamps in the ballot objects or that can be linked to specific ballot objects and b) you store them in a java.util.HashSet (not a LinkedHashSet though!) after implementing hashCode() on the ballot object to convolve the hashcodes of the fields (e.g. all the various candidate choices). This might produce too many hash collisions on its own so you can construct each one with a randomly generated string (using something strong, like Mersenne Twister, or even a hardware RNG) and use this in the hashcode, or even generate the hashcode with this alone. I recommend this, because the default Object hash code might contain information about the instantiation order or instantiation time of objects depending on the JVM used.
All of that said, I would still not trust an electronic voting apparatus further than I could throw it. Hand-counted paper for me, please.
“The constructive response in these situations is to say, ‘We take all security issues seriously and we’re investigating this report.'”
Actually, “we take X very seriously” is often used as the polite way of saying “We wish you would shut up about X. Now run along.”
RE: Companies might try PR bluster once or twice, but they learn that bluster doesn’t work and they’re just driving away customers.
Where is the connection that bluster drives away customers? When do election officials (customers) return their machines, demand a repair, or sue for repair?
When there is no consequence for PR bluster, then PR bluster is the most economical response.
As one half of the the team being discussed, I’d like to invite you to our blog, The Public Ballot. Here you can track developments as they occur.
Thanks for this detailed post, Ed!
It’s important to point out that this attack appears to rely on the paper-trail printers (“Real Time Audit Logs”) that ES&S offers in some states. The electronic records generated by ES&S’s “Unity” database provide two separate files: an event log and a vote log. The events are all timestamped, but they only indicate that a vote was cast, not who it was cast for. The vote logs are (allegedly) randomized and certainly contain no timestamps. An interesting analysis yet to be performed is to determine whether ES&S’s electronic records are as easily derandomized. If/when ES&S’s system comes under the same kind of detailed analysis as the other vendors did in California’s Top-to-Bottom review, we’ll look forward to learning more.
(To the best of my understanding, ES&S’s iVotronic system is not used in California, so this particular review will need to be performed elsewhere. The most detailed review, to date, of ES&S’s iVotronic systems was conducted by the State of Florida as part of their analysis of 13th Congressional Precinct race in Sarasota whose outcome is still being challenged. That review did not look at this issue. David Dill and I co-authored a manuscript that discusses other unresolved issues in that election.)
You answered your own question.
“but they learn that bluster doesn’t work and they’re just driving away customers”
In the case of the e-voting vendors, they are not driving away customers and the bluster does work. It is just now starting to look like the tide might be changing.
I don’t think it’s all that hard to understand. Voting machines are not sold in a circumstance where the ordinary market mechanisms operate. They are sold as govt contracts – where accountability of the purchaser is virtually non-existent and the political connections of the vendor are more important in the end than the technical properties of the device. Here and everywhere, bluster, PR, fog, FUD ultimately have their limits, but “ultimately” is a lot further away here than elsewhere.
Where I vote (New York City) we still use the old mechanical pull-lever voting machines. I have to say I’m more confident in them than I am in any of the modern “improvements”.
I think you forgot the /a tag somewhere 🙂
[That’s fixed now. Thanks. — Ed]
I have to say even though I don’t live in the US, this worries me that the process of choosing the most powerful man in the world is so full of holes.