August 31, 2016

Archives for October 2006


Diebold's Motherboard Flaw: Implications

Yesterday I explained the design error that led Diebold in 2005 to recall and replace the motherboards in thousands of voting machines, most of which had been used in the November 2004 election. Today I’ll talk about how the motherboard flaws might have affected the accuracy of elections.

Machines with flawed boards were normally identified when they “froze” on election day. When personal computers crash, they often manage to reboot themselves, but the Diebold machines don’t reboot themselves on a crash, so any kind of general system crash will make the system freeze. So the bug was usually identified when a voting machine crashed. Mystery crashes typically don’t happen at random times but are concerntrated at certain stages of the machine’s use, because the detailed technical conditions that trigger the crash are more likely to happen at some times than at others.

When did the flawed Diebold machines crash? Here’s the Montgomery County (Maryland) Lessons Learned report from the 2004 election (page 11):

Election judges and technical staff reported that many of these units froze when the voter pressed the Cast Ballot button. This leads to great confusion for judges and voters. The voter leaves the polling place with little or no confidence that their vote was counted. In many cases, the election judges are unable to provide substantial confirmation that the vote was, in fact, counted.

You’d be hard pressed to pick a worse time for a voting machine to crash. The voter has made his selections, confirmed them on the ballot review screen, and now wants them to be recorded. When the Cast Vote button is pressed, the machine reads the intended votes out of its temporary RAM memory and copies them into the official ballot record file, which lives in the machine’s flash memory. If the machine crashes just before the vote is copied, the vote is lost. If it crashes just after the vote is copied, the vote is recorded. It won’t be immediately obvious which case you’re in – hence the confused voters and poll workers.

The kind of design mistake Diebold made – timing errors in the use of RAM chips – crops up in other (non-voting) systems, so we know what kinds of problems it tends to cause. Sometimes it will cause system crashes, but sometimes it will cause data to be corrupted when it gets copied from one place to another. Which is particularly worrisome because the Diebold flaw tends to show up just at the time when the vote is copied into the official record.

And that’s not all. Some other machines failed with Ballot Exception Errors, which happen when the machine’s log file is corrupted – a file that is stored alongside the vote record file, and is also updated when the Cast Vote button is pressed. So we know that some of the records kept by the voting machine (either internally or on removable memory cards) were getting corrupted.

Were votes ever actually corrupted? We’ll never know. If we had a voter-verified paper audit trail, we could compare it to the records kept by the crashed machines. But with only the electronic records to go on, it’s probably impossible to tell.

The good news is that all of the affected motherboards have now been replaced. The bad news is that Diebold knew about these problems in March 2004, and yet they allowed thousands of affected machines to be used in the November 2004 election.


Diebold Quietly Recalled Voting Machine Motherboards

Diebold replaced the motherboard (i.e., the main electronic component) on about 4700 of Maryland’s AccuVote-TS voting machines in 2005, according to Cameron Barr’s story in Thursday’s Washington Post. The company and state officials kept the recall quiet – even some members of the state’s Board of Elections were unaware of it until contacted by the Post. (“If they had asked, we would have told them,” an official said.)

The original motherboards had a design error that caused the machines to become unresponsive, or “freeze”, sometimes during elections. In the 2004 general election, about four percent of Montgomery County’s machines had this problem, according to the county’s 2004 Presidential General Election Review: Lessons Learned report (page 11).

In March 2004, Diebold had sent the state a memo describing the problem in the original motherboards. The memo says that “stack-up of component tolerances” led to timing errors in accessing RAM memory.

Let’s decode that for non-engineer readers. A circuitboard uses many chips or components. The technical specifications for each chip give a set of tolerances, which might say something like this: “If the temperature is between 40 and 140 degrees, and the supply voltage is between 2.9 and 3.1 volts, and a stable signal is delivered on pin 13 for at least 30 nanoseconds, then the chip will respond by sending a signal on pin 19, between 30 and 70 nanoseconds after receiving the pin-13 signal.” This is a promise from the chip’s manufacturer to the system designer. Designers rely on promises like this to make sure their systems will work.

When the designer connects different chips together – when a signal produced by one chip is fed into another one – the designer has to make sure that the signal provided by the first chip falls within the tolerances accepted by the second chip. Otherwise the second chip might not work as advertised, and the overall system might be flaky or simply fail.

