Misassment of Security in Computer Based Election Systems

Part of the Voting and Elections web pages, http://www.cs.uiowa.edu/~jones/voting/
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Sept. 22, 2004.

Copyright © 2004 RSA Security Inc.
This is the author's version of the work. The definitive version was published in Cryptobytes, 7, 2 (Fall 2004) 9-13, http://www.rsasecurity.com/rsalabs/cryptobytes/CryptoBytes_Fall2004.pdf

Abstract

When today's computer-based election systems use cryptographic technology, it is more likely to serve a cosmetic purpose, providing an illusion of security, than it is to actually secure anything. Example abuses range from simple ``fairy dust'' applications of cryptography to confusing encryption with authentication, encrypting the wrong data, poor key management, and related problems such as failure to understand the difference between random and pseudorandom. These demonstrate serious weaknesses not only among voting system vendors, but also in independent testing labs, security consultants, and government.

1 Introduction

When an election is conducted in a small group by a show of hands, security is not an issue. Everyone present can observe the entire process and determine the result for themselves. Security becomes an issue when the number of participants grows to the point that the voters cannot all vote in the same room, and it becomes an issue when secret ballots are introduced in order to protect the rights of voters who oppose the powerful or hold unpopular opinions.

When elections are distributed between many locations, we must secure the conveyance of data between these locations, not so much because of the possibility of eavesdropping, but because we need to assure ourselves that it is authentic. In fact, almost all of the data we are interested in conveying is public. The ballot layout is usually published weeks before the election and the totals from the precinct are usually posted in public when the polls close. The only actual secrets included with this data are authentication keys being distributed for later use.

Unfortunately, these elementary facts appear to be lost on many voting system developers, evaluators and customers. The following examples illustrate this.

2 Fairy Dust

In the summer of 1996, a subcontractor working for Wyle Laboratories of Huntsville, Alabama evaluated the software of the Electronic Ballot Station, an innovative new voting system made by I-Mark Systems of Omaha Nebraska. In the review of this software, the subccontractor reported that this was the best voting system software they had ever seen, and they were particularly impressed by its security and its use of DES [1].

This system was brought before the Iowa Board of Examiners for Voting Machines and Electronic Voting Systems on November 6, 1997 by Global Election Systems of McKinney Texas, which had renamed the system the AccuTouch EBS 100. At that examination, it quickly became apparent that the use of DES in this system was quite naive. The question that exposed this was simple: Given that DES is a symmetric key cypher, the security of the system depends crucially on how the key management and distribution problems are solved. So, how are they solved?

The answer from Global was disappointing but difficult to draw out: There was no key management or key distribution problem because there was only one key and it was hard coded into every copy of the system. In a prototype system, as a place-holder for future development, such a scheme might be appropriate, but such a primitive scheme should never have come to market. Unfortunately, this primitive security system remained in use until 2003, by which time, Diebold had purchased Global Election Systems [2].

Here, it is clear that cryptography was used as fairy dust. It was sufficient to fool the examiner for Wyle Labs into believing that the system was secure, where a more able examiner would have admitted an inability to evaluate the system's security instead of being impressed by a thin veneer of cryptography.

3 Incorrect use of Cryptography

What did the I-Mark system encrypt? As it turns out, encryption was used to guard the contents of the electronic ballot box during transfer from the electronic ballot station to the centralized election management system. This raises a second issue: This information is not secret. The best practice when closing the polls at a polling place is to print and post in public a copy of the election totals for that polling place before transfer of the electronic record to the election management system. This allows observers to verify that the data eventually published for that polling place matches the data disclosed before transmission.

If the data is already public, encryption must serve some other purpose. In this case, the intent is clearly to offer some degree of authentication. Unfortunately, simple encryption offers no authentication at all unless there is some redundant structure to the encrypted data. A compactly encoded binary file of election results would offer little assurance in this regard.

I-Mark, Global and Diebold were not alone in making this error. In the fall of 2003, the state of Ohio contracted with Compuware Corporation to evaluate four of the direct-recording electronic voting systems then on the market [3]. The Compuware report noted that the Election Systems and Software iVotronic system made no use of cryptography in data transfers from the voting machine to the election management system, it recommended that strong encryption be used, but it did not mention the need for authentication.

