# 11.6 Exercises

1. Let  be a prime and let  be an integer with . Let . Explain why  is not a good cryptographic hash function.

1. Alice claims that she knows who will win the next World Cup. She takes the name of the team, , and encrypts it with a one-time pad , and sends  to Bob. After the World Cup is finished, Alice reveals , and Bob computes  to determine Alice’s guess. Why should Bob not believe that Alice actually guessed the correct team, even if  is correct?

2. To keep Alice from changing , Bob requires Alice to send not only  but also , where  is a good cryptographic hash function. How does the use of the hash function convince Bob that Alice is not changing ?

3. In the procedure in (b), Bob receives  and . Show how he can determine Alice’s prediction, without needing Alice to send ? (Hint: There are fewer than 100 teams  that could win the World Cup.)

2. Let  be the product of two distinct large primes and let .

1. Why is  preimage resistant? (Of course, there are some values, such as  for which it is easy to find a preimage. But usually it is difficult.)

2. Why is  not strongly collision resistant?

3. Let  be a cryptographic hash function. Nelson tries to make new hash functions.

1. He takes a large prime  and a primitive root  for . For an input , he computes , then sets . The function  is not fast enough to be a hash function. Find one other property of hash functions that fails for  and one that holds for , and justify your answers.

2. Since his function in part (a) is not fast enough, Nelson tries using . This is very fast. Find one other property of hash functions that holds for  and one that fails for , and justify your answers.

4. Suppose a message  is divided into blocks of length 160 bits: . Let . Which of the properties (1), (2), (3) for a hash function does  satisfy and which does it not satisfy? Justify your answers.

5. One way of storing and verifying passwords is the following. A file contains a user’s login id plus the hash of the user’s password. When the user logs in, the computer checks to see if the hash of the password is the same as the hash stored in the file. The password is not stored in the file. Assume that the hash function is a good cryptographic hash function.

1. Suppose Eve is able to look at the file. What property of the hash function prevents Eve from finding a password that will be accepted as valid?

2. When the user logs in, and the hash of the user’s password matches the hash stored in the file, what property of the hash function says that the user probably entered the correct password? (Hint: Your answers to (a) and (b) should not be the same.)

6. The initial values  in SHA-256 are extracted from the hexadecimal expansions of the fractional parts of the square roots of the first eight primes. Here is what that means.

1. Compute  and write the answer in hexadecimal. The answer should be .

2. Do a similar computation with  replaced by , , and  and compare with the appropriate values of .

7. Alice and Bob (and no one else) share a key . Each time that Alice wants to make sure that she is communicating with Bob, she sends him a random string  of 100 bits. Bob computes , where  is a good cryptographic hash function, and sends  to Alice. Alice computes . If this matches what Bob sent her, she is convinced that she is communicating with Bob.

1. What property of  convinces Alice that she is communicating with Bob?

2. Suppose Alice’s random number generator is broken and she sends the same  each time she communicates with anyone. How can Eve (who doesn’t know , but who intercepts all communications between Alice and Bob) convince Alice that she is Bob?

1. Show that neither of the two hash functions of Section 11.2 is preimage resistant. That is, given an arbitrary  (of the appropriate length), show how to find an input  whose hash is .

2. Find a collision for each of the two hash functions of Section 11.2.

8. An unenlightened professor asks his students to memorize the first 1000 digits of  for the exam. To grade the exam, he uses a 100-digit cryptographic hash function . Instead of carefully reading the students’ answers, he hashes each of them individually to obtain binary strings of length 100. Your score on the exam is the number of bits of the hash of your answer that agree with the corresponding bits of the hash of the correct answer.

1. If someone gets 100% on the exam, why is the professor confident that the student’s answer is correct?

2. Suppose each student gets every digit of  wrong (a very unlikely occurrence!), and they all have different answers. Approximately what should the average on the exam be?

9. A bank in Tokyo is sending a terabyte of data to a bank in New York. There could be transmission errors. Therefore, the bank in Tokyo uses a cryptographic hash function  and computes the hash of the data. This hash value is sent to the bank in New York. The bank in New York computes the hash of the data received. If this matches the hash value sent from Tokyo, the New York bank decides that there was no transmission error. What property of cryptographic hash functions allows the bank to decide this?

10. (Thanks to Danna Doratotaj for suggesting this problem.)

1. Let  map 256-bit strings to 256-bit strings by . Show that  is not preimage resistant but it is collision resistant.

2. Let  be a good cryptographic hash function with a 256-bit output. Define a map  from binary strings of arbitrary length to binary strings of length 257, as follows. If , let  (that is,  with appended). If , let . Show that  is collision resistant, and show that if  is a randomly chosen binary string of length 257, then the probability is at least 50% that you can easily find  with .

The functions  and  show that collision resistance does not imply preimage resistance quite as obviously as one might suspect.

11. Show that the computation of  in Keccak (see the end of Section 11.5) can be given by an LFSR.

12. Let  be the function on 32-bit strings in the description of SHA-2.

1. Suppose that the first bit of  and the first bit of  are 1 and the first bit of  is arbitrary. Show that the first bit of  is 1.

2. Suppose that the first bit of  and the first bit of  are 0 and the first bit of  is arbitrary. Show that the first bit of  is 0.

This shows that Maj gives the bitwise majority (for 0 vs. 1) for the strings .

13. Let  be an iterative hash function that operates successively on input blocks of 512 bits. In particular, there is a compression function  and an initial value . The hash of a message  of 1024 bits is computed by , and . Suppose we have found a collision  for some 512-bit blocks  and . Choose distinct primes  and , each of approximately 240 bits. Regard  and  as numbers between 0 and .

1. Show that there exists an  with  such that


2. Show that if , then  is approximately , and similarly for . (Assume that  and  are approximately .)

3. Use the Prime Number Theorem (see Section 3.1) to show that the probability that  is prime is approximately  and the probability that both  and  are prime is about .

4. Show that it is likely that there is some  with  such that both  and  are primes.

5. Show that  and  satisfy .

This method of producing two RSA moduli with the same hash values is based on the method of [Lenstra et al.] for using a collision to produce two X.509 certificates with the same hashes. The method presented here produces moduli  with  and  of significantly different sizes (240 bits and 784 bits), but an adversary does not know this without factoring .