But sometimes design errors like these turn out not to cause trouble. If tolerances are just a little bit out of whack, you might just get lucky. Maybe a chip that is guarantted only for voltages over 2.9 volts will still work at 2.88 volts. Maybe a delay guaranteed between 30 and 70 nanoseconds tends to come out on the low end of that range in the batch of chips you got. Or maybe everything works fine, except when something unusual happens – a hot day, or a glitch in the building’s power supply, or an unusual sequence of button presses on the screen. A designer might choose to risk such problems to save money, in an application where reliability isn’t critical. But it shouldn’t happen in a voting machine.

Diebold’s March 2004 memo explains their design problem and says that they redesigned the motherboard to fix the problem. Newly manufactured machines were getting the redesigned motherboards, and any old machines that exhibited problems would have their motherboards replaced. But at that time old machines that hadn’t been seen malfunctioning were left in the field. Diebold estimated that fewer than one percent of the old machines would have problems.

In the November 2004 election, about four percent of Montgomery County machines had screen freezes. Afterward, Diebold decided to recall the old motherboards, replacing them all with new redesigned boards. Today, every Maryland voting machine has one of the new motherboards. Will we see further problems with Diebold’s motherboard design? Only time will tell.

(You may be wondering how these design problems might have affected the accuracy of vote-counting in the 2004 election. I’ll consider that question in the next post.)


Why So Little Attention to Botnets?

Our collective battle against botnets is going badly, according to Ryan Naraine’s recent article in eWeek.

What’s that? You didn’t know we were battling botnets? You’re not alone. Though botnets are a major cause of Internet insecurity problems, few netizens know what they are or how they work.

In this context, a “bot” is a malicious software agent that gets installed on an unsuspecting user’s computer. Bots get onto computers by exploiting security flaws. Once there, they set up camp and wait unobtrusively for instructions. Bots work in groups, called “botnets”, in which many thousands of bots (hundreds of thousands, sometimes) all over the Net work together at the instruction of a remote badguy.

Botnets can send spam or carry out coordinated security attacks on targets elsewhere on the Net. Attacks launched by botnets are very hard to stop because they come from so many places all at once, and tracking down the sources just leads to innocent users with infected computers. There is an active marketplace in which botnets are sold and leased.

Estimates vary, but a reasonable guess is that between one and five percent of the computers on the net are infected with bots. Some computers have more than one bot, although bots nowadays often try to kill each other.

Bots exploit the classic economic externality of network security. A well-designed bot on your computer tries to stay out of your way, only attacking other people. An infection on your computer causes harm to others but not to you, so you have little incentive to prevent the harm.

Nowadays, bots often fight over territory, killing other bots that have infected the same machine, or beefing up the machine’s defenses against new bot infections. For example, Brian Krebs reports that some bots install legitimate antivirus programs to defend their turf.

If bots fight each other, a rationally selfish computer owner might want his computer to be infected by bots that direct their attacks outward. Such bots would help to defend the computer against other bots that might harm the computer owner, e.g. by spying on him. They’d be the online equivalent of the pilot fish that swim into sharks’ mouths with impunity, to clean the sharks’ teeth.

Botnets live today on millions of ordinary users’ computers, leading to nasty attacks. Some experts think we’re losing the war against botnets. Yet there isn’t much public discussion of the problem among nonexperts. Why not?


YouTube and Copyright

YouTube has been much in the news lately. Around the time it was bought by Google for $1.65 billion, YouTube signed copyright licensing deals with CBS television and two record companies (UMG and Sony BMG). Meanwhile, its smaller rivals Bolt and Grouper were sued by the record industry for infringement.

The copyright deals are interesting. The first question to ask is whether YouTube needed the deals legally – whether it was breaking the law before. There’s no doubt that some of the videos that users upload to YouTube include infringing video and audio content. You might think this makes YouTube an infringer. But the law exempts service providers from liability for material stored on a server at users’ request, as long as certain conditions are met, including a requirement that the service provider take down material promptly on being notified that specific content appears to be infringing. (See section 512(c) of the DMCA.) Whether a site like YouTube qualifies for this exemption will be one of the main issues in the lawsuits against Bolt and Grouper.

