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)
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)
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/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)
-- 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)
-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)
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)
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)
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 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]
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]