A printable PDF is available.
Note: You are strongly encouraged to use the PDF version linked above. The formatting is much better than the version shown below.
Assignment 4 - Due Wednesday, April 2
A "key recovery attack" takes a matching plaintext/ciphertext pair (P,C) and finds a key K such that EK(P)=C. We can formalize this by saying that there is a probabilistic polynomial time algorithm findkey(P,C) that computes K. Show that if such a function exists, then the encryption scheme is not IND-CPA secure (to do this, define the adversary functions A1E and A2E for the chosen-plaintext game, where the adversary functions can call both the encryption oracle and the findkey function). In addition to giving the algorithms, analyze the advantage of your adversary algorithm under the assumption that findkey always succeeds.
In the handout on security models, it was shown that no stateless, deterministic encryption can be IND-CPA secure. For this problem, consider CBC mode in which the IV is picked in a way that can be predicted by the adversary (but may be stateful and/or non-deterministic).
(a) Describe CBC mode using algorithm specifications (both encryption and decryption), where the IV is selected during encryption using a function named getIV(lambda). You need to give names to both full CBC as well as individual block cipher encryption/decryption functions.
(b) Assume the adversary has a predictIV() function that always predicts the next IV that will be returned by getIV(lambda) (and hence the next IV that will be used in an encryption). Define adversary algorithms A1E and A2E that can win the CPA game. (Hint: Think about what is fed into the block cipher as plaintext. Can you arrange it so that you can do multiple encryptions in which the same values are fed into the block cipher?) Do a quick analysis of your algorithms to find the advantage of your adversary.
(c) What if the predictIV algorithm isn't perfect? In other words, what if predictIV only predicts the correct IV with probability p? What is the advantage now?
(d) CBC-Chain mode is a variant of CBC mode in which the encryption function keeps a record of the last ciphertext block produced, and uses that as the IV for the next encryption (so a series of CBC-Chain encryptions is the same as a single long CBC encryption). Show that CBC-Chain mode is not IND-CPA secure. (Note: This attack appears in the real world as part of the basis for the BEAST attack on SSL, discovered in 2011.)
It's clear that repeating a deterministic block cipher, as in ECB mode, is not secure. But what about repeating a secure (non-deterministic) cipher? In other words, let EK(P) -> C be an IND-CCA encryption scheme, and then define a two-block version of this by E2K(P1,P2) -> (C1,C2)=(EK(P1),EK(P2)). It turns out that this construction is IND-CPA secure, but not IND-CCA secure. Prove the second part of that statement (in other words, give an adversary that wins the CCA game against the E2 two-block encryption scheme -- like almost all CCA attacks, the trick is to disguise your decryption oracle requests so they don't exactly repeat the challenge ciphertext). Make sure you analyze the advantage of your adversary!
(Note: Taking large modular powers is tricky, but modern programming languages have good support for this -- for example, in Java you can use the modPow function in the BigInteger class, and in Python you can use the built-in pow function, where pow(a,x,n) computes axmod n.) Consider the value n=8911 (this is a composite number with factors 7, 19, and 67).
(a) Select three different random a values in the range 2,...,8909 that are relatively prime to n, and calculate an-1mod n for each of these three a values. Does it seem that n behaves like a prime number as far as Fermat's Little Theorem is concerned?
(b) Use your random a values from part (a) to run the Miller-Rabin primality-testing algorithm on n, showing each step. If your first a value returns "composite" you can stop with just that one simulation -- otherwise, try the other a values until you get "composite."
Use Table 8.1 on page 235 to pick two random primes (p and q) in the range 1500,...,2000. Compute n=pq and phi(n). Pick a random a in the range 2,...,n-1 such that it is relatively prime to n. Compute b=aphi(n)-1mod n. Finally, compute the product a·bmod n. What does this tell you about the relation between a and b? Will this relationship always hold for any values that you pick according to these directions? Justify your answer.
What are the primitive roots of 31? (A very simple program can quickly solve this problem.)
Understanding the density of prime numbers is important for reasoning about lots of things in cryptography. The basis for this question is the "Prime Number Theorem," which states that the number of prime numbers less than or equal to n (written pi(n)) is approximately equal to (x)/(lnx).
(a) Estimate the number of 512-bit prime numbers (here, "512-bit" means with no leading zeroes, so a number x is 512 bits if 2511 <= x<2512).
(b) The RSA cryptosystem uses a modulus that is the product of two large prime numbers, and if you could factor the modulus you could break the system. Sometimes when people hear this, they think that if the modulus is restricted to be the product of 512-bit prime numbers then they can make a table of all 512-bit prime numbers and use that table to factor the modulus. Is that reasonable? How big would such a table be? What is the size of the largest hard drive that you can buy today? See if you can estimate the total amount of disk storage that has ever been manufactured in the history of mankind. How does that compare to the size required for such a table?
(c) When picking a random prime number, a typical algorithm will pick a random odd integer, use the Miller-Rabin primality testing algorithm to see if it's prime, and if it's not prime start over by picking a different random odd integer. How many iterations would you expect this to take if you wanted to pick a random 512-bit prime number? Hint: This is the scenario that is sketched at the end of Section 8.3, but with a different size (200 bits rather than 512 bits). For this part, adjust the reasoning to 512 bits, and be a little more formal and careful in the analysis, using your result from part (a).
(d) Picking a random odd number to start is really just a way of saying we are excluding multiples of 2. We can quickly test and adjust a random number so that it is not a multiple of other small primes as well. Redo part (c) where when we pick a random number we ensure that it is not a multiple of 2, 3, 5, 7, 11, or 13 before running Miller-Rabin. How many iterations (in other words, how many Miller-Rabin tests) are expected now?