Comp527: Voting (in)security

Project assigned Wednesday, 2 September 2003
Phase 1 Due Wednesday, 17 September 2003, 11:59am
Phase 2 Due Wednesday, 24 September 2003, 11:59am
Phase 3 Due Friday, 10 October 2003, 11:59am

Introduction

This project will give you a chance to explore both sides of the security issues involved in building and verifying direct-recording electronic (DRE) voting systems. DRE systems record votes electronically, without necessarily producing a paper record. Their use has been advocated recently, especially after the problems in Florida during the 2000 presidential election. DRE systems promise greater accuracy of recording, increased accessibility for people with various physical handicaps, and no hanging chads. They also put tremendous amounts of trust in the computer to correctly record the votes - if the computer system is wrong, there is no written backup to fall back on. Therefore, security flaws in DRE systems can be called, without exaggeration, threats to democracy.

The project is split into three phases. In the first phase, you will play the part of a co-opted voting machine vendor intent on damaging the election in some way; in the second, you will be an auditor trying to spot problems that may have been introduced. In the last phase, you'll use what you've learned about cryptographic protocol verification to find a solution to a problem discovered in a real voting system.

Partners

You're expected to work with a partner. You can choose any partner you like, and if you really want to change partners after each phase, that's okay. We'll allow at most one group of three people, and that's only if we need it to keep the class balanced. Rather than trying to split the work in half, with each partner doing their half, we strongly recommend that you work together, side-by-side, on everything (design, analysis, the works) with only one computer. Change off who is typing once in a while, but go at it together. This style, sometimes called pair programming has been shown time and again to keep people working efficiently. Also, in terms of security analysis or other forms of devious thinking, it's amazingly helpful to have somebody else there to bounce ideas around. Your work, and your grade, will be that much better.

Grading

Each phase will be graded equally, even though we've given more time to some phases than others. Rather than trying to give you an exact breakdown or point system, we'll be applying a more wholistic approach. You'll be rewarded for being creative. You'll be penalized if your design is obviously broken.

Phase One: Crouching Bug, Hidden Trojan

Due date: Wednesday, 17 September 2003, 11:59am

Premise

You are the development team for Hack-A-Vote Election Systems, a major election vendor that has contracts with several U.S. states and counties to supply voting machines. Unfortunately for democracy, you are of questionable moral character, and you've been offered a large sum of money to sabotage Hack-A-Vote's flagship election product.

Assignment

There are any number of ways you could use your position as the supplier of voting machine technology to introduce problems into an election. The obvious thing to do is steal the election by modifying your machine to occasionally change votes to a preferred candidate. There are other nasty things you might do, though - if all of your machines produce uncertain or garbage results, you could cause electoral chaos. You might try to selectively disenfranchise some group of voters you don't like. Be creative; find a way to modify the machines that will create problems of your choice in the electoral system.

You'll implement your changes against Hack-a-Vote's current product. The user interface has already passed approval testing, so don't modify what is seen by an ordinary voter. It's important to keep your changes small in scope and hard to detect via a source code inspection, because later, your classmates will be scrutinizing your codebase trying to figure out what you did. Cleverness in hiding your changes is therefore crucial to your success.

The Hack-a-Vote source code is here: http://www.cs.rice.edu/~arudys/hackavote.tar.gz
Javadoc is also available.

You only have to worry about your changes being spotted before the election; afterwards, your benefactors have arranged for you to be flown to a location with sandy beaches, scantily clad members of the preferred sex, and no extradition treaties with the United States.

You should submit:

  1. A file called yourname-vote.tar.gz which represents your modified version of the Hack-a-Vote system, where yourname is the username of one of your group members.
  2. A short report in HTML or PDF format that describes the nefarious modifications that you've made, and why. Come up with a scenario describing who has bribed you to make these changes and how they expect to benefit from them.

Please place these files on a publically accessible web site and e-mail the URL to Algis. Do not make your documents globally visible. Don't link to them from your home page. Just make sure somebody can type the URL into a browser and download the files.

Please keep your modifications private until after the end of Phase Two. You don't know which group is going to get your code to analyze, and the less they know, the better off you are.

Phase Two: Crime Scene Investigation

Due Date: Wednesday, 24 September 2003, 11:59am

Premise

Real voting machines are audited before they can be sold. Generally, this auditing is done by certified private laboratories that test all manner of functionality and failure modes. These laboratories submit a report with their recommendations to the vendor and interested voting authorities.

Assignment

