Gs2745 Unit 2 Assignment 1 Cryptography

On By In 1

Assignment 1 - Cryptography

Due date:

This assignment has threen parts that each account for one third of the total grade. In this assignment you will build code to implement a secure facility for client-server communication across the Internet. You should work on this assignment by yourself and we strongly recommend that you get started early.

Part I

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 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 to implement a pseudo-random generator class. You will modify to implement a stream cipher. You will modify and 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 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 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, 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 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 .

If the nonce is included in the message, then the message should be decrypted with . Otherwise, the nonce should be provided along with the ciphertext to .

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 determinstically generate pseudorandom values. See the comments in 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.
  • 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 75, 61, 66, and 76 lines of code (the whole file, including everything, even comments, whitespace, brackets, etc.) for , , , and respectively.

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 only submit 4 files: , , , and . You may submit any number of times. Only your most recent submission will be graded. Submit your code using this link.


Part II

In this part, you'll add functionality to the code you wrote for part 1, toward the goal of implementing a secure facility for client-server communication across the Internet.

As before, 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. Create a fresh directory and unzip the downloaded code into it. Then copy into that same directory all of the files from your solution to part 1. As before, you must not use any crypto libraries; the only primitives you may use are the ones we gave you, and ones you implemented from scratch yourself.

In this part you will implement three facilities, by modifying three Java code files. You will modify to generate an RSA key-pair. You will modify to implement secure RSA encryption and decryption, and to create and verify digital signatures. You will modify to implement a secure key exchange. As in the previous assignment, we have provided you with code files 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.

Although your solution may call on code that you wrote for part 1, your solution to this homework should not rely on any specific properties of your part 1 code. We will test your solution with our own implementation of the part 1 functionality. Your solution must work correctly when we do this --- this shouldn't be a problem as long as you respect the API boundaries between the different classes we have given you.

RSAKeyPair. Your RSAKeyPair class should implement the following API:

public class RSAKeyPair { public RSAKeyPair(PRGen rand, int numBits) public RSAKey getPublicKey() //already implemented public RSAKey getPrivateKey() //already implemented public BigInteger[] getPrimes() }

For , the bulk of the interesting work is performed by the constructor. This constuctor should create an RSA key pair using the algorithm discussed in class. The constructor will use the PRGen called to get pseudorandom bits. numBits is the size in bits of each of the primes that will be used. The key pair should be stored as a pair of objects.

is a method we've added in order to help us with the grading process. getPrimes() should return the two primes that were used in key generation. Typically, you would not explicitly have a method to return these primes. The primes may be returned in either order.

RSAKey. Your RSAKey class should implement the following API:

public class RSAKey { public RSAKey(BigInteger theExponent, BigInteger theModulus) // already implemented public BigInteger getExponent() // already implemented public BigInteger getModulus() // already implemented public byte[] encrypt(byte[] plaintext, PRGen prgen) public byte[] decrypt(byte[] ciphertext) public byte[] sign(byte[] message, PRGen prgen) public boolean verifySignature(byte[] message, byte[] signature) public int maxPlaintextLength() public byte[] encodeOaep(byte[] input, PRGen prgen) public byte[] decodeOaep(byte[] input) public byte[] addPadding(byte[] input) public byte[] removePadding(byte[] input)

The class implements core RSA functions, namely encrypting/decryption as well as signing/verification. Note that the class is used for both public and private keys, even though some key/method combinations are unlikely to be used in practice. For example, it is unlikely that the method of a public would ever be used.

The method should encrypt the plaintext using optimal asymmetric encryption padding (OAEP) as discussed in class. It is not enough to simply exponentiate and mod the plaintext. , , and take a PRGen parameter, in case the implementation wants to use some pseudorandom bits. The method should be able to decrypt the ciphertext.

Your code for OAEP encoding and decoding should be in the provided and methods. Your other methods should call these utility methods to encode/decode when necessary. For full credit, don't forget to pad the input to the OAEP algorithm if it is too short -- this is necessary to guarantee security (otherwise the exponentiated message might be smaller than the modulus).

The method should generate a signature (array of bytes) that can be verified by the method of the other in the private/public pair. You should not include the entire message as part of the signature; assume that the verifier will already have access to this message. This assumption of access is reflected in the API for , which accepts the message as one of its arguments.

The method should be used by a public object to verify a signature generated by the corresponding private 's method.

The method should return the largest N such that any plaintext of size N bytes can be encrypted with this key and padding scheme. Your code must correctly operate on plaintexts that are any size less than or equal to the size returned by .

The and methods are used to pad the input to the OAEP algorithm if it is too short. You should not call these methods from within encodeOAEP()/decodeOAEP(). See below for more information on this.

KeyExchange. Your KeyExchange class should implement the following API:

public class KeyExchange { public static final int OUTPUT_SIZE_BYTES public static final int OUTPUT_SIZE_BITS public KeyExchange(PRGen rand, boolean iAmServer) public byte[] prepareOutMessage() public byte[] processInMessage(byte[] inMessage) }

The constructor should prepare to do a key exchange. is a secure pseudorandom generator that can be used by the implementation. is true if and only if we are playing the server role in this exchange. Each exchange has two participants; one of them plays the client role and the other plays the server role.

Once the object is created, two things have to happen for the key exchange process to be complete:

  1. Call prepareOutMessage on this object, and send the result to the other participant.
  2. Receive the result of the other participant's prepareOutMessage, and pass it in as the argument to a call on this object's processInMessage.
These two things can happen in either order, or even concurrently (e.g., in different threads). This code must work correctly regardless of the order.

The call to processInMessage should behave as follows:

  • If passed a null value, then throw a NullPointerException.
  • Otherwise, if passed a value that could not possibly have been generated by prepareOutMessage, then return null.
  • Otherwise, return a "digest" (hash) value with length and the property described below.

Your KeyExchange class must provide the following security guarantee: If the two participants end up with the same non-null digest value, then this digest value is not known to anyone else. This must be true even if third parties can observe and modify the messages sent between the participants.

This code is NOT required to check whether the two participants end up with the same digest value; the code calling this must verify that property.

Assignment Tips and Tricks.

  • Start with . While it is true that it contains instances of , does not use any of the methods that you'll be implementing in .
  • As in part 1, the spec is deliberately vague regarding how you should accomplish each task. There is a significant design component to each problem.
  • Make sure to run your code with the java -ea flag, so that assertions are enabled.
  • Use BigInteger:
    • Since you'll be doing math with very large integers, you'll probably want to use the library class for any such operations. This class provides myriad functions that you may find useful for this assignment, particularly as BigInteger was originally designed with RSA implementation in mind. (Using doesn't violate our rule against using external crypto primitives, because provides basic mathematical functions, and not crypto.)
    • If you find yourself writing complex functions involving BigIntegers (e.g. manually testing primality, manually generating primes, manually finding the gcd of two numbers, manually finding d given p, q, and e, etc.), you're doing way more work than you need to. Find the appropriate BigInteger method.
    • One particularly useful BigInteger function is modPow().
    • Converting back and forth between BigIntegers and byte[] arrays is a major hassle. It's surprisingly hard to get this code right. We have given you code, in the HW2Util.java file, that can do this.
    • For maximum elegance in RSAKey, your message should only be in BigInteger format for the purposes of exponentiating and modulusing. In other words, when you're applying OAEP, padding, unOAEP, etc., it's much easier to deal with your input in terms of byte[].
  • In class, we said that given public and private keys (d, N) and (e, N), we have that x = (x^(de) mod N), iff 0 < x < N. Thus, if you're going to use the built in BigInteger functions to encrypt and decrypt, it is important that you represent your input message as a positive BigInteger.
  • An RSAKey object does not know if it is "private" or "public". Indeed, it is even possible to sign messages using a public key or encrypt using a private key, though neither of these strange operations are likely to be useful in pratice.
  • We recommend that first you get your code working for the case where all inputs are full sized, then modify your code so that it handles padding. When you implement padding, the relevant code should be in the provided and methods. Your other methods should call these utility methods to pad/unpad when necessary.
  • There is a bit more programming this week. Our reference solutions are 45, 151, and 84 lines of code (including everything, even comments, whitespace, brackets, etc.) for , , and respectively.
  • If your think that your solution to part 1 is flawed, you will want to correct these mistakes before testing your implementation of part 2. Alternatively, you can use a precompiled version of our sample solution for part 1, which you can get here after the submission deadline for part 1.

Submitting your solution. You should only submit 3 files: , , and . Please cite any sources you used when developing your code. You may submit any number of times. Only your most recent submission will be graded. Submit your code using this link.

Part III

In this assignment, you'll add functionality to the code you wrote for Homeworks 1 and 2, to reach the goal of implementing a secure facility for client-server communication across the Internet.

As before, 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. Create a fresh directory and unzip the downloaded code into it. Then copy into that same directory all of the files from your solutions to Homeworks 1 and 2. As before, you must not use any crypto libraries; the only primitives you may use are the ones we gave you, and ones you implemented from scratch yourself. If you'd like to use our reference solutions for part 1 and 2, you may download them here after the submission deadline of part 2. Note that this library does not contain source code.

In this assignment you will implement a secure channel abstraction that can be used by two programs, a client and a server, to communicate across the network, with the confidentiality and integrity of messages guaranteed. We have given you a class which implements a channel that works but is not secure: everything is sent in unprotected cleartext. We have also given you stubbed-out code for a class that extends and (once you have modified it) will protect security and confidentiality.

To facilitate the testing process, we have provided a few test files. The first is Util432s.java, which provides a few methods used by the other testing files (feel free to use these methods for debugging). The second is ChannelTest.java, which provides a demonstration that the InsecureChannel class works correctly. The third is SecureChannelTest, which you can use to test your SecureChannel class (once implemented). Note that this class does NOT test security properties, instead testing only basic functionality. Note the commented out lines which give an example of how you can Util432s for debugging. The fourth is InsecureChannelDebug, which is a special version of InsecureChannel which provides the ability to echo channel transmissions to the screen. To use this class, simply rename the file "InsecureChannel.java" and place it in the same directory as SecureChannel.java.

Although your solution will call on code that you wrote for Homeworks 1 and 2, we will test your solution with our own implementation of the Homework 1 and 2 functionality. Your solution must work correctly when we do this --- this shouldn't be a problem for you as long as you respect the API requirements of the previous assignments.

IMPORTANT: For this assignment, we will also REQUIRE a README file. In the file, you should describe your setup and your threat model: What are you doing? How would a user of the classes you've written use them? And what security properties (against what sort of adversary) should they expect to get if they use them correctly? This should be in addition to any documentation you would normally put in comments or a README.

We're not looking for War and Peace in this (i.e. it doesn't need to be very long). Rather, you should provide a clean and clear description of your security goals and how they are achieved in a few paragraphs at most.

SecureChannel. Your SecureChannel class should implement the following API:

public class SecureChannel extends InsecureChannel { public SecureChannel(InputStream inStr, OutputStream outStr, PRGen rand, boolean iAmServer, RSAKey serverKey) throws IOException public void sendMessage(byte[] message) throws IOException public byte[] receiveMessage() throws IOException }

The constructor will contain the vast majority of your code. Its role is to set up the secure channel such that the sendMessage and receiveMessage methods can do their jobs. These methods should provide authenticated encryption for the messages that pass over the channel, ensuring that messages arrive at the receiving end in the same order that they were send on the sending end. Furthermore, when the client is setting up its channel, it should also authenticate the server's identity, and should take whatever steps are necessary to detect any man-in-the-middle. If one of the two parties (server or client) detects a potential security problem during channel construction, that party should close the channel by calling close(). You can assume the serverKey (public key) passed to the constructor of SecureChannel on the client side of the communication is verified externally in some way (for example via a trusted certificate).

The underlying InsecureChannel will normally deliver messages in the same order they were sent. But note that an adversary might try to reorder messages. should return null if an invalid or out-of-order message shows up.

Assignment Tips and Tricks. This list will definitely grow in response to Piazza questions.

