# 11.6 Exercises

Let $p$ be a prime and let $\alpha $ be an integer with $p\text{\hspace{0.17em}}\nmid \text{\hspace{0.17em}}\alpha $. Let $h(x)\equiv {\alpha}^{x}\text{\hspace{1em}}(\text{m}\text{o}\text{d}\text{\hspace{0.17em}}p)$. Explain why $h(x)$ 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, $T$, and encrypts it with a one-time pad $K$, and sends $C=T\oplus K$ to Bob. After the World Cup is finished, Alice reveals $K$, and Bob computes $T=C\oplus K$ to determine Alice’s guess. Why should Bob not believe that Alice actually guessed the correct team, even if $T=C\oplus K$ is correct?

To keep Alice from changing $K$, Bob requires Alice to send not only $C=T\oplus K$ 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$?

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.)

Let $n=pq$ be the product of two distinct large primes and let $h(x)={x}^{2}\text{\hspace{1em}}(\text{m}\text{o}\text{d}\text{\hspace{0.17em}}n)$.

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

Why is $h$ not strongly collision resistant?

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

He takes a large prime $p$ and a primitive root $\alpha $ for $p$. For an input $x$, he computes $\beta \equiv {\alpha}^{x}\text{\hspace{0.17em}}(\text{m}\text{o}\text{d}\text{\hspace{0.17em}}p)$, then sets ${H}_{2}(x)=H(\beta )$. The function ${H}_{2}$ is not fast enough to be a hash function. Find one other property of hash functions that fails for ${H}_{2}$ and one that holds for ${H}_{2}$, and justify your answers.

Since his function in part (a) is not fast enough, Nelson tries using ${H}_{3}=H(x\text{\hspace{0.17em}}\text{mod}\text{\hspace{0.17em}}p)$. This is very fast. Find one other property of hash functions that holds for ${H}_{3}$ and one that fails for ${H}_{3}$, and justify your answers.

Suppose a message $m$ is divided into blocks of length 160 bits: $m={M}_{1}||{M}_{2}||\cdots ||{M}_{\mathrm{\ell}}$. Let $h(x)={M}_{1}\oplus {M}_{2}\oplus \cdots \oplus {M}_{\mathrm{\ell}}$. Which of the properties (1), (2), (3) for a hash function does $h$ 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 ${H}_{k}^{(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.

Compute $\lfloor {2}^{32}(\sqrt{2}-1)\rfloor $ and write the answer in hexadecimal. The answer should be ${H}_{1}^{(0)}$.

Do a similar computation with $\sqrt{2}$ replaced by $\sqrt{3}$, $\sqrt{5}$, and $\sqrt{19}$ and compare with the appropriate values of ${H}_{k}^{(0)}$.

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.

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

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?

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$.

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

An unenlightened professor asks his students to memorize the first 1000 digits of $\pi $ 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.

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 $\pi $ 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 $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?

(Thanks to Danna Doratotaj for suggesting this problem.)

Let ${H}_{1}$ map 256-bit strings to 256-bit strings by ${H}_{1}(x)=x$. Show that ${H}_{1}$ is not preimage resistant but it is collision resistant.

Let $H$ be a good cryptographic hash function with a 256-bit output. Define a map ${H}_{2}$ from binary strings of arbitrary length to binary strings of length 257, as follows. If $0\text{\hspace{0.17em}}\le \text{\hspace{0.17em}}x\text{\hspace{0.17em}}<{2}^{256}$, let ${H}_{2}(x)=x||$ (that is, $x$ with appended). If $x\ge {2}^{256}$, let ${H}_{2}(x)=H(x)||1$. Show that ${H}_{2}$ 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 ${H}_{1}$ and ${H}_{2}$ show that collision resistance does not imply preimage resistance quite as obviously as one might suspect.

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

Let $Maj(X\text{,}\text{}Y\text{,}\text{}Z)=(X\wedge Y)\oplus (X\wedge Z)\oplus (Y\wedge Z)$ be the function on 32-bit strings in the description of SHA-2.

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 $\text{Maj}(X\text{,}\text{}\text{\hspace{0.17em}}Y\text{,}\text{}\text{\hspace{0.17em}}Z)$ is 1.

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 $\text{Maj}(X\text{,}\text{}Y\text{,}\text{}Z)$ is 0.

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

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 ${M}_{1}\parallel {M}_{2}$ of 1024 bits is computed by ${X}_{1}=h(IV\text{,}\text{}{M}_{1})$, and $H({M}_{1}\parallel {M}_{2})=h({X}_{1}\text{,}\text{}{M}_{2})$. Suppose we have found a collision $h(IV\text{,}\text{}{x}_{1})=h(IV\text{,}\text{}{x}_{2})$ for some 512-bit blocks ${x}_{1}$ and ${x}_{2}$. Choose distinct primes ${p}_{1}$ and ${p}_{2}$, each of approximately 240 bits. Regard ${x}_{1}$ and ${x}_{2}$ as numbers between 0 and ${2}^{512}$.

Show that there exists an ${x}_{0}$ with $0\le {x}_{0}<{p}_{1}{p}_{2}$ such that

$$\begin{array}{ccc}{x}_{0}+{2}^{512}{x}_{1}\equiv 0& (\text{mod}\text{\hspace{0.17em}}{p}_{1})\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}{x}_{0}+{2}^{512}{x}_{2}\equiv 0& (\text{mod}\text{\hspace{0.17em}}{p}_{2})\text{.}\end{array}$$Show that if $0\le k<{2}^{30}$, then ${q}_{1}=({x}_{0}+{2}^{512}{x}_{1}+k{p}_{1}{p}_{2})/{p}_{1}$ is approximately ${2}^{784}$, and similarly for ${q}_{2}=({x}_{0}+{2}^{512}{x}_{2}+k{p}_{1}{p}_{2})/{p}_{2}$. (Assume that ${x}_{1}$ and ${x}_{2}$ are approximately ${2}^{512}$.)

Use the Prime Number Theorem (see Section 3.1) to show that the probability that ${q}_{1}$ is prime is approximately $1/543$ and the probability that both ${q}_{1}$ and ${q}_{2}$ are prime is about $1/300000$.

Show that it is likely that there is some $k$ with $0\le k<{2}^{30}$ such that both ${q}_{1}$ and ${q}_{2}$ are primes.

Show that ${n}_{1}={p}_{1}{q}_{1}$ and ${n}_{2}={p}_{2}{q}_{2}$ satisfy $H({n}_{1})=H({n}_{2})$.

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$.