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 [EMAIL PROTECTED]
