[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Generic CBC-MAC specification


Unlike most of you, I do not believe that the security of 
CBC-MAC is so straightforward. Most of the (public) results
on its security are only a few years old, so I would not rely
on a text book... 

For the additional encryption: this is only necessary to make 
CFB-MAC exactly identical to CBC-MAC (you get the same result,
but with a different mode).  So it is not used in CBC-MAC. 

- While there is indeed the very nice security proof by Bellare 
  and Rogaway [1], this proof only "works" up till 2**32 messages 
  both for DES and for 3-DES.
  An attack using this number of known text-MAC pairs can be found
  in [2]. The forgery attack becomes harder if only a 32-bit 
  result is being used (more chosen texts required).  

- Addressing the variable length problem is not as easy as it seems.
   - There is a trivial attack if you do nothing. If you only use
     32 bits, there is a very recent attack requiring only 2**16 texts [3]. 
   - Prepending the length seems to work, but is not possible in 
     all applications [1].
   - Encrypting the final result with a derived key has been proposed 
     by the RIPE consortium in 1992 [4]. This proposal was then included in the
     annex of ISO/IEC 9797:1993 (which is not informational).  
   - The ANSI retail MAC uses triple encryption in the last step; 
     this solution has also been included in the annex of ISO 9797.
     However, there is a recent key recovery attack showing that this
     is not as secure as it should be [5].

In conclusion: 
it might be wise to consider writing up a solid draft on CBC-MAC.
 

[1] BELLARE, M., KILIAN, J., and ROGAWAY, P.: `The security of cipher block 
    chaining', Advances in Cryptology, CRYPTO'94, Lect. Notes Comput. Sci. 839,
   (Springer-Verlag, 1994), pp.~341--358

[2] PRENEEL, B. and VAN OORSCHOT, P.C.: `MDx-MAC and building fast MACs
   from hash functions', Advances in Cryptology, CRYPTO'95, Lect. Notes Comput.
   Sci. 963, (Springer-Verlag, 1995), pp. 1-14

[3] KNUDSEN, L.R.: `A chosen text attack on CBC-MAC', Electron. Lett., 
   1997, 33, (1), pp. 48-49

[4] RIPE: `Integrity Primitives for Secure Information Systems. 
    Final Report of RACE Integrity Primitives Evaluation
    (RIPE-RACE 1040),' LNCS 1007, A. Bosselaers, B. Preneel, Eds., 
    (Springer-Verlag, 1995)

[5] PRENEEL, B and VAN OORSCHOT, P.C.:  `A key recovery attack on the
    ANSI X9.19 retail MAC', Electron. Lett., 1996, 32, (17), pp. 1568-1569

 FIPS 113: `Computer Data Authentication,' Federal
    Information Processing Standard (FIPS), Publication 131, 
    (National Bureau of Standards, US Department of Commerce, 
    Washington D.C., May 1985)
 ANSI X9.9 (revised): `Financial institution message authentication         
    (wholesale)' (American Bankers Association, April 7, 1986)
 ANSI X9.19:  `Financial institution retail message 
   authentication' (American Bankers Association, August 13, 1986)
 ISO 8731:  `Banking - approved algorithms for message authentication, 
    Part 1, DEA, Part 2, Message authentication algorithm (MAA)' (ISO, 1987)
 ISO/IEC 9797: `Information technology - Data cryptographic techniques -
    Data integrity mechanisms using a cryptographic check function employing a 
    block cipher algorithm' (ISO/IEC, 1993)
    (this standard is currently under revision).


If you want to find out how all these standards are related: check 
 MENEZES, A., VAN OORSCHOT, P.C., VANSTONE, S.A.: 
    Handbook of Applied Cryptography, (CRC Press, 1997)


--Bart Preneel  
-------------------------------------------------------------------------------
Katholieke Universiteit Leuven                       tel. +32 16 32 11 48
Dept. Electrical Engineering-ESAT / COSIC            fax. +32 16 32 19 86
K. Mercierlaan 94, B-3001 Heverlee, BELGIUM    

                           bart.preneel@esat.kuleuven.ac.be
                        http://www.esat.kuleuven.ac.be/~preneel
-------------------------------------------------------------------------------


On Thu, 12 Feb 1998, Rich Ankney wrote:

> Actually, the extra encryption of the last block was defined in
> ANSI X9.19 (retail MAC for things like ATM transactions).
> A recent paper by Bellare and Rogaway proves that this approach
> does indeed provide the optimum amount of extra security.
> 
> Regards,
> Rich
> 
> ----------
> > From: Theodore Y. Ts'o <tytso@MIT.EDU>
> > To: FUKUMOTO Atsushi <fukumoto@isl.rdc.toshiba.co.jp>
> > Cc: ipsec@tis.com
> > Subject: Re: Generic CBC-MAC specification
> > Date: Thursday, February 12, 1998 2:48 PM
> > 
> >    Date: Thu, 12 Feb 1998 17:59:36 +0900
> >    From: FUKUMOTO Atsushi <fukumoto@isl.rdc.toshiba.co.jp>
> > 
> >    Only description I could find about CBC-MAC in "Applied Cryptography
> >    2nd ed." (first print) is in p.456, where it says:
> > 
> > 	   [...] encrypt a message with a block algorithm in CBC or CFB
> > 	   modes.  The hash is the last encrypted block, encrypted once
> > 	   more in CBC or CFB modes.
> > 
> >    This last line, "encrypted once more in CBC or CFB modes", seems to be
> >    different from FIPS81 Appendix F, or Mr.Rogers' CBC-MAC draft.
> > 
> >    So my question is, am I right that the description of Applied
> >    Cryptography is wrong, and the "encrypted once more" should only be
> >    applied to CFB mode?
> > 
> > If Applied Crypto says this, Applied Crypto is wrong....
> > 
> > 						- Ted
>
Follow-Ups: References: