Information Security

Homework: 1 2 3 4 5 6 7

Assignment 1: Storing Votes Securely

Introduction

Diebold voting machines store the record of cast votes in a file called a vote result file. The files are stored in an encrypted format that is supposed to prevent an observer who doesn't know the secret encryption key(s) from (a) reading the votes, or (b) modifying the votes without detection.

Unfortunately, Diebold's encrypted file format is misdesigned and does not provide the required guarantees. Your job is to design a file format that is secure, and write programs to write and read that format.

Assumptions

The voting machine has a removable memory card that stores ordinary files. The votes cast on the machine are stored in a file on the memory card. After the election ends, the memory card is removed from the machine and transported to the county clerk's office by a police officer. There the votes are inserted into the tabulator, a computer that reads the file off the memory card and adds the votes into its county-wide totals which will eventualyl determine the final result of the election.

The poll workers and police officers who handle the memory cards are probably trustworthy, but we do not want them to be able to compromise the election's integrity or the secrecy of the votes. Just to be safe, our threat model will assume that a malicious person can get access to the memory card at any time.

The Software

You will write two programs, createFile and tabulator.

createFile reads in a sequence of votes (represented as integers between 0 and 1,000,000,000 inclusive) from standard input and emits a sequence of bytes on its standard output. These bytes are the secure vote file that is written to the memory card.

tabulator receives a secure vote file on its standard input, and emits a sequence of integer votes (one per line) on its standard output. However, if an adversary has tampered with the secure vote file, tabulator should exit with an error (by failing an assertion or calling exit() with a nonzero argument).

If votes.in is a file containing a sequence of integers, one per line, then the output of the shell command cat votes.in | createFile | tabulator should be the same as votes.in. We are providing a starting point that you must use. It contains programs that work, except that they are totally insecure. It also contains code for a pseudorandom function.

In accordance with good cryptographic practice, you should assume that the adversary can read all of your code, except for a single file called secretKey.h, which may declare variables and set their values but may not contain code or macros. This file represents a secret key that is preprogrammed into the voting machine and the tabulator.

Threat Model

The adversary "wins" if he can do any one of these things:

learn the contents of any vote,
modify a vote without the tabulator noticing the modification,
add one or more votes without the tabulator noticing the change, or
remove one or more votes without the tabulator noticing the change.

You should make the following assumptions:

The adversary can read all of your source code, except the secretKey.h file.
The adversary can observe and/or modify the output of createFile before it is fed to tabulator.

Note that the tabulator need not recover from vote tampering, vote insertion, or vote removal. It is enough to detect that something is wrong and raise an alarm.

Your Report

Your report should describe your solution, and justify why it prevents the adversary from achieving any of his goals. 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.

Logistics

Your solution should be a zip-file containing your source code (including any provided files that you did not modify), a Makefile, and a report that describes what you did and why. The report should be an HTML file named index.html. (It may contain links to other files, if you include those files in your submission.)

When we unzip your submission into a directory and type "Make" there, it should build two programs that we can execute by typing "createFile" and "tabulator", which operate as described above.

You must work by yourself on this assignment. You may not collaborate with anybody else.