Network  Working Group                                       H. Krawczyk
Internet Draft                                               M. Bellare
                                                             R. Canetti
Expires September, 1996                                      March, 1996


               HMAC-MD5: Keyed-MD5 for Message Authentication
                     <draft-ietf-ipsec-hmac-md5-txt.00>


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]
.