It’s easy to see why CBS and the record companies want a deal with YouTube – they get money and greater control over where their content shows up on YouTube. Reading between the lines in the articles, it looks like YouTube will give them fairly direct means of taking down videos that they think infringe their copyrights.

Why would YouTube make a deal? Perhaps they’re worried about the possibility of lawsuits. YouTube hasn’t been sued yet, but the Bolt and Grouper cases might create precedents that put YouTube in jeopardy. YouTube might prefer to make deals now rather than take that risk.

But even if it faces no legal risk, YouTube might want to make these deals anyway. If users feel safer in posting CBS, UMG and Sony BMG content on the site, they’ll post more of that content, and they’ll face fewer frustrating takedowns. The deals might give YouTube users more confidence in using the site, which can only help YouTube.

Finally, we can’t ignore the influence of politics. In recent years, entertainment companies have run to Congress whenever they thought a new product led to more infringement. Congress has typically responded by pressuring the product’s maker to cut licensing deals with the entertainment companies. YouTube is getting in front of this process by making deals now. Again, whether YouTube is actually breaking the law makes little difference, because the dynamic of entertainment company complaints followed by threats to regulate relies not on existing laws but on threats to create new, more restrictive law.

Whether YouTube qualifies for the legal exemption is an interesting question for lawyers to debate. But in today’s copyright policy environment, whether a company is breaking the law is only one piece of the equation.


iPods Shipped with Worm Infection

Apple revealed yesterday that some new iPods – about 1% of the new iPod Videos shipped in the last month or so – were infected with a computer worm that will spread to Windows PCs, according to Brian Krebs at the Washington Post. Apparently a PC used to test the iPods got infected, and the worm spread to the iPods that were connected to that PC for testing.

As far as the worm is concerned, the iPod is just another storage device, like a thumb drive. The worm spreads by jumping from an infected PC to any removable storage device inserted into the PC, and then using the Windows autorun mechanism to jump from the storage device into any PC the storage device is inserted into.

Apple tried to spread the blame: “As you might imagine, we are upset at Windows for not being more hardy against such viruses, and even more upset with ourselves for not catching it.” The jab at Windows probably refers to the autorun feature, which MacOS lacks, and which is indeed a security risk. (I hear that autorun will be disabled by default in Windows Vista.) Apple also says that the infected machine belonged to a contractor, not to Apple itself. If I were a customer, I would blame Apple – it’s their job to ship a product that won’t hurt me.

As Brian Krebs reminds us, this is at least the third case of portable music players shipping with malware. Last year Creative shipped a few thousand infected players, and McDonalds Japan recently gave away spyware-infected players.

In all of these cases, the music players were not themselves infected – they didn’t run any malware but only acted as passive carriers. It didn’t matter that the music players are really little computers, because the worm treated them like dumb memory devices. But someday we’ll see a scary virus or worm that actively infects both computers and music players, jumping from one to the other and doing damage on both. Once autorun goes away, this will be the natural approach to writing player-borne malware.

In principle, any device that has updatable software might be subject to malware infections. That includes music players, voting machines, printers, and many other devices. As more devices get “smart”, we’ll see malware popping up in more and more places.


ThreeBallot and Tampering

Let’s continue our discussion (1; 2) of Rivest’s ThreeBallot voting system. I’ve criticized ThreeBallot’s apparent inability to handle write-in votes. More detailed critiques have come from Charlie Strauss (1; 2) and Andrew Appel. Their analysis (especially Charlie’s) is too extensive to repeat here, so I’ll focus on just one of Charlie’s ideas.

Recall that ThreeBallot requires each voter to mark three ballots. Each candidate must be marked on at least one ballot (call this the mandatory mark); and the voter can vote for a candidate by marking that candidate on a second ballot. I call these rules (each candidate gets either one or two marks, and at most one candidate per race gets two marks) the Constraints. Because of the Constraints, we can recover the number of votes cast for a candidate by taking the total number of marks made for that candidate, and subtracting off the number of mandatory marks (which equals the number of voters).

