Security Analysis of the Diebold AccuBasic Interpreter
David Wagner David Jefferson Matt Bishop
Voting Systems Technology Assessment Advisory Board (VSTAAB)
with the assistance of:
Chris Karlof Naveen Sastry
University of California, Berkeley
February 14, 2006
http://www.votetrustusa.org/pdfs/California_Folder/DieboldReport.pdfMemory card attacks are a real threat: We determined that anyone who has access to a
memory card of the AV-OS, and can tamper it (i.e. modify its contents), and can have
the modied cards used in a voting machine during election, can indeed modify the election
results from that machine in a number of ways. The fact that the the results are incorrect
cannot be detected except by a recount of the original paper ballots.
Harri Hursti's attack does work: Mr. Hursti's attack on the AV-OS is denitely real. He was
indeed able to change the election results by doing nothing more than modifying the contents
of a memory card. He needed no passwords, no cryptographic keys, and no access to any
other part of the voting system, including the GEMS election management server.
Interpreter bugs lead to another, more dangerous family of vulnerabilities: However, there is
another category of more serious vulnerabilities we discovered that go well beyond what Mr.
Hursti demonstrated, and yet require no more access to the voting system than he had. These
vulnerabilities are consequences of bugs|16 in all|in the implementation of the AccuBasic
interpreter for the AV-OS. These bugs would have no eect at all in the absence of deliberate
tampering, and would not be discovered by any amount of functionality testing; but they
could allow an attacker to completely control the behavior of the AV-OS. An attacker could
change vote totals, modify reports, change the names of candidates, change the races being
voted on, or insert his own code into the running rmware of the machine.
Successful attacks can only be detected by examining the paper ballots: There would be no
way to know that any of these attacks occurred; the canvass procedure would not detect any
anomalies, and would just produce incorrect results. The only way to detect and correct the
problem would be by recount of the original paper ballots, e.g. during the 1 percent manual
recount.
The bugs are classic, and can only be found by source code review: Finding these bugs was only
possible through close study of the source code. All of them are classic security flaws, including
buer overruns, array bounds violations, double-free errors, format string vulnerabilities, and
several others. There may, of course, be additional bugs, or kinds of bugs, that we did not find.
---------------------------------------------
Impact. The consequence of these vulnerabilities is that any person with unsupervised access to
a memory card for sucient time to modify it, or who is in a position to switch a malicious memory
card for a good one, has the opportunity to completely compromise the integrity of the electronic
tallies from the machine using that card.
Many of these vulnerabilities allow the attacker to seize control of the machine. In particular,
they can be used to replace some of the software and the rmware on the machine with code of
the attacker's choosing. At that point, the voting system is no longer running the code from the
vendor, but is instead running illegitimate code from the attacker. Once the attacker can replace
the running code of the machine, the attacker has full control over all operation of the machine.
Some of the consequences of this kind of compromise could include:
The attack could manipulate the electronic tallies in any way desired. These manipulations
could be performed at any point during the day. They could be performed selectively, based
on knowledge about running tallies during the day. For instance, the attack code could wait
until the end of the day, look at the electronic tallies accumulated so far, and choose to modify
them only if they are not consistent with the attacker's desired outcome.
The attack could print fraudulent zero reports and summary reports to prevent detection.
The attack could modify the contents of the memory card in any way, including tampering
with the electronic vote counts and electronic ballot images stored on the card.
The attack could erase all traces of the attack to prevent anyone from detecting the attack
after the fact. For instance, once the attack code has gained control, it could overwrite
the malicious AccuBasic object code (.abo le) stored on the memory card with legitimate
AccuBasic object code, so that no amount of subsequent forensic investigation will uncover
any evidence of the compromise.
It is even conceivable that there is a way to exploit these vulnerabilities so that changes could
persist from one election to another. For instance, if the rmware or software resident on
the machine can be modied or updated by running code, then the attack might be able to
modify the rmware or software in a permanent way, aecting future elections as well as the
current election. In other words, these vulnerabilities mean that a procedural lapse in one
election could potentially aect the integrity of a subsequent election. However, we would
not be able to verify or refute this possibility without experimentation with real systems.
---------------------------------------------------------------------------
It is conceivable that the attack might be able to propagate from machine to machine, like a
computer virus. For instance, if an uninfected memory card is inserted into an infected voting
machine, then the compromised voting machine could replace the AccuBasic object code on
that memory card with a malicious AccuBasic script. At that point, the memory card has
been infected, and if it is ever inserted into a second uninfected machine, the second machine
will become infected as soon as it runs the AccuBasic script.
------------------------------------------
In addition, most of the bugs we found could be used to crash the machine. This might
disenfranchise voters or cause long lines. These bugs could be used to selectively trigger a crash only on some machines, in some geographic areas, or based on certain conditions, such as which
candidate has received more votes. For instance, it would be possible to write a malicious AccuBasic script so that, when the operator prints a summary report at the end of the day, the script examines the vote counters and either crashes or continues operating normally according to which candidate is in the lead.
Unfortunately, the ability of malicious AccuBasic scripts to crash the machine is currently embedded in the architecture of the interpreter. Any innite loop in the AccuBasic script immediately translates into an innite loop in the interpreter (which causes the machine to stop responding, and is indistinguishable from a crash), and any innite recursion in the AccuBasic script translates into stack over row in the interpreter (which could corrupt stack memory or crash the machine).