CSCI 6268 - Foundations of Computer and Network Security - Fall 2002

Assignment #2

Due: Oct 1st, 2002 at 10am MDT


1. Show that for any group G with |G| > 2, every element a in G can be written as (b * c) where neither b nor c equals a. (Note: We are not talking about any particular type of group here... prove the statement for any group.)

2. In class we saw the MMO construction which made a cryptographic hash function from a block cipher. Consider the following similar construction on some n-bit block cipher E, called the BHF construction: as usual, write M as t blocks of n-bits each. So M=M1M2...Mt. Then h0 = 0n, and hi = Emi xor h i-1 (mi xor hi-1) xor mi. Finally, H(M) = ht. Show that the BHF construction is not collision-resistant independent of the block cipher.

3. We briefly learned about formal cryptography in class, and defined what IND$-CPA meant, intuitively; we now discuss this a little further.

A "deterministic" encryption mode is a mode where repeating the encryption of the same plaintext twice yields the same ciphertext. A "randomized" encryption mode is a mode where you encrypt message M twice and you almost always get two different ciphertexts.

  1. Is CTR a randomized or deterministic encryption mode?
  2. Is ECB a randomized or deterministic encryption mode?
  3. Is CBC a randomized or deterministic encryption mode?
  4. Is it possible for any deterministic encryption mode to be IND$-CPA? Why or why not?

4. We said in lecture that CBC with a random IV was IND$-CPA. I also mentioned that if we instead used a counter for the IV with CBC mode, then it was not IND$-CPA. Please demonstrate a chosen-plaintext attack to prove my point.

(To clarify the mode: for the first message, the IV=0 (as an n-bit string), then for the second message the IV=1, then IV=2, etc. The IV increments for each message rather than being randomly-chosen.)

5. (Hard) Here is another challenging problem, similar to number 5 on the last homework. Once again, do not attempt to work on this unless you have finished the preceeding 4 problems and have a good number of hours to work on it. (This one isn't as hard as the last one, but it's a bit of work still.)

We know how to build a cryptographic hash function from a block cipher using the MMO construction. And if we have such a hash function with an n-bit output, we can always obtain a new hash function with p bits in its output, p < n, simply by chopping off the last n-p bits. Here is your task:

  1. Obtain the Rijndael (aka AES) code off the web; it's freely available in C or Java or assembly language (for certain platforms).
  2. Implement a hash function with a 60-bit output by using MMO with AES and chopping off the last 68 bits.
  3. Find a collision in this hash function.

Notes:

  1. You probably don't have to implement the full MMO hash function: there are more than enough one-block queries to generate a collision.
  2. As we know, we expect a collision after about 230 hash queries. That's not a lot for the NSA, but it's a lot for us. You'll have to be judicious in your use of memory and disk to store intermediate results.
  3. Think deeply about which data structures to use for this task. Also, be careful and don't overwhelm any CS machines with runaway code, infinite loops, infinite forking programs, etc. And using multiple gigs of disk on a CS machine will get you in trouble, I'll bet. Try to use your home PC (if you have one).
  4. There are ways to use less memory at the expense of using a little more CPU time. Think about this.
  5. You MUST document your methods to get credit for this project. Simply handing in a pair of inputs which form a collision will not get many points. Proper documentation includes what choices you made and why you made them, along with source code used for this problem.