Problem (was: Re: need help with tool requirement)

[Bill Sconce]

On Wed, 21 Apr 2004 01:33:26 -0400
bmcculley at rcn.com wrote:

> Here's the real problem description.
>     [...] 
> What approach would provide sufficient assurance that the code
> does not contain any "Easter eggs" or trap doors to allow
> future egg-laying?


Too bad the Perl script is lost.  It was the only solution.  :)

Seriously, this isn't going to be possible.  However, if you have
a client who is asking this question, write your own Perl script,
produce lots of output listings, and take their money.

There is substantial literature on the subject, and a nearly total
mess between IEEE, the EFF, and the security community.  Google for
"ieee voting" for a start.

As for "close being good enough", the attached appeared in Bruce
Schneier's CRYPTO-GRAM for April 15th 2004.  Just one article
among many.

-Bill


             Stealing an Election

There are major efforts by computer security professionals to convince 
government officials that paper audit trails are essential in any 
computerized voting machine.  They have conducted actual examination of 
software, engaged in letter writing campaigns, testified before 
government bodies, and collectively, have maintained visibility and 
public awareness of the issue.

The track record of the computerized voting machines used to date has 
been abysmal; stories of errors are legion.  Here's another way to look 
at the issue: what are the economics of trying to steal an election?

Let's look at the 2002 election results for the 435 seats in the House 
of Representatives.  In order to gain control of the House, the 
Democrats would have needed to win 23 more seats.  According to actual 
voting data (pulled off the ABC News website), the Democrats could have 
won these 23 seats by swinging 163,953 votes from Republican to 
Democrat, out of the total 65,812,545 cast for both parties.  (The 
total number of votes cast is actually a bit higher; this analysis only 
uses data for the winning and second-place candidates.)

This means that the Democrats could have gained the majority in the 
House by switching less than 1/4 of one percent of the total votes -- 
less than one in 250 votes.

Of course, this analysis is done in hindsight.  In practice, more 
cheating would be required to be reasonably certain of winning.  Even 
so, the Democrats could have won the house by shifting well below 0.5% 
of the total votes cast across the election.

Let's try another analysis: What is it worth to compromise a voting 
machine?  In contested House races in 2002, candidates typically spent 
$3M to $4M, although the highest was over $8M.  The outcomes of the 20 
closest races would have changed by swinging an average of 2,593 votes 
each.  Assuming (conservatively) a candidate would pay $1M to switch 
5,000 votes, votes are worth $200 each.  The actual value is probably 
closer to $500, but I figured conservatively here to reflect the 
additional risk of breaking the law.

If a voting machine collects 250 votes (about 125 for each candidate), 
rigging the machine to swing all of its votes would be worth 
$25,000.  That's going to be detected, so is unlikely to 
happen.  Swinging 10% of the votes on any given machine would be worth 
$2500.

This suggests that it is necessary to assume that attacks against 
individual voting machines are a serious risk.

Computerized voting machines have software, which means we need to 
figure out what it's worth to compromise a voting machine software 
design or code, and not just individual machines.  Any voting machine 
type deployed in 25% of precincts would register enough votes that 
malicious software could swing the balance of power without creating 
terribly obvious statistical abnormalities.

In 2002, all the Congressional candidates together raised over 
$500M.  As a result, one can conservatively conclude that affecting the 
balance of power in the House of Representatives is worth at least 
$100M to the party who would otherwise be losing.  So when designing 
the security behind the software, one must assume an attacker with a 
$100M budget.

Conclusion:  The risks to electronic voting machine software are even 
greater than first appears.


This essay was written with Paul Kocher.