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