12.8 Exercises – Introduction to Cryptography with Coding Theory, 3rd Edition

12.8 Exercises

  1. In a family of four, what is the probability that no two people have birthdays in the same month? (Assume that all months have equal probabilities.)

  2. Each person in the world flips 100 coins and obtains a sequence of length 100 consisting of Heads and Tails. (There are 21001030 possible sequences.) Assume that there are approximately 1010 people in the world. What is the probability that two people obtain the same sequence of Heads and Tails? Your answer should be accurate to at least two decimal places.

    1. Let EK be an encryption function with N possible keys K, N possible plaintexts, and N possible ciphertexts. Assume that if you know the encryption key K, then it is easy to find the decryption function DK (therefore, this problem does not apply to public key methods). Suppose that, for each pair (K1, K2) of keys, it is possible to find a key K3 such that EK1(EK2(m))=EK3(m) for all plaintexts m. Assume also that for every plaintext–ciphertext pair (m, c), there is usually only one key K such that EK(m)=c. Suppose that you know a plaintext–ciphertext pair (m, c). Give a birthday attack that usually finds the key K in approximately 2N steps. (Remark: This is much faster than brute force searching through all keys K, which takes time proportional to N.)

    2. Show that the shift cipher (see Section 2.1) satisfies the conditions of part (a), and explain how to attack the shift cipher mod 26 using two lists of length 6. (Of course, you could also find the key by simply subtracting the plaintext from the ciphertext; therefore, the point of this part of the problem is to illustrate part (a).)

  3. Alice uses double encryption with a block cipher to send messages to Bob, so c=EK1(EK2(m)) gives the encryption. Eve obtains a plaintext–ciphertext pair (m, c) and wants to find K1, K2 by the Birthday Attack. Suppose that the output of EK has N bits. Eve computes two lists:

    1. EK(m) for 32N/2 randomly chosen keys K.

    2. DL(c) for 32N/2 randomly chosen keys L.

      1. Why is there a very good chance that Eve finds a key pair (L, K) such that c=EL(EK(m)) ?

      2. Why is it unlikely that (L, K) is the correct key pair? (Hint: Look at the analysis of the Meet-in-the-Middle Attack in Section 6.5.)

      3. What is the difference between the Meet-in-the-Middle Attack and what Eve does in this problem?

  4. Each person who has ever lived on earth receives a deck of 52 cards and thoroughly shuffles it. What is the probability that two people have the cards in the same order? It is estimated that around 1.08×1011 people have ever lived on earth. The number of shuffles of 52 cards is 52!8×1067.

  5. Let p be a 300-digit prime. Alice chooses a secret integer k and encrypts messages by the function Ek(m)=mk(modp).

    1. Suppose Eve knows a cipher text c and knows the prime p. She captures Alice’s encryption machine and decides to try to find m by a birthday attack. She makes two lists. The first list contains cEk(x)1(modp) for some random choices of x. Describe how to generate the second list, state approximately how long the two lists should be, and describe how Eve finds m if her attack is successful.

    2. Is this attack practical? Why or why not?

  6. There are approximately 3×10147 primes with 150 digits. There are approximately 1085 particles in the universe. If each particle chooses a random 150-digit prime, do you think two particles will choose the same prime? Explain why or why not.

  7. If there are five people in a room, what is the probability that no two of them have birthdays in the same month? (Assume that each person has probability 1/12 of being born in any given month.)

  8. You use a random number generator to generate 109 random 15-digit numbers. What is the probability that two of the numbers are equal? Your answer should be accurate enough to say whether it is likely or unlikely that two of the numbers are equal.

  9. Nelson has a hash function H1 that gives an output of 60 bits. Friends tell him that this is not a big enough output, so he takes a strong hash function H2 with a 200-bit output and uses H(x)=H2(H1(x)) as his hash function. That is, he first hashes with his old hash function, then hashes the result with the strong hash function to get a 200-bit output, which he thinks is much better. The new hash function H can be computed quickly. Does it have preimage resistance, and does it have strong collision resistance? Explain your answers. (Note: Assume that computers can do up to 2501015 computations for this problem. Also, since it is essentially impossible to prove rigorously that most hash functions have preimage resistance or collision resistance, if your answer to either of these is “yes” then your explanation is really an explanation of why it is probably true.)

  10. Bob signs contracts by signing the hash values of the contracts. He is using a hash function H with a 50-bit output. Eve has a document M that states that Bob will pay her a lot of money. Eve finds a file with 109 documents that Bob has signed. Explain how Eve can forge Bob’s signature on a document (closely related to M) that states that Bob will pay Eve a lot of money. (Note: You may assume that Eve can do up to 230 calculations.)

  11. This problem derives the formula (12.1) for the probability of at least one match in a list of length r when there are N possible birthdays.

    1. Let f(x)=ln(1x)+x and g(x)=ln(1x)+x+x2. Show that f(x)0 and g(x)0 for 0x1/2.

    2. Using the facts that f(0)=g(0)=0 and f is decreasing and g is increasing, show that

      xx2ln(1x)xfor0x1/2.
    3. Show that if rN/2, then

      (r1)r2Nr33N2j=1r1ln1jN(r1)r2N.

      (Hint: j=1r1j=(r1)r/2 and j=1r1j2=(r1)r(2r1)/6<r3/3.)

    4. Let λ=r2/(2N) and assume that λN/8 (this implies that rN/2). Show that

      eλec1/Nj=1r11jNeλec2/N, 

      with c1=λ/213(2λ)3/2 and c2=λ/2.

    5. Observe that when N is large, ec/N is close to 1. Use this to show that as N becomes large and λ is constant with λN/8, then we have the approximation

      j=1r11jNeλ.
  12. Suppose f(x) is a function with n-bit outputs and with inputs much larger than n bits (this implies that collisions must exist). We know that, with a birthday attack, we have probability 1/2 of finding a collision in approximately 2n/2 steps.

    1. Suppose we repeat the birthday attack until we find a collision. Show that the expected number of repetitions is

      112+214+318+4116+=2

      (one way to evaluate the sum, call it S, is to write S12S=12+(21)14+(32)18+=1).

    2. Assume that each evaluation of f takes time a constant times n. (This is realistic since the inputs needed to find collisions can be taken to have 2n bits, for example.) Show that the expected time to find a collision for the function f is a constant times n2n/2.

    3. Show that the expected time to produce the messages m0, m0, , mt1, mt1 in Section 12.2 is a constant times tn2n/2.

  13. Suppose we have an iterative hash function, as in Section 11.3, but suppose we adjust the function slightly at each iteration. For concreteness, assume that the algorithm proceeds as follows. There is a compression function f that operates on inputs of a fixed length. There is also a function g that yields outputs of a fixed length, and there is a fixed initial value IV. The message is padded to obtain the desired format, then the following steps are performed:

    1. Split the message M into blocks M1, M2, , M.

    2. Let H0 be the initial value IV.

    3. For i=1, 2, , , let Hi=f(Hi1, Mi||g(i)).

    4. Let H(M)=H.

    Show that the method of Section 12.2 can be used to produce multicollisions for this hash function.

  14. Some of the steps of SRP are similar to the Diffie-Hellman key exchange. Why not use Diffie-Hellman to log in, using the following protocol? Alice and the server use Diffie-Hellman to establish a key K. Or they could use a public key method to transmit a secret key K from the server to Alice. Then they use K, along with a symmetric system such as AES, to submit Alice’s password P. Finally, the hash of the password is compared to what is stored in the computer’s password file.

    1. Show how Eve can do an intruder-in-the-middle attack and obtain Alice’s password.

    2. In order to avoid the attack in part (a), Alice and the server decide that Alice should send the hash of her password. Show that if Eve uses an intruder-in-the-middle attack, then she can log in to the server, pretending to be Alice.

    3. Alice and the server have another idea. The server sends Alice a random r and Alice sends H(r||P) to the server. Show how Eve can use an intruder-in-the-middle-attack to log in as Alice.

  15. Suppose that in SRP, the number u is chosen randomly by the server and sent to Alice at the same time that s is sent. Suppose Eve has obtained v from the server’s password file. Eve chooses a random a, computes Agavu mod p, and sends this value of A to the server. Then Eve computes S as (B3v)a mod p. Show that these computations appear to be valid to the server, so Eve can log in as Alice.