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

[[e-mail] (Martin Rex)]

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