Project 1 — Symmetric Crypto

Due Monday, October 16 at 6pm

This is the first in a series of three short assignments in which you will build code to implement a secure facility for client-server communication across the Internet.

We will give you some of the code you need, and we'll ask you to implement certain functions missing from the code we provide via chisubmit. We are giving you two fully-implemented code files, on which you should build all of the crypto functionality you need to do this assignment. The file PRF.java gives you access to a pseudorandom function, as described in lecture. The file TrueRandomness.java gives you access to truly random bits which have been extracted from the unpredictable state of the local system, but it can only be used once. It might be useful for testing purposes, but you should not need it to implement your crypto functionality. These are the only two crypto primitives you are allowed to use—any other crypto you use must be built (by you) on top of these two files. You may not use any other crypto libraries, not even the ones that are part of the standard Java libraries.

In this assignment you will implement three facilities by modifying four Java code files. You will modify PRGen.java to implement a pseudo-random generator class. You will modify StreamCipher.java to implement a stream cipher. You will modify AuthEncryptor.java and AuthDecryptor.java to implement a facility for authenticated encryption and decryption. In each case, we have provided you with a code file in which some parts of "stubbed out". You will replace the stubbed out pieces with code that actually works and provides the required security guarantee. We have put a comment saying "IMPLEMENT THIS" everywhere that you have to supply code. You may add extra functions to the classes as you see fit (although you shouldn't need to), but please do not change the inputs or outputs of any of the existing functions. In addition, if you do add an extra function to a class, do not call it from another class. Doing so will disrupt our grading scripts (We test each class individually).

The file Proj1Constants.java specifies that sizes of the keys and nonces that you should use in this assignment as well as the size of the PRF's output. You may not modify this file, and your crypto functionality must adhere to these sizes.

We will be testing your code with Java 8, and so please use that version when compiling and running your implementation. You can check your Java version by typing javac -version and verifying that the version begins with 1.8.0_. (If you only have the java command but not the javac command, you have the Java runtime, but you need to install the Java Development Kit.) You can download the Java Development Kit here.

PRGen. Your PRGen class should extend Java's built-in java.util.Random class and implement the following API:

public class PRGen extends Random {
    public PRGen(byte[] seed)      //creates a new PRGen
    protected int next(int bits)  //generates the next pseudorandom number
}

The next method of your PRGen will override the corresponding method in the parent Random class. You do not need to override any other of methods of Random. (Hint: Nevertheless, your PRGen will inherit all of the other methods of Random, including nextBytes. You can use them because they are implemented using next which you will have overridden.) You may not use Java's SecureRandom class.

As stated in the Random spec "The general contract of next is that it returns an int value and if the argument bits is between 1 and 32 (inclusive), then that many low-order bits of the returned value will be (approximately) independently chosen bit values, each of which is (approximately) equally likely to be 0 or 1." For example, if you call next(4), it will return an int between 0 and 15. If you call next(32), it will return an int between -2,147,483,648 and 2,147,483,647 (the highest order bit determines the sign).

Your PRGen must obey the following three properties:

It must be pseudorandom, meaning that there is no (known) way to distinguish its output from that of a truly random generator, unless you know the key.
It must be deterministic, meaning that if two programs create generators with the same seed, and then the two programs make the same sequence of calls to their generators, they should receive the same return values from all of those calls.
It must be backtracking-resistant, meaning that if an adversary is able to observe the full state of the generator at some point in time, that adversary cannot reconstruct any of the output that was produced by previous calls to the generator. Note that the next function in java.util.Random is not backtracking-resistant.

StreamCipher. Your StreamCipher class should implement the following API:

public class StreamCipher {
    public StreamCipher(byte[] key)
    public void setNonce(byte[] nonce, int offset)
    public void setNonce(byte[] nonce)
    public byte cryptByte(byte in)                          //encrypts the next byte
    public void cryptBytes(byte[] inBuf, int inOffset,      //encrypts next numBytes
               byte[] outBuf, int outOffset,                //in the inBuf, writing
               int numBytes)                                //results to the outBuf
}

This class encrypts or decrypts a stream of bytes, using a stream cipher. (Recall that for a stream cipher, encryption and decryption are the same operation.)

AuthEncryptor. Your AuthEncryptor class should implement the following API:

public class AuthEncryptor {
    public AuthEncryptor(byte[] key)       
    public byte[] encrypt(byte[] in, byte[] nonce, boolean nonceInMessage)
}

This class is used to perform authenticated encryption on values. Authenticated encryption protects the confidentiality of a value, so that the only way to recover the initial value is to decrypt the value using the same key and nonce that was used to encrypt it. At the same time, authenticated encryption protects the integrity of a value, so that a party decrypting the value using the same key and nonce (that were used to encrypt it) can verify that nobody has tampered with the value since it was encrypted.

Code that uses AuthEncryptor will be required to pass in a different nonce for every call to encrypt. The AuthEncryptor class is not required to detect violations of this rule; it is the responsibility of the code that uses AuthEncryptor to avoid re-using a nonce with the same AuthEncryptor instance.

If nonceInMessage is true, then the nonce should be included (in plaintext form) in the output of encrypt. If nonceInMessage is false, then the nonce should still be used in calculating the output, but the nonce itself should not be copied into the output. (Presumably the party who will decrypt the message already knows what the nonce will be.)

AuthDecryptor. Your AuthDecryptor class should implement the following API:

public class AuthDecryptor {
    public AuthDecryptor(byte[] key)       
    public byte[] decrypt(byte[] in, byte[] nonce, boolean nonceInMessage)     
}

The value passed as in will normally have been created by calling encrypt with the same nonce in an AuthEncryptor that was initialized with the same key as this AuthDecryptor.

If the integrity of the input value cannot be verified (that is, if the input value could not have been created by calling encrypt with the same nonce in an AuthEncryptor that was initialized with the same key as this AuthDecryptor), then this method returns null. Otherwise it returns a newly allocated byte-array containing the plaintext value that was originally passed to encrypt .

If nonceInMessage is true, then the nonce will be included in the in array, and the value passed in as nonce should be disregarded. If nonceInMessage is false, then the nonce is not included in the in array, so the value passed in a nonce should be used.

Tips for Getting Started. This list may grow in response to Piazza questions.

Make sure you understand what a PRF is, and how you can use the PRF class to deterministically generate pseudorandom values. See PRF.main for examples.
You don't have to use every bit generated by your PRF.
The spec is deliberately vague regarding how you should accomplish each task. There is a significant design component to each problem.
You may encounter situations in which the specified key sizes are too short for what you need. This is not a mistake in the assignment. It's up to you to figure out how to solve this problem securely.
The bulk of the work for this assignment will be in the design, not the implementation. It shouldn't take many additional lines of code to complete the classes. Our reference solutions are less than 100 lines of code for each class including whitespace and comments.

Advice on testing crypto code. As always, it's important to test your code. But you should be aware that crypto code presents different testing issues than other code does. Testing can sanity-check your code, but it can't verify that your code has the desired security properties. For example, if your code is encrypting data for confidentiality, you can test whether the ciphertext is the right size, and you can test whether the ciphertext looks kind of random-ish, and you can test whether different plaintexts yield different ciphertexts. But you can't test whether there is a way for an adversary to recover the plaintext. So by all means test your code — if you don't, it's almost certain not to work—but remember that passing the tests is not enough.

A few words about grading. Some of your grade will be based on whether your code passes certain automated tests. But, as stated previously, the security of your implementation ultimately depends on its design and cannot be verified by testing alone. An implementation that compiles, runs, and appears to work may in fact be insecure. As a result, manual inspection of your design will determine a large part of your grade.