Submitted to:IP Security B. Rogers Internet Draft Ascend Communications expires in six months 12. February 1998 Use of Block Ciphers for Message Authentication Status of this Memo This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and 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 inapproporiate to use Internet Drafts as reference material or to cite them other than as "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), munnari.oz.au (Australia), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). Abstract This draft describes CBC-MAC, a method for using encryption functions to produce message authentication hashes. CBC-MAC can be used with any block cipher (eg. DES, 3DES, Blowfish) in combination with a secret key appropriate for that cipher. The cryptographic strength of this authentication depends on the strength of the algorithm, and may be influenced by other factors appropriate to the algorighm (eg. Weak Keys for DES). Introduction Providing a way to check the integrity of information transmitted over or stored in an unreliable medium is a prime necessity in the world of open computing and communications. Mechanisms that provide such integrity check based on a secret key are usually called "message authentication codes" (MAC). Typically, message authentication codes are used between two parties that share a secret key in order to validate information transmitted between these parties. A method for creating MACs using block ciphers has been well known to the cryptographic community for quite some time [Sch96]. However, Rogers expires in six months [Page 1] INTERNET DRAFT CBC-MAC February 1998 cryptographers tend to omit details necessary for programmers to produce interoperable implementations. This document is intended to provide those details. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC 2119]. Notation b1^b2 This is the bitwise exclusive or of blocks `b1' and `b2'. These blocks are assumed to be the same length. e(k,b) This is the result of encrypting block `b' using algorithm `e' and key `k'. e-CBC-MAC(k,m) This is the authenticator produced by the CBC-MAC algorithm given the message `m' and the key `k'. In practice, `e' will be replaced by the name of a cipher (eg. 3DES-CBC-MAC). Definition of CBC-MAC CBC-MAC is defined with regards to a specific shared key block cipher (Such as DES, 3DES or Blowfish). It produces a message authenticator for arbitrary octet streams which can be verified by any entity sharing the key of the authenticator. The basic algorithm is only capable of authenticating messages which are an integral number of blocks in length. Thus, for a given cipher and message, the message must be tail-padded the the closest block boundary using all zeroes. Once this padding is done (producing m'), the message should be divided into sequential blocks P(0),...,P(n). The production of the authenticator can be described inductively: C(0) = e(k, P(0)) C(i+1) = e(k, P(i+1)^C(i)) The result e-CBC-MAC(k,m) is the result of C(n). Discussion The property we look for in a "good" message authentication code is that another party cannot create valid codes without knowing the shared secret key. In this case, we need only to show that it is Rogers expires in six months [Page 2] INTERNET DRAFT CBC-MAC February 1998 "difficult" to either discover information about the key, or to produce valid results without having the key. If these two properties hold, the MAC will be called strong. While it does not make sense to compare the strength of an encryption algorighm to that of an authentication algorithm, it can be shown that the strength of a CBC-MAC on fixed lenght messages will be dependent on the strength of the base cipher `e' [BKR94]. In fact, for fixed length messages, it has been proven that discovering information about the key, or producing invalid results without the key is at least as difficult as compromising the key, or generating arbitrary ciphertext-plaintext pairs within the given encryption algorithm. This is not the case for variable length messages. Certainly, the padding can be exploited to produce collisions in a trivial manner. [BKR94] shows that CBC-MAC can be compromized as well when the length of the message follows the message itself, assuming a system exists which will authenticate arbitrary messages. This problem can be addressed by prepending the length to the message. CBC-MAC will also serve well as a pseudo-random number generator, as it demonstrates the characteristics (distribution of entropy from the input string and irreversibility) we would like to see in such a function simply as a result of the same characteristics being evident in the underlying block cipher. The tail vulnerability of CBC-MAC may compromise the effectiveness of this function if mutually hostile parties are allowed to contribute pieces to the encrypted string. References [BKR94] Bellare, M., J. Kilian and P. Rogaway., "The Security of Cipher Block Chaining", Advances in Cryptology - CRYPTO 94 Proceedings. [Sch96] Schneier, B., "Applied Cryptography, Protocols, Algorithms, and Source Code in C", 2nd edition. Author's Address Ben Rogers Ascend Communications 655 Metro Place South Suite 370 Dublin, OH 43017 Phone: (614) 760-4045 Rogers expires in six months [Page 3] INTERNET DRAFT CBC-MAC February 1998 EMail: ben@ascend.com Rogers expires in six months [Page 4]