Attack on Free-MAC

[csj...@watson.ibm.com]

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 available
at http://eprint.iacr.org/2000/039/
The lower bound says that any linear scheme which does
MAC and encryption together would require at least log m extra
encryptions (m is the number of blocks).
That would imply that the above scheme is broken. Various
attacks on this scheme were posted earlier as well. However,
doubts remained about various simple fixes. Using the lower
bound, 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, and
let 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_i
Hence, x'_{i+2}= x_{i+2}

So, x'_{i+2}=x_{i+2}, and y'_{i+2}=y_{i+2}, and the computation continues
unperturbed !!

If the last block was a checksum of the plaintexts, then this would require a
chosen plaintext attack. All in all, any such scheme is hopeless. However,
see the aforementioned paper for new and interesting schemes which are
provably secure. They are also quite simple.

-Charanjit Jutla

From: Adam Back <ad...@zeroknowledge.com>

Subject: Free-MAC mode
Date: 07 Mar 2000 00:00:00 GMT
Message-ID: <38C5A4ED...@zeroknowledge.com>
Content-Transfer-Encoding: 7bit
X-Accept-Language: en
Content-Type: text/plain; charset=us-ascii
X-Complaints-To: ab...@sprint.ca
X-Trace: newscontent-01.sprint.ca 952476942 209.5.124.20 (Tue, 07 Mar 2000 19:55:42
EST)
Organization: Sprint Canada Inc.
MIME-Version: 1.0
NNTP-Posting-Date: Tue, 07 Mar 2000 19:55:42 EST
Newsgroups: sci.crypt

Following on from the discussion of block modes which try to exhibit error
propagation to give a MAC or MDC combined with a block mode in the thread
with subject "avoid man-in-the-middle known plaintext attack using a stream
cipher", 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 the
message and verify that this fixed block was preserved on decryption. This
block 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 feedback
as a way to get error propagation on the decryption operation of a block
mode.

The result is likely to be essentially as efficient as CBC encryption, and
doesn't suffer the block swapping attacks that Propagating-CBC,
Plaintext-CBC, iaPCBC and CBCC do.

Adam

[Adam Back]

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 also
discovered 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