Cryptography Reference
In-Depth Information
On the one hand,
h
is collision resistant. If
h
(
x
) begins with a one, then
there is no collision at all. If
h
(
x
) begins with a zero, then finding a collision
means finding a collision for
g
(which is assumed to be computationally
infeasible). On the other hand,
h
is not preimage resistant. For all
h
(
x
)
that begin with a one, it is trivial to find a preimage (just drop the leading
one) and to invert
h
accordingly. Consequently,
h
is a hash function that is
collision resistant but not preimage resistant, and we conclude that preimage
resistance and collision resistance are inherently different properties that must
be distinguished accordingly.
In practice, Σ
in
and Σ
out
are often set to
{
0
,
1
}
, and a hash function then
n
. A question that occurs immediately is
how large to choose the parameter
n
. A lower bound for
n
is obtained by the
birthday attack
. This attack is based on the
birthday paradox
that is well known
in probability theory. It says that the probability of two persons in a group sharing
the same birthday is greater than 1
/
2 if the group is chosen at random and has
more than 23 members. To obtain this result, we employ a sample space Σ that
consists off all
n
-tuples over the 365 days of the year (i.e.,
}
∗
to
represents a map from
{
0
,
1
{
0
,
1
}
|
|
= 365
n
). Let Pr[
A
]
be the probability that at least two out of
n
persons have the same birthday. This
value is difficult to compute directly. It is much simpler to compute Pr[
Σ
A
] (i.e., the
probability that all persons have different birthdays) and to derive Pr[
A
] from this
value. In fact, Pr[
A
] can be computed as follows (for 0
≤
n
≤
365):
Pr[
A
]=1
−
Pr[
A
]
−
| A|
|
=1
Σ
|
1
365
n
=1
−
365
·
364
·
...
·
(365
−
n
)
·
365!
(365
1
365
n
=1
−
n
)!
·
−
365!
=1
−
n
)!365
n
(365
−
] is equal to 1 for
n>
365 (in this case, it is not possible that all
n
persons have different birthdays). In either case, Pr[
Pr[
A
] grows surprisingly fast and
n
must only be 23 to reach a probability greater or equal to 1
/
2.If
n
=23,then
A
365!
Pr[
A
]=1
−
(365
−
23)!365
23
