Cryptography Reference
In-Depth Information
it is thus desirable that the function
h
is computationally efficient. Even if we hash
large messages in the range of, say, hundreds of megabytes, it should be relatively
fast to compute. Another desirable property is that the output of a hash function is
of fixed length and independent of the input length. Practical hash functions have
output lengths between 128-512 bits. Finally, the computed fingerprint should be
highly sensitive to all input bits. That means even if we make minor modifications
to the input
x
, the fingerprint should look very different. This behavior is similar
to that of block ciphers. The properties which we just described are symbolized in
Figure 11.3.
!"#
Fig. 11.3
Principal input-output behavior of hash functions
11.2 Security Requirements of Hash Functions
As mentioned in the introduction, unlike all other crypto algorithms we have dealt
with so far, hash functions do not have keys. The question is now whether there are
any special properties needed for a hash function to be “secure”. In fact, we have
to ask ourselves whether hash functions have any impact on the security of an ap-
plication at all since they do not encrypt and they don't have keys. As is often the
case in cryptography, things can be tricky and there are attacks which use weak-
nesses of hash functions. It turns out that there are three central properties which
hash functions need to possess in order to be secure:
1. preimage resistance (or one-wayness)
2. second preimage resistance (or weak collision resistance)
3. collision resistance (or strong collision resistance)
These three properties are visualized in Figure 11.4. They are derived in the fol-
lowing.