You will now play the part of an overworked contract auditor. Your job is to analyze the code of two voting systems submitted to you, determine if there are any security problems with it, and write a report (in HTML or PDF format) for the voting officials that indicates what, if any, problems you found and what should be done to mitigate them. You'll receive two codebases with the work of two of the other groups in the class. Read the source code, compile and run it, debug it, do whatever you can to figure out what sorts of Trojan horses may have been introduced. Be sure to answer the following questions:

  1. What approach did you take to analyze the code? Describe in detail, including software tools you used. Include approaches you tried that didn't work. Why didn't they work? Knowing what you do now after having analyzed the code, how would you have approached your analysis differently?
  2. What problems exist in this voting system?
  3. If you found problems that seem to have been introduced deliberately, what do you think the motivation was for introducing them? Who is likely to benefit from the modifications you found?
  4. Could you have found these problems if you had not had access to the source code of the voting machine? Why or why not? How much did access to the source speed your analysis?

You probably also want to look over the 2002 "final" voting standards from the Federal Election Commission. Section 6 on the "voting standards" talks about security. In theory, real voting systems are supposed to meet these standards (even though most current systems have not been certified to these standards yet).

Pretend that you don't have the official source code from Phase One from which you could otherwise have computed the diffs. You'll have to be more clever than that. Make your report available at a web page accessible to anyone and e-mail the URL to Algis.

(Incidentally, you will get to read the reports that other groups write about your system. This will help you see how successful you were in phase one.)

Phase Three: Back to the Future

Due Date: Friday, 10 October 2003, 11:59am

You've spent some time learning about designing correct cryptographic protocols. One place in some election systems where a crypto protocol is appropriate is when the user is authenticated as a properly registered voter who has not voted before. Many DRE systems use a smart card issued to the voter either at the polling place or before the election to perform this authentication.

It's important that the protocol used allows the voter to remain anonymous, since a secret ballot is a goal of the election system. It's also important that the voter not be able to supply proof of his ballot choices to a third party; this prevents vote-buying and undue influence by employers, family members, and so forth.

Diebold's AccuVote-TS system, which has been used in actual elections, uses the following protocol:

User inserts smartcard into machine, which prompts for a PIN
Machine -> Card PIN
Card -> Machine OK or Not OK
Card responds "OK" iff the PIN is correct and this is the first use.

This protocol does not use cryptography improperly - it just doesn't use cryptography at all! The major problem here is that a voter could sneak in his own card that always responds "OK." This would permit multiple votes.

Your job is to produce a model for smartcard distribution and a protocol that meets the following security goals:

Voters are divided into precincts, districts served by one central polling place. A voter may vote only at the polling place for his or her precinct, but there may be several voting machines at the precinct, and the voter will use whatever machine comes available first.

You may assume that there is an out-of-band method of identifying registered voters and providing them with their correct smartcards; however, you may not assume that registered voters will necessarily be motivated to keep their smartcards to themselves. Think about the problems that might be caused by voters trading or selling cards, and the methods (technical and administrative) that you would use to mitigate these problems.

You should model as much of your protocol as you can using the cryptyc system.

Your submission

  1. Design document: A report (HTML or PDF) that describes your scheme in detail, and the administrative actions by the voting authorities that would be required to support it. Be sure to sure to include a list of attack scenarios that you intend your system to be robust against. Argue in your report that your approach is correct, that it meets the security goals above, and that it is in fact robust against the attack scenarios you considered.
  2. Protocol Proof: Using cryptyc, model the protocol(s) spoken between the smart card and the voting machine, and also between the smart card and any other devices it may need to speak to. Be sure that any compromises you make in order to produce a cryptyc model of your system are documented in your design document.

You will be graded on completeness and attention to detail, but you won't be graded on correctness. We want to see that you thought about the issues in your design and that you managed to produce a cryptyc model that reflects your design and has some meaningful proof of correctness.

Your submission should be a URL readable by anyone, with links to your design document in HTML or PDF as well as the files used in your cryptyc model.

Advice

Strive for simplicity. If you must use 'deep mathematics' (e.g., blinded signatures, zero knowledge proofs, etc) you must state why, and why simpler techniques won't work; avoid using public key cryptography unless you really need it. Likewise, when we ask you to discuss different attack scenarios and how you'll address them, you should think "out of the box." Imagine all the different way things could go wrong. For example:

You'll want to add more and elaborate on these scenarios. Feel free to discuss them on the course newsgroup, but don't discuss how you plan to address them. On the other hand, don't feel obliged to address each and every thing you hear about on the newsgroup. If you don't believe an attack is feasible because of some external administrative procedure ("We strip-search all voters to make sure they haven't brought in a hacked smartcard"), say so, but back up what you say with a sound argument.

Resources

Johns Hopkins/Rice study of the Diebold election system
Scott Crosby's cryptyc tutorial: PDF

Credits

The original idea for Hack-a-Vote came from David Dill at Stanford. Both the code and this assignment were written by David Price (Jones '03, now at UT Law School).


Dan Wallach, CS Department, Rice University
Last modified: Tue 02-Sep-2003 16:45