?splints for broken hash functions

[Hal Finney]

John Kelsey writes:
> So, what this means is that you can still find multicollisions on
> these variant ways of hashing (the two-pass and Practical Cryptography
> constructions) much more quickly than you'd expect from an ideal hash
> function.  You can extend the result to convince yourself that you
> can't get much more than 80 bits of collision resistance from
> constructions like:
>
> hash(X) = SHA1(X) || RIPE-MD160(SHA1(X)||X)

Hi, John, yes, I see that works.  That's a very strong result.
David Wagner suggested almost exactly the same attack to me in private
email, with regard to the construction of running two parallel hashes.
I hope it will appear soon on the cryptography list.  He also used super
blocks and applied the Joux attack at both the small and large level.
You could call it the mega-Joux attack :-).

I believe that it also applies to John Denker's construction of rotating
some bits from the front to the back of one of the two parallel hashes,
working along the lines you suggest for dealing with offset block
boundaries.

These various constructions may still have a certain amount of practical
value in terms of raising the bar for attackers who are using stable bit
techniques to create these shortcut collisions.  But for the ultimate
goal of creating a hash which mimics a random function, it seems another
approach is needed.

At this point the only one I know is to create a k-bit hash function
by using internal paths of 2k bits and compression functions with 2k
bits of strength.  I am still convinced that this construction resists
the Joux multicollision attack, because to even take the first step of
finding a block collision will require 2^k work, and you have already
lost if you are trying to break a k-bit hash function and your attack
takes 2^k work.  A concrete example would be SHA-512 derated to 256 bits,
at least if you believe that the SHA-512 compression function really
has 512 bits of strength.

Hal

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com