[16441] in cryptography@c2.net mail archive
A new academic hash result on the preprint server
daemon@ATHENA.MIT.EDU (John Kelsey)
Thu Nov 18 13:21:15 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 17 Nov 2004 14:03:53 -0500 (GMT-05:00)
From: John Kelsey <kelsey.j@ix.netcom.com>
Reply-To: John Kelsey <kelsey.j@ix.netcom.com>
To: cryptography@metzdowd.com
Guys,
Bruce and I have a new result on hash function security, which uses Joux' multicollision trick in a neat way to allow long-message second preimage attacks. We've posted it to the e-print server.
The basic result is that for any n-bit hash function built along the lines of SHA1 or Whirlpool (e.g., using an n-bit compression function and Damgard-Merkle strengthening), we can mount a second preimage attack on long messages for a lot less than 2^n work. For a 2^k message-block message, we do about 2^{n-k+1} work (when k<n/2) to get a second preimage. We also have a little cheaper way to find a kind of goofy set of multicollisions than Joux gives.
None of this result leads to a practical attack on anything, as far as I can see. The messages that are vulnerable are impractically long, and there's never an attack cheaper than offline collision finding. But I think this result raises some kind-of interesting questions about the security of hash functions between the 2^{n/2} bound for collision finding and the 2^n bound for first and second preimage finding.
Comments appreciated,
--John
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
