1
2
3
4
5
6
7Network Working Group H. Krawczyk
8Request for Comments: 2104 IBM
9Category: Informational M. Bellare
10 UCSD
11 R. Canetti
12 IBM
13 February 1997
14
15
16 HMAC: Keyed-Hashing for Message Authentication
17
18Status of This Memo
19
20 This memo provides information for the Internet community. This memo
21 does not specify an Internet standard of any kind. Distribution of
22 this memo is unlimited.
23
24Abstract
25
26 This document describes HMAC, a mechanism for message authentication
27 using cryptographic hash functions. HMAC can be used with any
28 iterative cryptographic hash function, e.g., MD5, SHA-1, in
29 combination with a secret shared key. The cryptographic strength of
30 HMAC depends on the properties of the underlying hash function.
31
321. Introduction
33
34 Providing a way to check the integrity of information transmitted
35 over or stored in an unreliable medium is a prime necessity in the
36 world of open computing and communications. Mechanisms that provide
37 such integrity check based on a secret key are usually called
38 "message authentication codes" (MAC). Typically, message
39 authentication codes are used between two parties that share a secret
40 key in order to validate information transmitted between these
41 parties. In this document we present such a MAC mechanism based on
42 cryptographic hash functions. This mechanism, called HMAC, is based
43 on work by the authors [BCK1] where the construction is presented and
44 cryptographically analyzed. We refer to that work for the details on
45 the rationale and security analysis of HMAC, and its comparison to
46 other keyed-hash methods.
47
48
49
50
51
52
53
54
55
56
57
58Krawczyk, et. al. Informational [Page 1]
59
60RFC 2104 HMAC February 1997
61
62
63 HMAC can be used in combination with any iterated cryptographic hash
64 function. MD5 and SHA-1 are examples of such hash functions. HMAC
65 also uses a secret key for calculation and verification of the
66 message authentication values. The main goals behind this
67 construction are
68
69 * To use, without modifications, available hash functions.
70 In particular, hash functions that perform well in software,
71 and for which code is freely and widely available.
72
73 * To preserve the original performance of the hash function without
74 incurring a significant degradation.
75
76 * To use and handle keys in a simple way.
77
78 * To have a well understood cryptographic analysis of the strength of
79 the authentication mechanism based on reasonable assumptions on the
80 underlying hash function.
81
82 * To allow for easy replaceability of the underlying hash function in
83 case that faster or more secure hash functions are found or
84 required.
85
86 This document specifies HMAC using a generic cryptographic hash
87 function (denoted by H). Specific instantiations of HMAC need to
88 define a particular hash function. Current candidates for such hash
89 functions include SHA-1 [SHA], MD5 [MD5], RIPEMD-128/160 [RIPEMD].
90 These different realizations of HMAC will be denoted by HMAC-SHA1,
91 HMAC-MD5, HMAC-RIPEMD, etc.
92
93 Note: To the date of writing of this document MD5 and SHA-1 are the
94 most widely used cryptographic hash functions. MD5 has been recently
95 shown to be vulnerable to collision search attacks [Dobb]. This
96 attack and other currently known weaknesses of MD5 do not compromise
97 the use of MD5 within HMAC as specified in this document (see
98 [Dobb]); however, SHA-1 appears to be a cryptographically stronger
99 function. To this date, MD5 can be considered for use in HMAC for
100 applications where the superior performance of MD5 is critical. In
101 any case, implementers and users need to be aware of possible
102 cryptanalytic developments regarding any of these cryptographic hash
103 functions, and the eventual need to replace the underlying hash
104 function. (See section 6 for more information on the security of
105 HMAC.)
106
107
108
109
110
111
112
113
114Krawczyk, et. al. Informational [Page 2]
115
116RFC 2104 HMAC February 1997
117
118
1192. Definition of HMAC
120
121 The definition of HMAC requires a cryptographic hash function, which ../store/account.go:1615
122 we denote by H, and a secret key K. We assume H to be a cryptographic
123 hash function where data is hashed by iterating a basic compression
124 function on blocks of data. We denote by B the byte-length of such
125 blocks (B=64 for all the above mentioned examples of hash functions),
126 and by L the byte-length of hash outputs (L=16 for MD5, L=20 for
127 SHA-1). The authentication key K can be of any length up to B, the
128 block length of the hash function. Applications that use keys longer
129 than B bytes will first hash the key using H and then use the
130 resultant L byte string as the actual key to HMAC. In any case the
131 minimal recommended length for K is L bytes (as the hash output
132 length). See section 3 for more information on keys.
133
134 We define two fixed and different strings ipad and opad as follows
135 (the 'i' and 'o' are mnemonics for inner and outer):
136
137 ipad = the byte 0x36 repeated B times
138 opad = the byte 0x5C repeated B times.
139
140 To compute HMAC over the data `text' we perform
141
142 H(K XOR opad, H(K XOR ipad, text)) 2195:138 ../imapserver/server.go:1669 ../smtpserver/server.go:1227
143
144 Namely,
145
146 (1) append zeros to the end of K to create a B byte string
147 (e.g., if K is of length 20 bytes and B=64, then K will be
148 appended with 44 zero bytes 0x00)
149 (2) XOR (bitwise exclusive-OR) the B byte string computed in step
150 (1) with ipad
151 (3) append the stream of data 'text' to the B byte string resulting
152 from step (2)
153 (4) apply H to the stream generated in step (3)
154 (5) XOR (bitwise exclusive-OR) the B byte string computed in
155 step (1) with opad
156 (6) append the H result from step (4) to the B byte string
157 resulting from step (5)
158 (7) apply H to the stream generated in step (6) and output
159 the result
160
161 For illustration purposes, sample code based on MD5 is provided as an
162 appendix.
163
164
165
166
167
168
169
170Krawczyk, et. al. Informational [Page 3]
171
172RFC 2104 HMAC February 1997
173
174
1753. Keys
176
177 The key for HMAC can be of any length (keys longer than B bytes are
178 first hashed using H). However, less than L bytes is strongly
179 discouraged as it would decrease the security strength of the
180 function. Keys longer than L bytes are acceptable but the extra
181 length would not significantly increase the function strength. (A
182 longer key may be advisable if the randomness of the key is
183 considered weak.)
184
185 Keys need to be chosen at random (or using a cryptographically strong
186 pseudo-random generator seeded with a random seed), and periodically
187 refreshed. (Current attacks do not indicate a specific recommended
188 frequency for key changes as these attacks are practically
189 infeasible. However, periodic key refreshment is a fundamental
190 security practice that helps against potential weaknesses of the
191 function and keys, and limits the damage of an exposed key.)
192
1934. Implementation Note
194
195 HMAC is defined in such a way that the underlying hash function H can
196 be used with no modification to its code. In particular, it uses the
197 function H with the pre-defined initial value IV (a fixed value
198 specified by each iterative hash function to initialize its
199 compression function). However, if desired, a performance
200 improvement can be achieved at the cost of (possibly) modifying the
201 code of H to support variable IVs.
202
203 The idea is that the intermediate results of the compression function
204 on the B-byte blocks (K XOR ipad) and (K XOR opad) can be precomputed
205 only once at the time of generation of the key K, or before its first
206 use. These intermediate results are stored and then used to
207 initialize the IV of H each time that a message needs to be
208 authenticated. This method saves, for each authenticated message,
209 the application of the compression function of H on two B-byte blocks
210 (i.e., on (K XOR ipad) and (K XOR opad)). Such a savings may be
211 significant when authenticating short streams of data. We stress
212 that the stored intermediate values need to be treated and protected
213 the same as secret keys.
214
215 Choosing to implement HMAC in the above way is a decision of the
216 local implementation and has no effect on inter-operability.
217
218
219
220
221
222
223
224
225
226Krawczyk, et. al. Informational [Page 4]
227
228RFC 2104 HMAC February 1997
229
230
2315. Truncated output
232
233 A well-known practice with message authentication codes is to
234 truncate the output of the MAC and output only part of the bits
235 (e.g., [MM, ANSI]). Preneel and van Oorschot [PV] show some
236 analytical advantages of truncating the output of hash-based MAC
237 functions. The results in this area are not absolute as for the
238 overall security advantages of truncation. It has advantages (less
239 information on the hash result available to an attacker) and
240 disadvantages (less bits to predict for the attacker). Applications
241 of HMAC can choose to truncate the output of HMAC by outputting the t
242 leftmost bits of the HMAC computation for some parameter t (namely,
243 the computation is carried in the normal way as defined in section 2
244 above but the end result is truncated to t bits). We recommend that
245 the output length t be not less than half the length of the hash
246 output (to match the birthday attack bound) and not less than 80 bits
247 (a suitable lower bound on the number of bits that need to be
248 predicted by an attacker). We propose denoting a realization of HMAC
249 that uses a hash function H with t bits of output as HMAC-H-t. For
250 example, HMAC-SHA1-80 denotes HMAC computed using the SHA-1 function
251 and with the output truncated to 80 bits. (If the parameter t is not
252 specified, e.g. HMAC-MD5, then it is assumed that all the bits of the
253 hash are output.)
254
2556. Security
256
257 The security of the message authentication mechanism presented here
258 depends on cryptographic properties of the hash function H: the
259 resistance to collision finding (limited to the case where the
260 initial value is secret and random, and where the output of the
261 function is not explicitly available to the attacker), and the
262 message authentication property of the compression function of H when
263 applied to single blocks (in HMAC these blocks are partially unknown
264 to an attacker as they contain the result of the inner H computation
265 and, in particular, cannot be fully chosen by the attacker).
266
267 These properties, and actually stronger ones, are commonly assumed
268 for hash functions of the kind used with HMAC. In particular, a hash
269 function for which the above properties do not hold would become
270 unsuitable for most (probably, all) cryptographic applications,
271 including alternative message authentication schemes based on such
272 functions. (For a complete analysis and rationale of the HMAC
273 function the reader is referred to [BCK1].)
274
275
276
277
278
279
280
281
282Krawczyk, et. al. Informational [Page 5]
283
284RFC 2104 HMAC February 1997
285
286
287 Given the limited confidence gained so far as for the cryptographic
288 strength of candidate hash functions, it is important to observe the
289 following two properties of the HMAC construction and its secure use
290 for message authentication:
291
292 1. The construction is independent of the details of the particular
293 hash function H in use and then the latter can be replaced by any
294 other secure (iterative) cryptographic hash function.
295
296 2. Message authentication, as opposed to encryption, has a
297 "transient" effect. A published breaking of a message authentication
298 scheme would lead to the replacement of that scheme, but would have
299 no adversarial effect on information authenticated in the past. This
300 is in sharp contrast with encryption, where information encrypted
301 today may suffer from exposure in the future if, and when, the
302 encryption algorithm is broken.
303
304 The strongest attack known against HMAC is based on the frequency of
305 collisions for the hash function H ("birthday attack") [PV,BCK2], and
306 is totally impractical for minimally reasonable hash functions.
307
308 As an example, if we consider a hash function like MD5 where the
309 output length equals L=16 bytes (128 bits) the attacker needs to
310 acquire the correct message authentication tags computed (with the
311 _same_ secret key K!) on about 2**64 known plaintexts. This would
312 require the processing of at least 2**64 blocks under H, an
313 impossible task in any realistic scenario (for a block length of 64
314 bytes this would take 250,000 years in a continuous 1Gbps link, and
315 without changing the secret key K during all this time). This attack
316 could become realistic only if serious flaws in the collision
317 behavior of the function H are discovered (e.g. collisions found
318 after 2**30 messages). Such a discovery would determine the immediate
319 replacement of the function H (the effects of such failure would be
320 far more severe for the traditional uses of H in the context of
321 digital signatures, public key certificates, etc.).
322
323 Note: this attack needs to be strongly contrasted with regular
324 collision attacks on cryptographic hash functions where no secret key
325 is involved and where 2**64 off-line parallelizable (!) operations
326 suffice to find collisions. The latter attack is approaching
327 feasibility [VW] while the birthday attack on HMAC is totally
328 impractical. (In the above examples, if one uses a hash function
329 with, say, 160 bit of output then 2**64 should be replaced by 2**80.)
330
331
332
333
334
335
336
337
338Krawczyk, et. al. Informational [Page 6]
339
340RFC 2104 HMAC February 1997
341
342
343 A correct implementation of the above construction, the choice of
344 random (or cryptographically pseudorandom) keys, a secure key
345 exchange mechanism, frequent key refreshments, and good secrecy
346 protection of keys are all essential ingredients for the security of
347 the integrity verification mechanism provided by HMAC.
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394Krawczyk, et. al. Informational [Page 7]
395
396RFC 2104 HMAC February 1997
397
398
399Appendix -- Sample Code
400
401 For the sake of illustration we provide the following sample code for
402 the implementation of HMAC-MD5 as well as some corresponding test
403 vectors (the code is based on MD5 code as described in [MD5]).
404
405/*
406** Function: hmac_md5
407*/
408
409void
410hmac_md5(text, text_len, key, key_len, digest)
411unsigned char* text; /* pointer to data stream */
412int text_len; /* length of data stream */
413unsigned char* key; /* pointer to authentication key */
414int key_len; /* length of authentication key */
415caddr_t digest; /* caller digest to be filled in */
416
417{
418 MD5_CTX context;
419 unsigned char k_ipad[65]; /* inner padding -
420 * key XORd with ipad
421 */
422 unsigned char k_opad[65]; /* outer padding -
423 * key XORd with opad
424 */
425 unsigned char tk[16];
426 int i;
427 /* if key is longer than 64 bytes reset it to key=MD5(key) */
428 if (key_len > 64) {
429
430 MD5_CTX tctx;
431
432 MD5Init(&tctx);
433 MD5Update(&tctx, key, key_len);
434 MD5Final(tk, &tctx);
435
436 key = tk;
437 key_len = 16;
438 }
439
440 /*
441 * the HMAC_MD5 transform looks like:
442 *
443 * MD5(K XOR opad, MD5(K XOR ipad, text))
444 *
445 * where K is an n byte key
446 * ipad is the byte 0x36 repeated 64 times
447
448
449
450Krawczyk, et. al. Informational [Page 8]
451
452RFC 2104 HMAC February 1997
453
454
455 * opad is the byte 0x5c repeated 64 times
456 * and text is the data being protected
457 */
458
459 /* start out by storing key in pads */
460 bzero( k_ipad, sizeof k_ipad);
461 bzero( k_opad, sizeof k_opad);
462 bcopy( key, k_ipad, key_len);
463 bcopy( key, k_opad, key_len);
464
465 /* XOR key with ipad and opad values */
466 for (i=0; i<64; i++) {
467 k_ipad[i] ^= 0x36;
468 k_opad[i] ^= 0x5c;
469 }
470 /*
471 * perform inner MD5
472 */
473 MD5Init(&context); /* init context for 1st
474 * pass */
475 MD5Update(&context, k_ipad, 64) /* start with inner pad */
476 MD5Update(&context, text, text_len); /* then text of datagram */
477 MD5Final(digest, &context); /* finish up 1st pass */
478 /*
479 * perform outer MD5
480 */
481 MD5Init(&context); /* init context for 2nd
482 * pass */
483 MD5Update(&context, k_opad, 64); /* start with outer pad */
484 MD5Update(&context, digest, 16); /* then results of 1st
485 * hash */
486 MD5Final(digest, &context); /* finish up 2nd pass */
487}
488
489Test Vectors (Trailing '\0' of a character string not included in test):
490
491 key = 0x0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
492 key_len = 16 bytes
493 data = "Hi There"
494 data_len = 8 bytes
495 digest = 0x9294727a3638bb1c13f48ef8158bfc9d
496
497 key = "Jefe"
498 data = "what do ya want for nothing?"
499 data_len = 28 bytes
500 digest = 0x750c783e6ab0b503eaa86e310a5db738
501
502 key = 0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
503
504
505
506Krawczyk, et. al. Informational [Page 9]
507
508RFC 2104 HMAC February 1997
509
510
511 key_len 16 bytes
512 data = 0xDDDDDDDDDDDDDDDDDDDD...
513 ..DDDDDDDDDDDDDDDDDDDD...
514 ..DDDDDDDDDDDDDDDDDDDD...
515 ..DDDDDDDDDDDDDDDDDDDD...
516 ..DDDDDDDDDDDDDDDDDDDD
517 data_len = 50 bytes
518 digest = 0x56be34521d144c88dbb8c733f0e8b3f6
519
520Acknowledgments
521
522 Pau-Chen Cheng, Jeff Kraemer, and Michael Oehler, have provided
523 useful comments on early drafts, and ran the first interoperability
524 tests of this specification. Jeff and Pau-Chen kindly provided the
525 sample code and test vectors that appear in the appendix. Burt
526 Kaliski, Bart Preneel, Matt Robshaw, Adi Shamir, and Paul van
527 Oorschot have provided useful comments and suggestions during the
528 investigation of the HMAC construction.
529
530References
531
532 [ANSI] ANSI X9.9, "American National Standard for Financial
533 Institution Message Authentication (Wholesale)," American
534 Bankers Association, 1981. Revised 1986.
535
536 [Atk] Atkinson, R., "IP Authentication Header", RFC 1826, August
537 1995.
538
539 [BCK1] M. Bellare, R. Canetti, and H. Krawczyk,
540 "Keyed Hash Functions and Message Authentication",
541 Proceedings of Crypto'96, LNCS 1109, pp. 1-15.
542 (http://www.research.ibm.com/security/keyed-md5.html)
543
544 [BCK2] M. Bellare, R. Canetti, and H. Krawczyk,
545 "Pseudorandom Functions Revisited: The Cascade Construction",
546 Proceedings of FOCS'96.
547
548 [Dobb] H. Dobbertin, "The Status of MD5 After a Recent Attack",
549 RSA Labs' CryptoBytes, Vol. 2 No. 2, Summer 1996.
550 http://www.rsa.com/rsalabs/pubs/cryptobytes.html
551
552 [PV] B. Preneel and P. van Oorschot, "Building fast MACs from hash
553 functions", Advances in Cryptology -- CRYPTO'95 Proceedings,
554 Lecture Notes in Computer Science, Springer-Verlag Vol.963,
555 1995, pp. 1-14.
556
557 [MD5] Rivest, R., "The MD5 Message-Digest Algorithm",
558 RFC 1321, April 1992.
559
560
561
562Krawczyk, et. al. Informational [Page 10]
563
564RFC 2104 HMAC February 1997
565
566
567 [MM] Meyer, S. and Matyas, S.M., Cryptography, New York Wiley,
568 1982.
569
570 [RIPEMD] H. Dobbertin, A. Bosselaers, and B. Preneel, "RIPEMD-160: A
571 strengthened version of RIPEMD", Fast Software Encryption,
572 LNCS Vol 1039, pp. 71-82.
573 ftp://ftp.esat.kuleuven.ac.be/pub/COSIC/bosselae/ripemd/.
574
575 [SHA] NIST, FIPS PUB 180-1: Secure Hash Standard, April 1995.
576
577 [Tsu] G. Tsudik, "Message authentication with one-way hash
578 functions", In Proceedings of Infocom'92, May 1992.
579 (Also in "Access Control and Policy Enforcement in
580 Internetworks", Ph.D. Dissertation, Computer Science
581 Department, University of Southern California, April 1991.)
582
583 [VW] P. van Oorschot and M. Wiener, "Parallel Collision
584 Search with Applications to Hash Functions and Discrete
585 Logarithms", Proceedings of the 2nd ACM Conf. Computer and
586 Communications Security, Fairfax, VA, November 1994.
587
588Authors' Addresses
589
590 Hugo Krawczyk
591 IBM T.J. Watson Research Center
592 P.O.Box 704
593 Yorktown Heights, NY 10598
594
595 EMail: hugo@watson.ibm.com
596
597 Mihir Bellare
598 Dept of Computer Science and Engineering
599 Mail Code 0114
600 University of California at San Diego
601 9500 Gilman Drive
602 La Jolla, CA 92093
603
604 EMail: mihir@cs.ucsd.edu
605
606 Ran Canetti
607 IBM T.J. Watson Research Center
608 P.O.Box 704
609 Yorktown Heights, NY 10598
610
611 EMail: canetti@watson.ibm.com
612
613
614
615
616
617
618Krawczyk, et. al. Informational [Page 11]
619
620