IGE mode is broken (Re: IGE mode in OpenSSL)

[James A. Donald]

     --
Adam Back wrote:
 > Hi Ben, Travis
 >
 > IGE if this description summarized by Travis is
 > correct, appears to be a re-invention of Anton Stiglic
 > and my proposed FREE-MAC mode. However the FREE-MAC
 > mode (below described as IGE) was broken back in Mar
 > 2000 or maybe earlier by Gligor, Donescu and Iorga.  I
 > recommend you do not use it.  There are simple attacks
 > which allow you to manipulate ciphertext blocks with
 > XOR of a few blocks and get error recovery a few
 > blocks later; and of course with free-mac error
 > recovery means the MAC is broken, because the last
 > block is undisturbed.
 >
 > There is some more detail here:
 >
 > 
http://groups.google.ca/group/sci.crypt/browse_thread/thread/e1b9339bf9fb5060/62ced37bb9713a39?lnk=st

http://www.quadibloc.com/crypto/co040603.htm gives a
list of integrity preserving techniques, most of them
patented - perhaps all of them patented.

Of the top of my head, I would think the following
method preserves integrity - but then who am I.  I
cannot prove it preserves integrity, whereas some of the
modes listed in url above have such proofs.

Let P(k) be the kth block of plain text.  We prepend a
random block, P(0) to the text, and append a fixed block
to the end.  If anything is altered, the fixed block at
the end will not contain the expected data, but will be
gibberish.

The adversary knows every block in the plain text
message except our P(0).  He can intercept and change
the encrypted message.  He wishes to modify the message
so that the intended recipient receives something
different from the message that the adversary knows he
should receive without the intended recipient realizing
something is wrong.

Let W(k) = P(k) + W(k-1) + W(k-1)&{W(k-1)}

Where & means bitwise and, and + means addition modulo 2
to the block size.

W(0) = P(0) (our random block, unknown to the adversary
or the recipient, and changing with every message.)

{} means encryption, {W(k-1)} is the block we get by
encrypting W(k-1)

We transmit T(k)= {W(k)} + W(k-1)|{W(k-1)} where |
means bitwise or, curly brace means encryption.

W(-1) is zero.

The adversary knows P(k), except for P(0), and can
intercept all transmitted values T(k).

Because the combination of addition and bitwise logical
operations is non linear, this method gets through a
loophole in Jutla's proof in
http://eprint.iacr.org/2000/039


     --digsig
          James A. Donald
      6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG
      YQoZxoUUL1Yd2nQ51t9INEhGv6av+5inX+kWvsHX
      49/HJZZyTbJf7yBMbpd6xO13ERPibcb3683FhcMMI

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com