Let be a prime and let be an integer with . Let . Explain why is not a good cryptographic hash function.
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?
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 ?
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.)
Let be the product of two distinct large primes and let .
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.)
Why is not strongly collision resistant?
Let be a cryptographic hash function. Nelson tries to make new hash functions.
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.
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.
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.
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.
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?
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.)
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.
Compute and write the answer in hexadecimal. The answer should be .
Do a similar computation with replaced by , , and and compare with the appropriate values of .
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.
What property of convinces Alice that she is communicating with Bob?
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?
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.
If someone gets 100% on the exam, why is the professor confident that the student’s answer is correct?
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?
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?
(Thanks to Danna Doratotaj for suggesting this problem.)
Let map 256-bit strings to 256-bit strings by . Show that is not preimage resistant but it is collision resistant.
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.
Show that the computation of in Keccak (see the end of Section 11.5) can be given by an LFSR.
Let be the function on 32-bit strings in the description of SHA-2.
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.
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 .
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 .
Show that there exists an with such that
Show that if , then is approximately , and similarly for . (Assume that and are approximately .)
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 .
Show that it is likely that there is some with such that both and are primes.
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 .