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

[Ben Laurie]

Travis H. wrote:
> On 9/9/06, Adam Back <adam at cypherspace.org> wrote:
>> 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.
> 
>> http://groups.google.ca/group/sci.crypt/browse_thread/thread/e1b9339bf9fb5060/62ced37bb9713a39?lnk=st
>>
> 
> I don't see why integrity+confidentiality has to cost n log n

Not what he said, he said n+log n.

> operations.  I haven't read the whole paper yet (and the proof is at
> the end), but I don't see why you can't append a universal hash
> (chosen by a second key, or at random and identified in the plaintext
> in some suitable way) of the input to the plaintext prior to
> encryption, and get integrity for cheap.

Which is cost kn, k > 1, so kn > n+log n, in the limit. Proof left as an
exercise for the reader.

>  Or are universal hashes
> considered cryptographic-weight primitives, and thus this constitutes
> a "second pass" over the plaintext?  I must admit I don't know of any
> lower bound on universal hash complexity... wikipedia only mentions
> f(x) = ax + b mod p, (p prime) which is clearly less heavy than modexp
> and other PK algos, and it looks like you could do it incrementally
> over the plaintext x, I think... my intuition tells me this is way
> faster than a block cipher.


-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

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