Cryptography Reference
In-Depth Information
useful hash function is required to be a very fast function to compute (not just
'easy', but in fact 'very easy'). In general a practical hash function is expected to
be much faster to compute than even a symmetric encryption operation.
SECURITY PROPERTY 1: PREIMAGE RESISTANCE
Ahash function should be
preimage-resistant
, whichmeans that it should be 'hard'
(in terms of efficiency and speed) to reverse a hash function. In other words, for a
hash function
h
, given an output (hash) value
z
it should be a difficult operation
to find any input value
x
that hashes to
z
(in other words,
h
(
x
)
z
). The term
'preimage-resistant' comes from the fact that the output
h
(
x
) of a function
h
is
often called the
image
of
x
, and hence
x
is referred to as a
preimage
of
h
(
x
).
Note that preimage resistance is often 'lazily' defined as
given h
(
x
)
, it is hard
to determine x
. This is 'lazy' because preimage resistance is actually a much
stronger property than that. Recall that because the hash function is a compression
function, there will bemany inputs with the same hash. Preimage resistancemeans
that if we obtain a hash value
h
(
x
) that was obtained by hashing
x
(but we do not
know what
x
was) then it is not just hard to find
x
, it is hard to find
any
input that
hashes to
h
(
x
).
In terms of complexity theory, security property 1 demands that reversing a
hash function involves a process that runs in exponential time. Indeed, for all
application purposes we require a hash function to be 'impossible' to reverse in
any practical sense. Note that functions with practical property 2 and security
property 1 are often referred to as
one-way functions
, as we mentioned in
Section 5.1.4.
=
SECURITY PROPERTY 2: SECOND PREIMAGE RESISTANCE
The second security property is similar, but subtly different, to preimage
resistance. A hash function should be
second-preimage-resistant
, which means
that given an input and its hash it should be hard to find a
different
input with the
same
hash. In other words, for a hash function
h
, given an input
x
and its output
(hash) value
h
(
x
) it should be a difficult operation to find any other input value
y
such that
h
(
y
)
h
(
x
).
Essentially the difference between the first two security properties is the starting
premise. Preimage resistance protects against an attacker who only has a hash
value (no input value) and is trying to reverse the hash function. Second preimage
resistance protects against an attacker who has an input value and its hash, and
now wants to find a different input value that results in the same hash.
Another way of thinking about this is to return to our earlier example of
payment card PINs. Recall that we observed that there will be many bank
customers with the same PIN. Consider your own bank and your own PIN. All the
other customers with the same PIN as you can be thought of as second preimages
of your bank's PIN derivation function. It is desirable that the PIN derivation
function is second-preimage-resistant since this makes it difficult for you to work
out who they are! (Strictly speaking, this analogy assumes that the PIN derivation
function is publicly known, which it may not be.)
=
