Thoughts on voting machine fraud

Posted 19 Nov 2002 at 21:49 UTC by alan Share This

I've been having a ponder on some of the problems of systematic voting fraud and came up with a suggestion. Since its not an academically rigorous approach and I don't make voting machines I thought it might be interesting to throw it at people who might care

A Proposal For Reducing The Potential For Voting Counter Machine Fraud

Systematic fraud by vote counting systems is one of the big threats to electronic democracy today. In the USA for example pretty much all the vote counting machine companies are owned by pro republican companies. Regardless of the honesty of the companies concerned the question of trust and accountability is inevitable, and rightfully so.

Currently the system focusses on auditing of the companies and the machines. This fails to recognize the fundamental problems that verifying hardware behaviour is extremely difficult, and verifying the trust of a complete computer system including software is a nightmare.

(see FEC draft voting system standards Dec 13, 2001)

This idea permits certain degrees of distrust to exist within the system while making it extremely difficult to commit fraud. The basis of this design is to provide insufficient information to the voting machine to permit it to make a decision aimed at fraud.

The voting machine is delivered complete with hardware and software into a secure location. Cryptography and secure packaging technqiues are used to deliver the equipment so that it cannot be tampered with. This is existing art as documented by the US government for the delivery of trusted computing systems. The voting machine is never connected to an external communications system such as a modem.

After the voting machine has been delivered and is in a secure location modification is not permitted. Only after the voting machine is in the secure location are ballot cards printed.

A range of values (perhaps 100) are assigned at random to candidates. The randomness of this assignment is important and the use of a strong system such as candidates pulling numbers out of a hat observed by an election monitor is appropriate.

Ballot cards are printed with random numbers of the cards assigned each of the random values for the candidate. Other information which might identify a candidate such as position on the card is also varied for all machine readable components.

The user marks the card and feeds it to the machine. The machine counts which of the values is marked by the user. The machine is unable to identify the other values on the card or the significance of the value it has been presented.

At the end of the count the values for each range are read from the machine, tallied and then those assigned to each candidate are summed. This final addition and sum is easy to audit and the values from each voting machine can be verified by the election monitors.

The system is extremely tamper resistant because the knowledge of the ranges associated with each candidate is not available at the time the machine was created and software loaded into it. Because each candidate is assigned multiple values and the number of cards of each value is not known to the machine it is harder to perform a statistical attack.

In theory it is possible to encode information about the election and feed it into the machine in two ways. The first attack is to ensure the machine can read other parts of the card, so it can deduce rules about which values belong together (since two values for the same candidate would not normally be on the same card). This is significantly harder than hiding systematic fraud in the software or processor of the system, and also very hard to pass off as "a bug".

The second attack is more interesting. A series of users encode cards with erroneous votes, or arrange themselves in a specific pattern in front of one voting machine. An encoded pattern, probably including errors, is used to pass a heavily forward error corrected message into the machine, using a system such as a golay or viterbi codec. There are several problems with this attack. Firstly it assumes the user has some control over which machine cards enter. Secondly it requires a measurable number of users working together to control even one voting machine.

As well as mechanical seperation of knowledge it is possible to build an electronic interface which seperates the input side of the system from the vote counter. In this variant three components are present. The first is the input system - which might for example be a card scanner and keyboard into which the user types the number for their choice of candidate from the card.

The second component is the vote counting system as described above.

The third component is a small trusted system which sits between the two and is tightly audited as well as very simple. This component takes the values from the input system, verifies they are correct and hands them on to the counting machine. This component also adds random time delays, and performs other well known and existing art to remove covert channels so that the front end and counting machine cannot conspire together to provide a secret channel by which users modify the operation of the voting machine and direct it on how to commit fraud. All three components are subject to the same rules about secure storage.


See comp.risks / Rebecca Mercuri, posted 20 Nov 2002 at 04:36 UTC by ghostgum » (Journeyer)

There have been a number of articles in the comp.risks archive recently. The articles by Rebecca Mercuri are worth reading. She did her PhD in this area and continues to make contribution to this field.

It is hard to beat a system of paper ballots that can be quickly read by machine, but hand counted in case of dispute. It is then a matter of trusting the observers instead of a secret voting machine.

Not auditable, posted 20 Nov 2002 at 11:18 UTC by gerv » (Master)

