Cryptography Reference
In-Depth Information
SECURITY PROPERTY 3: COLLISION RESISTANCE
The third security property that a hash function should have is
collision resistance
,
which means that it should be hard to find two different inputs (of any length)
that, when fed into the hash function, result in the same hash being computed.
This property is sometimes described as requiring a hash function to be
collision-
free
. In other words, for a hash function
h
, it is hard to find two different inputs
x
and
y
such that
h
(
x
)
h
(
y
).
Note that, as we observed during our discussion of practical property 1, it
is impossible for a hash function
not
to have collisions. The point is that these
collisions should be hard to find. This makes it very difficult for an attacker to
find two input values with the same hash.
Going back to our PIN analogy, security property 3 states that, even though
many people share the same PIN, it should be very hard to find any two people
who have the same PIN.
=
RELATIONSHIPS BETWEEN THE THREE SECURITY PROPERTIES
The three security properties of a hash function are summarised in Figure 6.1.
While these three security properties are related, they are all
different
. The best
way to see this is to look at some different hash function applications and identify
the security properties that they require, which we do in Section 6.2.2.
There is only one clear relationship between the security properties: if a
function is collision-resistant then it is second-preimage-resistant. If a function
h
is collision-resistant then it is hard to find any pair of values
x
and
y
for which
h
(
x
)
=
h
(
y
). Since this is true for
any
pair of values, it is true that given a
particular
Preimage
resistance
x
?
h
(
x
)
h
x
h
h
(
x
)
Second
preimage
resistance
y
?
h
h
(
y
)
x
?
h
h
(
x
)
Collision
resistance
y
?
h
h
(
y
)
Figure 6.1.
Three security properties of a hash function
