Can we use a block cipher to build a hash function or MAC?

/ / Published in Cybersecurity, EITC/IS/CCF Classical Cryptography Fundamentals, Applications of block ciphers, Modes of operation for block ciphers

Certainly, the use of block ciphers to construct hash functions and Message Authentication Codes (MACs) is a well-established practice in the field of cryptography. A block cipher is a symmetric key cipher that operates on fixed-size blocks of data using a shared secret key. Examples of block ciphers include the Advanced Encryption Standard (AES) and the Data Encryption Standard (DES). These ciphers are primarily designed for encryption and decryption, but their properties can be leveraged to create other cryptographic primitives such as hash functions and MACs.

Hash Functions from Block Ciphers

A cryptographic hash function is a deterministic algorithm that maps an arbitrary amount of data to a fixed-size string of bytes. The output, known as the hash value, should have several key properties: it should be computationally infeasible to reverse (preimage resistance), find two different inputs that produce the same output (collision resistance), or find a different input that produces the same output as a given input (second preimage resistance).

Merkle-Damgård Construction

One of the most well-known methods to construct a hash function from a block cipher is the Merkle-Damgård construction. This method uses a block cipher in a specific mode of operation to process the input data in blocks.

1. Initialization: Start with an initial value, known as the initialization vector (IV).
2. Processing: Divide the input message into fixed-size blocks. For each block, use the block cipher to transform the current state.
3. Finalization: After processing all blocks, the final state is the hash value.

For instance, let E be a block cipher, K a key, IV the initialization vector, and M the message divided into blocks M_1, M_2, \dots, M_n. The hash function H(M) can be defined as follows:

    \[ H(M) = E_K(E_K(\dots E_K(IV, M_1), M_2) \dots, M_n) \]

This construction ensures that the hash function inherits the security properties of the underlying block cipher, assuming the block cipher is secure.

Davies-Meyer Construction

Another popular method is the Davies-Meyer construction, which uses a block cipher in a feed-forward manner to build a hash function. The construction is defined as follows:

    \[ H_i = E_K(H_{i-1}, M_i) \oplus H_{i-1} \]

Where H_i is the hash value after processing the i-th block, E_K is the block cipher encryption function with key K, and \oplus denotes the bitwise XOR operation. The initial value H_0 is typically set to a fixed constant.

Message Authentication Codes (MACs) from Block Ciphers

A Message Authentication Code (MAC) is a short piece of information used to authenticate a message and ensure its integrity. A MAC algorithm takes as input a message and a secret key, and outputs a MAC tag. The recipient, who also possesses the secret key, can verify the authenticity of the message by recomputing the MAC tag and comparing it to the received tag.

CBC-MAC

One of the simplest and most widely used methods to construct a MAC from a block cipher is the Cipher Block Chaining Message Authentication Code (CBC-MAC). This method uses the CBC mode of operation of a block cipher to process the message, and the final block is used as the MAC tag.

1. Initialization: Start with an initialization vector (IV) set to zero.
2. Processing: Encrypt each block of the message using the block cipher in CBC mode.
3. Finalization: The output of the final block encryption is the MAC tag.

For example, let E be a block cipher, K a key, M the message divided into blocks M_1, M_2, \dots, M_n, and IV the initialization vector. The CBC-MAC tag T is computed as follows:

    \[ C_0 = IV \]

    \[ C_i = E_K(C_{i-1} \oplus M_i) \text{ for } i = 1, \dots, n \]

    \[ T = C_n \]

The security of CBC-MAC relies on the uniqueness of the message length and the key. To ensure security, it is recommended to use different keys for encryption and MAC generation.

HMAC

Another widely used MAC construction is the Hash-based Message Authentication Code (HMAC), which can be built using a block cipher-based hash function. HMAC provides better security properties and is more robust against certain types of attacks.

HMAC is defined as follows:

    \[ HMAC(K, M) = H((K' \oplus opad) \| H((K' \oplus ipad) \| M)) \]

Where:
– H is a hash function (e.g., one constructed using a block cipher).
– K' is the key K padded to the block size of the hash function.
– \oplus denotes the bitwise XOR operation.
– opad and ipad are fixed padding constants.
– \| denotes concatenation.

Security Considerations

When using block ciphers to construct hash functions and MACs, several security considerations must be taken into account:

1. Key Management: The security of the constructions relies on the secrecy of the key. Proper key management practices must be followed to ensure that keys are not compromised.
2. Collision Resistance: For hash functions, collision resistance is important. The block cipher must be secure against attacks that could lead to collisions in the hash function.
3. Message Length: For CBC-MAC, the security can be compromised if the same key is used for messages of different lengths. It is important to ensure that the key is unique for each message length or use additional techniques to handle variable-length messages.
4. Padding: Proper padding schemes must be used to ensure that the message blocks are of the correct size for the block cipher. Incorrect padding can lead to security vulnerabilities.
5. Performance: The performance of the constructions depends on the efficiency of the underlying block cipher. High-performance block ciphers such as AES are preferred for practical implementations.

Practical Examples

Example of CBC-MAC

Consider a block cipher E with a block size of 128 bits and a key K. Let the message M be "Hello, World!" padded to the nearest block size. The message is divided into blocks M_1, M_2, and the CBC-MAC tag is computed as follows:

1. Initialization: IV = 0
2. Processing:
– C_1 = E_K(IV \oplus M_1)
– C_2 = E_K(C_1 \oplus M_2)
3. Finalization: T = C_2

The resulting tag T is used as the MAC for the message.

Example of HMAC

Consider a hash function H constructed using a block cipher with a block size of 512 bits. Let the key K be "secretkey" and the message M be "Hello, World!". The HMAC tag is computed as follows:

1. Key Padding: Pad the key K to the block size of the hash function to obtain K'.
2. Inner Hash: Compute the inner hash:
– inner = H((K' \oplus ipad) \| M)
3. Outer Hash: Compute the outer hash:
– outer = H((K' \oplus opad) \| inner)

The resulting tag outer is the HMAC for the message.

Block ciphers are versatile cryptographic primitives that can be used to construct both hash functions and MACs. The Merkle-Damgård and Davies-Meyer constructions are popular methods for building hash functions from block ciphers, while CBC-MAC and HMAC are widely used MAC constructions. The security of these constructions depends on the properties of the underlying block cipher, proper key management, and adherence to best practices in cryptographic implementation.

Other recent questions and answers regarding Modes of operation for block ciphers:

View more questions and answers in Modes of operation for block ciphers

More questions and answers:

Tagged under: , , , , ,