Cryptography Reference
In-Depth Information
11.2.3 Collision Resistance and the Birthday Attack
We call a hash function collision resistant or strong collision resistant if it is com-
putationally infeasible to find two different inputs
x
1
=
x
2
with
h
(
x
1
)=
h
(
x
2
).This
property is harder to achieve than weak collision resistance since an attacker has two
degrees of freedom: Both messages can be altered to achieve similar hash values.
We show now how Oscar could turn his ability to find collisions into an attack. He
starts with two messages, for instance:
x
1
=
Transfer $10 into Oscar's account
x
2
=
Transfer $10,000 into Oscar's account
He now alters
x
1
and
x
2
at “nonvisible” locations, e.g., he replaces spaces by tabs,
adds spaces or return signs at the end of the message, etc. This way, the semantics
of the message is unchanged (e.g., for a bank), but the hash value changes for every
version of the message. Oscar continues until the condition
h
(
x
1
)=
h
(
x
2
) is fulfilled.
Note that if an attacker has, e.g., 64 locations that he can alter or not, this yields 2
64
versions of the same message with 2
64
different hash values. With the two messages,
he can launch the following attack:
Alice
Oscar
Bob
k
pub
,
B
←−−−−−
x
1
−−−−−→
z
=
h
(
x
1
)
s
= sig
k
pr
,
B
(
z
)
(
x
2
,
s
)
←−−−−−
(
x
1
,
s
)
←−−−−−
substitute
z
=
h
(
x
2
)
ver
k
pub
,
B
(
s
,
z
)=true
This attack assumes that Oscar can trick Bob into signing the message
x
1
.This
is, of course, not possible in every situation, but one can imagine scenarios where
Oscar can pose as an innocent party, e.g., an e-commerce vendor on the Internet,
and
x
1
is the purchase order that is generated by Oscar.
As we saw earlier, due to the pigeonhole principle, collisions always exist. The
question is how difficult it is to find them. Our first guess is probably that this is as
difficult as finding second preimages, i.e., if the hash function has an output length of
80 bits, we have to check about 2
80
messages. However, it turns out that an attacker
needs only about 2
40
messages! This is a quite surprising result which is due to the
birthday attack
. This attack is based on the
birthday paradox
, which is a powerful
tool that is often used in cryptanalysis.
It turns out that the following real-world question is closely related to finding
collisions for hash functions: How many people are needed at a party such that
there is a reasonable chance that at least two people have the same birthday? By
