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

[Ben Laurie]

Adam Back wrote:
> On Sat, Sep 09, 2006 at 09:39:04PM +0100, Ben Laurie wrote:
>>> There is some more detail here:
>>>
>>> http://groups.google.ca/group/sci.crypt/browse_thread/thread/e1b9339bf9fb5060/62ced37bb9713a39?lnk=st
>> Interesting. In fact, Gligor et al appear to have proposed IGE rather
>> later than this date (November 2000).
> 
> Well looking at the paper by Gligor in their mode submission to NIST
> on IGE, it appears rather that our FREE-MAC was a re-invention of IGE!
> Apparently according to Gligor IGE was proposed by Carl Campbell in
> Feb 1977, about the same time as CBC mode was proposed.  Gligor et al
> wrote the mode-submission for IGE in Nov 2000.
> 
>> I may have misunderstood the IGE paper, but I believe it includes proofs
>> for error propagation in biIGE. Obviously if you can prove that errors
>> always propagate (with high probability, of course) then you can have
>> authentication cheaply - in comparison to the already high cost of
>> biIGE, that is.
> 
> I am not sure about the proofs in the IGE-spec paper, but at least the
> proofs about IGE at least must be flawed somehow because the sci.crypt
> post shows a a class of known plaintext modifications that exhibits
> error recovery.

Indeed, and you'll find this attack (or a similar one) in the proof of
Lemma 4 ("the schemes IGE$-z0 and IGE$-c are not EF-CPA, PU-CPA, PI-CPA,
and NM-CPA secure"), so I don't think you can cite them as flaws :-)

> I worked through it on paper at the time, and as far
> as I can see it trivially breaks IGE/FREE-MAC.  No doubt there are
> other variations so there are lots of permutations you can do in
> rearranging the ciphertext such that the "integrity check" still
> passes.

Note that I was talking about biIGE, not IGE. IGE is indeed broken under
many attack types, and the paper acknowledges that.

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