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

So it seems this attack applies if the output size and the chaining value
size are the same, but not if they're different. The assumption you're
making is that if F(X) = F(X') then F(X|N) = F(X'|N) but that's not true if
the output of F is truncated.

William

On Sat, Jul 4, 2015 at 8:30 AM, Dang, Quynh <quynh.dang@nist.gov> wrote:

>
> 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 <tls-bounces@ietf.org> on behalf of Martin Rex <mrex@sap.com>
> Sent: Friday, July 3, 2015 11:42 PM
> To: Quynh Dang
> Cc: tls@ietf.org
> 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
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>
>