Friday, August 17, 2007

2007 Electronic Voting Technology Workshop

Last week I was presenting a paper at EVT07. Here are my notes/observations. 2007 USENIX/ACCURATE Electronic Voting Technology Workshop ( 6th August: EVT Session Analysis I: First talk of the day was a talk from the Dutch group "We don't trust voting computers". This a well presented talk with video clips showing how easy it was to change the EEPROM on a voting computer, in 60 seconds, and of reprogrammed voting machine which could play chess. The second talk was similar, but was about Diebold machines in the US. The lock can be picked in less than 10 seconds. The third talk was about issues with technologies for disabled voters, namely the DV eSlate ( All three types of voting machines have radio emissions from raster displays, which can be detected and analyzed. EVT Session Design I: The first talk showed how to use hash chains to prevent/detect tampering with an audit log. This assumes that the information in the audit log can safely be made public (in encrypted form) and then shared between servers for redundancy. The second talk was about how to reduce the complexity of voting machine software by pre-rendering the user interface. My talk about verification of electronic vote counting for PRSTV was before last before lunch. This was the only paper at EVT to discuss formal methods, with mixed reaction. Several cryptographers suggested that a list of votes cast could be made public (in encrypted form) to allow each candidate/party to count the votes for themselves. I was asked to explain PRSTV in more detail. Also, some cryptographers suggested that is better to verify the result with independent counts rather than to verify the count process or the software. However, I don't know of any existing cryptographic schemes which work well with PRSTV from a vote counting perspective. At present in the paper based system, ballots are not made public, only the number of votes held by each candidate in each round and the proportion of transfers in each round. It was suggested that randomization, which is part of PSTRV, could be done in advance with a predefined table of random numbers. However, this could compromise the anonymity of the votes. So, I still think that the actual vote counting process needs to be formally verified. EVT Session Auditing and Transparency: The first talk of this session described the confidentially requirements of contracts between voting machine vendors and election agencies in the US, which prohibit almost all use/analysis of the voting machines/software, except where necessary for the purpose of casting a vote. Also, the contracts are confidential. In some cases the audit logs are confidential. Some vendors to reserve the right to update the election software at any time e.g. just before an election. The second talk of the session described how to calculate the optimal sample size for auditing. The next talk described how to automate the auditing of ballots ( The last talk of the session described an experiment in which college students were unable to successfully complete an audit that required recounting of VVPAT (voter verified paper audit trail) receipts, meaning that VVPAT receipts need to be redesigned for usability. EVT Session Analysis II: The first talk of this session described a software tool called Pioneer, which is designed to run on voting machines, checking that none of the software runs slower than expected. The idea is that if the software is compromised or acting maliciously, then it will take longer, than it should, to perform certain calculations. The next paper described a ballot layout attack against optical scan vote terminals; candidate name indexes can be swapped in memory, but the VVPAT receipt will appear to be correct. The last paper of this session showed how voting certification standards discourage good database design by requiring additional documentation if the design is more secure. The data model for GEMS, which is the Election Management Software used by Diebold, does not even comply with first normal form. Different parts of the tally get stored in different parts of the database. It has been shown to give inconsistent reporting of election results i.e. count the same set of votes on two different days and get two different results! Negative numbers of votes were stored in some parts of the database. Microsoft JET was used as as the database engine, although it does not guarantee "absolute data integrity". Law professor Candice Hoke, makes the point that the legislation needs to specify some minimum set of technical/quality standards e.g. database schema must be at least as good as 2NF, or equivalent. How best to express these technical standards in legal form is an open question. EVT Session Design II: The first talk proposed a scheme whereby a voter using a direct recording (DRE) voting machine can choose either to cast the vote as normal or to challenge the machine to decrypt the vote correctly, just by adding one question to the voting process. The next paper described a more complex scheme with two half-receipts for each vote. The voter retains one half-receipt; enough to verify the vote, not enough to reveal the vote. The last talk described three different non-cryptographic schemes: Three Ballot (which would not work with PRSTV), VAV (Vote, Anti-Vote, Vote) and Twin. Although VAV might work with PRSTV, it has some usability issues i.e. the need to fill out the ballot paper three times. See also: ===== USENIX Security 07 Technical Sessions ( 8-10th August: Web Security Session: First talk was about SIF (servlets with information flow) which is based on JIF. Next talk was about using tokens to weight the value of clicks on a syndication site. Then a talk about execution based analysis of untrusted websites using a kind of virtual machine. Privacy Session: The privacy session described how variable bit rate encoding, which leads to more efficient packet sizes can also leak data, so that encryption is not enough. The second talk of that session applied the same analysis to pervasive computing devices. The third talk described how to infer data from anonymised documents e.g. most people can be identified just by their gender, date of birth and ZIP code. Authentication Session: Very interesting talk about relay attacks on smartcard payment systems, including a video clip from BBC TV programme 'Watchdog' and a proposed solution using distance bounding. The next talk showed techniques that be used to discover graphical passwords by finding hot spots in images.. The third talk was a way of encoding a user-specified time delay into offline passwords so as to make dictionary attacks about 3.59 times harder. Threats Session: Two talks about spam and one about botnets. The first talk about using image shingling on screenhots to profile the 'scam' sites. The second talk about establishing IP reputation so that overloaded mail servers could bias towards legitimate mail senders. The third talk was about a BotHunter tool for detecting bots i.e. remote controlled malware. Analysis Session: The analysis session included a talk on integrity checking of cryptographic file systems, and a talk on reverse engineering of message protocols. The last talk in that section, awarded 'best' in conference was about detecting variations in different implementations of the same protocol e.g. two different HTTP servers. This was done by extracting symbolic logic from the binaries (assembly code) using an intermediate language and weakest precondition analysis and then finding a set of inputs for which the two implementations differ. This could be used either to find error conditions or to fingerprint the binary executables. Invited Talks on Electronic Voting: There were two invited talks on Computer Security and Voting. The first was a general introduction to the topic by David Dill and the second was a discussion by David Wagner and others of their review of electronic voting machines in California. After the first talk, someone asked a question about randomisation in PR-STV, is used in Cambridge, MA, for city elections. In the second talk, David Wagner described some of the more basic security flaws in Diebold, Sequouia and Hart machines, and then said that those were less harmful than the ones which could not be publicly disclosed! All three systems have very weak or no use of encryption and all three are vulnerable in different ways to malicious viral code. The review team focussed only on the security code and could not comment on other parts of the code e.g. vote counting. Obfuscation Session: Interesting talks on both software and hardware obfuscation. The obfuscation technique for software is too much like a hack; it is an example of what malware developers might do to avoid detection. The hardware obfuscation is a legitimate way to protect intellectual property using physical variation in fabricated circuits. Network Security and Privacy Session: The first talk showed that connection time is the bottleneck in cellular networks and thus vulnerable to denial of service attacks by using up the pool of connection IDs. The second talk discussed various possible attacks on dense urban w-ifi networks. The last talk was about data mining of anonymised network data by profiling data flows for different websites. Work In Progress Session: Some of the WIP talks discussed virtualisation. One talk described how to use virtual machines to isolate malware. Another talk showed how to use virtual machines to subvert software licenses, using a form of replay attack. Yet another talked about using VMs to detect kernel modifying rootkits.

Labels: ,


Blogger Edinburgh said...

Very interesting report.

You say:
"At present in the paper based system, ballots are not made public, only the number of votes held by each candidate in each round and the proportion of transfers in each round."

At the recent STV-PR local government elections in Scotland the votes were recorded on conventional papers ballot papers which were then scanned electronically to produce vote data files for computerised counting. Glasgow City Council has published the full ballot data for all of its wards, as preference profiles in BLT format. There is no linkage to any voter. See:
and follow the links to "Full Results" under each ward. The BLT file is first in the zipped folder.

You also say:
"It was suggested that randomization, which is part of PSTRV, could be done in advance with a predefined table of random numbers. However, this could compromise the anonymity of the votes."

There is no need for randomisation in an STV-PR count, though it does depend on the STV rules you are using. In the recent STV-PR elections in Scotland, the election rules prescribed the transfer of every ballot paper when any transfer had to be made. Then randomisation becomes irrelevant. For a description of the count under the STV rules used in Scotland see:
NB For those not familiar with STV-PR, this document should be read only after reading the more general description of STV on the webpages that start at:

A more complete description has just been published in the August edition of the journal "Representation":

James Gilmour

18 August, 2007 11:46  
Blogger Dermot Cochran said...

Thanks for your comments. I agree that there should be no need for randomisation in PR-STV although the Irish version does use it to facilitate the counting of votes by hand. When a candidate reaches a quota after receiving transfers from another candidate, only those most recent transfers are looked at when the surplus is distributed. Also, the Irish system does not allow fractional transfers of votes, except for Senate elections which have a much smaller electorate.

There is a risk in publishing the full ballot paper. If there are a large number of candidates then the permutations of preferences can be more than the number of voters. This would allow a voters to identify their vote by choosing a peculiar combination of lower preference votes, so as to facilitate vote selling or coercion.

21 August, 2007 10:10  
Blogger Edinburgh said...

The ballot papers are randomised in the Dáil Éireann elections, but not because the votes are counted by hand. Rather, it is because the Dáil STV rules specify the transfer of individual ballot papers always at a value of one vote - so they have to select randomly the required number of ballot papers. STV-PR elections in Northern Ireland are also counted by hand, but there the ballot papers are not randomised because they use the Gregory Method of fractional transfers.

The numbers of possible preference permutations rises very rapidly with the number of candidates. If there are 5 candidates, the number of possible unique preference profiles is 325, rising to 13,699 for 7 candidates, to 986,409 for 9 candidates and to 108,505,111 for 11 candidates. Thus the numbers of possible unique preference profiles in many public elections greatly exceed the numbers of electors voting in those elections. (We had up to 14 candidates in our recent local government STV elections for which the maximum electorate was around 25,000, of whom about 12,500 voted.) So the theoretical risk of tracking individual voters is well established and well known.

However, in the UK at least, the penalties for the offences that would be committed in any such tracking are severe. For secrecy offences in local government elections, Section 66 of the Representation of the People Act 1983 specifies a fine not exceeding level 5 on the standard scale (currently £5,000) or a term of imprisonment not exceeding six months. These penalties provide an effective deterrent because they far outweigh any benefit that could be obtained by a voter who marked an “unusual” sequence of preferences or anyone who attempted to track such a voter. And if anyone did this successfully, there would be little chance of keeping that secret for long. So we have no fears at all about full disclosure and hope that our Government will soon make this a requirement in Scotland.

James Gilmour

22 August, 2007 00:12  
Blogger Dermot Cochran said...

Interesting. Although, the secrecy requirements are described in terms of paper ballots, so it could be hard to prove that a voter had sold his or her vote.

23 August, 2007 10:26  
Blogger Dermot Cochran said...

There was an interesting paper at EVT08 which describes this kind of attack on STV systems.

22 January, 2009 11:18  

Post a Comment

<< Home