ThreeBallot uses optical scan technology: the voter marks paper ballots that can be read by a machine. A voter’s three ballots are initially attached together. After filling out the ballots, the voter runs them through a checker machine that verifies the Constraints. If the ballots meet the Constraints, the checker puts a red stripe onto the ballots to denote that they have been checked, separates the three ballots, and gives the voter a copy of one ballot (the voter chooses which) to take home. The voter then deposits the three red-striped ballots into a ballot box, where they will eventually be counted by a tabulator machine.

Charlie Strauss points out there is a window of vulnerability from the time the ballots are checked until they’re put in the ballot box. During this time, the voter might add marks for his desired candidate, or erase marks for undesired candidates, or just put one of the ballots in his pocket and leave. These tactics are tantamount to stuffing the ballot box.

This kind of problem, where a system checks whether some condition is true, and then later relies on that assumption still being true even though things may have changed in the meantime, is a common cause of security problems. Security folks, with our usual tin ear for terminology, call these “time of check to time of use” or TOCTTOU bugs. (Some people even try to pronounce the acronym.) Here, the problem is the (unwarranted) assumption that if the Constraints hold when the ballots are put into the checker, they will still hold when the ballots are later tabulated.

One way to address this problem is to arrange for the same machine that checks the ballots to also tabulate them, so there is no window of vulnerability. But ThreeBallot’s security depends on the checker being dumb and stateless, so that it can’t remember the ballot-sets of individual voters. The tabulator is more complicated and remembers things, but it only sees the ballots after they are separated and mixed together with other voters’ ballots. Rivest makes clear that the checker and the tabulator must be separate mechanisms.

We might try to fix the problem by having the checker spit out the checked ballots into a sealed, glass-sided chute with a ballot box at the bottom, so the voter never gets to touch the ballots after they are checked. This might seem to eliminate the window of vulnerability.

But there’s still a problem, because the ballots are scanned by two separate scanner devices, one in the checker and one in the tabulator. Inevitably the two scanners will be calibrated differently, so there are some borderline cases that look like a mark to one scanner but not to the other. This means that ballot-triples that meet the Constraints according to one scanner won’t necessarily meet them according to the other scanner. A clever voter can exploit these differences, regardless of which scanner is more permissive, to inflate the influence of his ballots. He can make his mandatory marks for disfavored candidates faint, so that the checker just barely detects them, in the hope that the tabulator will miss them. And he can add a third mark for his favored candidate, just barely too faint for the checker to see, in the hope that the tabulator will count it. If either of these hopes is fulfilled, the final vote count will be wrong.

This is just a small sample of Charlie Strauss’s critique of ThreeBallot. If you want to read more, check out Charlie’s reports (1; 2), or Andrew Appel’s.


Spamhaus Tests U.S. Control Over Internet

In a move sure to rekindle debate over national control of the Internet, a US court may soon issue an order stripping London-based of its Internet name.

Here’s the backstory. Spamhaus, an anti-spam organization headquartered in London, publishes ROKSO, the “Register of Known Spam Operations”. Many sites block email from ROKSO-listed sites, as an anti-spam tactic. A US company called e360 sued Spamhaus, claiming that Spamhaus had repeatedly and wrongly put e360 on the ROKSO, and asking the court to award monetary damages and issue an injunction ordering e360’s removal from ROKSO.

Spamhaus lost the case, apparently due to bad legal maneuvering. Faced with a U.S. lawsuit, Spamhaus had two choices: it could challenge the court’s jurisdiction over it, or it could accept jurisdiction and defend the case on the merits. It started to defend on the merits, but then switched strategies, declaring the court had no jurisdiction and refusing to participate in the proceedings. The court said that Spamhaus had accepted its jurisdiction, and it proceeded to issue a default judgment against Spamhaus, ordering it to pay $11.7M in damages (which it apparently can’t pay), and issuing an injunction ordering Spamhaus to (a) take e360 off ROKSO and keep it off, and (b) post a notice saying that previous listings of e360 had been erroneous.

Spamhaus has ignored the injunction. As I understand it, courts have broad authority to enforce their injunctions against noncompliant parties. In this case, the court is considering (but hasn’t yet issued) an order that would revoke Spamhaus’s use of the name; the order would require ICANN and the Tucows domain name registry to shut off service for the name, so that anybody trying to go to would get a domain-not-found error. (ICANN says it’s up to Tucows to comply with any such order.)

