HMAC

From Wikipedia, the free encyclopedia

A keyed-hash message authentication code, or HMAC, is a type of message authentication code (MAC) calculated using a cryptographic hash function in combination with a secret key. As with any MAC, it may be used to simultaneously verify both the data integrity and the authenticity of a message. Any iterative cryptographic hash function, such as MD5 or SHA-1, may be used in the calculation of an HMAC; the resulting MAC algorithm is termed HMAC-MD5 or HMAC-SHA-1 accordingly. The cryptographic strength of the HMAC depends upon the cryptographic strength of the underlying hash function, on the size and quality of the key and the size of the hash output length in bits.

An iterative hash function breaks up a message into blocks of a fixed size and iterates over them with a compression function. For example, MD5 and SHA-1 operate on 512-bit blocks. The size of the output of HMAC is the same as that of the underlying hash function (128 or 160 bits in the case of MD5 and SHA-1), although it can be truncated if desired. Truncating the hash image reduces the security of the MAC which is upper bound by the birthday attack.

HMAC is defined as:

$\mathrm{HMAC}_K(m) = h\Bigg((K \oplus \mathrm{opad}) \| h\Big((K \oplus \mathrm{ipad}) \| m\Big)\Bigg),$

where $h$ is an iterated hash function, $K$ is a secret key padded with extra zeros to the block size of the hash function, $m$ is the message to be authenticated, $\|$ denotes concatenation, $\oplus$ denotes exclusive or, and the outer padding $\mathrm{opad} = \texttt{0x5c5c5c\ldots5c5c}$ and inner padding $\mathrm{ipad} = \texttt{0x363636\ldots3636}$ are two one-block–long hexadecimal constants.

The construction and analysis of HMACs was first published in 1996 by Mihir Bellare, Ran Canetti, and Hugo Krawczyk, who also wrote RFC 2104. FIPS PUB 198 generalizes and standardizes the use of HMACs. HMAC-SHA-1 and HMAC-MD5 are used within the IPsec and TLS protocols.

1 Example usage
2 Security
3 External links
4 References

[edit] Example usage

A pizza restaurant that suffers from attackers that place bogus Internet orders may insist that all its customers deposit a secret key with the restaurant. Along with an order, a customer must supply the order's HMAC digest, computed using the customer's secret key. The restaurant, knowing the customer's secret key, can then verify that the order originated from the stated customer and has not been tampered with.

[edit] Security

The cryptographic strength of the HMAC depends upon the cryptographic strength of the underlying hash function, on the size and quality of the key and the size of the hash output length in bits. As outlined in "Keying Hash Functions for Message Authentication", MACs can be vulnerable to birthday, collision, extension, and other attacks.

In the recently (2006) published paper "On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1", by Jongsung Kim, Alex Biryukov, Bart Preneel, Seokhie Hong, claim to have devised: "two new distinguishers of the structure of HMAC, called differential and rectangle distinguishers, and use them to discuss the security of HMAC based on HAVAL, MD4, MD5, SHA-0 and SHA-1. We show how to distinguish HMAC with reduced or full versions of these cryptographic hash functions from a random function or from HMAC with a random function. We also show how to use our differential distinguisher to devise a forgery attack on HMAC. Our distinguishing and forgery attacks can also be mounted on NMAC based on HAVAL, MD4, MD5, SHA-0 and SHA-1. Furthermore, we show that our differential and rectangle distinguishers can lead to second-preimage attacks on HMAC and NMAC.". They go on to claim: "With these distinguishing and forgery attacks we have shown that HMAC with the full versions of 3-pass HAVAL and SHA-0 can be distinguished from HMAC with a random function, and HMAC with the full version of MD4 can be forged. These distinguishing and forgery attacks have also been applied to HMAC based on reduced versions of MD5 and SHA-1. All these attacks do not contradict the security proof of HMAC, but they improve our understanding of the security of HMAC based on existing cryptographic hash functions."

[edit] External links

RFC 2104, HMAC: Keyed-Hashing for Message Authentication
RFC 2202, HMAC-MD5 and HMAC-SHA1 Test Vectors, HMAC-SHA1 implementation in C
FIPS PUB 198, The Keyed-Hash Message Authentication Code
HMAC Algorithm in Detail
Python HMAC implementation
An introduction to HMAC

[edit] References

Mihir Bellare, Ran Canetti and Hugo Krawczyk, Keying Hash Functions for Message Authentication, CRYPTO 1996, pp1–15 (PS or PDF).
Mihir Bellare, Ran Canetti and Hugo Krawczyk, Message authentication using hash functions: The HMAC construction, CryptoBytes 2(1), Spring 1996 (PS or PDF).
Jongsung Kim, Alex Biryukov, Bart Preneel, Seokhie Hong, "On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1", 2006. (pdf)

Cryptographic hash functions and Message authentication codes (MACs) v • d • e
Hash algorithms: Gost-Hash \| HAS-160 \| HAS-V \| HAVAL \| MDC-2 \| MD2 \| MD4 \| MD5 \| N-Hash \| RadioGatún \| RIPEMD \| SHA family \| Snefru \| Tiger \| VEST \| WHIRLPOOL \| crypt(3) DES
MAC algorithms: DAA \| 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 \| Rainbow table \| 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