776 views

Skip to first unread message

Sep 13, 2000, 3:00:00 AM9/13/00

to

There was a scheme proposed some time back for MAC along with encryption,

called Free-MAC (attached below)

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

Sep 16, 2000, 3:00:00 AM9/16/00

to

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:

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu