Cryptography Reference
In-Depth Information
365!
(342)!365
23
−
=1
365
·
364
···
343
=1
−
≈
0
.
508
365
23
This result is somehow paradoxical. If we fix a date and ask for the number
of persons that are required to make the probability that at least one person has this
date as his or her birthday, then
n
must be much larger. In fact, in this case
n
has to
be
= 183.
Applying this argument to hash functions means that finding two persons with
the same birthday reveals a collision, whereas finding a person with a given birthday
reveals a second preimage. Hence, due to the birthday paradox, one can argue
that collision resistance is much more difficult to achieve than second-preimage
resistance. More specifically, one can show that for any collision resistant hash
function with an
n
-bit output, no attack finding a collision betters a birthday attack
with a worst-case running time of
362
/
2
O
(
√
2
n
)=
O
(2
n/
2
)
That's why the birthday attack is sometimes also referred to as
square root
attack
. This result implies that a collision resistant hash function must produce
outputs that are twice as long as one would usually suggest to make an exhaustive
search computationally infeasible. For example, if we assume that searching a key
space of 2
64
is computationally infeasible, then we must use a hash function that
outputs at least 2
64 = 128 bits.
In addition to preimage, second-preimage, and collision resistance, there are
also some other properties of hash functions mentioned (and sometimes discussed)
in the literature.
·
•
A hash function
h
is
noncorrelated
if its input bits and output bits are not
correlated in one way or another.
•
A hash function
h
is
generalized collision resistant
if it is computationally
infeasible to find two input words
x
and
x
with
x
=
x
such that
h
(
x
) and
h
(
x
) are similar in some specific sense (e.g., they are equal in some bits).
•
A hash function
h
is
weakened collision resistant
if it is computationally
infeasible to find two input words
x
and
x
with
x
=
x
and
h
(
x
)=
h
(
x
)
such that
x
and
x
are similar in some specified sense (e.g., they are equal in
some bits).
