Cryptography Reference
In-Depth Information
Exercise 5.15
In the following questions, we assume that people are randomly cho-
sen and birthdays uniformly distributed among the possible ones.
(i) Find the minimum number of people in a room such that the probability that
at least one of them shares a birthday with another person entering the room is
≥
2.
(ii) Find the minimum value of
n
such that if a group of 2
n
people is separated into
two groups of
n
people each, the probability that one person of the first group
shares a birthday with one person of the second group is
1
/
≥
1
/
2.
5.7.2 The Birthday Attack
The birthday paradox gives rise to a brute-force collision attack against hash functions
which is much more efficient than fixing a string and trying to find another one with
the same hash value. The idea is simply to compute as many hash values as possible
for strings chosen at random, store these strings together with their hash values, and
then compare these values trying to find a collision. When the number of hash values
computed is slightly larger than
√
2
n
, where
n
is the bit length of the hash function,
then the probability of a collision among two of these strings will be
≥
1
/
2, so that
2
n
/
2
finding a collision requires time
O
. Why is this so?
The reason is simple: if we pick strings at random and assume that their hash
values are uniformly distributed among all the possible values, then computing these
hashes is like choosing at random integers between 1 and 2
n
, so that Theorem 5.4
applies.
To better appreciate the possible impact of this
birthday attack
, let us consider a
widely used hash function: MD5. MD5 was introduced by R. Rivest in 1991; it is
obtained from a compression function by the Merkle-Damgård construction and has
an output length of 128 bits. Thus a brute-force attack against the second preimage
resistance is out of question, as 2
128
hash operations are far from feasible today.
However, a birthday attack can find a collision by just computing slightly more
than 2
64
hash operations and is regarded as feasible (although costly) by taking as
reference some distributed computations of similar size that have already been done.
In consequence, MD5 is regarded as broken since a few years ago and its usage
is strongly discouraged. In fact, stronger attack techniques against MD5 have been
discovered, starting with the work of Xiaoyun Wang and colleagues who found the
first collisions for MD5 in 2004 [196] and leading to attacks that are able to findMD5
collisions in just a few seconds on a personal computer. Furthermore, it was shown
in [188] how to create a rogue
Certification Authority certificate
trusted and regarded
as valid by all common web browsers on the date it was announced (a demonstration
is available at [185]). We will describe these certificates when studying public-key
cryptography and public-key infrastructures but, for now, let us just mention that this
certificate, constructed by exploiting MD5 weaknesses, would allow its authors to
(
)