There are several interesting questions here. (1) Is it appropriate under U.S. law for the judge to do this? (2) If the is revoked, how will spamhaus and its users respond? (3) If U.S. judges can revoke domain name registrations, what are the international implications?

I’ll leave Question 1 for the lawyers to argue.

The other two questions are actually interrelated. Question 3 is about how much extra power (if any) the US has by virtue of history and of having ICANN, the central naming authority, within its borders. The relevance of any US power depends on whether affected parties could work around any assertion of US power, which gets us back to Question 2.

Suppose that gets shut down. Spamhaus could respond by registering Would the .uk registry, which is run or chartered by the UK government, comply with a US court order to remove Spamhaus’s registration? My guess would be no. But even if the .uk registry complied and removed, that decision would not depend on any special US relationship to ICANN.

The really sticky case would be a dispute over a valuable name in .com. Suppose a US court ordered ICANN to yank a prominent .com name belonging to a non-US company. ICANN could fight but being based in the US it would probably have to comply in the end. Such a decision, if seen as unfair outside the US, could trigger a sort of constitutional crisis for the Net. The result wouldn’t be pretty. As I’ve written before, ICANN is far from perfect but the alternatives could be a lot worse.

(via Slashdot)


ThreeBallot and Write-Ins

Yesterday I wrote about Ron Rivest’s ThreeBallot voting system. Today I want to start a discussion of problems with the system. (To reiterate: the purpose of this kind of criticism is not to dump on the designer but to advance our collective understanding of voting system design.) Charlie Strauss and Andrew Appel have more thorough criticisms, which I’ll get to in future posts. Today I want to explain what I think is the simplest problem with ThreeBallot: it has no natural way to handle write-in votes.

(For background on how ThreeBallot works, see the previous post.)

The basic principle of ThreeBallot voting is that each voter fills out three ballots. Every candidate’s name must be marked on either one or two of the three ballots – to vote for a candidate you mark that candidate on exactly two of the three ballots; all other candidates get marked on exactly one of the three ballots. The correctness of ThreeBallot depends on what I’ll call the Constraint: each voter creates at least one mark, and no more than two marks, for each candidate.

But how can we maintain the Constraint for write-in candidates? The no-more-than-two part is easy, but the at-least-one part seems impossible. If some joker writes in Homer Simpson on two of his ballots, does that force me and every other voter to write in Homer on one of my three ballots? And how could I, voting in the morning, know whether somebody will write in Homer later in the day?

We could give up on the Constraint for write-in candidates. But the desirable features of ThreeBallot – the combination of auditability and secrecy – depend on the Constraint.

In particular, it’s the at-least-one part of the Constraint that allows you to take home a copy of one of your ballots as a receipt. Because you have to mark at least one ballot for every candidate, a receipt showing that you marked one ballot for a particular candidate (a) doesn’t force you to help that candidate, and (b) doesn’t prove anything about how you really voted – and that’s why it’s safe to let you take a receipt. If we throw out the at-least-one rule for write-ins, then a receipt showing a write-in is proof that you really voted for that write-in candidate. And that kind of proof opens the door to coercion and vote-buying.

Alternatively, we can declare that people who cast write-in votes don’t get to take receipts. But then the mere existence of your receipt is proof that you didn’t vote for any write-in candidates. I don’t see any way out of this problem. Do you?

There’s an interesting lesson here about election security, and security in general. Systems that work well in the normal case often get in trouble when they try to handle exceptional or unusual cases. The more complicated the system is, the more likely such problems seem to be.

In the next post I’ll talk about some other instructive problems with ThreeBallot.



ThreeBallot is a new voting method from Ron Rivest that is supposed to make elections more secure without compromising voter privacy. It got favorable reviews at first – Michael Shamos even endorsed it at a congressional hearing – but further analysis shows that it has some serious problems. The story of ThreeBallot and its difficulties is a good illustration of why voting security is hard, and also (I hope) an interesting story in its own right.

One reason secure voting is hard is that it must meet seemingly contradictory goals. On the one hand, votes must be counted as cast, meaning the vote totals reported at the end are the correct summation of the ballots actually cast by the voters. The obvious way to guarantee this is to build a careful audit trail connecting each voter to a ballot and each ballot to the final tally. But this is at odds with the secret ballot requirement, which says that there can be no way to connect a particular voter to a particular ballot. Importantly, this last requirement must hold even if the voter wants to reveal his ballot, because letting a voter prove how he voted opens the door to coercion and vote-buying.

