HMAC - Hash-Based Message Authentication Code

    2024, Nov 27

    HMAC (Hash-Based Message Authentication Code) is a cryptographic algorithm used to ensure both integrity and authenticity of a message.

    It combines a cryptographic hash function (e.g., SHA-256) with a secret key, creating a tamper-proof mechanism for verifying that data has not been altered or forged.

    [TOC]

    Introduction

    Unlike encryption, which protects the confidentiality of data, HMAC ensures the data’s authenticity and integrity, making it a critical component of secure communication protocols.

    • Published in 1996 by Bellare, Canetti and Krawczyk
    • Standardized in RFC 2104, and in the document NIST FIPS PUB 198
    • Constructs a MAC from any hash function cryptographically secure
    • HMAC-MD5 and HMAC-SHA1 are very widely used in practice (TLS, IPSec, etc.)
    • Transition to HMAC-SHA2.

    Terms

    The following key terms are relevant to understand HMAC

    From nist.fips.198-1.pdf

    • Cryptographic key (key): a parameter used in conjunction with a cryptographic algorithm that determines the specific operation of that algorithm. In this Standard, the cryptographic key is used by the HMAC algorithm to produce a MAC on the data.

    • Hash function: a mathematical function that maps a string of arbitrary length (up to a predetermined maximum size) to a fixed length string.
    • Keyed-hash message authentication code (HMAC): a message authentication code that uses a cryptographic key in conjunction with a hash function.
    • Message Authentication Code (MAC): a cryptographic checksum that results from passing data through a message authentication algorithm. In this Standard, the message authentication algorithm is called HMAC, while the result of applying HMAC is called the MAC.
    • Secret key: a cryptographic key that is uniquely associated with one or more entitie. The term “secret” implies the need to protect the key from disclosure or substitution.

    Basic MAC Workflow

    • Alice and Bob agree on a shared secret K.
    • Alice sends her message X as well as the MAC value tto Bob.

    [\begin{aligned} τ = MAC_K (X) \end{aligned}]

    • Bob calculates t with the message X’ received.

    [\begin{aligned} τ = MAC_K (X’ ) \end{aligned}]

    • The message is accepted if and only if \(\begin{aligned} T = T' \end{aligned}\) where T'is the value of the MAC attached to the message.

    Security

    We say that a MAC is cryptographically secure if it is impossible in practice to forge a valid pair \(\begin{aligned} x', MAC_K(x') \end{aligned}\) with \(\begin{aligned} x_i \neq x' \end{aligned}\) from one or more pairs \(\begin{aligned} x_i, MAC_K(x_i) \end{aligned}\) The message x' does not need to make sense!

    How HMAC Works

    [\begin{aligned} MAC(text) = HMAC(K, text) = H((K_0 ⊕ opad )|| H((K_0 ⊕ ipad) || text)) \end{aligned}]

    HMAC uses a hash function and a secret key to compute a MAC (Message Authentication Code).

    Before describing the process, here two constants defined by the algorithm;

    o_pad = 0x5C5C5C . . . 5C i_pad = 0x363636 . . . 36

    Schema

    From nvlpubs.nist.gov - nist.fips.198-1.pdf

    hmac-schema

    Workflow

    The process involves the following steps:

    1. Preparation of Keys:

      • If the key is longer than the block size of the hash function (e.g., 64 bytes for SHA-256), it is hashed to produce a shorter key.
      • If the key is shorter than the block size, it is padded with zeros to match the block size.

    2. Key Mixing:

      • Two derived keys are created: an inner padded key ipad and an outer padded key opad).
      \[\begin{aligned} \text{ikey\_pad} = \text{key} \oplus o\_{pad} \end{aligned}\]
      \[\begin{aligned} \text{okey\_pad} = \text{key} \oplus i\_{pad} \end{aligned}\]

    3. Hashing Process:

      • Compute an intermediate hash using the inner padded key and the message:

    [\begin{aligned} H_{inner}=H(ikey_pad ∣∣ message) \end{aligned}]

    • Compute the final HMAC by hashing the outer padded key concatenated with the intermediate hash:

    [\begin{aligned} MAC =H(okey_pad ∣∣ H_{inner}) \end{aligned}]

    Here, H represents the hash function (e.g., SHA-256), ||denotes concatenation, and ⊕ denotes the XOR operation.

    Use Cases of HMAC

    HMAC is widely used in security scenarios:

    1. Data Integrity and Authentication:
      • Ensures that data has not been tampered with during transmission and that it originates from a trusted source.
    2. Secure Protocols:
      • HMAC is a core component of protocols like TLS (for HTTPS), IPsec, and SSH to ensure secure communication.
    3. API Authentication:
      • Used in systems like AWS, where API requests include HMAC-based signatures to authenticate clients.
    4. Password Storage and Key Derivation:
      • Forms a crucial part of algorithms like PBKDF2 for securely storing passwords.

    Security of HMAC

    HMAC provides robust security due to the following reasons:

    1. Resistance to Cryptographic Attacks:

      HMAC is secure as long as the underlying hash function (e.g., SHA-256) is cryptographically strong.

    2. Key-Based Authentication:

      The secret key ensures that only someone with access to the key can generate valid HMACs, protecting against forgery.

    3. Prevention of Length Extension Attacks:

      By incorporating a key into the hash computation, HMAC is resistant to length extension attacks that exploit properties of some hash functions.

    4. Collision Resistance:

      • Birthday attack

      HMAC is considered as secure against birthday attacks wich are totally impractical.

      As indicated in the RFC-2104, the strongest attack known against HMAC is based on the frequency of collisions for the hash function H (“birthday attack”). For example, a birthday attack with md5:

      “if we consider a hash function like MD5 where the output length equals L=16 bytes (128 bits) the attacker needs to acquire the correct message authentication tags computed (with th same secret key K!) on about 2**64 known plaintexts”.

      • Hash function vulnerable to collision attack

      Not totally sure about this paragraph

      I have seen different point of view against collision attack on the underlying hash function

      The RFC RFC-2104 states that the hash function must be replaced if the hash function contains serious flaws in the collision behaviour (e.g. collisions found after 2**30 messages)

      But on StackExchange, a user indicated that even if the hash function is vulnerable to collision, the attack must also perform a successful key recovery attack.

    HMAC with PBKDF2

    PBKDF2 (Password-Based Key Derivation Function 2) is a key derivation function that generates cryptographically strong keys from an input, generally a password. It uses HMAC as a pseudo-random function (PRF) to provide resistance against brute-force and dictionary attacks.

    Simple hashes function like SHA-256 are vulnerable to dictionary attacks

    To derive the key or the password, you will use a salt stored in a secure place to derive the same key again from the same input.

    See cryptobook.nakov.com - hmac-and-key-derivation and RFC 2898 (PKCS #5)

    Why Use HMAC in PBKDF2?

    • Cryptographic Strength: HMAC ensures the derived keys are resistant to cryptographic attacks, leveraging the strength of hash functions.
    • Slows Down Attackers: The iterative nature of PBKDF2, combined with HMAC, increases the computational effort required for brute-force attacks.
    • Salt Protection: The salt prevents the use of precomputed hash tables (rainbow tables).

    Conclusion

    HMAC offers a secure method to verify the integrity and authenticity of data.

    It can also be as a pseudo-random function (PRF) by a Key Derivation Algorithm such as PBKDF2 to derive a cryptographic key.

    References

    Feel free to contact me on
    # blockchain # wallet

    Share button

    You might also enjoy

    Hypergraph and Hypertree - Overview

    Tornado Cash Circuits - Overview

    Recurrent Neural Networks (RNNs) - Overview