idnits 2.17.1 draft-ietf-ipsec-hmac-md5-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-26) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 11 instances of too long lines in the document, the longest one being 6 characters in excess of 72. ** The abstract seems to contain references ([RFC-1321]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The "Author's Address" (or "Authors' Addresses") section title is misspelled. == Line 221 has weird spacing: '...on tags compu...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- Couldn't find a document date in the document -- date freshness check skipped. -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'PV' is mentioned on line 219, but not defined -- Looks like a reference, but probably isn't: '65' on line 267 -- Looks like a reference, but probably isn't: '16' on line 268 ** Obsolete normative reference: RFC 1826 (Obsoleted by RFC 2402) -- Possible downref: Non-RFC (?) normative reference: ref. 'BCK1' -- Possible downref: Non-RFC (?) normative reference: ref. 'BCK2' -- Possible downref: Non-RFC (?) normative reference: ref. 'KR' -- Possible downref: Non-RFC (?) normative reference: ref. 'PV1' -- Possible downref: Non-RFC (?) normative reference: ref. 'PV2' ** Downref: Normative reference to an Informational RFC: RFC 1321 -- Possible downref: Non-RFC (?) normative reference: ref. 'SHA' -- Possible downref: Non-RFC (?) normative reference: ref. 'Tsu' -- Possible downref: Non-RFC (?) normative reference: ref. 'VW' Summary: 12 errors (**), 0 flaws (~~), 4 warnings (==), 13 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group H. Krawczyk 2 Internet Draft M. Bellare 3 R. Canetti 4 Expires September, 1996 March, 1996 6 HMAC-MD5: Keyed-MD5 for Message Authentication 7 9 Status of this Memo 11 Distribution of this memo is unlimited. 13 This document is an Internet-Draft. Internet Drafts are working 14 documents of the Internet Engineering Task Force (IETF), its Areas, 15 and its Working Groups. Note that other groups may also distribute 16 working documents as Internet Drafts. 18 Internet Drafts are draft documents valid for a maximum of six 19 months, and may be updated, replaced, or obsoleted by other documents 20 at any time. It is not appropriate to use Internet Drafts as 21 reference material, or to cite them other than as a ``working draft'' 22 or ``work in progress.'' 24 To learn the current status of any Internet-Draft, please check the 25 ``1id-abstracts.txt'' listing contained in the internet-drafts Shadow 26 Directories on: 28 ftp.is.co.za (Africa) 29 nic.nordu.net (Europe) 30 ds.internic.net (US East Coast) 31 ftp.isi.edu (US West Coast) 32 munnari.oz.au (Pacific Rim) 34 Abstract 36 This document describes a keyed-MD5 mechanism (called HMAC-MD5) for 37 use as a message authentication code (or, integrity check value). 38 It is mainly intended for integrity verification of 39 information transmitted over open networks (e.g., Internet) between 40 parties that share a common secret key. The proposed mechanism 41 combines the (key-less) MD5 hash function [RFC-1321] with a shared 42 secret key. The description of HMAC-MD5 in this document is 43 independent of its use in any particular protocol. An analogous 44 mechanism can be used in combination with other iterative hash 45 functions, e.g., SHA. 47 1. Introduction 49 Rivest introduced MD5 [RFC-1321] as a cryptographic hash function. 50 It was originally designed and intended as a collision-resistant 51 function as required for the hashing of information prior to 52 application of a signature function (e.g., RSA). However, due 53 to its relatively good performance in software implementation 54 and its free availability the same function was adapted to provide 55 functionalities different than the one for which MD5 was originally 56 designed. In particular, MD5 (as well as other cryptographic 57 hash functions) was proposed to provide message authentication 58 by combining it with a secret key (see [Tsu]). 60 Only recently a close analysis of the security of these keyed 61 MD5 modes has been initiated [BCK1,BCK2,KR,PV1,PV2]. In particular, 62 Bellare, Canetti, and Krawczyk [BCK2] described a keyed-hash 63 mechanism called HMAC which we adopt here for use with MD5. 64 (An analogous mechanism can be used in combination with other 65 iterative hash functions, e.g., SHA [SHA].) 66 The description of this transform in this document 67 is independent of its use in any particular protocol. It is intended 68 to serve as a common mechanism for the many protocols (especially, 69 IETF protocols) that require integrity verification based on 70 a shared secret key (e.g., IP Authentication Header [RFC-1826]). 72 The proposed mechanism follows the same principles that guided some 73 of the previous keyed-MD5 proposals, that is: 75 * it is based on MD5 76 * no change to the MD5 code required 77 * no degradation of MD5 speed 78 * simple key requirements 79 * replaceability of MD5 by other cryptographic hash functions 81 However, it improves on previous proposals relative to its security 82 analysis. The present is the first construction (and the only one we are 83 aware of) that can be fully analyzed based on relatively weak 84 assumptions on the underlying hash function (MD5). 85 It only requires MD5 to be collision-resistant in a weak sense, and 86 its compression function to be weakly unpredictable. 87 These requirements are weaker than the ones needed for other common 88 applications of MD5, e.g., as hash functions for digital signatures and 89 as "randomizers" (for pseudorandom generation, key derivation, etc.). 90 In particular, we only require that collisions are hard to find when 91 the "initial vector" of the function is random and secret, and that 92 the output of the compression function is unpredictable when applied 93 to partially unknown strings. The analytical results that back this 94 particular construction are provided in [BCK2]. 96 Note: The mechanism presented next differs from the one presented in 97 draft-krawczyk-keyed-md5-txt.01 in the way padding is defined 98 (see section 2). 100 2. Calculation 102 The definition and reference implementation of MD5 appears in 103 [RFC-1321]. Let `text' denote the data to which HMAC-MD5 is 104 to be applied and K be the message authentication secret key shared by 105 the parties. The key K can be of any length up to the block length of 106 the hash function, namely, 64 bytes for MD5 (however, 16 bytes is the 107 minimal recommended length for keys -- see section 3). 108 Applications that use longer than 64 byte keys will first hash the key 109 using MD5 and then use the resultant 16 byte string as the actual key 110 to HMAC-MD5. 112 We define two fixed and different strings ipad and opad as follows 113 (the 'i' and 'o' are mnemonics for inner and outer): 115 ipad = the byte 0x36 repeated 64 times 116 opad = the byte 0x5C repeated 64 times. 118 To compute HMAC-MD5 over the data `text' we perform 120 MD5(K XOR opad, MD5(K XOR ipad, text)) 122 Namely, 124 (1) append zeros to the end of K to create a 64 byte string 125 (e.g., if K is of length 16 bytes it will be appended with 48 126 zero bytes 0x00) 127 (2) XOR (bitwise exclusive-OR) the 64 byte string computed in step 128 (1) with ipad 129 (3) append the data stream 'text' to the 64 byte string resulting 130 from step (2) 131 (4) apply MD5 to the stream generated in step (3) 132 (5) XOR (bitwise exclusive-OR) the 64 byte string computed in 133 step (1) with opad 134 (6) append the MD5 result from step (4) to the 64 byte string 135 resulting from step (5) 136 (7) apply MD5 to the stream generated in step (6) and output 137 the result 139 For illustration purposes, sample code is provided as an appendix. 141 3. Keys 143 The key for HMAC-MD5 can be of any length (keys longer than 64 bytes 144 are first hashed using MD5). However, less than 16 bytes is strongly 145 discouraged as it would decrease the security strength of the function. 146 Keys longer than 16 bytes are acceptable but the extra length would not 147 significantly increase the function strength. (A longer key may be 148 advisable if the randomness of the key is considered weak.) 150 Note: when using other cryptographic hash functions the length of 151 the key should be chosen at least as the length of the hash output 152 (e.g., 160 bits in the case of SHA). 154 Keys need to be chosen at random, or using a cryptographically strong 155 pseudo-random generator seeded with a random seed. 156 We recommend that the key be changed periodically and as frequently 157 as possible. (Current attacks do not indicate a specific recommended 158 frequency for key changes as these attacks are practically infeasible. 159 However, periodic key refreshment is a fundamental security practice 160 that helps against potential weaknesses of the function and keys, and 161 limits the damage of an exposed key.) 163 4. Implementation Note 165 Implementation of HMAC-MD5 requires the implementation of MD5 166 (see [RFC-1321]) and the calculation described in Section 2. 167 Notice that this calculation does not require any change in the 168 definition or code of MD5. However, if desired, a performance 169 improvement can be achieved by a simple adaptation of the MD5 170 code as presented next. (Choosing or not to implement HMAC-MD5 171 in this way is a decision of the local implementation and has no 172 effect on inter-operability.) 173 The idea is that the intermediate results of MD5 on the 174 64-byte blocks (K XOR ipad) and (K XOR opad) can be 175 precomputed only once at the time of generation of the key K, or before 176 its first use. These intermediate results (called "contexts", and 177 stored under MD5's structure MD5_CTX [RFC-1321]) are then used to 178 initialize the MD5 function each time that a message needs to be 179 authenticated. (This involves setting the MD5_CTX variable to the 180 stored value and applying MD5Update to the data.) This method saves, 181 for each authenticated message, 182 the application of the MD5's compression function (MD5Update) on two 183 64-byte blocks; a savings which may be significant when authenticating 184 short streams of data. We stress that the stored contexts need to be 185 treated and protected the same as secret keys. 187 5. Security 189 The security of the message authentication mechanism presented here 190 depends on cryptographic properties of MD5: the resistance to 191 collision finding (limited to the case where the initial value is 192 secret and random, and where the output of the function is not 193 explicitly available to the attacker), and the message authentication 194 property of the compression function of MD5 when applied to single 195 blocks (these blocks are partially unknown to an attacker as they 196 contain the result of the internal MD5 computation and, in particular, 197 cannot be fully chosen by the attacker). 199 These properties, and actually stronger ones, are commonly assumed for 200 MD5. While significant weaknesses of MD5 regarding these properties 201 could be discovered in the future, such weaknesses would rend MD5 202 useless for most (probably, all) cryptographic applications, including 203 alternative message authentication schemes based on this function. 204 Two important properties of the application of MD5 here are: 206 1. This construction is independent of the particular details of MD5 207 and then the latter can be replaced by any other secure (iterative) 208 cryptographic hash function. 210 2. Message authentication, as opposed to encryption, has a "transient" 211 effect. A published breaking of a message authentication scheme 212 would lead to the replacement of that scheme, but would 213 have no adversarial effect on information authenticated in the past. 214 This is in sharp contrast with encryption, where information encrypted 215 today may suffer from exposure in the future if, and when, the 216 encryption algorithm is broken. 218 The strongest attack known against the proposed scheme is based on the 219 frequency of collisions for MD5 ("birthday attack") [BCK1,PV] 220 for which the attacker needs to acquire the correct message 221 authentication tags computed on about 2**64 known plaintexts 222 (and with the _same_ secret key K!). This would require the 223 processing of 2^70 bytes under MD5, an impossible task in any 224 realistic scenario (this would take 250,000 years in a continuous 225 1Gbit link, and without changing the secret key K all this time). 226 This attack could become realistic only if serious flaws in the collision 227 behavior of MD5 are discovered (e.g. collisions found after 2**30 228 messages). Such a discovery would determine the immediate 229 replacement of MD5 (the effects of such failure would be far more 230 severe for the traditional uses of MD5 in the context of digital 231 signatures, public key certificates, etc.). 233 Note: this attack needs to be strongly contrasted with regular 234 collision attacks on MD5 where no secret key is involved and where 235 2^64 off-line parallelizable (!) operations suffice to find collisions. 236 The latter attack is approaching feasibility [VW] while the birthday 237 attack on HMAC-MD5 is totally impractical. 238 (In all of the above discussion 64 should be replaced by 80 if 239 one uses a 160 bit hash function as SHA.) 241 A correct implementation of the above construction, the choice of 242 random (or cryptographically pseudorandom) keys, a secure key 243 exchange mechanism, frequent key refreshments, and good secrecy 244 protection of keys are all essential ingredients for the security of 245 the integrity verification mechanism provided by HMAC-MD5. 247 Appendix -- Sample Code 249 The following sample code for the implementation of HMAC-MD5 and 250 corresponding test vectors are provided for the sake of illustration only. 252 /* 253 ** Function: hmac_md5 254 */ 256 void 257 hmac_md5(text, text_len, key, key_len, digest) 258 unsigned char* text; /* pointer to data stream */ 259 int text_len; /* length of data stream */ 260 unsigned char* key; /* pointer to authentication key */ 261 int key_len; /* length of authentication key */ 262 caddr_t digest; /* caller digest to be filled in */ 264 { 265 MD5_CTX context; 266 unsigned char k_ipad[65]; /* inner padding - key XORd with ipad */ 267 unsigned char k_opad[65]; /* outer padding - key XORd with opad */ 268 unsigned char tk[16]; 269 int i; 271 /* sanity check parameters */ 272 if ((text == NULL) || (key == NULL) || (digest == NULL)) 273 /* most heinous, probably should log something */ 274 return; 276 /* if key is longer than 64 bytes reset it to key=MD5(key) */ 277 if (key_len > 64) { 279 MD5_CTX tctx; 281 MD5Init(&tctx); 282 MD5Update(&tctx, key, key_len); 283 MD5Final(tk, &tctx); 285 key = tk; 286 key_len = 16; 287 } 289 /* 290 * the HMAC_MD5 transform looks like: 291 * 292 * MD5(K XOR opad, MD5(K XOR ipad, text)) 293 * 294 * where K is an n byte key 295 * ipad is the byte 0x36 repeated 64 times 296 * opad is the byte 0x5c repeated 64 times 297 * and text is the data being protected 298 */ 300 /* start out by storing key in pads */ 301 bzero( k_ipad, sizeof k_ipad); 302 bzero( k_opad, sizeof k_opad); 303 bcopy( key, k_ipad, key_len); 304 bcopy( key, k_opad, key_len); 306 /* XOR key with ipad and opad values */ 307 for (i=0; i<64; i++) { 308 k_ipad[i] ^= 0x36; 309 k_opad[i] ^= 0x5c; 310 } 311 /* 312 * perform inner MD5 313 */ 314 MD5Init(&context); /* init context for 1st pass */ 315 MD5Update(&context, k_ipad, 64) /* start with inner pad */ 316 MD5Update(&context, text, text_len); /* then text of datagram */ 317 MD5Final(digest, &context); /* finish up 1st pass */ 318 /* 319 * perform outer MD5 320 */ 321 MD5Init(&context); /* init context for 2nd pass */ 322 MD5Update(&context, k_opad, 64); /* start with outer pad */ 323 MD5Update(&context, digest, 16); /* then results of 1st hash */ 324 MD5Final(digest, &context); /* finish up 2nd pass */ 325 } 327 Test Vectors: 329 key = 0x0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b 330 key_len = 16 331 data = "Hi There" 332 digest = 0x9294727a3638bb1c13f48ef8158bfc9d 334 key = "Jefe" 335 data = "what do ya want for nothing?" 336 digest = 0x750c783e6ab0b503eaa86e310a5db738 338 key = 0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 339 key_len 16 340 data = 0xDDDDDDDDDDDDDDDDDDDD... 341 ..DDDDDDDDDDDDDDDDDDDD... 342 ..DDDDDDDDDDDDDDDDDDDD... 343 ..DDDDDDDDDDDDDDDDDDDD... 344 ..DDDDDDDDDDDDDDDDDDDD 345 data_len = 50 346 digest = 0x56be34521d144c88dbb8c733f0e8b3f6 348 Acknowledgments 350 Adi Shamir has suggested the use of the XOR-based padding technique as 351 adopted in this draft instead of the previous concatenation pads. 352 Pau-Chen Cheng, Jeff Kraemer, and Michael Oehler, have provided useful 353 comments on the draft, and ran the first interoperability tests of this 354 specification. Jeff and Pau-Chen kindly provided the sample code and test 355 vectors that appear in the appendix. 357 References 359 [RFC-1826] R. Atkinson, "IP Authentication Header", 360 RFC-1826, August 1995. 362 [BCK1] M. Bellare, R. Canetti, and H. Krawczyk, 363 "Cascaded Pseudorandomness and Its Concrete Security", 364 manuscript. 366 [BCK2] M. Bellare, R. Canetti, and H. Krawczyk, 367 "Keyed Hash Functions and Message Authentication", 368 presented at the 1996 RSA Data Security Conference, 369 San Francisco, Jan. 1996. 370 (http://www.research.ibm.com/security/keyed-md5.html) 372 [KR] B. Kaliski and M. Robshaw, "Message Authentication with MD5", 373 RSA Labs' CryptoBytes, Vol. 1 No. 1, Spring 1995. 374 (http://www.rsa.com/rsalabs/cryptobytes/) 376 [PV1] B. Prennel and P. van Oorschot, "Building fast MACs from hash 377 functions", Advances in Cryptology -- CRYPTO'95 Proceedings, 378 Lecture Notes in Computer Science, Springer-Verlag Vol.963, 379 1995, pp. 1-14. 381 [PV2] B. Prennel and P. van Oorschot, "On the security of two MAC 382 algorithms", to appear Eurocrypt'96. 384 [RFC-1321] Ronald Rivest, "The MD5 Message-Digest Algorithm", 385 RFC-1321, DDN Network Information Center, April 1992. 387 [SHA] NIST, FIPS PUB 180: Secure Hash Standard, May 1993. 389 [Tsu] G. Tsudik, "Message authentication with one-way hash 390 functions", In Proceedings of Infocom~92, 1992. 392 [VW] P. van Oorschot and M. Wiener, "Parallel Collision 393 Search with Applications to Hash Functions and Discrete 394 Logarithms", Proceedings of the 2nd ACM Conf. Computer and 395 Communications Security, Fairfax, VA, November 1994. 397 Authors Address 399 Hugo Krawczyk 400 IBM T.J. Watson Research Center 401 P.O.Box 704 402 Yorktown Heights, NY 10598 404 hugo@watson.ibm.com 406 Mihir Bellare 407 Dept of Computer Science and Engineering 408 Mail Code 0114 409 University of California at San Diego 410 9500 Gilman Drive 411 La Jolla, CA 92093 413 mihir@cs.ucsd.edu 415 Ran Canetti 416 Laboratory for Computer Science 417 MIT 418 545 Technology Square 419 Cambridge, Ma 02139 421 canetti@theory.lcs.mit.edu