## Attack on Free-MAC

Showing 1-2 of 2 messages
 Attack on Free-MAC csj...@watson.ibm.com 9/13/00 12:00 AM There was a scheme proposed some time back for MAC along with encryption,called Free-MAC (attached  below)encryption in FREE_MAC is:y_i = E_k( x_i + y_{i-1} ) + x_{i-1}I have a lowerbound  on such schemes. This paper is availableat  http://eprint.iacr.org/2000/039/The lower bound says that any linear scheme which doesMAC and encryption together would require at least log m extraencryptions (m is the number of blocks).That would imply that the above scheme is broken. Variousattacks on this scheme were posted earlier as well. However,doubts remained about various simple fixes. Using the lowerbound, I demonstrate below that this scheme needs major overhaul.Let M_i denote the intermediate quantity x_i+y_{i-1},and N_i denote  E_k(x_i+y_{i-1}).Here is a known plaintext attack (first shown to me by Pankaj Rohatgi).Let y' be the new ciphertext, andlet primed variables denote the new quantities.Now, N_{i+2}= y_{i+2}+x_{i+1} N_i         = y_i          +x_{i-1}Let y'_i = y_i +N_i+N_{i+2}  (all earlier y' remain same as y)Then N'_i = N_{i+2}Hence M'_i = M_{i+2}x'_i= x_i+M_i+M_{i+2}Let y'_{i+1}=  y+{i+1}+M_i+M_{i+2}Then,  N'_{i+1}= N_{i+1}hence, M'_{i+1} = M_{i+1}So, x'_{i+1}= x_{i+1} + N_i +N_{i+2}Let, y'_{i+2}= y_{i+2}Then, N'_{i+2}= N_{i+2}+N_i+N_{i+2}=  N_{i}So, M'_{i+2}= M_iHence, x'_{i+2}=  x_{i+2}So, x'_{i+2}=x_{i+2}, and y'_{i+2}=y_{i+2}, and the computation continuesunperturbed !!If the  last block was a checksum of the plaintexts, then  this would require achosen plaintext attack. All in all, any such scheme is hopeless.  However,see the aforementioned paper for new and interesting schemes which areprovably secure. They are also quite simple.-Charanjit JutlaFrom: Adam Back Subject: Free-MAC modeDate: 07 Mar 2000 00:00:00 GMTMessage-ID: <38C5A4ED...@zeroknowledge.com>Content-Transfer-Encoding: 7bitX-Accept-Language: enContent-Type: text/plain; charset=us-asciiX-Complaints-To: ab...@sprint.caX-Trace: newscontent-01.sprint.ca 952476942 209.5.124.20 (Tue, 07 Mar 2000 19:55:42EST)Organization: Sprint Canada Inc.MIME-Version: 1.0NNTP-Posting-Date: Tue, 07 Mar 2000 19:55:42 ESTNewsgroups: sci.cryptFollowing on from the discussion of block modes which try to exhibit errorpropagation to give a MAC or MDC combined with a block mode in the threadwith subject "avoid man-in-the-middle known plaintext attack using a streamcipher", here's a block mode Anton and I have been working on.encryption is:y_i = E_k( x_i + y_{i-1} ) + x_{i-1}and decryption is:x_i = D( y_i + x_{i-1} ) + y_{i-1}In practice to make a MAC out of this you would append a fixed block to themessage and verify that this fixed block was preserved on decryption.  Thisblock could be public, or perhaps could be the IV, or a separate key.We are working on a paper describing the Free-MAC mode, and output feedbackas a way to get error propagation on the decryption operation of a blockmode.The result is likely to be essentially as efficient as CBC encryption, anddoesn't suffer the block swapping attacks that Propagating-CBC,Plaintext-CBC, iaPCBC and CBCC do.Adam Attack on Free-MAC Adam Back 9/16/00 12:00 AM The lower bound is an interesting result.  Wei commented on this: are you convinced that the formulation you use in your lower bound proof still holds when there are additional shared secret values for:- the checksum- the IV- other keys to encrypt a small constant number of extra blocks under   independent keys (eg. the checksum).   The specific attack you attribute to Pankaj Rohatgi was alsodiscovered by Virgil Gligor, Pompiliu Donescu and Michaela Iorga.Gligor and Donescu found a version of it while working on their IACBC(integrity aware) mode.  I am not sure when they first discovered it, Gligor sent me a mail sometine in March 2000.David Wagner found a related attack against Gligor and Donescu's ioPCBC variant using modular addition for the feedback.Adam