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