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

2006-09-25 Thread James A. Donald

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)

2006-09-23 Thread Travis H.

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)

2006-09-23 Thread Ben Laurie
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)

2006-09-16 Thread Travis H.

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)

2006-09-16 Thread James A. Donald

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

2006-09-13 Thread Kuehn, Ulrich
 

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

2006-09-13 Thread Ben Laurie
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)

2006-09-13 Thread Ben Laurie
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)

2006-09-11 Thread James A. Donald

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)

2006-09-10 Thread Ben Laurie
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)

2006-09-10 Thread Adam Back
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)

2006-09-10 Thread 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 [EMAIL PROTECTED]