Critical Security Issues In Diebold Optical Scan

EXCERPTS FROM THE REPORT: Incorporated into the foundation of the Diebold Precinct-Based Optical Scan 1.94w system is the mother of security holes, and no apparent cure will produce infertility, or system safety.

...the removable media (memory card), which should contain only the ballot box, the ballot design and the race definitions, but also contains a living thing – an executable program which acts on the vote data. Changing this executable program on the memory card can change the way the optical scan machine functions and the way the votes are reported. The system won’t work without this program on the memory card. Whereas we would expect to see vote data in a sealed, passive environment, this system places votes into an open active environment.

With this architecture, every time an election is conducted it is necessary to reinstall part of the functionality into the Optical Scan system via memory card, making it possible to introduce program functions (either authorized or unauthorized), either wholesale or in a targeted manner, with no way to verify that the certified or even standard functionality is maintained from one voting machine to the next.

...Within the context of expected security responsibilities, one layer of security should be preventive cost factors. While the system will always be breakable, the feasibility of penetration should be inhibited by the cost of such an endeavor. What the author has identified, however, is an exceptionally flexible one-man exploit requiring only a few hundred dollars, mediocre technical ability, and modest persuasive skills (or, in lieu of persuasive skills, just a touch of inside access).

...This design would not appropriately be characterized as “a house with the door open.” The design of the Diebold Precinct-Based Optical Scan 1.94w system is, in the author’s own view, more akin to “a house with an unlockable revolving door.”

...Only awareness of the flaws will facilitate development of the countermeasures needed to hamper the effectiveness of the attack vectors. If the layers of protection are interconnected and relying on each other they are not true layers – it is just a one-layer system which is only as strong as its weakest point. Also bear in mind that layer interaction removes the layer separation. Therefore, a proper security analysis should always begin with the assumption that the previous layer has been compromised.

If that assumption cannot be made, the layers are interconnected and the dominoes will fall.

... (Background) On May 26, another visit was scheduled at the Leon County Elections Warehouse, and the author quickly penetrated the security of the Diebold Precinct-Based Optical Scan 1.94w system three times, each time with a different memory card manipulation.

...The Diebold optical scan system

The Diebold optical scan system consists of three components: The optical scan reader used at the polling place to scan and interpret ballot data; the central tabulator, which resides on a standard PC computer using the Windows operating system, used at the county election office to collect and tally votes from polling places; and a removable data storage unit, the memory card that stores the votes.

Before each election, the Diebold central tabulator program, called “GEMS,” defines the races in the election. The optical scan machine is then connected to the GEMS server via an RS-232 serial port connection.

The removable storage (memory card) is placed into the optical scan machine, and GEMS writes information onto the memory card through the optical scan unit.

According to the Diebold optical scan user’s manual, the programming of the memory card can also be done remotely by modem connection over a public telephone network.(7) After the cards have been programmed, they are interchangeable among voting machines with the same or similar firmware version. Therefore a single machine can be used to program all cards needed.

During the election, voters place filled-out ballots into the scanner, which interprets the ballot data and stores the totals (but not the individual votes) on the memory card. After the election, the data on the memory card is transferred into the central tabulator by a modem through a modem pool, or is physically brought to the county elections office and uploaded through an optical scan machine there via an RS-232 serial port connection. It is noteworthy that operational practices may vary -- from election office in-house operated modem pools to a virtual modem pool purchased as access service from a 3rd party provider.

...Findings

It has been known for years that Diebold uses its own proprietary programming language, Accu-Basic, for report-generation. This can be known from publicly available information, including compiler source code(10), an unfinished programming manual(11), AccuBasic source code files(12), pre-compiled files(13) and memos(14).

A large number of experts have reviewed this information but they have generally failed to understand the role and execution environment of Accu-Basic. A contributing factor could be that these critical pieces of information may have been omitted from official documentation, evidenced from the AccuVote-OS 1.94 Precinct Count User’s Manual, Revision 2.0, July 18, 2002, page 14, which fails to list the executable program as an item stored in the memory card.(15)

Accu-Basic programming is a two phase process. First the Accu-Basic program source code needs to be pre-compiled with a compiler, converting it from a human readable source code form into token based pseudo-code. The pseudo-code is still a non-binary, ascii file. This first phase programming is normally done on a standard PC running Windows or *ix –variant operating system. The author used the FreeBSD platform. Then this pseudo-code is transferred to the final execution environment (that is, to the voting machine), where the pseudo-code is executed by an interpreter.

Note: The interpreter, built into the optical scan firmware, will execute the code following the instructions on the memory card. No information has been provided about the interpreter.

