|
DDJ contributing editor Jack Woehr talks to Avi Rubin, the world's leading authority on electronic voting and software engineering.
November 01, 2004
URL:http://www.drdobbs.com/a-conversation-with-avi-rubin/184405882
Reprinted, with permission, from IEEE Symposium on Security and Privacy, 2004. 2004 IEEE.
E-Voting Systems & Software Engineering
Computerized electronic voting machines have aroused a controversy nationwide: Are they accurate? How do they work? Are they secure? Avi Rubin was drawn into the controversy head-first with an analysis of Diebold AccuVote-TS voting system code. The paper that he and his associates authored—"Analysis of an Electronic Voting System" (http://avirubin.com/vote.pdf)—contained the following indictment of the current state of the art: "Our analysis shows that this voting system is far below even the most minimal security standards applicable in other contexts."
Rubin has subsequently become one of the computer scientists most expert in the search for verifiable means of electronic voting. He has been consulted extensively by government, industry, academia, and the press. DDJ contributing editor Jack Woehr spoke with Rubin.
DDJ: What got you interested and involved in electronic voting security?
AR: My field is computer security and applied cryptography. In 1997, I was a researcher at AT&T labs when we got approached by the Costa Rican government to help them with what they wanted to build as an experiment in electronic voting. I found the convergence of issues fascinating: security, cryptography, systems, public policy, human factors. All of these different factors that came together in the problem of voting. I flew down to Costa Rica, spent a couple of days with the Elections Tribunal of Costa Rica. We worked for several weeks on a design for them, but we were very concerned with the overall security issues and the adoption issues in Costa Rica where most of the population is not computer literate. They did interesting experiments, like one which showed that the older women, no matter how much they were taught, could not navigate a mouse. We looked at touch screens, explored a whole lot of ideas. In the end, the Costa Rican government backed out and decided they didn't want to do it.
But I had been bitten by the bug. I wrote up and published my analysis of what would be the issues of voting over the Internet. I was then invited onto a National Science Foundation Internet Policy Institute panel that was commissioned by President Clinton to study the feasibility of e-voting [http://www.cs.jhu.edu/~rubin/courses/sp03/papers/nsf.voting.pdf]. I began thinking and speaking more on the subject.
Then, last June, I got a phone call from [Stanford University professor] David Dill who has taken on the idea of opposing electronic voting and promoting voter-verifiable paper. He had a petition signed by hundreds of computer scientists—I had signed it—and he called me up to tell me Diebold's code was on the Internet, and I asked, "What's Diebold?" He told me that Diebold [http://www.diebold.com/] was one of the leading manufacturers of electronic voting machines and that these companies had never released their code and did I want to do a security analysis? I said sure.
I called in two grad students whom I had working with me over the summer and told them I had a drop-everything project that I thought they would be very interested in doing with me, which was to do a security assessment of this code. They got right on it and we worked for two weeks. Somewhere in there, I asked [Rice University professor] Dan Wallach to join us. The four of us wrote the report which became known as "The Hopkins Report." That's when I got completely immersed in this.
On a personal level, I had turned down some professor jobs that offered me tenure to come to Johns Hopkins without tenure. While all this was going on, I was in my tenure review year. It was a bit of a risk to drop my core research and take on something so political, something that resulted in letters slamming me being sent to the president of the university and calls to the director of the institute demanding my firing. This was all instigated by people who had certified these machines, and vendors and trade groups representing the vendors.
DDJ: Is academia subject to that kind of pressure these days?
AR: It's not because I got tenure! But those people think it is because, in the circles that those people who tried to attack me run in, that kind of thing can happen. When I was at AT&T—I spent nine years in industry labs before I came here—you definitely didn't want something like that to happen because a company is a company.
DDJ: People have written that, for instance, you can't say bad things about the drug companies in medical research because the drug companies are funding the medical schools.
AR: I've seen that there's a lot of care taken here that you cannot have research funded by a company you are testing. At least at Hopkins, you go through conflict of interest training, and there is all this documentation...If there was a software company I was consulting to, I could not accept a grant from them for research.
So in my case, [those offended by our paper on voting security] couldn't touch me. They sent me threatening "cease and desist" letters, and "we're going to sue you." Hopkins wrote back, "We support our researchers," and that they would defend me if there was any problem. They were extremely supportive of me.
DDJ: On the Internet, there are a lot of conspiracy theorists. Some have this theory that the voting system is not only vulnerable but intentionally rigged because of the political affiliations of the proprietors of some of these corporations.
AR: I think talk like that really dilutes the message and does a disservice to what we are trying to accomplish here. Whether such rigging is happening—it's probably not, in my opinion—what we need to focus on is the potential for security problems, the potential for a vendor to build a machine that could do whatever the vendor wanted it to do. We should not focus on assumptions that the president of some voting machine company is of one party or the other, ergo they are rigging the vote. Whether they are or not, we still have a valid point to make, which is, "Do we want our elections to be at the mercy of a vendor?" That's precisely where we are right now. That's much more important than whether they are actually doing any rigging. It's the potential to do so that counts.
DDJ: As someone who has been an election judge for various cities and counties since the 1980s, it seems to me that you don't have to have much insecurity to have a potential for cheating, not only in electronic voting, but in any kind of voting system.
AR: The fundamental problem with electronic voting systems is that the machine does whatever it was programmed to do. If the machine was programmed to count the votes that people put in, and there are no bugs in the program (which is very unlikely for a very large system) then it just might do that. But if I were building the machine, I could make it so that anyone I wanted to win would win. I could do it in such a way that there is no way anyone would know that I did it. You could do it in a way that it would just make it somewhat more likely that the candidate you wanted to win would win.
DDJ: Using self-modifying code so it wouldn't be obvious?
AR: There are many, many ways for this to be done. In my course this past semester, we did a whole experiment on hiding code [http://www.cs.jhu.edu/~rubin/courses/sp04/proj2.txt] in other code and having other students try to find it. It showed how much easier it is to hide malicious code in other code than it is to detect it. There's even an audit trail in the assignment, and the students have to hack the audit trail to match the back-doored code!
DDJ: What is the solution for voting systems? Are you one of the print-it-out-human-readable-and-drop-it-in-the-ballot-box guys, or...?
AR: I was in a workshop at Harvard. Ron Rivest was on the panel with myself and others, and he said, "When they first built cars, they didn't always do a good job. They sometimes designed a car without a roof. It's alright except when it rains. If it starts to rain, you can design a car with a roof, but if you need it this weekend, you buy an umbrella and ride around with an umbrella." That's what I think the paper ballot idea is. Right now, we have a problem: all these really insecure machines. The code is terrible. We have no proof that they were or were not rigged. We just don't know whether we can trust them. We do know that if we have a voter-verifiable paper printout that we stick in a ballot box, it makes it harder for the machine to cheat and get away with it, or to make a mistake.
DDJ: We've had several elections here in Colorado with electronic voting machines and the results seem quite plausible.
AR: That's one comment I hear that irks me: "They seem to working well." If you are concerned about functionality, sure, but if you're concerned about security... If the threat model is that some attacker is taking some small percentage of the vote and shifting the result, you cannot observe them and say that they are working well. You just don't know.
DDJ: There have been elections using these machines with rather surprising outcomes.
AR: The problem with these machines is that, the minute there is any controversy or doubt people can say, "Look at these machines!"...Well, that's simply not going to be a viable long-term way of running elections.
DDJ: If we don't have a presidential election this year that people can believe, I wonder what will happen in America?
AR: We seem to have survived last time. I have no doubt that, whatever happens, there is going to be a controversy. The polls are dead even. There will be states that could have tipped it in one direction or the other that use electronic machines. So there will be people, regardless of who wins, who will say, "How do we know?" And we won't be able to do recounts.
DDJ: Because there is nothing to recount. The machines do print out very nice paper summaries...
AR: But if the threat is that the votes are not being tallied the way they were voted...
DDJ: They had those same problems with the electromechanical voting machines in the 1950s and 1960s.
AR: I'm not crazy about lever machines or any machines where the stuff happens inside the machine and the voters don't get to see how their vote is recorded. I like optical scanners. I even think that punch cards, if designed better, could work as a voting technology.
DDJ: There are ways to cheat with punch cards.
AR: But you have to be there to do it. Electronic machines, it could be all of them at once.
DDJ: How successful have you been at getting the attention of policy makers?
AR: I spent a good deal of time with the Secretary of State of Minnesota. I've spoken with several other [states]. Every other week I'm in D.C. meeting with congressional staffers who want to hear about it and understand, staffers from both parties.
DDJ: Whatever their persuasion, this must hit home.
AR: There is Russ Holt's bill in the House, Clinton and Graham have bills in the Senate...They're all about voter- verifiable paper...They don't seem to be going anywhere, but the fact is that they exist and that there are more and more of them and that more and more people are thinking about the issue. Dean came out with some statements and Kerry made a few flippant statements why people are not taking a stronger stance right now, but I think they will after the election. People know there is nothing we can do by November.
DDJ: Where do you go from here?
AR: We professors from various universities who have been working hard on these issues have all gotten together and written a proposal to the National Science Foundation to study this further.
I think there's a lot of fundamental research to be done. We're going to look at how to design and build secure, accurate, accessible, easy-to-use voting machines that will be verifiable, easy to count, and as secure as possible. We wrote that grant for $10,000,000. If we get it, the piece that I'll cover is "design for audit," how you build software systems so that it's easier to audit them.
DDJ: What do you think about the argument it should be open source?
AR: I don't think there should be any argument. In something wherein transparency is the key, as in an election, everybody should have the right to inspect the machines. In the old days, they used to hold the back door open on the lever machines and allow anyone to inspect the machines and how they were set up. I think that should carry over to electronic systems, though it is a lot harder to analyze them. It's almost impossible to know if it's any good. But the appearance of a lack of transparency is not something we can tolerate in voting systems.
DDJ: Is the political battle that something has to be done a battle that is already won or should people get involved some way, write letters...?
AR: The current bills call for open source, voter-verifiable paper...I don't think that, 15 years from now, we are going to need voter-verifiable paper. I think we are going to have systems that are provably accurate and universally verifiable, systems where code can be published on a web site for which high-school students could write a program to verify that would prove the results were correct without revealing how any individual voted. But I don't think that this is feasible in four years or in eight years. We need to have a strong advocacy to push for open source and voter-verifiable paper in the near term.
As long as we have a situation where a vendor can single-handedly determine the outcome of the election, we have a problem. And that's the state we are in right now.
DDJ
void CBallotRelSet::Open(const CDistrict* district, const CBaseunit* baseunit,
const CVGroup* vgroup1, const CVGroup* vgroup2)
{
ASSERT(m_pDB != NULL);
ASSERT(m_pDB->IsOpen());
ASSERT(GetSize() == 0);
ASSERT(district != NULL);
ASSERT(baseunit != NULL);
if (district->KeyId() == -1) {
Open(baseunit, vgroup1);
} else {
const CDistrictItem* pDistrictItem = m_pDB->Find(*district);
if (pDistrictItem != NULL) {
const CBaseunitKeyTable& baseunitTable =
pDistrictItem->m_BaseunitKeyTable;
int count = baseunitTable.GetSize();
for (int i = 0; i < count; i++) {
const CBaseunit& curBaseunit = baseunitTable.GetAt(i);
if (baseunit->KeyId() == -1 || *baseunit == curBaseunit) {
const CBallotRelationshipItem* pBalRelItem = NULL;
while ((pBalRelItem = m_pDB->FindNextBalRel(curBaseunit,
pBalRelItem))){
if (!vgroup1 || vgroup1->KeyId() == -1 ||
(*vgroup1 == pBalRelItem->m_VGroup1 && !vgroup2) ||
(vgroup2 && *vgroup2 == pBalRelItem->m_VGroup2 &&
*vgroup1 == pBalRelItem->m_VGroup1))
Add(pBalRelItem);
}
}
}
m_CurIndex = 0;
m_Open = TRUE;
}
}
}
When creating a secure system, getting the design right is only part of the battle. The design must then be securely implemented. In this paper, we examine the coding practices and implementation style used to create the Diebold AccuVote-TS 4.3.1 system which was written in C++ and designed to run on a Windows CE device; see Figure 1. (The code also compiles and runs, with slightly different configurations, on regular Microsoft Windows machines, thus enabling us to verify that the code represents a complete system. The 4.3.1 snapshot of the AccuVote-TS tree has 136 .h files totaling 16,414 lines and 120 .cpp files totaling 33,195 lines, for a total of 256 files and 49,609 lines of C++ code.) This type of analysis can offer insights into future versions of the code. For example, if a current implementation has followed good implementation practices but is simply incomplete, one would be more inclined to believe that future, more complete versions of the code would be of a similar high quality. Of course, the opposite is also true, perhaps even more so: It is very difficult to produce a secure system by building on an insecure foundation.
Of course, reading the source code gives only an incomplete view into the actions and intentions of the developers who created that code. Regardless, we can see the overall software design, we can read the comments in the code and, thanks to the CVS repository, we can even look at earlier versions of the code and read the developers' commentary as they committed their changes to the archive.
Inside cvs.tar, we found multiple CVS archives. Two of the archives, AccuTouch and AVTSCE, implement full voting terminals. The AccuTouch code, corresponding to AccuVote-TS Version 3, dates from December 1998 to August 2001 and is copyrighted by "Global Election Systems Inc.," while the AVTSCE code, corresponding to the AccuVote-TS Version 4 system, dates from October 2000 to April 2002 and is copyrighted by "Diebold Election Systems Inc." (Diebold acquired Global Election Systems in September 2001.) Although the AccuTouch tree is not an immediate ancestor of the AVTSCE tree (from the CVS logs, the AVTSCE tree is actually an import of another AccuTouch-CE tree that we do not have), the AccuTouch and AVTSCE trees are related, sharing a similar overall design and a few identical files. From the comments, some of the code, such as the functions to compute CRCs and DES, date back to 1996 and a company later acquired by Global Election Systems called "I-Mark Systems." The same DES key has been hardcoded into the system since at least the beginning of the AccuTouch tree.
While the system is implemented in an unsafe language (C++), the code reflects an awareness of avoiding such common hazards as buffer overflows. Most string operations already use their safe equivalents, and there are comments; for example, "should really use snprintf," reminding developers to change others.
While we are not prepared to claim that there are no exploitable buffer overflows in the current code, there are at the very least no glaringly obvious ones. Of course, a better solution would have been to write the entire system in a safe language, such as Java or Cyclone. In such a language, we would be able to prove that large classes of attacks, including buffer overflows and type-confusion attacks, are impossible assuming a correct implementation of the compiler and runtime system. Overall, the code is rather unevenly commented. While most files have a description of their overall function, the meanings of individual functions, their arguments, and the algorithms within are more often than not undocumented. An example of a complex and completely undocumented function is the CBallotRelSet::Open function (Figure 2) from TSElection/TSElectionSet.cpp.
This block of code contains two nested loops, four complex conditionals, and five debugging assertions, but no comments that explain its purpose. Ascertaining the meaning of even a small part of this code is a huge undertaking. For example, what does it mean for vgroup->KeyId() == -1? That the ID is simply undefined? Or perhaps that the group should be ignored? Such poorly documented code impairs the ability of both internal developers and external security evaluator to assess whether the code is functioning properly or might lead to a security issue.
An important point to consider is how code is added to the system. From the project's CVS logs, we can see that most recent code updates are in response to specific bugs that needed to be fixed. There are, however, no references to tracking numbers from a bug database or any other indication that such fixes have been vetted through any change-control process. Indeed, each of the programmers seem to have completely autonomous authority to commit to any module in the project. The only evidence that we have found that the code undergoes any sort of review comes from a single log comment: "Modify code to avoid multiple exit points to meet Wyle requirements." This refers to Wyle Labs, one of the independent testing authorities charged with certifying that voting machines have met FEC guidelines.
Virtually any serious software engineering endeavor will have extensive design documents that specify how the system functions, with detailed descriptions of all aspects of the system, ranging from the user interfaces through the algorithms and software architecture used at a low level. We found no such documents in the CVS archive, and we also found no references to any such documents in the source code, despite references to algorithms textbooks and other external sources.
There are also pieces of the voting system that come from third parties. Most obviously, a flaw in the operating system, Windows CE, could expose the system to attack since the OS controls memory management and all of the device's I/O needs. In addition, an audio library called "fmod" (http://www.fmod.org/) is used. While the source to fmod is available with commercial licenses, unless this code is fully audited, it might contain a backdoor or an exploitable buffer overflow. Because both the operating system and fmod can access the memory of the voting program, both must be considered part of the trusted computing base (TCB) as a security vulnerability in either that could compromise the security of the voting program itself. The voting terminal's hardware boot instructions should likewise be considered part of the TCB. Due to the lack of comments, the legacy nature of the code and the use of third-party code and operating systems, we believe that any sort of comprehensive, top-to-bottom code review would be nearly impossible.
Not only does this increase the chances that bugs exist in the code, but it also implies that any of the coders could insert a malicious backdoor into the system without necessarily being caught. The current design deficiencies provide enough other attack vectors, however, that such an explicit backdoor is not required to successfully attack the system. Regardless, even if the design problems are eventually rectified, the problems with the coding process may well remain intact.
Since the initial version of this paper was made available on the Internet, Diebold has apparently "developed, documented, and implemented a change control process" (http://www.dbm.maryland .gov/SBE/). The details of this revised process have not been made available to the public, so we are unable to comment on their effectiveness.
While the code we studied implements a full system, the implementors have included extensive comments on the changes that would be necessary before the system should be considered complete. It is unclear whether the programmers actually intended to go back and remedy all of these issues as many of the comments existed, unchanged, for months, while other modifications took place around them. Of course, while the AVTSCE code we examined appears to have been the current codebase in April 2002, we know nothing about subsequent changes to the code. (Modification dates and locations are easily visible from the CVS logs.) These comments come in a number of varieties. For illustrative purposes, we have chosen to show a few such comments from the subsystem that plays audio prompts to visually impaired voters.
There are, however, no comments that would suggest that the design will radically change from a security perspective. None of the security issues that have been discussed in this paper are pointed out or marked for correction. In fact, the only evidence at all that a redesign might at one point have been considered comes from outside the code: the Crypto++ library (http://www.eskimo.com/~weidai/ cryptlib.html) is included in another CVS archive in cvs.tar. However, the library was added in September 2000, before the start of the AVTSCE AccuVote-TS Version 4 tree, and appears to have never been used. The subsequent SAIC (http://www.dbm.maryland.gov/SBE) and RABA (http://www.raba.com/press/TA_Report_AccuVote.pdf) analyses report that many of the problems we identify are still applicable to recent versions of the AccuVote-TS system, implying that, at least up to the version that SAIC and RABA analyzed, there has not been any radical change to the AccuVote-TS system.
DDJ
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.