Re: Voting Crypto Contest held by ES&S

From: Douglas W. Jones <jones_at_cs_dot_uiowa_dot_edu>
Date: Wed Jul 25 2007 - 09:42:51 CDT

On Jul 25, 2007, at 9:15 AM, charlie strauss wrote:

> ES&S held a voting crypto contest.
No, the VoComp competition was NSF sponsored. ES&S and Hewlett
Packard donated money for prizes. ES&S and HP had nothing to do with
the organization or judging of the contest. I was a Judge.
> The winner was (nominally) punchscan which is complicated fiddly
> voting scheme created by mathematician david chaum.
They weren't the nominal winner. They won, fair and square.
The strong runner-up was Pret a Voter, another fiddly voting
scheme. Both had significant human factors problems.
> Chaum himself is quite good and has proposed other related methods
> previously. I've not analyzed the method for flaws in detail but if
> I recall correctly it has the same achilles heel that Chaum's other
> method did. Namely someone has to have the keys to the crypto, at
> least at some point in the process.
Yup. Proof of information destruction is a key element of all
the crypto voting schemes. How do you know that the keys to the
kingdom have been destroyed? You can do theatrical things with
sledge hammers and steamrollers, and there are still ways the
information could have been leaked.

The Punchscan folks used diskless workstations (at least, they
removed a disk from the laptop, I didn't take it apart to see if
it also had an internal drive) booted from a read only USB drive
holding a bootable Ubuntu system. Of course, USB drives are
extraordinary things, with their own CPU and computer network
protocols over the USB wires. A carefully hacked USB drive could
be used to do all kinds of evil things.
> The second item will warm the cockles of the heart of all open-
> source enthusiasts. Namely, That the competing algorithm had a flaw
> deep in it's random number generator. A quintessentially classic
> but hard to find blunder in crypto.
That was a fun one. One of the Punchscan group found it while they
were reading the source code for the Pret a Voter code. One of the
rules of the contest is that all the source code for all the
submissions is open. It's all available to be examined and possibly
> It's no shame since the this kind of blunder has tripped up the
> best in the business over the years.
Yup. But because bad random number generation is so well known, for
example, from Diebold's TS system as examined by Avi Rubin et al 5
years ago, it's a mistake people shouldn't have made. We awarded a
laptop for finding that problem.
> Now let me unpack that last sentence further. Obviously the open
> source part was crucial. But so was the motivated competitor.
> Finally, I note it's pretty common for hastily written software--
> which is mostly what commercial election software appears to be--
> to delegate parts like say random number generation or windows
> management to some piece of third party software or hardware.
It is notable that all of the competitors used versions of Linux for
their platforms. In theory, it's all open. I would say that
security critical applications developers have an obligation to
minimize their footprint -- that is, to rely on a minimum of features
from the underlying environment, so that audits of the environment
can be simplified. Designing software for a minimum footprint is
difficult because you need to examine the footprint size of each
component and simply discard components that have giant footprints.

                Doug Jones
OVC-discuss mailing list
= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
Received on Tue Jul 31 23:17:05 2007

This archive was generated by hypermail 2.1.8 : Tue Jul 31 2007 - 23:17:08 CDT