Cryptography Reference
In-Depth Information
there is an important distinction here between the running time of the algorithm and the
running time of the programmer (who is obliged to compute the collision as part of their
task). A full discussion of this issue is given by Rogaway [
450
]; also see Section 4.6.1 of
Katz and Lindell [
300
].
Intuitively, if one can compute preimages then one can compute second-preimages
(though some care is needed here to be certain that the value
x
output by a preimage
oracle is not just
x
again; Note 9.20 of Menezes, van Oorschot and Vanstone [
376
]gives
an artificial hash function that is second-preimage resistant but not preimage resistant).
Similarly, if one can compute second-preimages then one can find collisions. Hence, in
practice we prefer to study hash families that offer collision resistance. For more details
about these relations see Section 4.6.2 of [
300
], Section 4.2 of [
532
] or Section 10.3 of [
513
].
Another requirement of hash families is that they be
entropy smoothing
:if
G
is a
“sufficiently large” finite set (i.e., #
G
2
l
) with a “sufficiently nice” distribution on it (but
not necessarily uniform) then the distribution on
=
x
∈
G
:
H
(
x
)
=
y
Pr(
x
)
is “close” to uniform. We do not make this notion precise, but refer to Section 6.9 of
Shoup [
497
].
In Section 23.2 the following notion (which is just a restatement of second-preimage
resistance) will be used.
l
givenbyPr(
y
)
{
0
,
1
}
Definition 3.1.2
Let
X
and
Y
be finite sets. A hash family
is called
target collision resistant
if there is no polynomial-time adversary
A
with non-negligible
advantage in the following game:
A
receives
x
{
H
k
:
X
→
Y
:
k
∈ K}
∈
X
and a key
k
∈ K
, both chosen uniformly
at random, then outputs an
x
∈
X
such that
x
=
x
and
H
k
(
x
)
=
H
k
(
x
).
For more details about target collision resistant hash families we refer to Section 5 of
Cramer and Shoup [
149
].
3.2 Birthday attack
Computing preimages for a general hash function with
l
-bit output is expected to take
approximately 2
l
computations of the hash algorithm, but one
can fi
nd collisions much
more efficiently. Indeed, one can find collisions in roughly
√
π
2
l
−
1
applications of the
hash function using a randomised algorithm as follows: choose a subset
l
of
distinguished points (e.g., those whose
κ
least significant bits are all zero, where 0
<κ<
l/
4). Choose random starting values
x
0
∈{
D
⊂{
}
0
,
1
l
(Joux [
283
] suggests that these should
be distinguished points) and compute the sequence
x
n
=
0
,
1
}
H
(
x
n
−
1
)for
n
=
1
,
2
,...
until
x
n
∈
D
.Store(
x
0
,x
n
) (i.e., the starting point and the ending distinguished point) and repeat.
When the same distinguished point
x
is found twice then, assuming the starting points
x
0
and
x
0
are distinct, one can find a collision in the hash function by computing the full
sequences
x
i
and
x
j
and determining the smallest integers
i
and
j
such that
x
i
=
x
j
and
H
(
x
j
−
1
).
If we assume that values
x
i
are close to uniformly
distribu
ted in
hence the collision is
H
(
x
i
−
1
)
=
l
then, by the birth-
{
0
,
1
}
day paradox, one expects to have a collision after
π
2
l
/
2 strings have been encountered