A publicly available Diebold memo from Guy Lancaster to Steve Ricke, dated 18 Nov 1999 17:28:23, subject “Re: Report Failure”(16) (Provided in Appendix), revealed that:

- The pre-compiled AccuBasic program is uploaded and is executed from the memory card.

- The AccuBasic program is not protected against corruption nor tampering with checksums.

This omission appears to be in conflict with the word and intention of the 1990 Federal Election Commission Standards, Chapter 5, specifically, but not limited to, articles 5.1, 5.3 and 5.5.(17)

Implications of this design:

With this design, the functionality – the critical element to be certified during the certification process -- can be modified every time an election is prepared. Functionality is downloaded separately into each and every machine, via memory card, for every election. With this design, there is no way to verify that the certified or even standard functionality is maintained from one voting machine to the next.

With regard to certification, please also note that, because of the architecture, a trustworthy certification cannot be done separately for hardware and software. For a true understanding of the execution environment, the certifier must understand both of these components.

...Security exploits

Exploits available with this design include, but are not limited to:

1) Paper trail falsification – Ability to modify the election results reports so that they do not match the actual vote data

1.1) Production of false optical scan reports to facilitate checks and balances (matching the optical scan report to the central tabulator report), in order to conceal attacks like redistribution of the votes or Trojan horse scripts such as those designed by Dr. Herbert Thompson.(19)

1.2) An ingenious exploit presents itself, for a single memory card to mimic votes from many precincts at once while transmitting votes to the central tabulator. The paper trail falsification methods in this report will hide evidence of out-of-place information from the optical scan report if that attack is used.

2) Removal of information about pre-loaded votes
2.1) Ability to hide pre-loaded votes
2.2) Ability to hide a pre-arranged integer overflow

3) Ability to program conditional behavior based on time/date, number of votes counted, and many other hidden triggers.

According to public statements by elections officials(20), the paper trail produced by the precinct optical scan has been placed into the role of a vital safeguard mechanism. The paper report from the optical scan machine is the key record used to confirm the integrity of the central tabulator record.

... It is important to understand that, because the AccuBasic program is aware of the election definitions and structure, attacks can be prepared months ahead of time, before the candidate and ballot design have been decided.
(Measures like ballot rotation have no affect on these exploits whatsoever, and do not need to be considered.)

...combining the false report method (demonstrated on page 16) with the pre-arranged integer overflow (demonstrated on 18) seems to be an especially efficient exploit because it is a one-step process that takes out both the actual process and its safeguard at the same time, while surviving scrutiny of almost anything short of a full manual recount.

Delivery mechanisms for memory card tampering

Delivery of a malicious program can be achieved with multiple methods; among them:

- Direct alterations to the memory cards themselves.

- Replacement of the “.abo” (AccuBasic executable) file(s) in the central tabulator before election definitions are uploaded to memory cards. In this approach the election office, while not necessarily aware of the situation, will distribute the malicious code when preparing the elections.

- The central tabulator approach (.abo file replacement) will also enable even remote work. Remote attacks can either use a technical approach or a social engineering approach. Social engineering can turn out to be quite effective to deliver malicious code to the GEMS computer. An example of this could be providing an automated CD/DVD disc or USB device “patch” or update, delivered to the elections office accompanied by a phone call recommending its installation.

Even if checksums were to be implemented in future versions of the firmware to protect the executable on the memory card, using GEMS to contaminate the memory card will neutralize the checksums because the program is inserted before the checksums are calculated.

...Proof of concept in detail

To show that the executable program on the memory card controls the optical scan report and the user interface, and to test the memory card alteration theory, the author was able to test sample cards from Leon County, Florida. These memory cards contained an election constructed for the purpose of educating poll workers for future elections. All relevant elements were identical to the platform and implementation of all elections run within the environment in question.

...When the author viewed the raw dump of the image file, which can be done using any hexadecimal or binary file editor, it became self-evident where the starting position of the executable pseudo-code was. Because the program is stored after election specific data, it is safe to assume that the starting location is not fixed.

(screen shot included in report)

The author also found the end location of the executable block to be self-evident.

(screen shot included in report)

...The author wrote and pre-compiled his own program. Please note that the compiler has been publicly available for several years(22). This significantly helps the average Joe to make his own program for the voting machine, although for sophisticated programmers this help is far from necessary. The compiler output is a pseudo-code in the format for GEMS to upload to the card....

(additional specifics provided in report)

...the memory card was inserted to the Optical Scan unit, and it was verified that the voting system functionalities changed according the programming concepts the author had chosen.

