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

Each person in the world flips 100 coins and obtains a sequence of length 100 consisting of Heads and Tails. (There are $2^{100}\approx {10}^{30}$ possible sequences.) Assume that there are approximately ${10}^{10}$ 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 $E_K$ be an encryption function with $N$ possible keys $K$, $N$ possible plaintexts, and $N$ possible ciphertexts. Assume that if you know the encryption key $K$, then it is easy to find the decryption function $D_K$ (therefore, this problem does not apply to public key methods). Suppose that, for each pair $(K_1\text{,}{K}_2)$ of keys, it is possible to find a key $K_3$ such that $E_{K_1}(E_{K_2}(m))=E_{K_3}(m)$ for all plaintexts $m$. Assume also that for every plaintext–ciphertext pair $(m\text{,}c)$, there is usually only one key $K$ such that $E_K(m)=c$. Suppose that you know a plaintext–ciphertext pair $(m\text{,}c)$. Give a birthday attack that usually finds the key $K$ in approximately $2\sqrt{N}$ steps. (Remark: This is much faster than brute force searching through all keys $K$, which takes time proportional to $N$.)

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

Alice uses double encryption with a block cipher to send messages to Bob, so $c=E_{K_1}(E_{K_2}(m))$ gives the encryption. Eve obtains a plaintext–ciphertext pair $(m\text{,}c)$ and wants to find $K_1\text{,}{K}_2$ by the Birthday Attack. Suppose that the output of $E_K$ has $N$ bits. Eve computes two lists:

1. $E_K(m)$ for $3\cdot 2^{N/2}$ randomly chosen keys $K\text{.}$

2. $D_L(c)$ for $3\cdot 2^{N/2}$ randomly chosen keys $L$.

   1. Why is there a very good chance that Eve finds a key pair $(L\text{,}K)$ such that $c=E_L(E_K(m))$ ?

   2. Why is it unlikely that $(L\text{,}K)$ 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?

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 $1.08\times {10}^{11}$ people have ever lived on earth. The number of shuffles of 52 cards is $52!\approx 8\times {10}^{67}$.

Let $p$ be a 300-digit prime. Alice chooses a secret integer $k$ and encrypts messages by the function $E_k(m)=m^k(\text{mod}p)$.

1. Suppose Eve knows a cipher text $c$ and knows the prime $p$. She captures Alice’s encryption machine and decides to try to find $m$ by a birthday attack. She makes two lists. The first list contains $c\cdot E_k(x{)}^{-1}(\text{mod}p)$ for some random choices of $x$. Describe how to generate the second list, state approximately how long the two lists should be, and describe how Eve finds $m$ if her attack is successful.

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

There are approximately $3\times {10}^{147}$ primes with 150 digits. There are approximately ${10}^{85}$ 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.

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

You use a random number generator to generate ${10}^9$ 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.

Nelson has a hash function $H_1$ 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 $H_2$ with a 200-bit output and uses $H(x)=H_2(H_1(x))$ 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 $H$ 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 $2^{50}\approx {10}^{15}$ 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.)

Bob signs contracts by signing the hash values of the contracts. He is using a hash function $H$ with a 50-bit output. Eve has a document $M$ that states that Bob will pay her a lot of money. Eve finds a file with ${10}^9$ documents that Bob has signed. Explain how Eve can forge Bob’s signature on a document (closely related to $M$) that states that Bob will pay Eve a lot of money. (Note: You may assume that Eve can do up to $2^{30}$ calculations.)

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

1. Let $f(x)=ln(1-x)+x$ and $g(x)=ln(1-x)+x+x^2$. Show that $f^{\prime }(x)\le 0$ and $g^{\prime }(x)\ge 0$ for $0\le x\le 1/2$.

2. Using the facts that $f(0)=g(0)=0$ and $f$ is decreasing and $g$ is increasing, show that

   $$-x-x^2\le ln(1-x)\le -x\text{for}0\le x\le 1/2.$$

3. Show that if $r\le N/2$, then

   $$-{\displaystyle \frac{(r-1)r}{2N}}-{\displaystyle \frac{r^3}{3N^2}}\le \sum _{j=1}^{r-1}ln\left(1-{\displaystyle \frac{j}{N}}\right)\le -{\displaystyle \frac{(r-1)r}{2N}}\text{.}$$

   (Hint: $\sum _{j=1}^{r-1}j=(r-1)r/2$ and $\sum _{j=1}^{r-1}{j}^2=(r-1)r(2r-1)/6<r^3/3$.)

4. Let $\lambda =r^2/(2N)$ and assume that $\lambda \le N/8$ (this implies that $r\le N/2$). Show that

   $$e^{-\lambda }{e}^{c_1/\sqrt{N}}\le \prod _{j=1}^{r-1}\left(1-{\displaystyle \frac{j}{N}}\right)\le e^{-\lambda }{e}^{c_2/\sqrt{N}}\text{,}$$

   with $c_1=\sqrt{\lambda /2}-{\displaystyle \frac{1}{3}}(2\lambda {)}^{3/2}$ and $c_2=\sqrt{\lambda /2}$.

5. Observe that when $N$ is large, $e^{c/\sqrt{N}}$ is close to 1. Use this to show that as $N$ becomes large and $\lambda$ is constant with $\lambda \le N/8$, then we have the approximation

   $$\prod _{j=1}^{r-1}\left(1-{\displaystyle \frac{j}{N}}\right)\approx e^{-\lambda }\text{.}$$

Suppose $f(x)$ is a function with $n$-bit outputs and with inputs much larger than $n$ 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 $2^{n/2}$ steps.

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

   $$1\cdot {\displaystyle \frac{1}{2}}+2\cdot {\displaystyle \frac{1}{4}}+3\cdot {\displaystyle \frac{1}{8}}+4\cdot {\displaystyle \frac{1}{16}}+\cdots =2$$

   (one way to evaluate the sum, call it $S$, is to write $S-{\displaystyle \frac{1}{2}}S={\displaystyle \frac{1}{2}}+(2-1){\displaystyle \frac{1}{4}}+(3-2){\displaystyle \frac{1}{8}}+\cdots =1$).

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

3. Show that the expected time to produce the messages $m_0\text{,}{m}_0^{\prime }\text{,}\dots \text{,}{m}_{t-1}\text{,}{m}_{t-1}^{\prime }$ in Section 12.2 is a constant times $tn{2}^{n/2}$.

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

1. Split the message $M$ into blocks $M_1\text{,}{M}_2\text{,}\dots \text{,}{M}_{\ell }$.

2. Let $H_0$ be the initial value $IV$.

3. For $i=1\text{,}2\text{,}\dots \text{,}\ell$, let $H_i=f(H_{i-1}\text{,}{M}_i||g(i))$.

4. Let $H(M)=H_{\ell }$.

Show that the method of Section 12.2 can be used to produce multicollisions for this hash function.

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 $K$. Or they could use a public key method to transmit a secret key $K$ from the server to Alice. Then they use $K$, along with a symmetric system such as AES, to submit Alice’s password $P$. 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 $r$ and Alice sends $H(r||P)$ to the server. Show how Eve can use an intruder-in-the-middle-attack to log in as Alice.

Suppose that in SRP, the number $u$ is chosen randomly by the server and sent to Alice at the same time that $s$ is sent. Suppose Eve has obtained $v$ from the server’s password file. Eve chooses a random $a$, computes $A\equiv g^a{v}^{-u}$ mod $p$, and sends this value of $A$ to the server. Then Eve computes $S$ as $(B-3v{)}^a$ mod $p$. Show that these computations appear to be valid to the server, so Eve can log in as Alice.