Personal tools

shamos.html

CFP'93 - Shamos

CFP'93 - Electronic Voting - Evaluating the Threat

by Michael Ian Shamos, Ph.D., J.D. [1]


3/93
Copyright (c) 1993 by Michael Ian Shamos.
All rights reserved.


Introduction

This paper proposes a method of evaluating security measures for countering threats to computerized election systems. It sets forth six system requirements that society, through the state legislatures, has mandated for its voting systems. Any security measure that violates the requirements is too stringent or intrusive and will not be accepted by either the public or election administrators. Any system that is too lax under the rules will be rejected as unsafe. The list of requirements can be used to critique such proposals as voting by telephone, voting by lottery equipment, and opening systems to full public inspection.

The primary function of an electronic voting system is to capture voter preferences reliably and report them accurately. The two functions are logically separable but may be performed by the same equipment. Capture involves the interaction between the human voter and the means used to display the slate of candidates and issues and direct the voter through them to elicit his choices. Reporting refers to the recording, tabulation, printing and auditing of vote totals. Capture is a human factors problem to which a poor solution can result in confusion, disenfranchisement and loss of confidence in the electoral process. Reporting is a technological problem to which a poor solution can also result in confusion, disenfranchisement and loss of confidence in the electoral process.

Electronic voting systems are a source of worry because they perform their work in microcircuitry not readily accessible to examination and they often leave no tangible record of what they have done. An entire day's voting may produce no more than a small cartridge with voting results recorded in electronic memory. What goes on inside these machines is a mystery to the public and therefore causes uneasiness. Is my vote being recorded correctly? Does the system know who I am and therefore how I voted? How do I know they programmed it correctly? Could some hacker manipulate the votes? Who ever approved these things anyway?

There is a naive belief that mechanical systems (gears and levers) and paper ballots are more trustworthy than electronic systems. It is thought that mechanical devices can be inspected visually for evidence of tampering. Paper ballots are taken as original documents embodying the true will of the electorate. Although such reliance may seem reasonable in a society mesmerized by the sanctity of written documents, the facts are very different. Lever machines can be subtly altered so that a fraction of votes for a particular candidate will not register and the alteration can be disabled from outside the machine (to escape being detected in testing). Paper media, such as punched cards and mark-sense ballots, are unreliable because their origin cannot be established after they have been deposited in the ballot box. That is, we cannot tell whether they were filled out by a legitimate voter or were replaced by an intruder. I hold that electronic systems are far safer than any prior method of voting because they implement redundant security checks and audit trails and are much tougher to tamper with because of the size and nature of their tabulating components. I do not claim that electronic voting is free of troubles, but instead urge that its advantages far outweigh its risks.

This material is based on the author's participation in official examinations of approximately 50 different electronic voting systems since 1980 and a review of the election statutes of about half of the states in the U.S.

The Six Commandments

Democracy is ingrained in the American character and is reflected in its political process from presidential elections down to the most minor of township races. Our passion for fairness and equality has given rise to a set of fundamental requirements for electronic voting systems that are substantially the same from state to state, listed in decreasing order of importance:

I. Thou shalt keep each voter's choices an inviolable secret.

II. Thou shalt allow each eligible voter to vote only once, and only for those offices for which she is authorized to cast a vote [2].

III. Thou shalt not permit tampering with thy voting system, nor the exchange of gold for votes.

IV. Thou shalt report all votes accurately.

V. Thy voting system shall remain operable throughout each election.

VI. Thou shalt keep an audit trail to detect sins against Commandments II-IV, but thy audit trail shall not violate Commandment I.

The ordering of the Commandments is empirical, based on observation of which regulations and requirements state officials are prepared to relax for the sake of expedience. I have never known anyone connected with elections to tolerate a violation of I, II or III, but the others are treated with some flexibility. Note that IV is decidedly not the most important rule. Small errors in tabulation (e.g., +/-3 votes) are permitted in some jurisdictions and no one insists on perfectly accurate results, particularly if the outcome of a race is not affected. Commandment I is for the protection of the voter, who may waive it, as in absentee voting. However, the ballot of anyone who wants her vote kept secret must remain confidential at all costs (at least within the budget allocated for elections). Commandments V and VI are less stringent. Equipment that breaks down during an election can be fixed or replaced; audit trails are often impractical, unreliable and, as we shall see later, easily contrived to conceal the very ills they are intended to reveal.

