Cryptography Reference
In-Depth Information
Exercise 5.14
Give Maple implementations of HMAC-SHA-224, HMAC-SHA-
384 and HMAC-SHA-512 by using the corresponding hash functions as indicated
in the names.
5.7 The Birthday Attack on Hash Functions
As we have seen, a hash function suitable for cryptographic use should be collision
resistant or, in some special cases which we have not discussed in detail, second
preimage resistant or preimage resistant at least. We are going to describe a generic
collision attack that gives a lower bound for the length of the hash values of a
cryptographic hash function.
5.7.1 The Birthday Paradox
In order to understand the collision attack we are going to present, let us first consider
a brute-force attack against preimage resistance or second preimage resistance. If the
hash function considered,
h
, produces hashes of length
n
, then there are 2
n
possible
hash values. Suppose then that, given a hash value
y
, the preimage resistance is
attacked by picking random strings
x
and computing
h
until we find a solution,
i.e., a stringwhich hashes to
y
. Then the expected number of trials is 2
n
by Proposition
2.2, and this is also the number of trials expected in a second preimage attack where,
given a string
x
, one tries to find a different string
x
such that the pair
(
x
)
x
)
(
x
,
is a
collision for
h
.
It could seem at first sight that this is also the average cost of finding a collision
of
h
and this is indeed the case if an initial string is selected and then further strings
are picked at random until finding one with the same hash as the initial string. But
this is far from being the best strategy to search for a collision and the reason is
the so-called
birthday paradox
which arises as a response to the following question:
How many people must be in a room for the probability that at least two of them
share the same birthday to be
2?
The answer, assuming that birthdays are independent and uniformly distributed
among 365 days, is that 23 persons suffice. This is called a 'paradox' because the
number 23 is surprisingly low at first sight, especially if one compares it, for example,
with the minimum number of persons so that the probability that at least one of them
shares their birthday with a
fixed
person is
>
1
/
2. If we view the
birthday map
, i.e.,
the function that assigns to each person his/her birthday as a sort of toy hash function
with only 365 hash values, the above question is like asking about the number of hash
values that should be computed to find a collision with probability
>
1
/
2, while the
problem referring to a fixed person asks for the probability of finding a collision with
something which is fixed in advance, i.e., it is similar to finding a second preimage
of the birthday of the specified person. The same reasoning that applies to this toy
example applies also to hash functions in general and makes it
much easier
to find a
collision than to find, say, a preimage. Let us quantify this claim.
>
1
/