The problem with having so many levels of indirection in the system is that it makes it much more difficult to provide and use a verifiable paper audit trail in case of dispute.

Gerv

Work by Rebecca Mercuri would be a good start, posted 20 Nov 2002 at 12:57 UTC by sjmurdoch » (Apprentice)

I can recommend ghostgum's advice to look at work by Rebecca Mercuri. I was at at one of her talks at Cambridge University, England and it was very informative.

Some links:

From my understanding of the talk she concluded that electronic voting is flawed, cryptography can't help enough and open source can't help enough (even if you are sure the software is correct, what about the compiler and hardware - then how do you know it is properly loaded). The system that she proposed was basically an electronic system which produced a paper voting slip which was put in a box. At worst if the voting system is suspect the pieces of paper can be counted by hand.

I would strongly agree that a paper backup is needed, but I question the need for electronic voting at all. The UK and most of Europe have a voting system which consists of people making crosses on bits of paper and putting them in a box. This system is easy to understand and works very well. Results are known by the next day.

Finally I think there is far greater potential for fraud in the generation of elligible voters and the proposal in the article doesn't address this so can at best solve only part of the problem.

Auditable, posted 21 Nov 2002 at 01:02 UTC by alan » (Master)

Gerv I disagree

If you want to do a hand recount, you count into 100 piles using the assignments published and seen by the election monitor and candidates originally

If you want to verify a given vote you compare the value on it to the table of assignments 0-99 -> Candidate Name. Thats something anyone can trivially do with their carbon of their vote or machine print out. Furthermore the machine doesn't know enough info to arrange deliberate misprinting with a specific goal

Elligible votes, posted 21 Nov 2002 at 01:06 UTC by alan » (Master)

Agreed about elligible voters. The kind of scheme where you take a retina scan of each voter and feed it through a one way function to anonymise it and manage to pick a function that wont accidentally cause collisions when you look for duplication is hard. Its a seperate problem and present in current paper voting schemes. "Vote early, vote often" as they say 8)

With regards to electronic voting (as opposed to electronic counting) I also don't see any solutions.

Other voting issues., posted 21 Nov 2002 at 23:04 UTC by jlbec » (Master)

All of this doesn't help when folks in Baltimore distribute leaflets claiming you need to pay your parking tickets before you can vote.

All of this doesn't help when the Florida State Police stop folks of a certain non-caucasian persausion before they reach the voting booth.

Why use electronic?, posted 22 Nov 2002 at 05:02 UTC by djm » (Master)

Electronic voting brings few benefits, but many, many risks. The only area where electronic voting would be clearly superior to manual systems is speed of counting, but others have observed than electronically-countable paper vote cards have this quality too without the risk.

A variation on this theme may be an electronic voting system which also spits out a paper record. This paper record should be shown to the voter before it is dropped in the box. Optionally it could give a copy to the voter, in case the box magically disappears.

The physical nature of a paper card makes all type of fraud more difficult. They cannot be invisibly changed as they are their own record. Stuffing a ballot in the paper domain is an exercise in corruption, logistics and physical stealth. In the electronic domain, one only requires the former.