Although there are small differences in detail among state statutory requirements across the country, in practice systems that meet these requirements are granted certification for use in public elections; those that demonstrably fail are denied certification. Between these extremes, numerous systems fall through the cracks; that is, they do not obey the Commandments but get certified anyway because they are not examined thoroughly enough to reveal deficiencies.

Secrecy is by far the most important voting requirement in this country. A voter might tolerate her vote not being counted because of technical errors, but will positively not stand for her choices being disclosed. The sanctity of a voting booth is not easily violated. Election officials are on hand to see that each voter enters alone and that no one can observe the voting process. There are no hidden cameras or eavesdropping equipment (well, I hope not; that fear might form the subject of another paper, since electronic systems emit signals that are easily received). Outside this controlled setting there is serious question whether secure voting is possible.

The implementation of IV (counting ballots correctly) is surprisingly tricky. My computer scientist friends assume that election programming is totally trivial - after all, to tally the vote you just have to keep adding one - and that coding it all up ought to be no more than an evening's exercise with the ++ operator. I can tell you that it isn't. There are many election phenomena that must be dealt with, including ballot rotation, straight-party voting, split precincts, cross-filed candidates, vote-for-many offices and primary lockout, to name a few. There is no universal agreement as to how these functions are to be implemented. For example, no one has yet come up with a suitable definition of what a straight-party vote is for tabulation purposes. If I vote Democratic in all offices except that I vote for a Republican in one office in which no Democrat is running, have I cast a straight Democratic vote or not?

We will see later that the Commandments can be used to measure and temper our response to election security threats.

No Receipts Allowed

If the voter is worried that the machine may not have processed her vote correctly, why doesn't it just print a receipt? After all, when I play the lottery I get a ticket, and it's that ticket alone that allows me to claim the prize.

