Homework 1 - Crypto I

Due at 11:00am, Monday, September 22

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 provide certain functions missing from the code we provide. You can download the code we are providing.

We are giving you one fully implemented code file, 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 pseudo-random function, as described in lecture. This is the only crypto primitive you are allowed to use---any other crypto you use must be built (by you) on top of this file. Specifically, 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 are "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.

PRGen.Your PRGen class should implement the following API:

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

You do not need to implement any other methods of the Random class. The long key that is used by the parent Random class will not be used by your PRGen 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:

StreamCipher.Your StreamCipher class should implement the following API:

public class StreamCipher {
    public StreamCipher(byte[] key, byte[] nonceArr, int nonceOffset)
    public StreamCipher(byte[] key, 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 includeNonce)

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 includeNonce is true, then the nonce should be included (in plaintext form) in the output of encrypt. If includeNonce 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)       
    public byte[] decrypt(byte[] in, byte[] nonce)     

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 the nonce is included in the message, then the message should be decrypted with decrypt(byte[] in). Otherwise, the nonce should be provided along with the ciphertext to decrypt(byte[] in, byte[] nonce).

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

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 randomish, 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.

Submitting your solution. You should submit any code files that you modified or created. You don't need to submit any files that you did not modify. You may submit any number of times. Only your most recent submission will be graded. Submit your code using this link.

Copyright 1998-2014, Edward W. Felten.