...The following images show the original optical scan report side-by-side with reports that were produced by modifying the program code on the memory cards. On all memory cards, the vote data remains identical in this particular exploit. Only the reporting mechanism was modified to give false results.

(image of scanned poll tapes provided in report)

Note that the run date and time on all reports are the same. The original report was run in Leon County on May 16, when the author was not present. However, the reports from the tampered memory cards, which also state run time to be May 16, were actually run on morning of May 26, when the author conducted the proof of concept test. These reports demonstrate that report data, including the date and other information, are easily altered on optical scan reports.

(image of scanned audit tape is provided in report)

Above is the Diebold “audit report” for the optical scan machine, printed on May 26. This audit log is printed from the optical scan firmware, not from the executable on the memory card. No changes were made on this report. Note that it shows no error messages. The memory card this report purports to be auditing was tampered with on an airplane at an earlier date in May, but nothing in the audit log reflects the actual timing of memory card events.
No anomalies appeared on the audit report because none of the changes made by the author affected any of the Diebold audit log information.

...Manipulation through integer overflows
Currently, many programmers have become accustomed to higher level programming languages, which give warnings and guidance to adjust integer overflow problems. The problem defined below will be familiar to programmers who have worked in earlier environments and/or with lower level programming languages. Please note that only 16 bit integers (2 byte) are used instead of longer integers, which are the default in today’s environment.

It is clear that the checksum algorithm used was chosen to be the simplest possible one, because it has been chosen to protect the votes against random corruption of the data instead of intentional tampering.

This finding led the author to create an exploit with the idea of inserting votes that will cancel each other out when added.

By the way: There were no error messages during start-up with this card, nor did any error messages appear afterward.

(image of scanned "zero tape" provided in report, with pre-loaded votes to trigger integer overflow)

...Pre-stuffing the ballot box with votes 65511 and 25 is essentially the same as if one candidate had -25 votes and the other +25 votes at the start. Naturally, the choice of -25 and +25 was arbitrary and different figures could have been used.

Further considerations

When the firmware turns control over to Accu-Basic, the user is not notified, nor is the user notified when control returns to the firmware. The Accu-Basic program on the memory card not only has control over the printer as output media, but also enables interaction with the user over the LCD display, and “YES” and “NO” the buttons located underneath the LCD.

The implications of this are:

1) Conditional behavior of malicious code can be based on user input

2) The user can be made to believe that his activities are real, while they are not, by programming the memory card so that it will not return control back to firmware.

(image of message "Are we having fun yet" on LCD screen, for the demonstration of control over the user interface performed in Leon County)

Conclusions

The Accu-Vote Precinct Count Optical Scan system inherits numerous attack vectors from flexibility to modify over security design.

Operational procedures required to secure the system would put an un-sustainable burden on the perimeter defense, training of the personnel and supervision among the other layers of security.

Recommendations

1. Further evaluation should be performed on the 1.96.x and 2.0.x versions of the Diebold optical scan system to determine whether they do or do not have the same fundamentally insecure architecture. A similar examination should also be performed on the Diebold touch-screens, including the TS-R4 and TS-R6 versions, the TSx version, and the new “VVPAT” version, along with any other component of the accumulation process for any of these systems.

2. Because memory cards have been given a pre-eminent position in the Diebold voting system studied, they should be deemed to contain critical data and should be considered to be a public document. Of course, they should be retained for 22 months in federal elections, as required by U.S. federal election law.

3. Memory cards or, in the event they are not available, the voting systems themselves, should be examined for all jurisdictions using any Diebold voting system which relies on this type of architecture. If manipulation is done properly, there will be no telltale anomalies in the reports printed for the public. In areas like Volusia County, (24)(25)(26) and Brevard County (27)(28) Florida, where significant anomalies have appeared related to vote tabulation, memory cards, or poll tapes, the memory cards should be certainly inspected by someone experienced in forensics.

4. The architecture of other manufacturers should be examined for similar vulnerabilities. Priority should be set for this examination according to the significance of the vendor.

Footnotes, acknowledgements

List of Appendices:

Appendix A: Diebold memo about memory cards used

Appendix B: Diebold memo about checksums

Appendix C: Diebold memo with more information about checksums

Appendix D: Sample program

Appendix E: List of locations that use Diebold voting systems

Let us now discuss practical next steps. It is important to achieve several things:

