HTTP/1.1 200 OK Date: Tue, 09 Apr 2002 09:39:21 GMT Server: Apache/1.3.20 (Unix) Last-Modified: Thu, 22 Jun 1995 22:00:00 GMT ETag: "323fd2-201b-2fe9e7e0" Accept-Ranges: bytes Content-Length: 8219 Connection: close Content-Type: text/plain Network Working Group H. Krawczyk Internet Draft June 28, 1995 Expires Dec 28, 1995 Keyed-MD5 for Message Authentication draft-krawczyk-keyed-md5-00.txt 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 for use as a message authentication code (MAC) (or, integrity check value -- ICV). 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 keyed-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 Expires Dec 28, 1995 [Page i] INTERNET-DRAFT Keyed-MD5 June 1995 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 [BCK], [KR], [PV]. As part of the results of this analysis we provide here with a particular definition of keyed-MD5. 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 [AH]). An analogous mechanism can be used in combination with other iterative hash functions, e.g., SHA [SHA]. 2. Calculation The definition and reference implementation of MD5 appears in [RFC-1321]. We let D denote the data to which keyed-MD5 is to be applied and K be the shared secret key. The length of K (in bits) is denoted L, and is assumed to be shorter than 512 bits (see section 3 for more information on key selection and size). We let K* be the 512 bits string of the form K*= K10.....0, namely, K* is composed of the L bits of the key K immediately followed by the bit '1' and 511-L bits '0'. Keyed-MD5 of D using the key K is computed by applying MD5 to the concatenation (left-to-right) of K*, D and K. That is, K* is concatenated with (i.e., immediately followed by) D and the obtained string concatenated with (i.e., immediately followed by) K. 3. Keys The key for keyed-MD5 can be of variable length. However, 128 bits is the recommended length. Keys longer than 128 bits do not provide a substantially better security that 128 bit keys. For the description in this draft we assume a key length of less than 512 bits. Keys need to be chosen at random, or using a cryptographically strong pseudo-random generator. Krawczyk Expires Dec 28, 1995 [Page 1] INTERNET-DRAFT Keyed-MD5 June 1995 4. Implementation Implementation of keyed-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 slight modification of MD5 code can provide with some performance improvement of keyed-MD5. This option (which is completely up to the local implementation to adopt or not) is described next. Due to the special form of MD5 iterations and the length of K* being exactly 512 bits the following performance improvement can be achieved. It requires a slight modification of MD5 code in order to allow the initialization of MD5 registers with a variable value rather than with the pre-defined constants. This involves the modification of the procedure MD5Init described in [RFC-1321]. For a 128 bit string V, we denote by MD5_V the application of MD5 with its registers initialized to the four words represented by V. Let K1 denote the 128 bit result of applying the MD5 transform (MD5Transform) to K* (the regular pre-defined MD5 constants are used in this transform). The computation of K1 is done only once per key K (e.g., at time of key sharing); after that, both K and K1 are saved (and their secrecy protected). When coming to apply keyed-MD5 to a stream of information D, this stream is concatenated with (i.e., immediately followed by) K, and MD5_K1 applied to this concatenated information. (Notice that this saves the computation of the first block K*). 5. Security The security of the mechanism presented here depends on the security properties of MD5, especially the pseudo-randomness properties of its basic transform (a.k.a. compression function). The proposed mechanism has better analytical properties relative to other proposed modes for keyed-MD5 like key-prepend, key-append and even the key-prepend-and-append (which is similar to the current mechanism except for the padding of K to K*). For analysis of this and other keyed-MD5 mechanisms see [BCK],[KR] and [PV]. A correct implementation of the above function, the choice of random (or cryptographically pseudorandom) keys, a secure key exchange mechanism, and good secrecy protection of keys are all essential ingredients for the security of the integrity verification mechanism provided by keyed-MD5. Krawczyk Expires Dec 28, 1995 [Page 2] INTERNET-DRAFT Keyed-MD5 June 1995 Acknowledgments The author thanks Mihir Bellare, Ran Canetti, Burt Kaliski and Matt Robshaw for their collaboration in the analysis of keyed-MD5. References [AH] R. Atkinson, "IP Authentication Header", draft-ietf-ipsec-auth-02.txt. [BCK] M. Bellare, R. Canetti, and H. Krawczyk, "Keing MD5 -- Message Authentication via Iterated Pseudo-randomness", manuscript. [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/) [PV] B. Prennel and P. VanOorschot, "Building fast MACs from hash functions", to appear Crypto'95. [RFC-1321] Ronald Rivest, "The MD5 Message-Digest Algorithm", RFC-1321, DDN Network Information Center, April 1992. [SHA] NIST, FIPS PUB 280: Secure Hash Standard, May 1993. [Tsu] G. Tsudik, "Message authentication with one-way hash functions", In Proceedings of Infocom~92, 1992. Author's Address Hugo Krawczyk IBM T.J. Watson Research Center P.O.Box 704 Yorktown Heights, NY 10598 hugo@watson.ibm.com Krawczyk Expires Dec 28, 1995 [Page 3]