  • Start by looking at ChannelTest.java, which will provide you with a better understanding of how InsecureChannel (and SecureChannel) are intended to be used. In particular, two instances of InsecureChannel will be created (one for the server->client channel and one for the client->server channel), each of which connects up two data streams (one input and one output data stream). Messages are sent through the channel using the sendMessage() method, and whenever a message is sent via a channel, it stays there until a corresponding receiveMessage() call is made. Luckily for you, you won't need to think about InputStreams or OutputStreams at all. That is all taken of in InscureChannel.java and in the main function of the ChannelTests.
  • If you're unfamiliar with InputStreams and OutputStreams, don't worry, you won't be dealing with them very closely. Same goes for Runnable classes and Threads.
  • Another thing you might try is copying InsecureChannelDebug over InsecureChannel and running ChannelTest, which will let you see the raw traffic being sent over the channel.
  • From there, look at SecureChannelTest.java to get a feeling for how the SecureChannel instantiations differ.
  • From here, you should design a threat model. Carefully consider everything that your adversary is trying to do that you'd like to prevent.
  • Once you feel comfortable with your threat model, consider what tools you have available from HW1 and HW2. Your design should be modular, where specific classes solve specific subtasks. Sketch everything out schematically and try to find ways to compromise the security of your design. Perhaps the best way to do this is to start your design early, sleep on it, and then come back later to analyze it from a perspective that has been freshened by sleep.
  • Once you feel comfortable with your overall design, implement and test.
  • For reference, our solution is a mere 87 lines of code. Unlike part 1 and 2, you should not run into any programming challenges while writing SecureChannel (though writing additional tests beyond ChannelTest might be tough). Your code should be very straightforward and easy to code up from your design.
  • In SecureChannelTest, if a thread calls "readMessage" and there is no message available, it will wait until a message becomes available.
Submitting your solution: You should only submit and using this link.


Copyright 1998-2014, Edward W. Felten.

1. This is the following algorithms I would recommendations for Shovels and Shingles email concerns:  Secure Sockets Layer (SSL)  Diffie-Hellman key exchange  Rivest, Shamir, and Adleman (RSA) encryption algorithm The reasoning for this is that the RSA algorithm is considered the most common public key encryption algorithm that can be used for either digital signatures or for encryption. The Diffie-Hellman key exchange is not implemented on hardware but used for emails and Secure Sockets Layer (SSL) offers secure communication between the client and the server. 2. This is what I would recommend for Top Ads encryption methods:  Digital Signature  Advanced Encryption Standard (AES)  Elliptic curve cryptography (ECC) The Digital Signature and Advanced Encryption Standard (AES), Digital Signatures are fairly efficient in the use of SHA-1 hash function to compute message digests, and AES is

0 comments

Leave a Reply

Your email address will not be published. Required fields are marked *