1) A product recall, as this vulnerability is not fixable with any software patch. It would be entirely inappropriate for taxpayers to foot the bill of corrective actions. Those costs should be born by the vendor. Bear in mind that when Diebold acquired Global Election Systems, its investment banking partner performed, (or should have done) a due diligence analysis of this system. Diebold Inc. either knew, and sold the system anyway, or did not know, but should have known. It is therefore appropriate that Diebold should foot the bill for the product recall. Certainly not the taxpayers.

2) It becomes important to understand who knew what, and when. Did the ITA certifiers (Wyle, and Ciber) know of this? If they knew, but certified it anyway, an investigation of the certification process must be conducted. If they did not know, their credentials as certifiers should be revoked. Did the state-level evaluators know? (Paul Craft - Florida; Britain Williams - Georgia, Maryland, Virginia; Steve Freeman - California).

Please note that this product was certified to 1990 FEC standards. However, it appears to violate a number of these standards, which can be found here: http://www.bbvforums.org/forums/messages/2197/2383.html

One item of review, when you look at the standards, should be the requirement to use checksums and parity. Another should be the prohibition against using nonstandard language. A third area to look at is the prohibition of self-modifying code. Be your own certifier. See what you think.

3) It is now very important to do forensics on the memory cards and voting systems used in the Nov. 2, 2004 election. Because this system is so open to tampering, please urge your local and state officials to sequester the memory cards for recent elections, so that they can be examined by a forensic expert, or an otherwise qualified expert, like Hursti, who has shown that he is both competent to evaluate this issue, and forthcoming about notifying the public. These memory cards are clearly of public interest, and should be deemed a public document.

4) Please urge local and state officials to have a competent, qualified examiner evaluate both the new optical scan systems, including the high speed central count system, and the touch-screen systems, because there are some indications that this architecture is being used (and even increased) in newer versions. The touch-screens may be using a different but similar architecture. Contact Black Box Voting when you have indications that such cooperation is forthcoming. (contact kathleen@blackboxvoting.org to help schedule an evaluation, or call 425-793-1030).

No new elections should be run on Diebold optical scan systems until these evaluations are complete.

Please note that any agency that redacted this issue from its report, perhaps working privately with the manufacturer behind the scenes to correct it, or working on some other private remedial concept should be disqualified from further certification or evaluation work. The reasons for this are twofold:

- The presidential primary, and a federal general election, were allowed to be held on the Diebold system, which is now used in 1,207 locations.

(Some of these locations are new purchases, the number of jurisdictions using Diebold in the 2004 election is closer to 800. Of these, approximately 200 used touch-screens at the precinct, with optical scans counting absentee votes. Of the 600 remaining jurisdictions, a handful used the 1.96.x firmware version, which probably carries the same vulnerability but has not yet been field-tested for it. At least 500 jurisdictions used systems that were certainly open to the exploits described in this report.)

In Nov. 2004, in Florida alone, the Diebold Precinct-Based Optical Scan 1.94w system counted approximately 2.5 million votes in 30 counties, or about one-third of all the votes in Florida. Nationwide, this version of Diebold voting machines counted approximately 25 million votes in Nov. 2004, or about 25 percent of the national election.

Any entity that allowed the Nov. 2004 election to proceed on a system with a fundamental architecture that is "open for business" -- even if working with a vendor behind the scenes -- compromised the integrity of the election.

We do not know if any scientists or testing authorities have been working privately with Diebold to correct the problems, but it is very difficult to explain why no one has come forth publicly with this information. It may be that someone feels they have a superior plan of action, which requires keeping the information quiet, but in view of the stunning hole through the security of the 2004 presidential election, this position would seem insupportable.

- The concept of working privately behind the scenes with a vendor to secretly correct flaws is incorrect as a consumer protection measure. Running a United States federal election on a voting system with this architecture is certainly parallel to letting people drive cars with exploding gas tanks.

Permission to reprint granted with a link to http://www.blackboxvoting.org, and provided that no edits or changes of text or graphics from EXCERPT FROM THE REPORT, OR THE REPORT ITSELF, are made in any way. ALL QUOTES AND EXCERPTS FROM THE REPORT, EVEN BRIEF ONES, MUST BE ATTRIBUTED.

Please send this report to the public officials using Diebold (here is a list of locations: http://www.blackboxvoting.org/diebold/locations.pdf, http://img.scoop.co.nz/media/pdfs/0507/BBVreport.pdf).

Please also consider sending a printout of this report to the network security administer of each jurisdiction that uses Diebold systems. This would be an employee who does not work for the elections division, but instead is responsible for the integrity of the data for the county or township.

Please send this report on to other computer professionals.

Please distribute this report to your lists.

© Scoop Media