From dawagner@tucson.princeton.edu Sat Dec  3 01:20:51 EST 1994
Article: 30783 of sci.crypt
Newsgroups: sci.crypt
Path: princeton!tucson.princeton.edu!dawagner
From: dawagner@tucson.princeton.edu (David A. Wagner)
Subject: Extended-width-DES CBC-MAC
Message-ID: <1994Dec3.061919.22473@Princeton.EDU>
Summary: Designing strong hash functions based on DES is subtly difficult.
Originator: news@hedgehog.Princeton.EDU
Sender: news@Princeton.EDU (USENET News System)
Nntp-Posting-Host: tucson.princeton.edu
Organization: Princeton University
Date: Sat, 3 Dec 1994 06:19:19 GMT
Lines: 57

I was reading a paper in Auscrypt '90 entitled
``The three faces of information security'',
and I ran across a suggestion which seems awfully
insecure to me.  I hope noone is using this
suggestion in practice...

The author mentioned that by running DES in
CBC mode over a message and keeping just the
last block, we can get a MAC.  The only problem
is that this is just a 64 bit MAC, so it is
vulnerable to birthday attacks.

The author proposed extending the width of
DES to create a new block cipher like this:

(AL,AR) = K1[Lin]		(BL,BR) = K1[Rin]
(CL,CR) = K2^{-1}[(AL,BL)]	(DL,DR) = K2^{-1}[(AR,BR)]
Lout = K1[(CL,DL)]		Rout = K1[(CR,DR)]

where the input plaintext block is split into
two 64 bit parts (Lin and Rin) and the output
ciphertext block is also split into two 64 bit
parts (Lout and Rout).  AL denotes a 32 bit
quantity, and (AL,BL) denotes the 64 bit block
obtained by concatenating the two 32 bit quantities
AL and BL.  Also, K1[Lin] denotes the result of
encrypting the 64 bit block Lin with single DES
under the key K1.

This is far too complicated -- and the worst
thing of all is that it still appears to have
the same problem as before (namely, falling to
a birthday attack of complexity 2^32):

1. Generate 2^32 arbitrary messages and send them as
   chosen plaintext to the hash function (which works
   by running the extended width DES CBC MAC over the
   chosen plaintext and keeping just the last 128 bits).
2. Look for two messages M, M' so that H(M) and H(M')
   differ only in the right 64 bits.  If such M, M'
   exist, fail.
3. Let X be the XOR of the right 64 bits of H(M) and
   H(M').  Pick any 64 bit plaintexts P, Q.
4. Form a new message A = M concatenated with (P, Q).
   Form a new message B = M' concatenated with (P, Q XOR X).
   Then H(A) = H(B).

Step 2 will fail only with probability 1/2
(or so).  This attack requires on the order
of 2^32 chosen plaintexts and 2^32 space: in
other words, the extended width DES CBC MAC
is no safer than plain old insecure DES CBC MAC.

Any comments or optimizations?

-------------------------------------------------------------------------------
David Wagner                                             dawagner@princeton.edu