[16072] in cryptography@c2.net mail archive
Re: ?splints for broken hash functions
daemon@ATHENA.MIT.EDU ("Hal Finney")
Wed Sep 1 14:25:11 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
To: cryptography@metzdowd.com, kelsey.j@ix.netcom.com
Date: Wed, 1 Sep 2004 10:55:39 -0700 (PDT)
From: hal@finney.org ("Hal Finney")
John Kelsey critiques the proposal from Practical Cryptography:
> >"We do not know of any literature about how to fix the hash functions,
> >but here is what we came up with when writing this book. ... Let h be
> >one of the hash functions mentioned above. Instead of m->h(m), we use
> >m->h(h(m) || m) as hash function.
>
> I believe this falls to a generalization of the Joux attack, as well. (Someone may have already noticed this.)
>
> a. I build a 2^{80} multicollision on h(m) using Joux' attack, requiring 80*2^{80} work.
>
> b. I now have 2^{80} different messages which are being hashed with the same IV. I expect one pair of them to give me a collision.
You did 80*2^80 work to create a collision. But you could create a
collision without all this effort in only 2^80 work, by a conventional
birthday attack. Just ignore the internal structure and treat it as
a 160 bit hash function and you can collide in 2^80 work. You worked
harder than you needed to, so this is not a break.
Hal
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
