HTTP/1.1 200 OK Date: Tue, 09 Apr 2002 04:15:51 GMT Server: Apache/1.3.20 (Unix) Last-Modified: Sat, 30 Mar 1996 23:00:00 GMT ETag: "2f542f-4ac6-315dbcf0" Accept-Ranges: bytes Content-Length: 19142 Connection: close Content-Type: text/plain Network Working Group H. Krawczyk Internet Draft M. Bellare R. Canetti Expires September, 1996 March, 1996 HMAC-MD5: Keyed-MD5 for Message Authentication Status of this Memo Distribution of this memo is unlimited. This document is an Internet-Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months, and may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material, or to cite them other than as a ``working draft'' or ``work in progress.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the internet-drafts Shadow Directories on: ftp.is.co.za (Africa) nic.nordu.net (Europe) ds.internic.net (US East Coast) ftp.isi.edu (US West Coast) munnari.oz.au (Pacific Rim) Abstract This document describes a keyed-MD5 mechanism (called HMAC-MD5) for use as a message authentication code (or, integrity check value). It is mainly intended for integrity verification of information transmitted over open networks (e.g., Internet) between parties that share a common secret key. The proposed mechanism combines the (key-less) MD5 hash function [RFC-1321] with a shared secret key. The description of HMAC-MD5 in this document is independent of its use in any particular protocol. An analogous mechanism can be used in combination with other iterative hash functions, e.g., SHA. Krawczyk, Bellare & Canetti Expires September 1996 [Page i] INTERNET-DRAFT HMAC-MD5 March 1996 1. Introduction Rivest introduced MD5 [RFC-1321] as a cryptographic hash function. It was originally designed and intended as a collision-resistant function as required for the hashing of information prior to application of a signature function (e.g., RSA). However, due to its relatively good performance in software implementation and its free availability the same function was adapted to provide functionalities different than the one for which MD5 was originally designed. In particular, MD5 (as well as other cryptographic hash functions) was proposed to provide message authentication by combining it with a secret key (see [Tsu]). Only recently a close analysis of the security of these keyed MD5 modes has been initiated [BCK1,BCK2,KR,PV1,PV2]. In particular, Bellare, Canetti, and Krawczyk [BCK2] described a keyed-hash mechanism called HMAC which we adopt here for use with MD5. (An analogous mechanism can be used in combination with other iterative hash functions, e.g., SHA [SHA].) The description of this transform in this document is independent of its use in any particular protocol. It is intended to serve as a common mechanism for the many protocols (especially, IETF protocols) that require integrity verification based on a shared secret key (e.g., IP Authentication Header [RFC-1826]). The proposed mechanism follows the same principles that guided some of the previous keyed-MD5 proposals, that is: * it is based on MD5 * no change to the MD5 code required * no degradation of MD5 speed * simple key requirements * replaceability of MD5 by other cryptographic hash functions However, it improves on previous proposals relative to its security analysis. The present is the first construction (and the only one we are aware of) that can be fully analyzed based on relatively weak assumptions on the underlying hash function (MD5). It only requires MD5 to be collision-resistant in a weak sense, and its compression function to be weakly unpredictable. These requirements are weaker than the ones needed for other common applications of MD5, e.g., as hash functions for digital signatures and as "randomizers" (for pseudorandom generation, key derivation, etc.). In particular, we only require that collisions are hard to find when the "initial vector" of the function is random and secret, and that the output of the compression function is unpredictable when applied to partially unknown strings. The analytical results that back this particular construction are provided in [BCK2]. Note: The mechanism presented next differs from the one presented in draft-krawczyk-keyed-md5-txt.01 in the way padding is defined (see section 2). Krawczyk, Bellare & Canetti Expires September 1996 [Page 1] INTERNET-DRAFT HMAC-MD5 March 1996 2. Calculation The definition and reference implementation of MD5 appears in [RFC-1321]. Let `text' denote the data to which HMAC-MD5 is to be applied and K be the message authentication secret key shared by the parties. The key K can be of any length up to the block length of the hash function, namely, 64 bytes for MD5 (however, 16 bytes is the minimal recommended length for keys -- see section 3). Applications that use longer than 64 byte keys will first hash the key using MD5 and then use the resultant 16 byte string as the actual key to HMAC-MD5. We define two fixed and different strings ipad and opad as follows (the 'i' and 'o' are mnemonics for inner and outer): ipad = the byte 0x36 repeated 64 times opad = the byte 0x5C repeated 64 times. To compute HMAC-MD5 over the data `text' we perform MD5(K XOR opad, MD5(K XOR ipad, text)) Namely, (1) append zeros to the end of K to create a 64 byte string (e.g., if K is of length 16 bytes it will be appended with 48 zero bytes 0x00) (2) XOR (bitwise exclusive-OR) the 64 byte string computed in step (1) with ipad (3) append the data stream 'text' to the 64 byte string resulting from step (2) (4) apply MD5 to the stream generated in step (3) (5) XOR (bitwise exclusive-OR) the 64 byte string computed in step (1) with opad (6) append the MD5 result from step (4) to the 64 byte string resulting from step (5) (7) apply MD5 to the stream generated in step (6) and output the result For illustration purposes, sample code is provided as an appendix. 3. Keys The key for HMAC-MD5 can be of any length (keys longer than 64 bytes are first hashed using MD5). However, less than 16 bytes is strongly discouraged as it would decrease the security strength of the function. Keys longer than 16 bytes are acceptable but the extra length would not significantly increase the function strength. (A longer key may be advisable if the randomness of the key is considered weak.) Note: when using other cryptographic hash functions the length of the key should be chosen at least as the length of the hash output (e.g., 160 bits in the case of SHA). Krawczyk, Bellare & Canetti Expires September 1996 [Page 2] INTERNET-DRAFT HMAC-MD5 March 1996 Keys need to be chosen at random, or using a cryptographically strong pseudo-random generator seeded with a random seed. We recommend that the key be changed periodically and as frequently as possible. (Current attacks do not indicate a specific recommended frequency for key changes as these attacks are practically infeasible. However, periodic key refreshment is a fundamental security practice that helps against potential weaknesses of the function and keys, and limits the damage of an exposed key.) 4. Implementation Note Implementation of HMAC-MD5 requires the implementation of MD5 (see [RFC-1321]) and the calculation described in Section 2. Notice that this calculation does not require any change in the definition or code of MD5. However, if desired, a performance improvement can be achieved by a simple adaptation of the MD5 code as presented next. (Choosing or not to implement HMAC-MD5 in this way is a decision of the local implementation and has no effect on inter-operability.) The idea is that the intermediate results of MD5 on the 64-byte blocks (K XOR ipad) and (K XOR opad) can be precomputed only once at the time of generation of the key K, or before its first use. These intermediate results (called "contexts", and stored under MD5's structure MD5_CTX [RFC-1321]) are then used to initialize the MD5 function each time that a message needs to be authenticated. (This involves setting the MD5_CTX variable to the stored value and applying MD5Update to the data.) This method saves, for each authenticated message, the application of the MD5's compression function (MD5Update) on two 64-byte blocks; a savings which may be significant when authenticating short streams of data. We stress that the stored contexts need to be treated and protected the same as secret keys. 5. Security The security of the message authentication mechanism presented here depends on cryptographic properties of MD5: the resistance to collision finding (limited to the case where the initial value is secret and random, and where the output of the function is not explicitly available to the attacker), and the message authentication property of the compression function of MD5 when applied to single blocks (these blocks are partially unknown to an attacker as they contain the result of the internal MD5 computation and, in particular, cannot be fully chosen by the attacker). Krawczyk, Bellare & Canetti Expires September 1996 [Page 3] INTERNET-DRAFT HMAC-MD5 March 1996 These properties, and actually stronger ones, are commonly assumed for MD5. While significant weaknesses of MD5 regarding these properties could be discovered in the future, such weaknesses would rend MD5 useless for most (probably, all) cryptographic applications, including alternative message authentication schemes based on this function. Two important properties of the application of MD5 here are: 1. This construction is independent of the particular details of MD5 and then the latter can be replaced by any other secure (iterative) cryptographic hash function. 2. Message authentication, as opposed to encryption, has a "transient" effect. A published breaking of a message authentication scheme would lead to the replacement of that scheme, but would have no adversarial effect on information authenticated in the past. This is in sharp contrast with encryption, where information encrypted today may suffer from exposure in the future if, and when, the encryption algorithm is broken. The strongest attack known against the proposed scheme is based on the frequency of collisions for MD5 ("birthday attack") [BCK1,PV] for which the attacker needs to acquire the correct message authentication tags computed on about 2**64 known plaintexts (and with the _same_ secret key K!). This would require the processing of 2^70 bytes under MD5, an impossible task in any realistic scenario (this would take 250,000 years in a continuous 1Gbit link, and without changing the secret key K all this time). This attack could become realistic only if serious flaws in the collision behavior of MD5 are discovered (e.g. collisions found after 2**30 messages). Such a discovery would determine the immediate replacement of MD5 (the effects of such failure would be far more severe for the traditional uses of MD5 in the context of digital signatures, public key certificates, etc.). Note: this attack needs to be strongly contrasted with regular collision attacks on MD5 where no secret key is involved and where 2^64 off-line parallelizable (!) operations suffice to find collisions. The latter attack is approaching feasibility [VW] while the birthday attack on HMAC-MD5 is totally impractical. (In all of the above discussion 64 should be replaced by 80 if one uses a 160 bit hash function as SHA.) A correct implementation of the above construction, the choice of random (or cryptographically pseudorandom) keys, a secure key exchange mechanism, frequent key refreshments, and good secrecy protection of keys are all essential ingredients for the security of the integrity verification mechanism provided by HMAC-MD5. Krawczyk, Bellare & Canetti Expires September 1996 [Page 4] INTERNET-DRAFT HMAC-MD5 March 1996 Appendix -- Sample Code The following sample code for the implementation of HMAC-MD5 and corresponding test vectors are provided for the sake of illustration only. /* ** Function: hmac_md5 */ void hmac_md5(text, text_len, key, key_len, digest) unsigned char* text; /* pointer to data stream */ int text_len; /* length of data stream */ unsigned char* key; /* pointer to authentication key */ int key_len; /* length of authentication key */ caddr_t digest; /* caller digest to be filled in */ { MD5_CTX context; unsigned char k_ipad[65]; /* inner padding - key XORd with ipad */ unsigned char k_opad[65]; /* outer padding - key XORd with opad */ unsigned char tk[16]; int i; /* sanity check parameters */ if ((text == NULL) || (key == NULL) || (digest == NULL)) /* most heinous, probably should log something */ return; /* if key is longer than 64 bytes reset it to key=MD5(key) */ if (key_len > 64) { MD5_CTX tctx; MD5Init(&tctx); MD5Update(&tctx, key, key_len); MD5Final(tk, &tctx); key = tk; key_len = 16; } /* * the HMAC_MD5 transform looks like: * * MD5(K XOR opad, MD5(K XOR ipad, text)) * * where K is an n byte key * ipad is the byte 0x36 repeated 64 times * opad is the byte 0x5c repeated 64 times * and text is the data being protected */ Krawczyk, Bellare & Canetti Expires September 1996 [Page 5] INTERNET-DRAFT HMAC-MD5 March 1996 /* start out by storing key in pads */ bzero( k_ipad, sizeof k_ipad); bzero( k_opad, sizeof k_opad); bcopy( key, k_ipad, key_len); bcopy( key, k_opad, key_len); /* XOR key with ipad and opad values */ for (i=0; i<64; i++) { k_ipad[i] ^= 0x36; k_opad[i] ^= 0x5c; } /* * perform inner MD5 */ MD5Init(&context); /* init context for 1st pass */ MD5Update(&context, k_ipad, 64) /* start with inner pad */ MD5Update(&context, text, text_len); /* then text of datagram */ MD5Final(digest, &context); /* finish up 1st pass */ /* * perform outer MD5 */ MD5Init(&context); /* init context for 2nd pass */ MD5Update(&context, k_opad, 64); /* start with outer pad */ MD5Update(&context, digest, 16); /* then results of 1st hash */ MD5Final(digest, &context); /* finish up 2nd pass */ } Test Vectors: key = 0x0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b key_len = 16 data = "Hi There" digest = 0x9294727a3638bb1c13f48ef8158bfc9d key = "Jefe" data = "what do ya want for nothing?" digest = 0x750c783e6ab0b503eaa86e310a5db738 key = 0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA key_len 16 data = 0xDDDDDDDDDDDDDDDDDDDD... ..DDDDDDDDDDDDDDDDDDDD... ..DDDDDDDDDDDDDDDDDDDD... ..DDDDDDDDDDDDDDDDDDDD... ..DDDDDDDDDDDDDDDDDDDD data_len = 50 digest = 0x56be34521d144c88dbb8c733f0e8b3f6 Krawczyk, Bellare & Canetti Expires September 1996 [Page 6] INTERNET-DRAFT HMAC-MD5 March 1996 Acknowledgments Adi Shamir has suggested the use of the XOR-based padding technique as adopted in this draft instead of the previous concatenation pads. Pau-Chen Cheng, Jeff Kraemer, and Michael Oehler, have provided useful comments on the draft, and ran the first interoperability tests of this specification. Jeff and Pau-Chen kindly provided the sample code and test vectors that appear in the appendix. References [RFC-1826] R. Atkinson, "IP Authentication Header", RFC-1826, August 1995. [BCK1] M. Bellare, R. Canetti, and H. Krawczyk, "Cascaded Pseudorandomness and Its Concrete Security", manuscript. [BCK2] M. Bellare, R. Canetti, and H. Krawczyk, "Keyed Hash Functions and Message Authentication", presented at the 1996 RSA Data Security Conference, San Francisco, Jan. 1996. (http://www.research.ibm.com/security/keyed-md5.html) [KR] B. Kaliski and M. Robshaw, "Message Authentication with MD5", RSA Labs' CryptoBytes, Vol. 1 No. 1, Spring 1995. (http://www.rsa.com/rsalabs/cryptobytes/) [PV1] B. Prennel and P. van Oorschot, "Building fast MACs from hash functions", Advances in Cryptology -- CRYPTO'95 Proceedings, Lecture Notes in Computer Science, Springer-Verlag Vol.963, 1995, pp. 1-14. [PV2] B. Prennel and P. van Oorschot, "On the security of two MAC algorithms", to appear Eurocrypt'96. [RFC-1321] Ronald Rivest, "The MD5 Message-Digest Algorithm", RFC-1321, DDN Network Information Center, April 1992. [SHA] NIST, FIPS PUB 180: Secure Hash Standard, May 1993. [Tsu] G. Tsudik, "Message authentication with one-way hash functions", In Proceedings of Infocom~92, 1992. [VW] P. van Oorschot and M. Wiener, "Parallel Collision Search with Applications to Hash Functions and Discrete Logarithms", Proceedings of the 2nd ACM Conf. Computer and Communications Security, Fairfax, VA, November 1994. Krawczyk, Bellare & Canetti Expires September 1996 [Page 7] INTERNET-DRAFT HMAC-MD5 March 1996 Authors Address Hugo Krawczyk IBM T.J. Watson Research Center P.O.Box 704 Yorktown Heights, NY 10598 hugo@watson.ibm.com Mihir Bellare Dept of Computer Science and Engineering Mail Code 0114 University of California at San Diego 9500 Gilman Drive La Jolla, CA 92093 mihir@cs.ucsd.edu Ran Canetti Laboratory for Computer Science MIT 545 Technology Square Cambridge, Ma 02139 canetti@theory.lcs.mit.edu Krawczyk Expires September 1996 [Page 8]