Cryptography Reference
In-Depth Information
Input
: a cryptographic hash function
h
onto a domain of size
N
Output
: a
pa
ir (
x
,
x
) such that
x
=
x
and
h
(
x
)
=
h
(
x
)
√
N
many different
x
do
1:
for
θ
compute
y
=
h
(
x
)
2:
x
) pair in the hash table
then
if
there is a (
y
,
3:
x
) and stop
yield (
x
,
4:
end if
5:
add (
y
,
x
) in the hash table
6:
7:
end for
8:
search failed
Figure 3.7.
Collision search with the birthday paradox.
birthdays are independent and uniformly distributed among 365 days, then at least two
of them are likely to share the same birthday. It can be mathematically expressed as
follows.
Theorem 3.2.
If
we pick independent random numbers in
{
1
,
2
,...,
N
}
with uniform
θ
√
N times, we get at least one number twice with probability
distribution
N
!
N
θ
√
N
(
N
e
−
θ
2
1
−
√
N
)!
−→
1
−
.
−
θ
N
→+∞
For
N
=
365
,
we obtain the following figures.
θ
√
N
10
15
20
25
30
35
40
θ
0
.
52
0
.
79
1
.
05
1
.
31
1
.
57
1
.
83
2
.
09
Probability
12%
25%
41%
57%
71%
81%
89%
So we can find a collision on a hash function by hashing random numbers until the list
of hashed values have a collision. If we want to find a collision on MD5 which uses
128-bit hashed values, we thus use
θ.
2
64
MD5 computations.
Proof.
The probability that w
e
have no collision is the
nu
mber of ordered subsets of
{
√
N
, wh
ich
is
N
!
√
N
)!, divided by the number of
1
,...,
N
}
of cardinality
θ
/
(
N
−
θ
√
N
, which is
N
θ
√
N
.
sequences of numbers of length
θ
We approximate the probability by using the Stirling Approximation
3
√
2
ne
−
n
n
n
n
!
∼
n
→+∞
π
.
3
The
∼
notation means that there is equality between both sides with a proportional coefficient which tends
toward 1 when
n
tends toward infinity.
Search WWH ::
Custom Search