Cryptography Reference
In-Depth Information
Fig. 11.4
The three security properties of hash functions
11.2.1 Preimage Resistance or One-Wayness
Hash functions need to be
one-way
: Given a hash output
z
it must be computation-
ally infeasible to find an input message
x
such that
z
=
h
(
x
). In other words, given a
fingerprint, we cannot derive a matching message. We demonstrate now why preim-
age resistance is important by means of a fictive protocol in which Bob is encrypting
the message but not the signature, i.e., he transmits the pair:
(
e
k
(
x
)
,
sig
k
pr
,
B
(
z
))
.
Here,
e
k
() is a symmetric cipher, e.g., AES, with some symmetric key shared by
Alice and Bob. Let's assume Bob uses an RSA digital signature, where the signature
is computed as:
z
d
s
= sig
k
pr
,
B
(
z
)
≡
mod
n
The attacker Oscar can use Bob's public key to compute
s
e
≡
z
mod
n
.
If the hash function is
not
one-way, Oscar can now compute the message
x
from
h
−
1
(
z
)=
x
. Thus, the symmetric encryption of
x
is circumvented by the signature,
which leaks the plaintext. For this reason,
h
(
x
) should be a one-way function.
In many other applications which make use of hash functions, for instance in key
derivation, it is even more crucial that they are preimage resistant.
11.2.2 Second Preimage Resistance or Weak Collision Resistance
For digital signatures with hash it is essential that two different messages do not
hash to the same value. This means it should be computationally infeasible to create
two different messages
x
1
=
x
2
with equal hash values
z
1
=
h
(
x
1
)=
h
(
x
2
)=
z
2
.
We differentiate between two different types of such collisions. In the first case,
x
1