If we were willing to abandon the secret ballot, we could help secure elections by giving each voter a receipt to take home, with a unique serial number and the list of votes cast, and publishing all of the ballots (with serial numbers) on the web after the election. A voter could then check his receipt against the online ballot-list, and complain if they didn’t match. But of course the receipt violates the secret-ballot requirement.

Rivest tries to work around this by having the voter fill out three ballots. To vote for a candidate, the voter marks that candidate on exactly two of the three ballots. To vote against a candidate, the voter marks that candidate on exactly one ballot. All three ballots are put in the ballot box, but the voter gets to take home a copy of one of them (he chooses which one). At the end of election day, all ballots are published, and the voter can compare the ballot-copy he kept against the published list. If anybody modifies a ballot after it is cast, there is a one-third chance that the voter will have a copy of that ballot and will therefore be able to detect the modification. (Or so the theory goes.)

Consider a two-candidate race between George Washington and Benedict Arnold. Alice wants to cast her vote for Washington, so she marks Washington on two ballots and Arnold on one. The key property is that Alice can choose to take home a copy of a Washington ballot or a copy of an Arnold ballot – so the mark on the ballot she takes doesn’t reveal her vote. Arnold’s crooked minions can offer to pay her, or threaten to harm her, if she doesn’t produce an Arnold ballot afterward, and she can satisfy them while still casting her vote for Washington.

ThreeBallot is a clever idea and a genuine contribution to the debate about voting methods. But we shouldn’t rush out and adopt it. Other researchers, including Charlie Strauss and Andrew Appel, have some pretty devastating criticisms of it. They’ll be the topic of my next post.


Dutch E-Voting System Has Problems Similar to Diebold's

A team of Dutch researchers, led by Rop Gonggrijp and Willem-Jan Hengeveld, managed to acquire and analyze a Nedap/Groenendaal e-voting machine used widely in the Netherlands and Germany. They report problems strikingly similar to the ones Ari Feldman, Alex Halderman and I found in the Diebold AccuVote-TS.

The N/G machines all seem to be opened by the same key, which is easily bought on the Internet – just like the Diebold machines.

The N/G machines can be put in maintenance mode by entering the secret password “GEHEIM” (which means “SECRET” in Dutch) – just as the Diebold machines used the secret PIN “1111” to enter supervisor mode.

The N/G machines are subject to software tampering, allowing a criminal to inject code that transfers votes undetectably from one candidate to another – just like the Diebold machines.

There are some differences. The N/G machines appear to be better designed (from a security standpoint), requiring an attacker to work harder to tamper with vote records. As an example, the electrical connection between the N/G machine and its external memory card is cleverly constructed to prevent the voting machine from undetectably modifying data on the card. This means that the strategy used by our Diebold virus, which allows votes to be recorded correctly but modifies them a few seconds later, would not work. Instead, a vote-stealing program has to block votes from being recorded, and then fill in the missing votes later, with “improvements”. This doesn’t raise the barrier to vote-stealing much, but at least the machine’s designers considered the problem and did something constructive.

The Dutch paper has an interesting section on electromagnetic emanations from voting machines. Like other computers, voting machines emit radio waves that can be picked up at a distance by somebody with the right equipment. It is well known that eavesdroppers can often exploit such emanations to “see” the display screen of a computer at a distance. Applied to voting machines, such an attack might allow a criminal to learn what the voter is seeing on the screen – and hence how he is voting – from across the room, or possibly from outside the polling place. The Dutch researchers’ work on this topic is preliminary, suggesting a likely security problem but not yet establishing it for certain. Other e-voting machines are likely to have similar problems.

What is most striking here is that different e-voting machines from different companies seem to have such similar problems. Some of the technical challenges in designing an e-voting machine are very difficult or even infeasible to address; and it’s not surprising to see those problems unsolved in every machine. But to see the same simple, easily avoided weaknesses, such as the use of identical widely-available keys and weak passwords/PINs, popping up again, has to teach a deeper lesson.