Cryptography Reference
In-Depth Information
algorithm would have to work for all functions
h
k
in order to include the one that is
chosen at random. Since in what follows we are only going to deal with unkeyed hash
functions, we will not go into the details of the formal definition for keyed functions
and we refer instead to [109, 4.6.1].
n
which is efficiently computable and such that it is hard (in the practical sense) to find
a
collision
for
h
, i.e., a pair
x
}
∗
→{
Definition 5.9
A
collision resistant hash function
is a function
h
:{
0
,
1
0
,
1
}
x
∈{
}
∗
such that
x
x
and
h
x
)
,
0
,
1
=
(
x
)
=
h
(
.
Remark 5.4
We stress again that the definition of collision resistance just given is
informal and hence imprecise but is very useful in practice. It just means that no
efficient algorithm for computing collisions is known to exist. For example, if the
best collision-finding algorithm known for a given function is estimated to take one
million years with the available computing resources, then we clearly would regard
the function as collision resistant.
In addition to collision resistance, there are other properties that are often consid-
ered for hash functions for cryptographic use. The most important of these properties
are the following:
}
∗
,itis
•
Second preimage resistance
: This property means that, given
x
∈{
0
,
1
hard to find an
x
=
x
)
. This property is also called
weak
collision resistance
since any
h
which is collision resistant is obviously second
preimage resistant.
x
such that
h
(
x
)
=
h
(
}
∗
,itis
•
Preimage resistance
: This means that, for a randomly chosen
x
∈{
0
,
1
,an
x
∈{
}
∗
such that
h
x
)
=
hard to find, given
y
=
h
(
x
)
0
,
1
(
y
. This essentially
says that
h
is a
one-way function
.
Remarks 5.4
1. The relation between preimage resistance and collision resistance has some sub-
tle points. It can be shown that a collision resistant function need not be preimage
resistant (see Exercise 5.12 below) but, intuitively, it seems clear that any “gen-
uine” collision resistant or even, second preimage resistant function must also
be preimage resistant. The reason is that if the latter property does not hold,
then given
x
}
∗
we compute
y
and find a preimage
x
such that
∈{
0
,
1
=
h
(
x
)
x
we have found a second preimage. If
h
is a
“genuine” hash function for which any hash value has a large number of preim-
ages, then
x
x
)
=
h
(
y
=
h
(
x
)
, so that if
x
=
x
indeed holds with high probability. Hence, for such “genuine”
hash functions, we have that collision resistance implies second preimage resis-
tance and this, in turn, implies that the function is one-way. We refer to [90,
8.4] where this point is discussed in detail for a very general class of keyed hash
functions.
2. The converses of the implications mentioned in the item above do not hold.
As shown below, finding a second preimage (or, in other words, showing that
h
is not second preimage resistant by finding a collision with a given
x
in the
domain of
h
) requires a much larger computational effort than merely finding
=
