Assignment
1. Consider a hash function that starts with an 32-bit initial value of c09db506
and repeatedly XORs it with 32-bit blocks of the input to produce a 32-bit output.
For example, the input de0fc223 would generate the following output:
() = ⊕ =
and the input cd1aa915 f08d7db7 would generate the following output:
( ) = ⊕ ⊕ =
(a) Approximately how many steps would be required to perform a brute force
attack to find a preimage for a given output of this hash function?
(b) Approximately how many steps would be required to perform a brute force
birthday attack to find a collision for this hash function?
(c) Use the properties of the XOR operation to find a 32-bit preimage for the
output 666cdce9.
(d) Find a 32-bit second preimage for the output fd0a61a4 calculated above.
(e) Find a collision other than the one demonstrated by your answer to (d).
(hint: pick a 32-bit input, then find a 64-bit input that generates the same
output using the properties of XOR.)
2. The birthday problem poses the following question: how many people do you need
in a room so that it is likely that two of them have the same birthday? Assuming that
all 366 birthdays are equally likely (they aren’t since February 29th only happens
every four years or so, but it makes the problem slightly simpler to understand) we
can determine the following:
• If there are two people in the room there is a 365
366 or 0.9973 probability that
they have different birthdays, giving us a 1 − 0.9973 = 0.0027 probablity that
they have the same birthday.
• If there are three people in the room there is a 365
366 â‹… 364
366 or 0.9918 probability
that all three people have different birthdays, giving us a 1 − 0.9918 = 0.0082
probability that at least two of them have the same birthday.
• Continuing this process, it turns out that only 23 people are needed for there
to be a probability of at least 0.5 that two people have the same birthday.
This is the foundation of the concept of the birthday attack on a hash function. A
hash function that produces an -bit output can produce 2 different values. If is
suitably large, roughly 2/2 inputs need to be tried before a collision is likely to be
found. For smaller values of we can compute the number of inputs required using
the process outlined above for the birthday problem.
For the following questions, assume there is a hash function that generates a
4-bit output and that every possible output is equally likely to be generated.
(a) How many different hash values can this function generate? (2 pts)
(b) Assume that for a given input 1, H1 = (1). Assuming 2 ≠1, how
many possible values for H2 = (2) are different than H1? (2 pts)
(c) What is the probability that H2 is different than H1? (3 pts)
(d) Assume that H1 and H2 are different values. Assuming 3 ≠1 and 3 ≠2,
how many possible values for H3 = (3) are different than both H1
and H2? (2 pts)
(e) Assuming H1 and H2 are different, what is the probability that H3 is different
from both H1 and H2? (3 pts)
(f) In general, what is the probability that H1, H2 and H3 are all different? (3 pts)
(g) What is the probability that at least two of H1, H2 and H3 are the same? (3
pts)
(h) Continuing the process outlined in (d) through (g), how many different
inputs must be tried before there is at least a 0.5 probablity that two or more
outputs have the same value?
3. Given a 32-bit plaintext block P and a 32-bit key K, let
(K, P) = (K + P) mod 232
For example, if K = and P = ),
(K, P) = ( + ) mod 232 = mod 232 =
Let be a compression function defined by using the Davies-Meyer
construction with block cipher . Let be a hash function defined by using the
Merkle-Damgård construction using as the compression function and
H0 = as the initial value for the 32-bit internal state. Compute the
chaining values H1, H2, H3, and H4 for the following message (broken into four 32-bit
blocks):
=
4. write a summary of: "Message Authentication with
One-Way Hash Functions" - Tsudik (1992)
• The summary should be 2-3 paragraphs long.
• Make sure to highlight all of the important points in all of the sections of the
paper.
