HMAC: Difference between revisions
m →Implementation: Move comment to another line. Currently too long to be correctly viewed in a 720p |
m →Examples of HMAC (MD5, SHA1, SHA256): Wrap answer in another line. Too short to be viewed in a 720p |
||
Line 140: | Line 140: | ||
HMAC_MD5("key", "The quick brown fox jumps over the lazy dog") = 0x80070713463e7749b90c2dc24911e275 |
HMAC_MD5("key", "The quick brown fox jumps over the lazy dog") = 0x80070713463e7749b90c2dc24911e275 |
||
HMAC_SHA1("key", "The quick brown fox jumps over the lazy dog") = 0xde7c9b85b8b78aa6bc8a7a36f70a90701c9db4d9 |
HMAC_SHA1("key", "The quick brown fox jumps over the lazy dog") = 0xde7c9b85b8b78aa6bc8a7a36f70a90701c9db4d9 |
||
HMAC_SHA256("key", "The quick brown fox jumps over the lazy dog") = |
HMAC_SHA256("key", "The quick brown fox jumps over the lazy dog") = 0xf7bc83f430538424b13298e6aa6fb143ef4d59a14946 |
||
175997479dbc2d1a3cd8 |
|||
<!-- HMAC_SHA512("key", "The quick brown fox jumps over the lazy dog") = 0xb42af09057bac1e2d41708e48a902e09b5ff7f12ab428a4fe86653c73dd248fb82f948a549f7b791a5b41915ee4d1ec3935357e4e2317250d0372afa2ebeeb3a --> |
<!-- HMAC_SHA512("key", "The quick brown fox jumps over the lazy dog") = 0xb42af09057bac1e2d41708e48a902e09b5ff7f12ab428a4fe86653c73dd248fb82f948a549f7b791a5b41915ee4d1ec3935357e4e2317250d0372afa2ebeeb3a --> |
||
Revision as of 09:15, 2 November 2014
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7f/SHAhmac.svg/400px-SHAhmac.svg.png)
In cryptography, a keyed-hash message authentication code (HMAC) is a specific construction for calculating a message authentication code (MAC) involving a cryptographic hash function in combination with a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and the authentication of a message. Any 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-SHA1 accordingly. The cryptographic strength of the HMAC depends upon the cryptographic strength of the underlying hash function, the size of its hash output, and on the size and quality of the key.
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 or SHA-1, respectively), although it can be truncated if desired.
The definition and analysis of the HMAC construction was first published in 1996 by Mihir Bellare, Ran Canetti, and Hugo Krawczyk,[1] who also wrote RFC 2104. This paper also defined a variant called NMAC that is rarely, if ever, used. FIPS PUB 198 generalizes and standardizes the use of HMACs. HMAC-SHA1 and HMAC-MD5 are used within the IPsec and TLS protocols.
Definition (from RFC 2104)
where
- H is a cryptographic hash function,
- K is a secret key padded to the right with extra zeros to the input block size of the hash function, or the hash of the original key if it's longer than that block size,
- m is the message to be authenticated,
- | denotes concatenation,
- ⊕ denotes exclusive or (XOR),
- opad is the outer padding (0x5c5c5c…5c5c, one-block-long hexadecimal constant),
- and ipad is the inner padding (0x363636…3636, one-block-long hexadecimal constant).
Implementation
The following pseudocode demonstrates how HMAC may be implemented. Blocksize is 64 (bytes) when using one of the following hash functions: SHA-1, MD5, RIPEMD-128/160.[2]
function hmac (key, message) if (length(key) > blocksize) then key = hash(key) // keys longer than blocksize are shortened end if if (length(key) < blocksize) then key = key ∥ [0x00 * (blocksize - length(key))] // keys shorter than blocksize are zero-padded (where ∥ is concatenation) end if o_key_pad = [0x5c * blocksize] ⊕ key // Where blocksize is that of the underlying hash function i_key_pad = [0x36 * blocksize] ⊕ key // Where ⊕ is exclusive or (XOR) return hash(o_key_pad ∥ hash(i_key_pad ∥ message)) // Where ∥ is concatenation end function
The following is a Python implementation of HMAC-MD5:
#!/usr/bin/env python
from hashlib import md5
trans_5C = bytearray((x ^ 0x5c) for x in range(256))
trans_36 = bytearray((x ^ 0x36) for x in range(256))
blocksize = md5().block_size # 64
def hmac_md5(key, msg):
if len(key) > blocksize:
key = md5(key).digest()
key = key + bytearray(blocksize - len(key))
o_key_pad = key.translate(trans_5C)
i_key_pad = key.translate(trans_36)
return md5(o_key_pad + md5(i_key_pad + msg).digest())
if __name__ == "__main__":
# This is one example from the appendix of RFC 2104
h = hmac_md5(b"Jefe", b"what do ya want for nothing?")
print(h.hexdigest()) # 750c783e6ab0b503eaa86e310a5db738
Python includes an hmac module,[3] so the function above can be replaced by a shorter version.
def hmac_md5(key, msg):
return hmac.HMAC(key, msg, md5)
HMAC_SHA256("", "")
Design principles
The design of the HMAC specification was motivated by the existence of attacks on more trivial mechanisms for combining a key with a hash function. For example, one might assume the same security that HMAC provides could be achieved with MAC = H(key ∥ message). However, this method suffers from a serious flaw: with most hash functions, it is easy to append data to the message without knowing the key and obtain another valid MAC ("length-extension attack"). The alternative, appending the key using MAC = H(message ∥ key), suffers from the problem that an attacker who can find a collision in the (unkeyed) hash function has a collision in the MAC (as two messages m1 and m2 yielding the same hash will provide the same start condition to the hash function before the appended key is hashed, hence the final hash will be the same). Using MAC = H(key ∥ message ∥ key) is better, but various security papers have suggested vulnerabilities with this approach, even when two different keys are used.[1][4][5]
No known extensions attacks have been found against the current HMAC specification which is defined as H(key ∥ H(key ∥ message)) because the outer application of the hash function masks the intermediate result of the internal hash. The values of ipad and opad are not critical to the security of the algorithm, but were defined in such a way to have a large Hamming distance from each other and so the inner and outer keys will have fewer bits in common. The security reduction of HMAC does require them to be different in at least one bit.
The Keccak hash function, that was selected by NIST as the SHA-3 competition winner, doesn't need this nested approach and can be used to generate a MAC by simply prepending the key to the message.[6]
Security
The cryptographic strength of the HMAC depends upon the size of the secret key that is used. The most common attack against HMACs is brute force to uncover the secret key. HMACs are substantially less affected by collisions than their underlying hashing algorithms alone.[7] [8] [9] Therefore, HMAC-MD5 does not suffer from the same weaknesses that have been found in MD5.
In 2006, Jongsung Kim, Alex Biryukov, Bart Preneel, and Seokhie Hong showed how to distinguish HMAC with reduced versions of MD5 and SHA-1 or full versions of HAVAL, MD4, and SHA-0 from a random function or HMAC with a random function. Differential distinguishers allow an attacker to devise a forgery attack on HMAC. Furthermore, differential and rectangle distinguishers can lead to second-preimage attacks. HMAC with the full version of MD4 can be forged with this knowledge. These attacks do not contradict the security proof of HMAC, but provide insight into HMAC based on existing cryptographic hash functions. [10]
In improperly-secured systems a timing attack can be performed to find out a HMAC digit by digit.[11]
Examples of HMAC (MD5, SHA1, SHA256)
Here are some empty HMAC values:
HMAC_MD5("", "") = 0x74e6f7298a9c2d168935f58c001bad88 HMAC_SHA1("", "") = 0xfbdb1d1b18aa6c08324b7d64b71fb76370690e1d HMAC_SHA256("", "") = 0xb613679a0814d9ec772f95d778c35fc5ff1697c493715653c6c712144292c5ad
Here are some non-empty HMAC values, assuming 8-bit ASCII or UTF-8 encoding:
HMAC_MD5("key", "The quick brown fox jumps over the lazy dog") = 0x80070713463e7749b90c2dc24911e275 HMAC_SHA1("key", "The quick brown fox jumps over the lazy dog") = 0xde7c9b85b8b78aa6bc8a7a36f70a90701c9db4d9 HMAC_SHA256("key", "The quick brown fox jumps over the lazy dog") = 0xf7bc83f430538424b13298e6aa6fb143ef4d59a14946 175997479dbc2d1a3cd8
References
- ^ a b Bellare, Mihir; Canetti, Ran; Krawczyk, Hugo (1996). "Keying Hash Functions for Message Authentication".
{{cite web}}
: CS1 maint: postscript (link) - ^ RFC 2104, section 2, "Definition of HMAC", page 3.
- ^ hmac — Keyed-Hashing for Message Authentication, Python Software Foundation, retrieved 7 May 2014
- ^ Preneel, Bart; van Oorschot, Paul C. (1995). "MDx-MAC and Building Fast MACs from Hash Functions". Retrieved 28 August 2009.
{{cite web}}
: CS1 maint: postscript (link) - ^ Preneel, Bart; van Oorschot, Paul C. (1995). "On the Security of Two MAC Algorithms". Retrieved 28 August 2009.
{{cite web}}
: CS1 maint: postscript (link) - ^ Keccak team. "Strengths of Keccak - Design and security". Retrieved 30 January 2013.
Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.
- ^ Bruce Schneier (August 2005). "SHA-1 Broken". Retrieved 9 January 2009.
although it doesn't affect applications such as HMAC where collisions aren't important
- ^ IETF (February 1997). "RFC 2104". Retrieved 3 December 2009.
The strongest attack known against HMAC is based on the frequency of collisions for the hash function H ("birthday attack") [PV,BCK2], and is totally impractical for minimally reasonable hash functions.
- ^ Bellare, Mihir (June 2006). "New Proofs for NMAC and HMAC: Security without Collision-Resistance". In Dwork, Cynthia (ed.). Advances in Cryptology – Crypto 2006 Proceedings. Lecture Notes in Computer Science 4117. Springer-Verlag. Retrieved 25 May 2010.
This paper proves that HMAC is a PRF under the sole assumption that the compression function is a PRF. This recovers a proof based guarantee since no known attacks compromise the pseudorandomness of the compression function, and it also helps explain the resistance-to-attack that HMAC has shown even when implemented with hash functions whose (weak) collision resistance is compromised.
{{cite conference}}
: Unknown parameter|booktitle=
ignored (|book-title=
suggested) (help)CS1 maint: date and year (link) - ^
Jongsung, Kim (2006). "On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1" (PDF).
{{cite journal}}
: Cite journal requires|journal=
(help); Unknown parameter|coauthors=
ignored (|author=
suggested) (help)CS1 maint: postscript (link) - ^ Briefly mentioned at the end of this session Sebastian Schinzel:Time is on my Side - Exploiting Timing Side Channel Vulnerabilities on the Web 28th Chaos Communication Congress, 2011.
- Notes
- 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).
External links
- RFC2104
- Online HMAC Calculator for dozens of underlying hashing algorithms
- Online HMAC Generator / Tester Tool
- FIPS PUB 198-1, The Keyed-Hash Message Authentication Code (HMAC)
- PHP HMAC implementation
- Python HMAC implementation
- Perl HMAC implementation
- Ruby HMAC implementation
- C HMAC implementation
- C++ HMAC implementation (part of Crypto++)
- Java implementation
- JavaScript MD5 and SHA HMAC implementation
- JavaScript SHA-only HMAC implementation
- .NET's System.Security.Cryptography.HMAC
- Delphi/Free Pascal implementation