A new academic hash result on the preprint server

[John Kelsey]

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 at metzdowd.com