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

11.6 Exercises

  1. Let p be a prime and let α be an integer with pα. Let h(x)αx(modp). Explain why h(x) 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, T, and encrypts it with a one-time pad K, and sends C=TK to Bob. After the World Cup is finished, Alice reveals K, and Bob computes T=CK to determine Alice’s guess. Why should Bob not believe that Alice actually guessed the correct team, even if T=CK is correct?

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

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

  2. Let n=pq be the product of two distinct large primes and let h(x)=x2(modn).

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

    2. Why is h not strongly collision resistant?

  3. Let H(x) be a cryptographic hash function. Nelson tries to make new hash functions.

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

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

  4. Suppose a message m is divided into blocks of length 160 bits: m=M1||M2||||M. Let h(x)=M1M2M. Which of the properties (1), (2), (3) for a hash function does h 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 Hk(0) 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 232(21) and write the answer in hexadecimal. The answer should be H1(0).

    2. Do a similar computation with 2 replaced by 3, 5, and 19 and compare with the appropriate values of Hk(0).

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

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

    2. Suppose Alice’s random number generator is broken and she sends the same S each time she communicates with anyone. How can Eve (who doesn’t know K, 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 y (of the appropriate length), show how to find an input x whose hash is y.

    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 H. 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 H 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 H1 map 256-bit strings to 256-bit strings by H1(x)=x. Show that H1 is not preimage resistant but it is collision resistant.

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

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

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

  12. Let Maj(X, Y, Z)=(XY)(XZ)(YZ) be the function on 32-bit strings in the description of SHA-2.

    1. Suppose that the first bit of X and the first bit of Y are 1 and the first bit of Z is arbitrary. Show that the first bit of Maj(X, Y, Z) is 1.

    2. Suppose that the first bit of X and the first bit of Y are 0 and the first bit of Z is arbitrary. Show that the first bit of Maj(X, Y, Z) is 0.

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

  13. Let H be an iterative hash function that operates successively on input blocks of 512 bits. In particular, there is a compression function h and an initial value IV. The hash of a message M1M2 of 1024 bits is computed by X1=h(IV, M1), and H(M1M2)=h(X1, M2). Suppose we have found a collision h(IV, x1)=h(IV, x2) for some 512-bit blocks x1 and x2. Choose distinct primes p1 and p2, each of approximately 240 bits. Regard x1 and x2 as numbers between 0 and 2512.

    1. Show that there exists an x0 with 0x0<p1p2 such that

      x0+2512x10(modp1)andx0+2512x20(modp2).
    2. Show that if 0k<230, then q1=(x0+2512x1+kp1p2)/p1 is approximately 2784, and similarly for q2=(x0+2512x2+kp1p2)/p2. (Assume that x1 and x2 are approximately 2512.)

    3. Use the Prime Number Theorem (see Section 3.1) to show that the probability that q1 is prime is approximately 1/543 and the probability that both q1 and q2 are prime is about 1/300000.

    4. Show that it is likely that there is some k with 0k<230 such that both q1 and q2 are primes.

    5. Show that n1=p1q1 and n2=p2q2 satisfy H(n1)=H(n2).

    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 n=pq with p and q of significantly different sizes (240 bits and 784 bits), but an adversary does not know this without factoring n.