Ness' Outpost

I watched the HBO documentary called “Hacking Democracy” last night and it was quite eye opening. They showed how a Diebold optical scanning voting machine was able to have it’s memory card altered to effectively “stuff” the ballot box in the favour of a candidate while maintaining the accuracy of the total vote count.

Without having looked at the software — because it is illegal thanks to the DMCA — I will speculate my thoughts on this situation.

The machine relies on removable memory cards in the same way that your camera does. This allows machines to be disconnected from a computer network, but relies on “sneaker net” to transfer the number of votes from each individual machine to the “central tabulator” which reads each memory card and sums up the totals for every machine in the election.

The memory card can be stolen, destroyed, damaged, replaced or simply lost in transit. This is of course horrible since the voting results for each machine are stored on a memory card.

But how are the results stored? Is each vote entered on the memory card or is it using a “totalizer” for each candidate in a vote to save space on the memory card. I am under the impression a totalizer is being used after watching the documentary. This would allow for an almost unlimited number of voters to use the same voting machine without running the risk of exhausting the available memory on the card. The only risk is the storage of the totalizer could overflow the variable storage space. This turns a very large positive number into a very large negative number depending on how the number is represented in binary on the memory card.

The Finnish hacker “stuffed” the ballot box by initially setting the number of “Yes” votes to 5 and the number of “No” votes to -5. You read correctly, minus 5. A computer doesn’t mind if a number is negative or not. It is only humans who understand and place the constraint that votes must be non-negative (greater or equal to zero) in an election. The interesting thing is that you’ll notice when summing the two totalizers together for “Yes” and “No” the total ballots cast in this election is currently 5 + (-5) = 0 which matches the totalizer for the number of votes cast which should be initialized to zero before an election starts.

This ballot box stuffing only works if you specify a negative number of votes that must be overcome by a candidate to bring them into positive votes so as not to attract attention. Do not get greedy if trying to apply this attack.

How to Safeguard the Totalizers

There is a common procedure when programing safety or mission critical systems that the program needs to satisfy the invariants of the system. This means that the software needs to check both the pre and post conditions of important states or data before and after they are modified. In our specific case a good invariant may be:

All candidates must have a non-negative vote total
The wording is tricky and uses “non-negative” to describe votes to include zero in the set of acceptable vote totals. This apparently is being ignored by the system that Diebold has produced as candidate totalizers appear to accept a value of -5 which violates the above invariant.

If an invariant is violated the machine should declare itself corrupt and return to a “safe state”. The definition of safe state can be debated, but it may involve rolling back the last vote transaction and alerting the voter that their vote was not counted. Obviously the machine should declare itself as having problems and alert the elections officers that unauthorized access may have taken place on the votes that are currently stored on the memory card. In the concrete example above that would take place during the first vote.

Initialization

Why are the memory cards not completely erased by the machines when the machine is turned on? By doing this leftover data from previous elections or previous days of the election cannot be appended to in the totalizers and counted twice.

Encryption

Why is the data on the memory cards not encrpyted? Perhaps some reasons are to minimize the amount of CPU power required to run these machines. Encryption adds overhead to the hardware which would be needed to decrypt the data on each access and then encrypt the new state of the memory card. Also ease of use for end users would become much more difficult if each election officer needed to handle multiple encryption key management.

Today these should trivial problems to overcome that greatly increase the security of the system.

Conclusion

I’m sure Diebold is scrambling to upgrade their systems, but the truth of the matter is that these machines will likely be in service for years to come. Some people still vote in the United States by using punch cards, which were input for old Unix mainframes! I’m not sure what the lifetime of an election machine is but I would expect it to be somewhere around 10 years or so, which could be a lifetime of at least 2 or 3 major elections.

I strongly suggest that those in the position of purchasing election equipment do not purchase Diebold systems which restrict the rights of users, voters and scrutineers from being sure that the election results are valid beyond a reasonable doubt.

Diebold needs to provide open access to their software and hardware for public review by qualified individuals. I’m not suggesting they provide information to competitors — I’m suggesting they audit their product correctly and get it certified by people with a Certificate of Authorization. These people have strong ethical morals that push them to make sure their work is accurate and in the best interest of the client and society.

I hope that qualified individuals like professional engineers are able to drive change so that democracy is maintained and not purchased or tampered with.

This entry was posted on Thursday, November 9th, 2006 at 1:34 pm and is filed under Geek, Hardware, Software, Technology. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.