Hash functions based on block ciphers

From Wikipedia, the free encyclopedia

In cryptography, there are several methods to use a block cipher to build a cryptographic hash function. The methods resemble the block cipher modes of operation usually used for encryption.

Some methods to turn any normal block cipher into the compression function for a hash function are Davies-Meyer, Miyaguchi-Preneel, Matyas-Meyer-Oseas, MDC-2 and MDC-4. They are then used inside the Merkle-Damgård structure to build the actual hash function. These methods are described in detail further down. (MDC-2 is also the name of a hash function patented by IBM.)

Using a block cipher as a hash function is usually much slower than using a specially designed hash function. But, in some cases it is easier because a single implementation of a block cipher can be used for both block cipher and a hash function. It can also save code space in very tiny embedded systems like for instance smart cards or nodes in cars or other machines.

If a block cipher has a block size of say 128 bits most of the methods create a hash function that has the block size of 128 bits and produces a hash of 128 bits. But there are also methods to make hashes with double the hash size compared to the block size of the block cipher used. So a 128-bit block cipher can be turned into a 256-bit hash function.

The hash function is considered secure if the following conditions are met:

• The block cipher is secure.
• The resulting hash size is big enough. 64-bit is too small, 128-bit might be enough.
• The last block is properly length padded prior to the hashing. (See the Merkle-Damgård structure below.) Length padding is normally implemented and handled internally in specialised hash functions like SHA-1 etc.

Contents 1 The Merkle-Damgård structure 2 Davies-Meyer 3 Matyas-Meyer-Oseas 4 Miyaguchi-Preneel 5 See also 6 References

[edit] The Merkle-Damgård structure

Main article: Merkle-Damgård construction

A hash function must be able to process an arbitrary-length message into a fixed-length output. This can be achieved by breaking the input up into a series of equal-sized blocks, and operating on them in sequence using a compression function. The compression function can either be specially designed for hashing or be built from a block cipher.

The last block processed should also be length padded, this is crucial to the security of this construction. This construction is called the Merkle-Damgård construction. Most widely used hash functions, including SHA-1 and MD5, take this form.

[edit] Davies-Meyer

The Davies-Meyer hash compression function feeds each block of the message (m_i) as the key to the block cipher. It feeds the previous hash value (H_i-1) as the cleartext to be encrypted. The output ciphertext is then also XORed () with the previous hash value (H_i-1) to produce the next hash value (H_i). In the first round when there is no previous hash value it uses a constant pre-specified initial value (H₀).

If the block cipher uses for instance 256-bit keys then each message block (m_i) is a 256-bit chunk of the message. If the same block cipher uses a block size of 128 bits then the input and output hash values in each round is 128 bits.

Variations of this method replace XOR with any other group operation, such as addition on 32-bit unsigned integers.

[edit] Matyas-Meyer-Oseas

The Matyas-Meyer-Oseas hash compression function can be considered the dual (the opposite) of Davies-Meyer.

It feeds each block of the message (m_i) as the cleartext to be encrypted. The output ciphertext is then also XORed () with the same message block (m_i) to produce the next hash value (H_i). The previous hash value (H_i-1) is fed as the key to the block cipher. In the first round when there is no previous hash value it uses a constant pre-specified initial value (H₀).

If the block cipher has different block and key sizes the hash value (H_i-1) will have the wrong size for use as the key. The cipher might also have other special requirements on the key. Then the hash value is first fed through the function g( ) to be converted/padded to fit as key for the cipher.

[edit] Miyaguchi-Preneel

The Miyaguchi-Preneel hash compression function is an extended variant of Matyas-Meyer-Oseas. It was independently proposed by Shoji Miyaguchi and Bart Preneel.

It feeds each block of the message (m_i) as the cleartext to be encrypted. The output ciphertext is then XORed () with the same message block (m_i) and then also XORed with the previous hash value (H_i-1) to produce the next hash value (H_i). The previous hash value (H_i-1) is fed as the key to the block cipher. In the first round when there is no previous hash value it uses a constant pre-specified initial value (H₀).

If the block cipher has different block and key sizes the hash value (H_i-1) will have the wrong size for use as the key. The cipher might also have other special requirements on the key. Then the hash value is first fed through the function g( ) to be converted/padded to fit as key for the cipher.

The roles of m_i and H_i-1 may be switched, so that H_i-1 is encrypted under the key m_i. Thus making this method an extension of Davies-Meyer instead.

[edit] See also

• WHIRLPOOL - A cryptographic hash function built using the Miyaguchi-Preneel hash construction and a block cipher similar to Square and AES.
• CBC-MAC, OMAC and PMAC - Methods to turn block ciphers into message authentication codes (MACs).

[edit] References

• Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone (2001), chapter 9.

Cryptographic hash functions and Message authentication codes (MACs) v • d • e
Hash algorithms: Gost-Hash | HAS-160 | HAVAL | MDC-2 | MD2 | MD4 | MD5 | N-Hash | RIPEMD | SHA family | Snefru | Tiger | VEST | WHIRLPOOL | crypt(3) DES
MAC algorithms: Data Authentication Code | CBC-MAC | HMAC | OMAC/CMAC | PMAC | UMAC | Poly1305-AES | VEST
Authenticated encryption modes: CCM | EAX | GCM | OCB | VEST   Attacks: Birthday attack | Collision attack | Preimage attack | Brute force attack
Standardization: CRYPTREC | NESSIE   Misc: Avalanche effect | Hash collision | Hash functions based on block ciphers
Cryptography v • d • e
History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography
Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers