Thoughts on voting machine fraud
Posted 19 Nov 2002 at 21:49 UTC by alan
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.
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
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.
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 :)
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.
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
- The manufacturers will know the assignment, and so can arrange
to broadcast it;
- Radio receivers, in particular, are very easily concealed;
- 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.
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.
- Dr. David Jefferson, a former professor of computer science and the Chair of the Technical Committee for the California Internet Voting Task Force, wrote up his alternate views (one paragraph down) to those of Rebecca Mercuri and Peter Neumann. I have spoken with Dr. Jefferson and have heard him speak, each on several occasions, and I have great respect for his views. His perspective is thoroughly grounded in real-world, hands-on, practical experience with public elections.
- Dr. Michael Shamos presented a paper on Electronic Voting - Evaluating the Threat back in 1993. He is an Adjunct Faculty in the Department of Computer Science at Carnegie Mellon University and has served as a voting systems examiner for two US states. Dr. Shamos wrote up a challenge (bottom of page) to those who comment publicly about hypothetical attacks on voting systems, while not mentioning the fact that many of the theoretical attacks would be very difficult, if not impossible, to execute undetected in the real world.
- Dr. Lorrie Cranor created the SENSUS voting system while working on her master's degree. She was the maintainer of the e-lection mailing list for several years, and had the opportunity to moderate a panel on Online Voting for the US Congress' Internet Caucus Advisory Committee. Dr. Cranor also wrote an excellent paper on Voting after Florida.
- Mr. Roy Saltman authored what has been referred to as "probably the most-cited work on electronic vote-counting", the 1988 NIST study on Accuracy, Integrity, and Security in Computerized Vote-Tallying. In 2001, Mr. Saltman also was an invited speaker before the US Congress on The Importance of Research and Standards in Effective Election Administration.
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.
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.
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?
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.
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.
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.