In fact, there is authentication in several of these voting systems, but it is accidental and weak. In the case of the Optech Eagle, sold by both Sequoia and Election Systems and Software, the data returned to the election management system includes the time at which the system was prepped for the election, and this is checked on receipt. While the time at which a system was prepped for the election is no secret, obtaining this information to the full precision of the hardware clock is difficult, so it represents a useful if weak authentication token, defending against forgery but not man-in-the-middle attacks [4].

4 How Strong is Strong Enough?

When the I-Mark/Global/Diebold AccuTouch system came under widespread public criticism in 2003, many considered the use of DES to be a significant weakness [2]. This encryption standard, with only a 56-bit key, was never seen as very secure; designs for a brute-force DES cracker had been published in 1998 [5], and successful attacks were demonstrated shortly after that.

The use of cryptographically secure authentication to protect transmission of election data from precincts to election management systems is a specialized context, in which the basic assumptions under which DES was cracked may not apply. There are two ways in which an adversary may attack this transmission path in a voting system:

First, the adversary may attempt a man-in-the-middle attack, trying to crack the authentication, edit the vote totals and forge new authentication data for the edited totals. In jurisdictions where polling places transmit totals by public networks, for example, by telephone, there is usually a fairly short window during which the data must be transmitted, on the order of an hour. If data is hand-delivered, for example, in an electronic cartridge, the delivery window will be longer to allow for physical travel, but this does not give the adversary much more time for computation. Attacks that take many hours would be of no use here.

Second, the adversary may forgo cracking the authentication keys and attempt a trial-and-error attack, hoping to deliver an acceptable forgery before the authentic data is transmitted. Alternately, the trial-and-error strategy could be forced on a man-in-the-middle attack when a complete crack of the authentication keys is impossible. In either case, if even one bit of authentication information is wrong, the attack can be detected. All modern voting systems offer alternative channels that can be used when an attack is discovered, so trial-and-error is unlikely to pay off. In short, very weak authentication is sufficient if the attacker gets only one shot at a trial-and-error attack.

5 Is Pseudo-Random Random?

One critical requirement for any voting system used in the United States is that it protect the secrecy of the voter's ballot. The order in which voters enter a particular voting booth is no secret, any observer can record this. The ballots themselves are also only weakly guarded. In case of a recount, they may well become public record, as in Florida 2000. What must be broken is the link between voters and their ballots.

One way to break this link is to store the ballots in random order inside the voting machine. Unfortunately, what a naive programmer may believe to be random may be merely pseudorandom and quite predictable, to a cryptanalyst. Unfortunately, this fact is lost on many who advertise their services as security professionals.

For the I-Mark/Global/Diebold AccuTouch system, for example, a well-known and very weak linear congruential random number generator was used [2]. Unfortunately, when Compuware Corporation evaluated this same system, they concluded that this generator posed no risks [3]. Curiously, they did note that the pseudorandom number generators used for this purpose by ES&S and Sequoia were seeded from the real-time clock, showing some awareness of the limits of randomness.

Unfortunately, a brute-force exhaustive search through all possible 32-bit seeds is remarkably fast on a modern computer. Furthermore, the sample size, typically around 100 ballots per voting machine, is large enough that an exhaustive search may well be sufficient to reveal the seed that put the ballots into particular slots within the ballot box. As a result, simply seeding a weak pseudorandom number generator from the time of day clock may offer no real privacy.

Clearly, the strength and seeding of the pseudorandom number generators used for ballot storage should have been investigated by Compuware. It is not safe to rely on the random number package that comes with whatever system or language is being used, nor to rely on default seeding of these generators. The only acceptable alternative to a carefully seeded cryptographically secure pseudorandom number generator is the use of additional carefully selected sources of randomness to bolster a weak generator.

6 Do We Need Public Keys?

Is symmetric key cryptography safe for use with voting machines, or do we need to build a public key infrastructure for elections? The central issue here is one of secure key distribution, and the answer rests on an understanding of how voting systems are used.

A typical jurisdiction has an elections office that includes a secure warehouse where all of the voting machines are stored between elections and where the election management system runs. Prior to the election, the election management system is used to prepare ballot information for each precinct and load this into the voting machines.

Some voting systems are loaded by physically connecting them to the election management system, one at a time in the secure warehouse. Others are loaded using PCMCIA cards or compact flash cards that are sealed into the system in the warehouse. Yet others are loaded at the polling place immediately before the polls open, using portable media hand delivered to precinct election officials.

