Re: IGE mode is broken (Re: IGE mode in OpenSSL)
On 9/9/06, Adam Back <[EMAIL PROTECTED]> 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 Travis H. wrote: I don't see why integrity+confidentiality has to cost n log n operations. I haven't read the whole paper yet (and the proof is at the end) The idea is to costlessly piggy back integrity on top of confidentiality is to have error propagation, so that any fiddling with the message will cause all packets after the fiddling to be random noise. Unfortunately, if this is done with linear operations, it can be undone with linear operations. If it is done with non linear operations (my recommendation), it is hard to prove anything. > Or are universal hashes considered cryptographic-weight primitives, and thus this constitutes a "second pass" over the plaintext? Yes. The idea is to get integrity for free, but unfortunately so many integrity-for-free schemes have come undone, making people suspicious. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
Travis H. wrote: > On 9/9/06, Adam Back <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
On 9/9/06, Adam Back <[EMAIL PROTECTED]> 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 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. 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. -- "On the Internet noone knows you're a dog - except Bruce Schneier." Unix "guru" for rent or hire -><- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
--
James A. Donald
> > > We transmit T(k)= {W(k)} + W(k-1)|{W(k-1)} where |
> > > means bitwise or, curly brace means encryption.
> > Should read: We transmit T(k) = {W(k)} +
> > ((~W(k-11){W(k-1)}) where ~ means bitwise negation,
> > | means bitwise or, curly brace means encryption.
Travis H. wrote:
> Today wasn't a good day for typing? ;-)
>
> T(k) = {W(k)} + (~W(k-1)|{W(k-1)})
>
> Right?
Yes, right, though usually when I get two errors in
rapid succession, I get a third error.
--digsig
James A. Donald
6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG
ORlgCbjNlrRQnTh47hjBg73t8LHfUA5a95TWiM1J
4GftBho6JL/7abDky8QXOX9fhwJxrXqtP87dChEdo
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
On 9/10/06, James A. Donald <[EMAIL PROTECTED]> wrote:
Typo:
> We transmit T(k)= {W(k)} + W(k-1)|{W(k-1)} where |
> means bitwise or, curly brace means encryption.
Should read:
We transmit T(k) = {W(k)} + ((~W(k-11){W(k-1)})
where ~ means bitwise negation, | means bitwise or,
curly brace means encryption.
Today wasn't a good day for typing? ;-)
T(k) = {W(k)} + (~W(k-1)|{W(k-1)})
Right?
I'm in agreement with the "don't use a screwdriver as a crowbar"
crowd; unless the combined modes came with clear proofs and
very weak assumptions computers are fast and getting faster,
and my performance needs remain relatively constant.
--
"On the Internet noone knows you're a dog - except Bruce Schneier."
Unix "guru" for rent or hire -><- http://www.lightconsulting.com/~travis/
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
Kuehn, Ulrich wrote: > > >> From: Ben Laurie [mailto:[EMAIL PROTECTED] >>> Do I understand correctly? You do want that nobody is able to >>> authenticate a message, however, it shall not be intelligible if >>> manipulated with? >> Correct. Minx (which is the only place I use IGE) avoids >> traffic marking attacks in two ways: >> >> a) all messages are "correct" >> >> b) any attempt to mark a message results in its complete corruption >> >> See the Minx paper, http://www.apache-ssl.org/minx.pdf. >> > Looks interesting! Have you looked at Ron Rivest's Chaffing and Winnowing? Yes. Not sure why its relevant? -- 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 [EMAIL PROTECTED]
RE: IGE mode is broken (Re: IGE mode in OpenSSL)
> From: Ben Laurie [mailto:[EMAIL PROTECTED] > > Do I understand correctly? You do want that nobody is able to > > authenticate a message, however, it shall not be intelligible if > > manipulated with? > > Correct. Minx (which is the only place I use IGE) avoids > traffic marking attacks in two ways: > > a) all messages are "correct" > > b) any attempt to mark a message results in its complete corruption > > See the Minx paper, http://www.apache-ssl.org/minx.pdf. > Looks interesting! Have you looked at Ron Rivest's Chaffing and Winnowing? Cheers, Ulrich - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
Kuehn, Ulrich wrote: > > >> -Original Message- From: Ben Laurie >> [mailto:[EMAIL PROTECTED] Sent: Samstag, 9. September 2006 22:39 >> To: Adam Back Cc: Travis H.; Cryptography; Anton Stiglic Subject: >> Re: IGE mode is broken (Re: IGE mode in OpenSSL) >> > [...] >> In any case, I am not actually interested IGE itself, rather in >> biIGE (i.e. IGE applied twice, once in each direction), and I don't >> care about authentication, I care about error propagation - >> specifically, I want errors to propagate throughout the plaintext. >> >> In fact, I suppose I do care about authentication, but in the >> negative sense - I want it to not be possible to authenticate the >> message. >> > > Do I understand correctly? You do want that nobody is able to > authenticate a message, however, it shall not be intelligible if > manipulated with? Correct. Minx (which is the only place I use IGE) avoids traffic marking attacks in two ways: a) all messages are "correct" b) any attempt to mark a message results in its complete corruption See the Minx paper, http://www.apache-ssl.org/minx.pdf. > Or do you want that the authentication test fails if the message has > been tampered with? No. Cheers, Ben. -- 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 [EMAIL PROTECTED]
RE: IGE mode is broken (Re: IGE mode in OpenSSL)
> -Original Message- > From: Ben Laurie [mailto:[EMAIL PROTECTED] > Sent: Samstag, 9. September 2006 22:39 > To: Adam Back > Cc: Travis H.; Cryptography; Anton Stiglic > Subject: Re: IGE mode is broken (Re: IGE mode in OpenSSL) > [...] > > In any case, I am not actually interested IGE itself, rather > in biIGE (i.e. IGE applied twice, once in each direction), > and I don't care about authentication, I care about error > propagation - specifically, I want errors to propagate > throughout the plaintext. > > In fact, I suppose I do care about authentication, but in the > negative sense - I want it to not be possible to authenticate > the message. > Do I understand correctly? You do want that nobody is able to authenticate a message, however, it shall not be intelligible if manipulated with? Or do you want that the authentication test fails if the message has been tampered with? > > 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 you want authentication, then authenticate. Use something with known security properties. So instead of running over the plaintext twice like with forward/backward IGE, try something like EAX, which is essentially counter mode with CBC-MAC for explicit authentication. Comes with proofs of security. But then, maybe I did not understand your problem (see above). Regards, Ulrich - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
Typo:
James A. Donald wrote:
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.
Should read:
We transmit T(k) = {W(k)} + ((~W(k-11){W(k-1)})
where ~ means bitwise negation, | 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
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
--
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 [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
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 [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
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. 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. Adam - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
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 Interesting. In fact, Gligor et al appear to have proposed IGE rather later than this date (November 2000). In any case, I am not actually interested IGE itself, rather in biIGE (i.e. IGE applied twice, once in each direction), and I don't care about authentication, I care about error propagation - specifically, I want errors to propagate throughout the plaintext. In fact, I suppose I do care about authentication, but in the negative sense - I want it to not be possible to authenticate the message. These properties are needed for the Minx protocol. So, I mentioned the authentication properties in passing. It is, however, good to know they don't work! And I love the more general result in the paper mentioned (http://eprint.iacr.org/2000/039/). 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. Thanks! Ben. -- 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 [EMAIL PROTECTED]
