Cryptography Reference
In-Depth Information
x
it is hard to find a different
y
such that
h
(
x
)
h
(
y
). In other words, the function
h
is also second-preimage-resistant. This makes intuitive sense. If finding
any
collision is hard, finding a
particular
collision will also be hard (indeed, it is
harder
).
A useful analogy is to consider a group of people, where each person is
associated with an input value
x
. We can consider the first name of person
x
as a 'hash'
h
(
x
) of that person's identity. It is much more likely that we will be
able to find any two people
x
and
y
with the same first name
h
(
x
)
=
h
(
y
) than
it is that we will be able to select one person whose name is (say) Bart, and then
find another person in the group whose name is also Bart. The same is true for
birthdays, as we will discuss more formally in Section 6.2.3.
The implication for hash functions, from an attacker's perspective, is that
collisions are always easier to find than second preimages. Hence attackers of
hash functions tend to focus on looking for collisions, and likewise designers of
hash functions try to make collisions as hard as possible to find.
Lastly, it is worth noting that while these three security properties are all
different and, as we will shortly see, they tend to be required by different types of
application, cryptographers have historically designed hash functions to have all
three of these security properties. There are three main reasons for this:
=
Potential for reuse
. Although a hash function may be employed in an application
that requires just one of the three security properties, it can be useful to
already have it implemented in case it is later needed for use in a different
application that requires a different security property. Hash functions are often
regarded as the 'Swiss army knife' of the cryptographic toolkit because of this
multifunctional capability.
Need for multiple properties
. Some applications of hash functions require more
than one of the security properties.
Similarity of the properties
. It is rather difficult to design a dedicated function
specifically for any of the three security properties and not the others. This is
partly because it has thus far been impossible to mathematically
prove
that a
function has any of these three security properties. It is only possible to design
a function that is
believed
to have these three security properties. This has had
serious implications in the past, as we will discuss in Section 6.2.4.
6.2.2
Applications of hash functions
We now look at three examples of applications of hash functions, each one
requiring a different security property.
APPLICATION REQUIRING PREIMAGE RESISTANCE
Hash functions provide a simple, and widely adopted, way of implementing
password storage protection. The idea is to store the passwords in a password
file in 'disguised' form so that they can be checked, yet anyone who gains access
