Introduction
Some real voting machines use a smartcard, called a "voter card," to control who can vote. On arriving at the polling place, the voter checks in and states his name and address. Election workers verify the voter's identity (we'll assume they can do this flawlessly) and verify that the voter is registered to vote and hasn't voted yet. Assuming that everything is in order, they enable a voter card (a special device the size of a credit card) and give it to the voter.The voter casts his vote on a voting machine. Before allowing him to vote, the machine insists that he insert the voter card. The machine interacts with the voter card, and if it likes the interaction, it disables the voter card and allows the voter to cast a vote.
After the voter is done voting, the machine ejects the now-disabled voter card, and the voter gives the voter card back to the election workers at the front desk before leaving the polling place. (The voter card may later be re-enabled for use by another voter.)
The idea of this scheme is that an enabled voter card allows one vote to be cast. Unfortunately, some real implementations of this scheme are insecure, allowing an adversary to re-enable his own voter card as often as he likes, and thereby to cast as many votes as he likes. Your job is to fix this.
Encoder, Voting Machine, and Voter Card
There are three kinds of devices: encoder, voting machine, and voter card. The encoder is used by election workers at the front desk when they want to enable a voter card. Assume that it plugs into the wall and is the size of a deck of cards, with a slot into which a voter card can be inserted. To enable a voter card, an election worker will insert that card into the encoder.The voting machine is a computer. It plugs into the wall and looks like an oversized laptop. It has a slot into which a voter card can be inserted. When a voter card has been inserted, the voting machine interacts with the card and then decides whether to allow a vote to be cast. If necessary, it interacts with the voter card to tell the voter card to disable itself.
When the voter card is inserted into another device, the voter card can communicate with that device using a bidirectional serial channel. For example, the voter card can send a byte to the other device, and the other device can receive that byte; or vice versa. This is the only way the devices can interact.
It is important to recognize that the voter card is a computer in its own right. Other devices, such as the encoder and voting machine, can never read or write the voter card's memory directly. All they can do is communicate with the voter card and rely on it to change its state.
Another important fact about the smartcard is that it does not have its own power source--it gets power only when it is inserted into another device (here, an encoder or voting machine). When the device ejects the smartcard, the smartcard immediately loses power and stops running. The smartcard has a "persistent memory" which can store up to 65536 bytes of data, and is preserved even when the smartcard is without power. The persistent memory is the only way for the smartcard to remember anything when it is not running.
The Software
For this assignment, you will modify Java code that runs in the encoder, the voting machine, and the smartcard; and you will write code that initializes newly manufactured voter cards. We are giving you starter code, which implements a fully functional but insecure voter authentication system. Your job is to make the system secure.The starter code is a bit tricky to understand. We'll start by discussing the communication protocol used in the starter code. The communication protocol can be thought of as a contract between the smartcard, voting machine, and encoder. This protocol must work no matter what sequence of devices the smartcard is inserted into (e.g. if the smartcard is inserted into an encoder 8 times before being inserted into a voting machine, it should still work).
Protocol used by Starter Code
The protocol used by the starter code is very simple. For a visual picture, see the smartcard-encoder protocol schematic, and the smartcard-machine protocol schematic.
- Smartcard: The smartcard has a persistent 1 byte state (using just 1/65536th of its memory). When a smartcard is inserted into any device, it will begin the communication process by sending its state. It will then wait for a return message. Upon receiving a message, the card sets its state equal to the value of this message. Finally, the card sends a dummy message of value 0, and the smartcard code completes. If the card is ejected at any point during this process, the code immediately terminates.
- Machine: The voting machine has no persistent state. When a smartcard is inserted, the voting machine waits for a message. If it is 1, the user is allowed to cast one vote (in this assignment, we don't actually collect or store votes, instead we simply print the message "Allowed one vote."). The machine then sends a 0 to the smartcard, and waits for a response. Once a response is received (the value is irrelevant), the machine ejects the card, and the machine code completes.
- Encoder: The encoder has no persistent state state. When a smartcard is inserted, the encoder waits for a message. Once any message is received (value is irrelevant), the encoder responds with a 1. After sending this 1, the encoder waits for a response from the smartcard. Upon receipt of this response (value is irrelevant), the card is ejected, and the encoder code completes.
Note that the smartcard (in our implementation) has no idea which type of device it's talking to. Your design may or may not have this feature. As a reminder, Cross-group collaboration -- including discussion of the merits/flaws of different protocol designs -- is not allowed.
The Roles of Each Class
Running the code. To simulate insertion of a smartcard into an encoder, one uses the command java Encoder [filename], where filename is a 65536 byte file on your computer's disk which holds the contents of a smartcard's memory, and likewise for a voting machine. To generate a 65536 byte smartcard memory file, java CreateCard [filename], which simulates the process of a brand new smartcard being manufactured in the bowels of the smartcard factory. Try it out, see how the [file] storing the memory changes (first byte should switch from 0x00 to 0x01 and back).
List of classes. The starter code is divided into 8 classes, summarized in the table below. The columns should be self-explanatory, except perhaps Usable by student code -- if this column is "no", you should not write any code which uses any methods from this class or any code which instantiates an instance of this class.
| Class name | Role | Edit | Classes used by | Usable by student code | Run from command line | Special Constraints |
|---|---|---|---|---|---|---|
| SmartCard | SmartCard protocol | Yes: execute() | InsertedSmartCard | No | No | N/A |
| Encoder | Encoder protocol | Yes: execute() | None | No | Yes | N/A |
| Machine | Machine protocol | Yes: execute() | None | No | Yes | N/A |
| CreateCard | Creates files that represent smartcard memory contents | Yes: initPersistentMemory() | None | No | Yes | N/A |
| EncoderSecrets | Stores encoder secrets | Yes: constants | Encoder, CreateCard | Yes | No | Constants only. Cannot be used in Machine or SmartCard |
| MachineSecrets | Stores machine secrets | Yes: constants | Machine, CreateCard | Yes | No | Constants only. Cannot be used in Encoder or SmartCard |
| PersistentMemory | Reads/writes SmartCard memory to files on your computer | No | CreateCard, SmartCard | Yes | No | N/A |
| InsertedSmartCard | Wrapper class for executing SmartCard class | No | Encoder, Machine | No | No | N/A |
The first three classes Encoder, Machine, SmartCard implement the protocol described above. The fourth class CreateCard simulates the process of creating SmartCards at the factory. EncoderSecrets and MachineSecrets may contain any constants you need for security, but the respective secrets can only be used by the respective device class and by CreateCard. You will use PersistentMemory in your SmartCard class to store/receive data in the smartcard's memory. InsertedSmartCard is a utility class that you will not use or edit.
Class details. The Encoder program's main function is invoked whenever an election worker inserts a smartcard into the encoder. Encoder takes one commandline argument, which is the name of a file containing (the persistent memory of) the smartcard that has been inserted into the encoder device.
The Encoder program does some initial setup steps in its main method, which you are not allowed to change. One of these steps is to launch a separate program that represents the inserted smartcard. These two programs run simultaneously, communicating via a serial connection, just as the real encoder would communicate with a real smartcard that is inserted into it.
Having set up an Encoder object, Encoder's main() method then calls the Encoder's execute() method, which does the main work of the encoder. This is what you will modify.
The voting machine program, called Machine, works similarly to the encoder. It takes one commandline argument (the name of a file containing a smartcard's persistent memory). It does some setup, which includes launching a program to represent the smartcard. Then it calls a method called execute, which does the main work of the voting machine and which you will modify.
The final program is the SmartCard program, which is invoked whenever a smartcard is inserted into a device. (By "device" we mean an encoder or a voting machine.) The SmartCard program does some initial setup steps, which we have provided and you may not modify. Then it calls the execute method, which you may modify. This procedure is invoked whenever the smartcard is inserted into another device. The smartcard runs until execute returns, or until the device ejects the smartcard, whichever comes first. Read the comments in SmartCard.java for more information.
The smartcard has a persistent memory, implemented in PersistentMemory.java. You may not modify PersistentMemory.java. The persistent memory is the only storage available to the smartcard which is preserved when the smartcard is not running.
Normally, you will not launch SmartCard directly. Instead, it will be launched automatically when you run Encoder or Machine.
The CreateCard program creates a new smartcard. Its job is to initialize the persistent memory of the new smartcard. When you invoke CreateCard, you give it a filename; CreateCard creates a new file with that name, and stores the smartcard's persistent memory in that file. You can have as many smartcards as you want -- there will be one file for each card, to hold the contents of that card's persistent memory.
We have provided working (but insecure) code for all of these programs. It's probably a good idea to read the code for these programs, and to run them after adding "hello world" code to the execute procedures, to get a better handle on how the pieces fit together.
The encoder and machine programs we have given you do not use any persistent storage (i.e. they have no persistent state). You can give them persistent storage if you want. If you do this, the persistent storage should be kept in a file, and of course one program's persistent storage should never by accessed by another program.
You may not use any crypto libraries except: PRF, TrueRandomness, or code from assignments 1, 2, or 3.
Assumptions
Assume that:- election workers are perfectly trustworthy, skilled, and diligent;
- there is one legitimate encoder and one legitimate voting machine, but many (potentially, a great many) legitimate smartcards;
- smartcards will not necessarily be inserted into the voting machine in the same order they were inserted into the encoder; in fact, some smartcards may never be inserted into the voting machine;
- the adversary can see all of your code, except for the two files EncoderSecrets.java and MachineSecrets.java;
- EncoderSecrets.java can be used by your Encoder program and your CreateCard program, but not by any other program,
- MachineSecrets.java can be used by your Machine program and your CreateCard program, but not by any other program,
- the adversary cannot read the persistent memory of any smartcard;
- the adversary can make his own smartcards that run any code he likes, and he can insert those cards into your devices whenever he wants
- the adversary can make his own devices that run any code he likes, and he can insert your smartcards or his own smartcards into his device(s) whenever he wants.
- the adversary cannot insert legitimate smart cards into the legitimate devices whenever he wants. Otherwise, he could obviously just sit there and vote all day. The adversary cannot do this because the poll worker is competent and won't let strangers use the encoder.
- the adversary CAN insert a bogus smart card into the real encoder and get it back. One way would be to collect a smartcard from the poll worker, and return a customzied smartcard to the poll worker. He could then have a confederate come in and recollect the customized smartcard. Assume this process could be repeated an arbitrary number of times. This clarification is just another way of saying "the adversary can make his own smartcards that run any code he likes, and he can insert those cards into your devices whenever he wants".
- the adversary cannot attach a device which passively eavesdrops on communications (using a smartcard shim).
- the adversary cannot build a wifi enabled smartcard that allows remote control of card behavior.
Assignment Tips and Tricks. This list will definitely grow in response to Piazza questions.
- Start by running the three command line programs (Encoder, Machine, CreateCard) to get a feeling for how they work. Feel free to add some print statements to the files in order to get a better feeling for the control flow (just don't forget to remove them).
- In Linux/OSX/Cygwin, you can use the command od -t x1 -N 5 [filename] to view the first 5 bytes of a file in hex.
- Make sure you understand the protocol used by the starter code.
- Make sure you understand how that protocol was translated to the starter code.
- Look at the table describing the classes and ensure that you understand which files you will be editing, and which classes are allowed to use which set of secrets.
- Design and discuss protocols with your group. Don't worry about coming up with a secure protocol right away! Start with simple embellishments on the protocol described in class, and understand why they are flawed -- this is a great exercise! One possible way to proceed is to have each member of the group come up with a few ideas.
- The amount of coding to be done will be somewhere in the neighborhood of assignment 2. Our reference solutions is 2697 bytes larger than the starter code (including whitespace characters).
- We will not answer broad questions like "Is my group's protocol secure?"
- When asking questions on Piazza, please be as specific as possible. Please mark posts which include details about your design as private.
- New: October 17: TrueRandomness is quite scarce in this assignment. To alleviate this issue, we have provided new instructor files here. In particular, these files contain a new class called SingletonPRGen, which contains a static PRGen seeded with TrueRandomness. Also, the new RSAKey class file has its static PRGen referencing the SingletonPRGen so as to avoid an exception caused by calling TrueRandomness multiple times. If you want to use random bits, you can seed your own PRGen using a call such as PRGen prg = SingletonPRGen.getPRGen(); See this Piazza post for more information.
Requirements
Your solution should allow voter cards to be enabled by inserting them into the encoder, and insertion of an enabled voter card into the voting machine should allow a vote to be cast and should disable the voter card. A disabled voter card should be able to be re-enabled by putting it into the encoder again, and so on.The adversary's goal is for the number of votes cast on the legitimate voting machine to exceed the number of times that a smartcard was inserted into the legitimate encoder.
Again, we reiterate all work should be within a single group. Cross-group collaboration -- including discussion of the merits/flaws of different protocol designs -- is not allowed.
Your Report
Your report should describe your solution, and justify why it prevents the adversary from achieving his goals while allowing votes to be cast properly in the absence of an adversary. Your report should be concise but should be as convincing as you can make it. The quality of your report will be a very important component of your grade, so pay at least as much attention to your report as to your code. Your report should be submitted in pdf or plaintext format.Logistics
You should submit any source code files that you were allowed to edit (see table above or the dropbox link) -- even if you did not edit them (e.g. if you do not use MachineSecrets, you must still submit a MachineSecrets file). You should also submit any additional class files that your program uses. For your README, if submitting in plaintext format, use the filename README.txt. If submitting in pdf format, use the filename README.pdf.
You must work in a group on this assignment. You may not collaborate with anyone outside your group [clarification!]
You can submit your code using this link.
Copyright 2000-2012, Edward W. Felten.