[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
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).


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


   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

   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",
   document are to be interpreted as described in [RFC 2119].


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


   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

   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.


   [BKR94] Bellare, M., J. Kilian and P. Rogaway., "The Security of
   Cipher Block Chaining", Advances in Cryptology - CRYPTO 94

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