# 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  possible sequences.) Assume that there are approximately  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  be an encryption function with  possible keys ,  possible plaintexts, and  possible ciphertexts. Assume that if you know the encryption key , then it is easy to find the decryption function  (therefore, this problem does not apply to public key methods). Suppose that, for each pair  of keys, it is possible to find a key  such that  for all plaintexts . Assume also that for every plaintext–ciphertext pair , there is usually only one key  such that . Suppose that you know a plaintext–ciphertext pair . Give a birthday attack that usually finds the key  in approximately  steps. (Remark: This is much faster than brute force searching through all keys , which takes time proportional to .)

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  gives the encryption. Eve obtains a plaintext–ciphertext pair  and wants to find  by the Birthday Attack. Suppose that the output of  has  bits. Eve computes two lists:

1.  for  randomly chosen keys 

2.  for  randomly chosen keys .

1. Why is there a very good chance that Eve finds a key pair  such that  ?

2. Why is it unlikely that  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  people have ever lived on earth. The number of shuffles of 52 cards is .

5. Let  be a 300-digit prime. Alice chooses a secret integer  and encrypts messages by the function .

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

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

6. There are approximately  primes with 150 digits. There are approximately  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  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  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  with a 200-bit output and uses  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  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  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  with a 50-bit output. Eve has a document  that states that Bob will pay her a lot of money. Eve finds a file with  documents that Bob has signed. Explain how Eve can forge Bob’s signature on a document (closely related to ) that states that Bob will pay Eve a lot of money. (Note: You may assume that Eve can do up to  calculations.)

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

1. Let  and . Show that  and  for .

2. Using the facts that  and  is decreasing and  is increasing, show that


3. Show that if , then



(Hint:  and .)

4. Let  and assume that  (this implies that ). Show that



with  and .

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


12. Suppose  is a function with -bit outputs and with inputs much larger than  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  steps.

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



(one way to evaluate the sum, call it , is to write ).

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

3. Show that the expected time to produce the messages  in Section 12.2 is a constant times .

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  that operates on inputs of a fixed length. There is also a function  that yields outputs of a fixed length, and there is a fixed initial value . The message is padded to obtain the desired format, then the following steps are performed:

1. Split the message  into blocks .

2. Let  be the initial value .

3. For , let .

4. Let .

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 . Or they could use a public key method to transmit a secret key  from the server to Alice. Then they use , along with a symmetric system such as AES, to submit Alice’s password . 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  and Alice sends  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  is chosen randomly by the server and sent to Alice at the same time that  is sent. Suppose Eve has obtained  from the server’s password file. Eve chooses a random , computes  mod , and sends this value of  to the server. Then Eve computes  as  mod . Show that these computations appear to be valid to the server, so Eve can log in as Alice.