Re: [TLS] TLS 1.3 draft-07 sneak peek

["Dang, Quynh" <[e-mail]>]

Hi Martin,

I talked about this issue at the interim meeting in Denver last year. A lot of people there who were very good at crypto, but were not aware of this issue.  In another word, nobody knows all. So, being not aware of something is common to everyone.

Let me explain one of your examples and I hope that will help to make the issue clear.

"OK, here are my algorithms F and G:

  F= sha-256, truncated to bits 0..95 of the output
  G= sha-256, truncated to bits 96..256 of the output"

It takes approximately 2^48 operations to find a block X and X' (X and X' can be any blocks) as long as their 96-bit hash values ( F) are the same.

It takes approximately 2^80 operations to find a block N (N can be any block) so that 160-bit hash values (G) of X|| N and X'|| N are the same.

So, the work required to find a collision for G is  2^80 and the work required to find a collision for F || G is 2^48 + 2^80 and 2^48 is like nothing when being compared to 2^80.

Happy the 4th of July!

Quynh.

________________________________________
From: TLS <[e-mail]> on behalf of Martin Rex <[e-mail]>
Sent: Friday, July 3, 2015 11:42 PM
To: Quynh Dang
Cc: [e-mail]
Subject: Re: [TLS] TLS 1.3 draft-07 sneak peek

Quynh Dang wrote:
> The ineffectiveness issue of cascading hashes has been widely known for a
> long time ago.
>
> Find block X and block X' which have collided hash for SHA1 which takes
> around 2^70 operations or possibly less.
>
> Finding a block N for which X|| N and X' || N have collided hash for MD5
> which is expected to have very low complexity (finding collision for MD5).
>
> Therefore, finding collisions for SHA1 and collisions for SHA1 || MD5
> require about the same computational complexity.


The previously mentioned paper

http://www.iacr.org/cryptodb/archive/2004/CRYPTO/1472/1472.pdf

describes the issue for two arbitrary hash algorithms F and G
with bit sizes nF and nG and you say this applies to

  F= md5  nF=128 bit
  G= sha1 nG=160 bit

  and that the security of F||G would be no stronger than the larger
  of the two (G alone, nG=160).


OK, lets take two other hash algorithms F and G, and even use
a weaker algorithm F with nF=96 and G with nG=160.
The assertion is, that he security of F||G would still be only 160.

OK, here are my algorithms F and G:

  F= sha-256, truncated to bits 0..95 of the output
  G= sha-256, truncated to bits 96..256 of the output

Now if your original assertion is true, then the strength of
F(m)||G(m) which curiously happens to be identical to the output of
sha256 for the message (m) has a security of only 160 bits?

Or lets look at a concatenation of 8 hashes of 32-bits each.

F=sha-256, truncated to bits 0..31 of the output
...



-Martin

_______________________________________________
TLS mailing list
[e-mail]
https://www.ietf.org/mailman/listinfo/tls