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

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

In order for the attack to work, I will have to find a collision for the whole output of the compression function of the first hash function.


The attack works for MD5 || SHA1, SHA1 || SHA-256 etc...But, it does not work for the construction Martin described which provides the same security level of SHA-256.


Quynh.


________________________________
From: TLS <[e-mail]> on behalf of Quynh Dang <[e-mail]>
Sent: Saturday, July 4, 2015 2:34 PM
To: [e-mail]
Cc: [e-mail]
Subject: Re: [TLS] TLS 1.3 draft-07 sneak peek

Hi Martin,

Right. The attack does not work for truncated hashes (or wide-pipe hashes) where hash outputs are smaller than their internal chaining hash values.

Quynh.

On Sat, Jul 4, 2015 at 9:31 AM, Watson Ladd <[e-mail]<mailto:[e-mail]>> wrote:
But these assertions below are not what the paper actually claims!
It's important to actually read the paper, and see that the claims
apply to hash functions of a particular form, namely iterated ones.
The functions mentioned in your counterexample are not iterated hash
functions in the sense of the paper.

Nor, if you believe that the designers of TLS got ciphersuite
negotiation correct, is the claimed "vulnerability" a vulnerability.
If the security of the scheme used by A and B was the strongest in the
intersection, having MD5 based schemes would be fine so long as
everyone had SHA-256 based ones. But we know now that this result
isn't true. (There is an added wrinkle, where a scheme based on a
sufficiently weak hash function will break the negotiation)

On Fri, Jul 3, 2015 at 8:42 PM, Martin Rex <[e-mail]<mailto:[e-mail]>> wrote:
> 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]<mailto:[e-mail]>
> https://www.ietf.org/mailman/listinfo/tls



--
"Man is born free, but everywhere he is in chains".
--Rousseau.