Re: electronically detecting tampering

From: Amit Sahai <sahai_at_CS_dot_Princeton_dot_EDU>
Date: Wed Nov 26 2003 - 14:39:19 CST

I want to address the concern raised by charlie strauss, but I also want
to propose that we initiate a process of dealing with security issues
systematically (for the post-demo project).

This process should have three aspects:

(1) Outlining security concerns,
(2) Proposing solutions,
(3) Discussing Pros/Cons of suggested solutions.

Of course, proposed solutions need not be technical. I would suggest that
no idea should be "shot down" during discussion, but rather possible
attacks or drawbacks are listed as "cons". Different solutions could then
be combined or adapted to achieve the level of security we desire. I also
suggest that when discussing cons, we stick to actual attacks, and not
vague notions like "lack of simplicity". For (1), I suggest we begin with
the following hierarchy:

I. Privacy/Anonymity Concerns
II. Robustness Concerns
    A. Dealing with Hardware/Software Failures
    B. Dealing with other malicious attacks

Let me also put forward a "design philosophy". When a civil engineer
suggests a bridge design, she does not suggest the simplest-to-build
design that will hold exactly the expected load of the bridge. Instead,
she has an ethical obligation to suggest a design that will withstand
several times the expected load, even if it is more complicated. As
computer scientists, we should hold ourselves to at least as high a
standard, especially when it comes to security concerns.


The concerns raised by charlie strauss are important, BUT: the "tricky
beast" he mentions is in fact extremely problematic, to which I know of no
complete solution. Some level of trust is obviously required.

I want to make several comments here:

0) Public Key Signature Schemes are extremely well-understood; they are
not "complex crypto" by any means. Well-accepted constructions exist for
this cryptographic primitive, as well as several widely used and trusted
pieces of code. While they do rely on unproven number-theoretic
assumptions, these problems have been open for, in some cases, thousands
of years. Compared to our other problems, worrying about someone who can
break these assumptions seems the least of our concerns.

1) I like charlie's idea of refering to previous ballots as a way of
catching insertions and deletions. I think this can be improved using
cryptographic techniques. However, it needs to be analyzed to determine
the level of security it provides. Clearly, it becomes easier to attack
toward the end of election.

2) The suggestions by charlie below do not fully address the problem of
trusting the code being run by the hardware. The problem of "easter eggs"
remain even with simple code. Furthermore, suppose that the machine is
required to output its entire instruction trace. There are still two
critical problems:
   A) One would still need to trust the verifier of the instruction trace.
   B) An "easter egg" could cause the machine to output a false
instruction trace which is consistent with the false ballots produced by
the machine.

3) On the other hand, public-key signatures offer a means to certify
software (though still one would need trust). Once our machine-level code
is compiled and ready, it could be sent out to the experts in the field
for verification. They could sign the (machine-level) code using a
public-key signature scheme. This signature would still need to be
verified in a trustworthy way, and one would still need to trust the
hardware running the software not to insert new code. The point is not
that trust can be eliminated, but it can be contained within specified

In any case, I would again like to suggest we begin (1) above
systematically. What are the security concerns?  What kinds of attacks are
possible?  Then we can propose solutions, and see which concerns are
addressed, and which are not...
Prof. Amit Sahai
Department of Computer Science
Princeton University
On Wed, 26 Nov 2003, charlie strauss wrote:
> All this talk of complex crypto I think is just using the wrong hammer
> on the problem.  I'm not against simple cryto like signed md5 hashes and
> such but I'm afraid we're obfuscating the true issues by worrying about
> key-control.
> As I see it the number one issue is transparency.  this means three
> things to me besides voter-verifiable hard copy ballots. 1) open source
> 2) A method to know what binary code the machine is actually running 3)
> human observable chain of custody of all modification to and output from
> the machine.
> two and three are a tricky beast that I dont think any software only
> solution can solve.  A complex hardware solution is the NGSC
> intel/microsoft (akak Paladium) systems (A solution I loath but would
> accept).  A simple solution is to make the bios dead simple with only
> two functions:  booting off a knopix style cd-rom and logging the
> checksum of the cdrom on a physically sealed unerasable device.  Since
> the CD-rom could be copied at will it would be possible for any election
> official to independently validate it's checksum agreed with the
> published source/binary
> Data going out of the machine must also be observable so again it gets
> written to an unerasable media like a cd-rom which can be copied (on
> dumb non-computerized machines) at will in the presence of election
> officials.  The disks could even be physically signed by all election
> judges with a pen if desired.
> Here's a low tech non-crypto solution to preventing post-election ballot
> stuffing and selective ballot losing:
> suppose that every time a machine printed out a voter-verifable ballot
> it also added a bar-code then contained the content of, say, some ten
> previous ballot chosen at random.  If some evil doer were to try to dump
> some of the ballots in the dumpster you could still recover the entire
> record from the remaider.  The missing ballots would be very obvious.
> Moreover any attempt to add additional ballots would be foiled unless
> these were added at the end.  And as long as one can keep track of the
> total number of true ballots one can weed out ones added at the end.
>  obviously one could improve on this scheme.  I'm just tryng to offer an
> easy to understand case that crypto discussions are clouding the main
> issues.
> If you want to argue this point I'll trump the issue by saying that
> there is always the possibility someone could place an easter egg in the
> software used to compile the source that would inject an evil program
> into the binary. adding yet another layer to this dicsussion.
> -----Original Message-----
> From: Clay Lenhart <>
> Sent: Nov 26, 2003 11:27 AM
> To:
> Subject: [voting-project] electronically detecting tampering
> I wanted to put on the table what I think is the current best solution for electronically detecting if ballots have been tampered with, and its weaknesses.  It is based on David's plan from a number of months ago, except that it uses public/private keys.  Please make suggestions, because my feeling is that this is not good enough.
> When the machine boots, it generates a public and private key pair.  The private key cannot be extracted from the machine.  A number of people, independent from the election administration, "publish" the public key so that we are fairly certain that we know which public keys are valid.
> Each voter completes a ballot and the ballot is signed with the private key.  The ballot has a unique ballot number that is included in the signature to detect duplication of signed ballots.
> The ballots and the signatures are uploaded to a central location to count the ballots and verify the signatures. (I know I'm missing some steps, but this is more other people's area)
> The ballots and signatures can be downloaded by anyone to verify the electronic signatures.
> This scheme will detect if ballots have been updated, but it doesn't *electronically* detect inserts and deletes. As you know "delete + insert = update". If we can prevent inserts of ballots through some process, then the independent group of people can publish the number of voters for a location and this will detect deleted ballots. I.e. if the number of electronic ballots does not match the number of voters, then a percentage of ballots were deleted.   There might be a process that can prevent inserts, but I would prefer to detect this electronically somehow, because I can be fairly certain about what happens eletronically, but I won't know if a process was obeyed.
> However, since the private keys cannot be extracted from the machines, then someone would have to use the machines to create fake ballots.  The insert problem seems somewhat contained.
> Another concern: What if the software were modified so that it didn't generate new pub/priv keys, but used a preknown pub/priv key pair and this public key became one of the "valid" public keys?  Is there a way to verify the software used at the time of the election, against its source code?  Since python runs text files, this seems possible.  Then the independent group of people would publish the source code at this time.  This is probably a good idea in general b/c it makes the software auditable and we are certain about which code was used by the machines.
> -Clay
= The content of this message, with the exception of any external 
= quotations under fair use, are released to the Public Domain    
Received on Sun Nov 30 23:17:09 2003

This archive was generated by hypermail 2.1.8 : Sun Nov 30 2003 - 23:17:13 CST