So long as the voting systems are prepped for the election in the secure premises of the election warehouse and then securely delivered to the polling place, or so long as portable media are held in trustworthy hands, cryptographic keys can be delivered to the voting system through this route and there should be no need for more complex cryptographic models.

There are two thorny issues that must be addressed before accepting this argument. First, the custody issue must be addressed seriously. If authentication or cryptographic keys are loaded in a voting machine and then it is left unattended in an insecure location, someone might open the machine up and extract this information. Clearly, physical security is not obsolete.

The second concern is rising pressure from county election managers for faster ways to prepare machines for election day. This leads, naturally, to proposals for remote-control initialization and testing of voting machines using wireless technology. The security problems this could create verge on nightmarish, yet some vendors are proposing that their next-generation voting systems will operate this way.

7 Anti-Virus Tools?

It is clear that voting systems must be protected from viruses, and this is required by Section 6.4.2 of current voting system standards [6]. What is not so obvious is that protection from viruses or other malware injected into the system via network ports or removable media need not rest on the use of anti-virus software. Unfortunately, this has not been understood by many well-meaning security evaluators. For example, one assessor asked that Miami-Dade County install anti-virus software on the ES&S iVotronic voting machine [7].

The iVotronic does not run a commodity operating system, nor does it use data formats that are known vectors for virus distribution, although it does use an industry-standard data format for compact flash card directories. As such, no commercial anti-virus software is applicable and it is quite possible that the system is inherently virus-proof. Furthermore, anti-virus software can only detect known viruses, which is to say, it can only defend against second and third attacks, after the discovery of an initial successful attack.

Certainly, assessment of the security of voting systems against viruses and similar attacks is appropriate, but simply checking that the latest anti-virus tools are installed is not enough. Instead, the relevant questions are: Are the communication protocols used by this system inherently free of virus delivery mechanisms, and are they correctly implemented, for example, free of buffer overflow vulnerabilities?

If it can be shown that a communications channel cannot deliver data that will serve as input to an interpreter or be read as machine code, then that channel cannot be used to inject viruses or other malware into the system. This is the question that must be assessed on most embedded systems, and in general, the security offered by systems that meet this standard is higher than can possibly be met by installing and regularly updating anti-virus software. In fact, routine installation of antivirus software offers a path for Trojan horse attacks via that software, so it poses security risks of its own.

Conclusion

Unfortunately, these stories show that not only voting system vendors but also a significant number of voting system evaluators have seriously misunderstood the security requirements for voting systems. The presence of inept security in voting systems reflects badly on the vendors and on the level of sophistication of their customers, but after the publication of \emph{Analysis of an Electronic Voting System} [2], this is not news.

What is more distressing is the extent to which the security evaluations that have been done for voting systems expose flaws in the knowledge of security professionals. It may not be too much of an exaggeration to state that many of today's security professionals have focused so much on conventional data processing applications using Microsoft Windows in a corporate setting that they are very poorly adapted to examining the security of novel applications outside the Windows domain or outside the commercial data processing domain.

References

1. Qualification Testing of the I-Mark Electronic Ballot Station, Report number 45450-01, Wyle Laboratories, Huntsville AL, 1996, 336 pages. Note, this report is proprietary. Only content discussed in open meetings of the Iowa Board of Examiners for Voting Machines and Electronic Voting Systems is cited here.

2. T. Kohno, A. Stubblefield, A. Rubin and D. Wallach, Analysis of an Electronic Voting System, IEEE Symposium on Security and Privacy, Oakland CA, May 2004.

3. Direct Recording Electronic (DRE) Technical Security Assessment Report, Compuware Corporation, Columbus OH, Nov 2003.

4. D. W. Jones, Problems with Voting Systems and the Applicable Standards, Improving Voting Technologies -- The Role of Standards, Serial No. 107-20, pages 154-191, U. S. House of Representatives Committee on Science, Washington DC, May 2001.

5. Electronic Frontier Foundation, Cracking DES, O'Reilly, 1998.

6. Voting System Standards, Federal Election Commission, Washington DC,April 2002.

7. C. Jackson, Audit Report -- City of Opa-locka Special Election Held April 29, 2002, Memo to D. Leahy, Miami-Dade County Elections Department Public Records, August 7, 2002.