Cryptography Reference
In-Depth Information
for small
x
values (such as ours). Hence, the probability of no collisions is
m
−
1
m
−
1
j
n
)
e
−
j/n
=
e
−
m
(
m
−
1)
/
(2
n
)
.
(1
−
≈
j
=1
j
=1
Therefore, the probability of at least one collision occurring is
e
−
m
(
m
−
1)
/
(2
n
)
.
p
c
≈
1
−
(7.1)
Since
e
−
m
(
m
−
1)
/
(2
n
)
≈
1
−
p
c
,
then
p
c
)
,
(where ln(
x
)isthe
natural logarithm
, meaning the log to the base
e
, with
e
x
being the
natural exponential function
.) Hence,
−
m
(
m
−
1)
/
(2
n
)
≈
ln(1
−
m
2
−
m
≈−
2
n
ln(1
−
p
c
)
,
and so
m
2
≈−
−
≈
−
2
n
ln(1
p
c
)
2
n
ln(1
/
(1
p
c
))
,
since we can safely ignore the smaller factor of
−
m
in an approximation, so
2
n
ln(1
/
(1
m
≈
−
p
c
))
.
1
.
17
√
n
. Clearly then, by hashing over little more than
√
n
random elements of
If
p
c
=1
/
2, then
m
≈
, we have a greater than 50% chance of finding a
collision. This is the birthday attack.
The birthday attack places a lower bound on the number of bits a hash
function should have in order to be secure. The reason is that the birthday
attack can find a collision in
O
(2
k/
2
) hashings on an
k
-bit function. Thus, if
k
= 64, then it is not secure against the birthday attack since only 2
32
hashings
are required.
S
The following illustration of the birthday attack was first presented by Yuval
in 1979 (see [297]), and we re-presented it in [170].
Alice Cheats Bob Using the Birthday Attack
The hash function has 64 bits. Alice wants Bob to sign a contract that he
thinks will benefit him, and later she wants to “prove” that he signed a contract
that actually robs him of his life savings.
1. Alice prepares two contracts, one that is “good” for Bob,
C
G
, and one,
C
B
,
which will sign away his savings.
(2) Alice makes very minor changes in each of
C
G
and
C
B
. Then she hashes
2
32
modified versions of
C
G
and 2
32
modified versions of
C
B
.
Search WWH ::
Custom Search