I haven't observed the push towards electronic vote systems here in .au, so I don't quite understand the motivation. I could imagine that "big media" would be anxious to make more of the election night spectacle (as if they don't already) and the voting equipment manufacturers seem from afar to be well connected and actively lobbying.

I'll be off to the polls in 8 days (Victorian state election), and will be happy to be doing it with a pen and paper :)

Other voting issues, posted 23 Nov 2002 at 05:47 UTC by Ankh » (Master)

jlbec is right here. We can get really excited by the geekiest 1% of the voing problem, but the hard stuff is social. If the US elections have under 50% turnout (and they do), it doesn't matter how reliable the actial voting booths are. Traditionally in the US, poor people are less likely to vote, says popular lore and anecdotal evidence (anyone have a better reference?) which probably biases the vote towards the right. That in turn makes politics seem less and less relevent to the less well off, and they become less likely to vote in the future.

The government clearly does not have a strong incentive to change this.

Simplicity vs. Security, posted 23 Nov 2002 at 17:26 UTC by helcio » (Journeyer)

As we move toward a better solution for electronic voting security, we are likely to get complex schemes. Security is good, but we should keep an eye at simplicity, otherwise many people might have a hard time learning about how to vote.

In countries where voting is optional, some people may not feel very interested in voting, and some of them may see how voting became more complex, and just that. Such people may not consider the security benefits, after all they might be unaware of the way things work under the cover.

It is somewhat easy for people related to technology to understand such issues, but what about others? True, this may vary much from country to country... As an example, in Brazil voting is not optional and as a consequence the lines for voting made people wait for some hours for their turn, yet voting scheme is simple. Making people vote using more complex methods may turn the election into a hell. My guess is that the solution may be a somewhat middle-term between security and simplicity.

An issue, posted 25 Nov 2002 at 12:30 UTC by chalst » (Master)

Alan: Am I right in understanding that the guarantee that the proposal is intended to ensure is that the voting machines do not learn the the assignment of numbers to candidates before they have produced the count, and this is ensured by (1) the assignment being created randomly after the machines are delivered, and (2) the machine being isolated in such a way that it cannot learn the assignment before it has conducted the count?

I'd like to comment that this is an inversion of the usual model of covert channels, where we try to guarantee that some information held on a secure site cannot leak out: here we are trying to ensure that widely dispersed information (it is needed by every voter, a group that presumably includes the machine manufacturers) cannot leak into the machine. It also seems to be a harder problem, since

  1. The manufacturers will know the assignment, and so can arrange to broadcast it;
  2. Radio receivers, in particular, are very easily concealed;
  3. The amount of information the covert channel needs to pass is rather small; just a single bit of information (which candidate has number 0) will allow the election to be slightly prejudiced.

I think your proposal could be a useful addition to auditing, but it is not a replacement. Imagine the 'voting machines' include a well-equipped, well-staffed communications laboratory: easily picked up by auditing, but makes eliminating covert channels a practical impossibility.

i believe the process of putting names on the ballot, posted 25 Nov 2002 at 21:32 UTC by badvogato » (Master)

is more at stake than any proof system of counting the votes. It seems to me that the closing up of all political races in most democratic systems is a sign that democracy has come to an end. The next thing to try is by the names of religion or taking apolitical stand.

my 2 cents, posted 26 Nov 2002 at 07:44 UTC by tgw » (Journeyer)

I have been studying voting technology since 1998, have worked as a public election official, and have done some writing on the topic - so this is right up my alley.

  • Both ghostgum and sjmurdoch mentioned Dr. Rebecca Mercuri's work.

    Her views have received more coverage within the past year or two than most experts in the field, but there are other experts worth listening to that have alternate views on various voting technology issues.

    Three of these experts each hold a PhD. All four have worked in and around voting technology for many years. All four are well-respected in the field. Their views are worth considering, in addition to those of Dr. Mercuri.

  • sjmurdoch questioned "the need for electronic voting" and pointed to the UK and Europe using "bits of paper" that get put "in a box" - a system the he and others have commented "works very well". Also, djm commented that he didn't "quite understand the motivation" for the "push towards electronic vote systems".

    David Olsen wrote up an excellent explanation of why a "bits of paper" voting system is not feasible for much of the US, and helps to show why there is a "push towards electronic vote systems" (in the US, at least).

  • sjmurdoch commented on the "potential for fraud in the generation of elligible voters".

    alan suggested that biometrics be used to prevent voter registration and voter authentication fraud. Biometrics would be the ideal way to solve that problem. However, in practice, there are powerful political forces that stand against this solution - because of privacy concerns and other issues.

    In thinking through to what extent the current system of voter registration could be manipulated, I have concluded that the current system could probably be manipulated to affect the outcome of small, local elections. However - even as weak as the current voter authentication system is - in practice it would be very difficult, if not impossible, to manipulate it enough to affect the outcome of a large-scale election - without being detected (a critical distinction). So even though our current system (in the US) is far from perfect, it seems sufficient to prevent large-scale, coordinated fraud using bogus voter registrations.

    Parenthetically, the recently-passed-into-law Help America Vote Act of 2002 contains some provisions that help standardize and improve voter registration and authentication [see Section 303(a)(5)] in the US.

  • alan linked to a draft version of the revised FEC Voting Systems Standards (VSS). There is also a final version of the revised FEC VSS available.

  • djm commented that the "only area where electronic voting would be clearly superior to manual systems is speed of counting".

    I disagree. Electronic voting systems, using currently available technology, can excel past paper systems in terms of user friendliness and accessibility to disabled voters, in addition to speed of counting. Electronic voting systems also have the potential to enable options not available with paper voting systems - such as wide-spread citizen observation; automated inspection of voting software, configurations, and data; and remote voting via telephone and/or computer (preferably via a closed network).

  • djm also referred to "an electronic voting system which also spits out a paper record". I've found that E2P is a convenient way to refer to this type of voting system.

  • Provided I understood correctly, I believe djm mentioned that an E2P voting system "could give a copy [of the voted ballot] to the voter, in case the [ballot] box magically disappears". alan also seemed to point to this same sort of thing when he referred to "their carbon of their vote".

    This is exactly what you don't want to do if you want to prevent vote fraud - it would enable vote-selling and coercion. The less-than-ethical would be able to either (a) sell their vote and prove they voted in a particular way or (b) coerce other people to vote a particular way (i.e. "you better bring me your ballot-copy with a vote for 'Candidate Y' on it, or you're-fired / will-be-in-physical-danger / insert-an-undesirable-consequence-here").

  • helcio's comment on simplicity vs security is an excellent reminder. Us techies can create the most secure voting system ever devised, but if it's not understandable or usable to the least-common-denominator voter, then it's irrelevant. Real-world voting systems need to make sense and be usable to everyone - including the illiterate, people who are fearful of technology, people who are unfamiliar with technology, those with learning disabilities, and those with diminished mental capacity (yet are legally deemed to be sufficiently competent to vote).

  • chalst's perspective - that alan's solution is an inversion of a covert channels model - is quite interesting. It seems to reveal the proposal as an "isolate the ignorant" solution, instead of an "isolate the secret" solution - a very interesting perspective.

Re: my 2 cents, posted 26 Nov 2002 at 12:37 UTC by sjmurdoch » (Apprentice)

tgw: Thanks for your very informative reply. I will just add some clarification to my previous post.

  • Regarding voter registration, I don't think Biometrics will help the problem much. Even assuming Biometrics were 100% accurate, the best it can do is prove that the person who places the vote is the same as the person on this registered voter list. From my perception of the issues, the risk of fraud is not in people impersonating registered voters, but in the generation of the registered voter list. If I remember correctly there was some talk of legitimate voters not being on the registered voter list in the Florida Presedential election.

  • I agree that there should not be a way for a voter to be forced to show which way they voted. In fact this issue came up in the last General Election in the UK. For the first time voters are now allowed to vote by post in all cases. Previously a voter had to prove that they were unable to vote in person. The common case would be where they are out of the country at the time (General Elections are normally held during the summer holidays). The ability to use a postal vote led to accusations that in some areas voters were being coerced to request a postal vote and give their voting slip to someone who would cast the vote in favour of the person doing the coercion.

    Previously in most cases the people doing the coercion could not obtain a postal vote for the person being coerced, so at best they could intimidate them until they get to the voting place, but they cannot accompany the person in the voting booth where they mark the bit of paper. At best the person doing the coercion can say that the person coerced turned up. They cannot tell whether the person voted as they were asked, or even that they cast a valid vote. The voter can say they voted for anyone and this cannot be disproved.

    An interesting item mentioned at Rebecca Mercuri's talk was a technique designed to give a receipt but not allow coercion. Due to time constraints not many details were given, but from my understanding the voting machine would produce two small sheets of transparent material, each of these has a pattern on them such that when the two are placed over each other it shows who the person voted for. Once printed and examined by the voter, one of the sheets is put in the ballot box and is the vote, the other is kept by the voter. The sheet kept by the voter is not sufficient to tell who they voted for however through some technique it is possible for the voter to verify that their vote was counted, but once the two parts are separated it is not possible for the persons choice to be identified. I don't have any more details on this scheme but it sounds promising.

Vote early and vote often, posted 27 Nov 2002 at 01:30 UTC by jlbec » (Master)

tgw says:
in practice it would be very difficult, if not impossible, to manipulate it enough to affect the outcome of a large-scale election

I'm not sure I buy this. The Florida State police did their best to keep minority voters from the polls in 2000. IIRC certain poll workers sent other minority voters from polling place to polling place. This small amount may have been enough to decide the 2000 presidential election -- even ignoring the butterfly ballot issues.

tgw might claim that this was "detected", but I disagree. Detection is not that we know about it, but that we were able to repair the damage. It's nice that we know the dead of Chicago vote. The system is still compromised until the dead can't vote anymore and the persons elected falsely have been removed.

An awful lot of effort to protect a flawed system from fraud, posted 27 Nov 2002 at 17:14 UTC by vorlon » (Master)

A more useful exercise would be to explore how the current system which favors two parties that both map poorly to the interests of the voting populace can be replaced by something that would empower voters to vote their sincerely without fear of repercussions.

Covert channels, posted 29 Nov 2002 at 11:54 UTC by chalst » (Master)

tgw: Actually, I didn't introduce the idea of covert channels, Alan used them to justify confidence in his proposal. The `issue' I raised is I don't think this is a valid picture: one thinks of things like TEMPEST screening, etc. which I don't think are applicable when one is trying to keep arbitrary broadcasts *out*. Also, isn't the TEMPEST model a certification based model?

Comparison of American, Australia, posted 1 Dec 2002 at 02:54 UTC by pfh » (Master)

I'd like to comment on some of the differences between American and Australian voting systems. From reading various links above, the impression i get of the American voting system is that one

  • can vote for many positions: this makes it hard to make informed choices
  • can only vote for one candidate
  • don't have to vote: this really biasses the result

    Here in Australia one

  • only has to vote for four levels of government: federal senate, federal lower house and upper and lower houses of state parliament
  • can vote preferentially
  • have to vote (or rather have to at least turn up) or face a fine

    A couple of factors give minor parties considerable power in Australia

  • The senate has proportional representation, so the makeup of the senate actually reflects the proportions of people who voted for each party
  • Preferential voting means a vote for a minor party is not wasted

    This means that at the federal level at least, minor parties hold the balance of power.

    There has been an interesting battle over the state upper house here in Victoria. The Victorian upper house is currently not proportional (this differs from the senate at the federal level), and has been controlled by the major right wing party for many years. The major left wing (well ok, there isn't really much difference between the major parties any more, but nominally left wing anyway) party just won control over the upper house, and is almost certainly going to convert it to a proportional representation system.

  • public internet postings of votes, posted 24 Dec 2002 at 00:07 UTC by lkcl » (Master)

    i believe that the entire process of voting as it progresses should be placed on-line, such that interested independent parties can mirror and monitor the progress of the votes.

    to ensure anonymity, digital signatures can be applied (with identification stripped, which isn't normally how digital signatures are used!) to the vote plus the identity of the voter encrypted.

    the vote also needs to be double-signed, by the voting system.

    in this way, only the voter themselves can decrypt their vote, and prove their identity, should it be required, and also they may themselves go and check the published results to verify that their vote has in fact been counted.

    additionally, a specific private/public key pair can be issued for the EXCLUSIVE purpose of voting, which is issued on a per-voter basis, and that too used to perform a digital signature of the vote.

    the whole idea being that the process of outside and public review should discourage fraudsters from attempting to attack the system.

    on-line voting systems have the advantage that you cannot be attacked on the way to the polling station, because you would be able to vote from home.

    democracy gets people the politicians they deserve.

    i have to be honest, here: i find the idea that people would listen to illegal leaflets to be very funny (and also sinister).

    i believe that anyone who is sufficiently gullible to be manipulable by illegal television and leaflets etc. and who cannot be bothered to check up on their own laws ESPECIALLY deserve to end up with the politicians that end up in power.

    Electronically Enhanced Voting, posted 25 Jun 2003 at 20:51 UTC by DeepNorth » (Journeyer)

    We present an "electronically enhanced" voting scheme at the following location:

    HushVote.com

    This scheme has been approved in principle by the relevant parties (Canada Post, Municipalities and our third party supplier). It allows for all the requirements I could find on the internet at the time the design was put in place. One of the keys (pardon the pun) is that all the individual people involved can have the vote audited to show that it genuinely reflects the will of the voters both as individuals and as a collective.

    Note that the scheme reflects certain realities in Canada at this time. To give the same level of security (in Canada tampering with any part of the system results in serious jail time), it might be necessary to pass legislation in the jurisdiction holding the vote.

    Even if the system is tampered with by a trusted party, cheating can be found and reversed. It is a simple scheme, but I think quite sound.

    New Advogato Features

    New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

    Keep up with the latest Advogato features by reading the Advogato status blog.

    If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!

    X
    Share this page