Cryptography Reference
In-Depth Information
There exist several other variants of block cipher based realizations of hash func-
tions. Two popular ones are shown in Figure 11.7.
Fig. 11.7
Davies-Meyer (left) and Miyaguchi-Preneel hash function constructions from block
ciphers
The expressions for the two hash functions are:
H
i
=
H
i
−
1
⊕
e
x
i
(
H
i
−
1
)
(Davies-Meyer)
H
i
=
H
i
−
1
⊕
x
i
⊕
e
g
(
H
i
−
1
)
(
x
i
)
(Miyaguchi-Preneel)
All three hash functions need to have initial values assigned to
H
0
. These can
be public values, e.g., the all-zero vector. All schemes have in common that the bit
size of the hash output is equal to the block width of the cipher used. In situations
where only preimage and second preimage resistance is required, block ciphers like
AES with 128-bit block width can be used, because they provide a security level of
128 bit against those attacks. For application which require collision resistance, the
128-bit length provided by most modern block ciphers is not sufficient. The birthday
attack reduces the security level to mere 64 bit, which is a computational complexity
that is within reach of PC clusters and certainly is doable for attackers with large
budgets.
One solution to this problem is to use Rijndael with a block width of 192 or
256 bit. These bit lengths provide a security level of 96 and 128 bit, respectively,
against birthday attacks, which is sufficient for most applications. We recall from
Section 4.1 that Rijndael is the cipher that became AES but allows block sizes of
128, 192 and 256 bit.
Another way of obtaining larger message digests is to use constructions which
are composed of several instances of a block cipher and which yield twice the width
of the block length
b
. Figure 11.8 shows such a construction for the case that a
cipher
e
is being employed whose key length is twice the block length. This is in
particular the case for AES with a 256-bit key. The message digest output are the
2
b
bit (
H
n
,
L
||
H
n
,
R
). If AES is being used, this output is 2
b
= 256 bit long, which
provides a high level of security against collision attacks. As can be seen from the
figure, the previous output of the left cipher
H
i
−
1
,
L
is fed back as input to both block