Some candidates have figured out that it can be cheaper to pay voters directly for their votes than to spend the money campaigning and risk losing on Election Day. If you think about it, though, you might wonder how the candidate could ever know whom I voted for. What a fool he would be to pay money and never be able to verify that it had done any good. However, if the voting system printed a receipt that recorded my choices, it would violate the vote-buying prohibition of Commandment III, since I could redeem the receipt for cash from an unscrupulous candidate. (I leave it to your political imagination to determine whether any such people exist.) Without a receipt you would think he has only my word for how I voted, but even this is not true. Every card, mark-sense and electronic system can easily be used to implement vote-buying, but not on a large scale. (I won't publish how this is done, but it is absurdly simple.) Receipts would turn the practice into a virtual epidemic.

The Quest for Perfection

The fact that banks can be robbed is not a valid justification for keeping your money in a shoebox. The reasons are that (1) the chance of a robbery is low; (2) even if money is stolen you will not necessarily suffer a loss; and (3) the bank keeps only a small portion of its assets in the form of cash. Why should voting systems be held to a standard of perfection when nothing else in society is? Nonetheless, electronic voting watchdogs insist that election equipment must be perfect or it is totally unusable. The analogy between voting systems and the bank is particularly apt because (1) the chance of a system being tampered with successfully is low; (2) even successful tampering does not necessarily result in the wrong candidate being elected; and (3) only a small portion of the vote is cast on one machine.

In short, perfection need not be sought in election systems and will certainly not be achieved. What makes sense instead is to evaluate the threat of intrusion or undetected error and minimize their probability.

The Audit Illusion

It is important to realize what is supposed to be accomplished in an audit of a voting machine or election. Ideally, one ought to be able to reconstruct the ballots in their entirety, verify that no unusual or unauthorized events took place during voting or tabulation, and review the correctness of the vote totals. To imagine that there is any realistic mechanism to accomplish this is to indulge in fantasy. Let me be very clear on this point - no existing voting system is auditable. Furthermore, I have never seen a design for an auditable system, and doubt that any jurisdiction could afford one if it existed.

The problem has to do with the separation of capture from reporting. The voter's intention must be elicited either directly or in machine-readable form for tabulation to occur. There are essentially only two types of systems to do this - those that employ physical ballots (ballot systems) and those that do not. The latter are usually known as direct recording systems, often DRE, for direct recording electronic.

Ballot systems are sometimes naively regarded as the safest, a vestige of our faith in the superiority of paper records over the electronic. The dream is that in order to verify the election one need do no more than gather up the ballots and tabulate them a second time. However, ballot systems are not only unsafe but completely unauditable. Ballots, particularly punched-cards, are easily forged. They must also be physically handled and transported, which provides the opportunity for substitution. Even if they are counted at the polling place by inserting them directly into the tabulating equipment, they must be gathered up for delivery to a storage location to be retained in case of a recount. Ballots are frequently damaged or altered by the equipment during tabulation. In this case, a recount will reveal a discrepancy between the original totals and the new results, but it is impractical to determine how the voter actually voted, since it cannot be readily discovered what condition the ballot was in when cast originally. And all of these problems arise before we even consider tampering in the form of ballot stuffing. When you see a ballot, try to imagine where it came from, whether the person who cast it was authorized to do so and whether the ballot is still in the same condition as it was when cast. You can't tell and neither can a tabulating machine, and no audit trail can change that.

Direct recording systems, while better than ballot systems, are also unauditable. At least there is little question of ballot authenticity and provenance, though correctness may be an issue. However, there is still no way to prove that the selections captured by the audit trail are really those made by the voter. Suppose that the system presents the slate of candidates to the voter properly, but either through error or nefarious design randomly records a vote for the Republican senatorial candidate regardless of who was actually selected. Suppose further that it keeps a perfectly accurate audit trail of these incorrectly recorded votes and that it even does so redundantly so that all copies of the audit trail match exactly. How would you propose to reconstruct the election from this audit trail?

Even if the voter could be given a receipt, which we have seen is impermissible, what good would that do? Through error, the receipt might be correct but the vote might still be recorded erroneously. But what if there were independent mechanisms, one at the point of capture and one at the point of recording, both of which produced receipts and these were compared for verification before the vote was permanently registered? This may reassure us against an innocent programming error, but it provides no protection against deliberate tampering with the equipment. It is therefore wrong to point to anonymity as the enemy of auditability.

What auditing an election really means is verifying that the software was working correctly, that no unauthorized acts or steps occurred during the election (such as resetting the counters to zero) and maintaining intermediate records so that votes will not be lost in case of an equipment or power failure. Auditing does not, and cannot, mean the ability to rebuild each individual ballot after the polls have closed.

These logical impossibilities do not prevent states from imposing the audit requirement, vendors from attempting to satisfy it, and examiners from certifying the systems anyway. On many occasions I have recommended certification of a system that had an imperfect auditing mechanism. The reason is that I felt the audit trail was adequate under the circumstances. I do not subscribe to the belief that an audit trail must allow complete reconstruction of the election and every ballot cast. I am satisfied if it is likely to reveal irregularities (mistakes) and most forms of tampering. The evil is not intrusion but undetected intrusion.

Testing

The most practical method of ensuring that systems comply with the Commandments and hence are safe for use in elections is to test them. We have seen that tampering cannot be prevented, but only discouraged and made difficult. The way to verify that a system has not been compromised is to put it through a battery of tests designed to uncover intrusion. If the intruder is not familiar with the nature of the tests, he will find it difficult to avoid detection.

Texas employs a three-step testing program. A first test is conducted at least 48 hours before the election at a time and place that is announced in advance and which is open to the public. The second test is performed immediately before the election under the supervision of the presiding judge of elections. A third test is made immediately after the closing of polls. Neither of the last two tests is open to the public, but the tests are witnessed by representatives of all parties or candidates represented on the ballot. All of the test materials are secret and are delivered and picked up by sheriff's deputies under seal, so there is no prospect of a potential intruder having any idea what will be tested.

One may readily argue that no reasonable sequence of tests can exercise every possible logical branch of a complex computer program. So be it. Neither can any such test guarantee that the navigation system of a 747 is working properly, or that it will continue to work during flight, but for some reason this fact does not keep me from flying. (The reason is probably that plane crashes are statistically rare.) The question is not whether a voting system is error-free - we may accept as given that it is not - but whether the undetected errors compromise our faith in the election. Because incidents of tampering with elections voting systems are extremely rare, we are probably justified in believing that the equipment works.

The Importance of Decentralization

The nightmare tampering scenario has an unscrupulous vendor altering its software to favor a particular candidate or party and distributing it all over the country so that the outcome of the next election is a foregone conclusion. Efforts to detect this tampering would be hopelessly frustrated by security interlocks and the confidentiality of the vendor's source code. This might make a good plot for a novel or a movie, but it is not feasible in practice. The reason has to do with decentralization of election setup, which is one of the principal saviors of voting integrity.

Election systems typically contain software that permits them to be used over again for a wide variety of elections. The system itself, when distributed, knows nothing about candidate names, party affiliations or ballot positions. That information is added locally as tabular data by election officials on a precinct basis. (There are over 100,000 voting precincts or their equivalent in the U.S.) The candidates that appear on the ballot, and the positions in which they appear, can literally be different for every precinct in the country. In many systems, the candidate names and parties are not even present in machine-readable form inside the voting machine. It is impossible, therefore, for any preset software to fix an election predictably. (It can introduce errors, but would have no way of ensuring victory for any particular candidate.) The software cannot search for names, since none may be stored.

Can software be made that accepts surreptitious input from local officials on the scene and alters the votes accordingly? Certainly, but I feel confident that any conspiracy involving 100,000 people is likely to unravel. You say it's not necessary to alter the results in every precinct to throw a presidential election? Maybe just a few key counties in a few key states? The trouble is that the more aberrant the outcome in a jurisdiction, the louder the cries of irregularity and the more certain there is to be a recount. You can't just divert every vote away from one candidate, especially if he was leading in the polls. Within a precinct, only small deviations can conceivably go unnoticed, so crowds of people need to be involved in the scheme. Even in counties that perform central tabulation (ballots are not counted locally but are transported to the county seat for processing), results are still reported broken down by precinct. It is therefore safe to confine one's worries about tampering to local elections. An appropriate response to the risk is to hold public testing, not to implement outlandish security measures.

Open Systems

The proposal has been made that voting systems be made "open" in the sense that their entire design, including schematics and source code, would be available for inspection and verification by the public. Although there is some merit to the idea, it carries risks and on balance does not solve the actual problem.

No one proposes to open bank or lottery software to public view. The reasons, aside from the fact that these systems are trusted, are that (1) the public is poorly equipped to conduct meaningful technical evaluations; (2) revealing all aspects of a system, including its security mechanisms, is itself a serious breach of security because it arms potential intruders with precise information about the system's vulnerabilities (a bank may as well distribute a blueprint showing where all of its alarm sensors are located); and (3) there is no assurance that the code so exposed is the code that is actually in use. Such an exercise tends to prove only that a suitable program existed at one time. With respect to the Commandments, open inspection violates III in that it facilitates, rather than suppresses, tampering.

I do not suggest that we are forced to rely helplessly on the good works of the system vendors. By no means. A thorough program of system evaluation and testing by disinterested examiners, combined with administrative control over the distribution of system software and updates and public pre- and post-election tests seem to me to be adequate.

Telephone Voting

Phone voting is an idea whose time has not come; it is a non-solution starving for want of a problem, as a brief look at the Commandments will verify. The arguments in favor of phone voting are that it is more convenient for voters, is simpler to administer, and obviates the need for polling places and warehousing of tabulation equipment. Here is a short list of its drawbacks:

Commandment I. It is neither private nor secure. Telephones are easily tapped or eavesdropped upon even without direct electrical connection. Suppose the authorities actually have a legal wiretap in place as the vote is cast? We could have the specter of the government watching its enemies to see how they vote.

Commandment II. Should I happen to learn a voter's password, I can not only vote twice (once for myself and once for her) but can disenfranchise the other voter. She will protest to the authorities that she was denied a vote, but the computerized record will show that her vote was indeed cast, and (without a receipt to show for it) she will not be believed.

Commandment III. Phone voting not only permits but encourages vote-buying schemes. In order to get paid for a vote, I go to the house of my local ward heeler and cast my vote there, in his full view. I then collect $20 for having voted "correctly." (But why should I even vote at all? I can just give my access code, or whatever other password is required to cast a vote, to a party official, who can then vote in my place.) A voter is not allowed to be accompanied to the voting booth in a polling place, so this problem cannot occur in regular elections.

Commandment V. What sort of equipment will be used to present the slate to the voter and capture the vote? Who will pay for it? How will it be set up and programmed for each election? How will it be maintained in the absence of centralized supervision?

Commandment VI. What would the audit trail look like? Surely not a list of traced telephone numbers along with the votes cast from them. But then how could anyone verify the source or authenticity of a vote?

There are numerous other social reasons why phone voting is a poor idea. Not everyone has a phone, and the requirement that people purchase something as a precondition of voting is an impermissible poll tax (24th Amendment). The voting process cannot be readily supervised when conducted over private telephones. Verification of identity and registration are substantial problems. Universal identity schemes, such as cards and internal passports, are anathema in the U.S., but would be needed for phone voting. The need to go to a polling place invests the voting process with an aura of seriousness that would be lost if one were to sandwich balloting in between other casual household activities.

Lottery Voting

In January 1993, the jackpot in Pennsylvania's weekly Super 7 lottery was $24 million. There was one winning ticket. In the absence of information to the contrary, I assume that the lucky winner had to do no more than present the ticket to lottery officials to claim the prize. I do not profess to understand the mind of the politician, but I would be far more interested in fooling with the lottery system for a possible gain of millions than to rig an election to become county commissioner. (We saw above that it is not feasible to throw a statewide or national election.) I have wondered for years why we are not troubled over the possibility that clever teenagers might divert huge sums from the public treasury by manipulating the lottery system. It must be that we feel the lottery systems are secure.

We don't deem electronic voting systems to be secure, though, judging from the number of articles, panel discussions and lawsuits over the issue. The conclusion seems obvious - just use the lottery system for voting. When I suggest this to state election officials, their reaction varies from disgust to amusement, but not a one of them has ever taken the idea seriously. Perhaps they are unwilling to use the same equipment for a frivolous and vaguely immoral activity (gambling) as for a high-minded civil function that goes right to the core of democracy (voting). Government spending, however, does not necessarily track righteousness. The annual operating budget of Pennsylvania's lottery is about a billion dollars; the allocation for its Bureau of Elections is barely a million. (The latter figure is misleading, since most election spending is by the separate counties, not the state.) Lottery equipment operates smoothly and securely and is exceptionally well-maintained, since a failure results in large losses in revenue. By contrast, there is not sufficient money available to justify applying the same level of technology to elections. A solution is to close down the lottery for Election Day (at a loss in income exceeding the Bureau of Elections' entire budget) and use the equipment for mark-sense voting. There are even more lottery booths in the state than there are polling places.

Of course this proposal is simplistic. It does not address the problems of verification of voter registration and distribution of ballots to authorized voters, along with a panoply of other problems. But it makes the point that security is available at a price; we're just not willing to pay that price for elections, which do not produce revenue.

Experience

Claims of election irregularities are frequent. In my experience, their chief source is the willingness of unsuccessful politicians to embrace any conceivable reason for their loss except that the voters didn't want them. Everything from equipment failure to outright tampering is alleged, often without the slightest shred of evidence. When the candidate's party learns that it will have to bear the cost of a recount, their zeal is quickly extinguished unless the claims are provable.

I have been asked to consult many times for candidates who hoped to demonstrate that an election had been stolen from them through tampering with electronic equipment. In no case have I found credible evidence to support any such theory. (By contrast, I am aware of situations in which punched card and mark-sense ballots have been switched or altered.)

Error is a different story. Conditions on election night are hectic, and media demands for instant returns are unrelenting. The result of these factors is that a large number of mistakes are made, most of which are corrected quickly. Precincts may be counted twice or fail to be counted at all. Ballots become mangled by the counting equipment or become separated from their write-in envelopes. Computers fail, the power goes out and incorrect ballot faces are inserted into the machines. These problems are the result of human limitations rather than deliberate tampering, and need to be given due attention. But it is a blunder to attempt to design a totally secure system while ignoring this very real source of election trouble.

In summary, the effort expended in meeting threats to the election process should be rationally related both to the probability of the threat and the seriousness of its effects. No one would buy a safe that could easily be opened, but everyone who has ever bought a safe has bought one that can be cracked. The same is true for voting systems. The issue is not whether they are secure, but whether they present barriers sufficiently formidable to give us confidence in the integrity of our elections.


References

  1. The author is an attorney and adjunct faculty member in the School of Computer Science at Carnegie-Mellon University. He has been a statutory examiner of electronic voting systems for Pennsylvania since 1980 and serves as the designee of the Attorney General of Texas at electronic voting examinations in that state. The views expressed herein are personal to the author and do not necessarily reflect the positions of the Pennsylvania Bureau of Elections or the Attorney General of Texas. Author's present address: 605 Devonshire Street, Pittsburgh, PA 15213. (back to text)

  2. Recall that women now constitute a majority of registered voters in the United States. (back to text)



Return to CPSR conferences page.


Return to the CPSR home page.


Send mail to webmaster.

Archived CPSR Information
Created before October 2004
Announcements

Sign up for CPSR announcements emails

Chapters

International Chapters -

> Canada
> Japan
> Peru
> Spain
          more...

USA Chapters -

> Chicago, IL
> Pittsburgh, PA
> San Francisco Bay Area
> Seattle, WA
more...
Why did you join CPSR?

In these times, this is the kind of organization that technology professionals should be a part of.