Cryptography Reference
In-Depth Information
•
A hash function
h
is
collision resistant
or
strong collision resistant
if it is
computationally infeasible to find two input words
x, x
∈
Σ
in
with
x
=
x
and
h
(
x
)=
h
(
x
).
There are some comments to make at this point:
•
In some literature, collision resistant hash functions are also called
collision
free
. This term is inappropriate, because collisions always occur if one uses
hash functions (i.e., functions that hash arbitrarily sized arguments to a fixed
size). Consequently, the term collision free is not used as an attribute to
cryptographic hash functions in this topic.
•
In a complexity-theoretic setting, one cannot say that finding a collision for
a given hash function is a difficult problem. In fact, finding a collision (for
a given hash function) is a problem instance rather than a problem (refer to
Section 6.2 for a discussion about the difference between a problem and a
problem instance). This is because there is always an efficient algorithm that
finds a collision, namely one that simply outputs two input words that hash
to the same value. Thus, the concept of collision resistance only makes sense
if one considers a sufficiently large class (or family) of hash functions from
which one is chosen at random. An algorithm to find collisions must then work
for all hash functions of the class, including the one that is chosen at random.
•
A collision resistant hash function must be second-preimage resistant. Oth-
erwise it is possible to find a second preimage for an arbitrarily chosen input
word, and this second preimage then yields a collision. The converse, however,
is not true—that is, a second-preimage resistant hash function must not be
collision resistant (that's why we used the terms
weak collision resistant
and
strong collision resistant
in the first place). Consequently, collision resistance
implies second-preimage resistance, but not vice versa.
•
A (strong or weak) collision resistant hash function must not be preimage
resistant. For example, let
g
be a collision resistant hash function with an
n
-
bit output and
h
a pathological (
n
+1)-bit hash function that is defined as
follows:
2
h
(
x
)=
1
||
x
if
|
x
|
=
n
0
||
g
(
x
)
otherwise
2
This example is taken from Ueli Maurer's seminar entitled “Cryptography—Fundamentals and
Applications.”
