Message Authentication Codes: An Overview

In recent years, there has been a growing interest in developing a Message Authentication Code (MAC) derived from cryptographic hash functions, such as SHA-1. The main reasons for this interest include:

1. Efficiency: Cryptographic hash functions generally execute faster in software compared to traditional encryption algorithms like DES.

2. Availability: There is a wealth of library code available for cryptographic hash functions that developers can utilize.

Although hash functions like SHA-1 can be useful, they were not originally designed to serve as a MAC since they do not utilize a secret key. To enhance security by incorporating a secret key, multiple proposals have emerged, with HMAC (Hash-based Message Authentication Code) being the most widely accepted. HMAC is defined in RFC 2104 and has been designated as the mandatory MAC for protocols such as IP Security, Transport Layer Security (TLS), and Secure Electronic Transaction (SET).

HMAC Design Objectives

RFC 2104 outlines several important design objectives for HMAC:

• Compatibility: HMAC should use existing hash functions without modifications, particularly those that perform well in software and for which implementation code is readily available.
  
  
• Flexibility: HMAC must allow easy replacement of the embedded hash function to accommodate faster or more secure algorithms as they become available.
  
  
• Performance: The performance of the hash function should be preserved, avoiding significant degradation in performance when implemented in HMAC.
  
  
• Simplicity: Keys should be managed in a straightforward manner.
  
  
• Security Assurance: A clear cryptographic analysis of the strength of the authentication mechanism should be based on reasonable assumptions about the embedded hash function.

The first two objectives significantly enhance the acceptability of HMAC. By treating the hash function as a “black box,” developers can leverage existing implementations, ensuring that HMAC can incorporate different hash functions easily. Moreover, if a hash function's security is compromised, the HMAC can replace it with a more secure alternative without requiring extensive changes.

HMAC Algorithm Flow

The operation of HMAC requires various defined terms:

• H: The embedded hash function (e.g., SHA-1).
  
  
• M: The message input to HMAC, which includes required padding.
  
  
• Yi: The ith block of the message \(M\), where \(0 \leq i \leq (L-1)\) and \(L\) is the total number of blocks in \(M\).
  
  
• b: Number of bits in a block.
  
  
• n: Length of the hash output from the embedded hash function.
  
  
• K: The secret key.
  
  
• K': The key padded with zeros to ensure it is \(b\) bits long.
  
  
• ipad: A specific byte pattern used in XOR operations.
  
  
• opad: Another byte pattern used in XOR operations.

HMAC can be mathematically expressed as:

\[

\text{HMAC}(K, M) = H[(K \oplus \text{opad}) \| H[(K \oplus \text{ipad}) \| M]]

\]

Process Steps:

1. Pad \(K\) with zeros to create a \(b\)-bit string.
2. XOR \(K'\) with \(\text{ipad}\) to form a padded block \(S_i\).
3. Append the message \(M\) to \(S_i\).
4. Apply the hash function \(H\) to the combined output from step 3.
5. XOR \(K\) with \(\text{opad}\) to form another padded block \(S_o\).
6. Append the hash result from step 4 to \(S_o\).
7. Apply \(H\) to the combined output from step 6 to produce the final HMAC output.

This method ensures that the resulting HMAC maintains similar performance speeds as the underlying hash function for lengthy messages.

MACs Based on Block Ciphers

The following sections discuss several MACs that utilize block ciphers for authentication.

Cipher-based Message Authentication Code (CMAC)

The Cipher-based Message Authentication Code (CMAC) is designed for use with AES and Triple DES, as specified in NIST Special Publication 800-38B. In CMAC, messages are divided into blocks of the cipher’s length. For example, AES uses a block length of 128 bits, while Triple DES uses 64 bits.

The CMAC process involves the following steps:

1. The message is split into \(n\) blocks (e.g., \(M_1, M_2, \ldots, M_n\)).
2. It utilizes a secret key \(K\) for encryption.
3. CMAC is calculated by encrypting each block using the key and chaining the output to the next block.

If the message does not align with the block size, the last block is padded to fit.