>From: "\"Hal Finney\"" <[EMAIL PROTECTED]> >Sent: Sep 1, 2004 1:55 PM >To: [EMAIL PROTECTED], [EMAIL PROTECTED] >Subject: Re: ?splints for broken hash functions
>John Kelsey critiques the proposal from Practical Cryptography: ... > 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. Ah, good point. I honestly was just trying to see if this construction gave inherent resistance to the Joux attack, and it doesn't. That means you still have to do 2^{80} work to get your first collision, but you can get multicollisions a lot more cheaply than you'd expect. Let's consider a slightly simpler version of the Practical Cryptography scheme, and I'll show how to get K-collisions on it for about lg(K)^2 2^{80} work, as opposed to lg(K) 2^{80} work for a standard hash function. I'll call this variant the "two pass hash:" hash'(x) = hash( x || x ) a. I produce a message with 80 * 80 = 6400 blocks, in which each message block is a collision pair. I thus do about 2^{93} work, in order to use Joux' attack to find a 2^{6400}-collision on hash(x). b. I now break the message into superblocks of 80 blocks, which I'll call B[0],B[1],...,B[79]. Note that for each of the 2^{80} possible values for a superblock, the result of hash(x) is identical. (In practice, I'll probably need a few extra blocks in each superblock to deal with the collision search taking longer than expected sometimes.) c. For each superblock, I try as many of the 2^{80} possible sequences of message blocks as I need (which all collide for hash(x)), until I find one that causes a collision in the second pass, as well. The total work is dominated by the 6400*2^{80} search at the beginning, and so we get a set of 2^{80} messages with the same result from the two-pass hash using this variant of Joux' attack, for about 2^{93} work total. Is there a better way to mount this kind of attack on this scheme? Unless I'm missing something, we can iterate this attack for more passes in a pretty straightforward way: for P passes of the hash over the message, when we want a K-collision, we need lg(K) distinct pieces of the message which are 2^{n/2} collisions for the P-1 pass hash. Now, applying this to the Practical Cryptography scheme is complicated a bit by the fact that the message handled by the second pass doesn't break into blocks in quite the same way (it's offset by the number of bits in the hash output). However, this doesn't prevent the attack, it just restricts which bits of the message blocks you can play with when finding collisions. For concreteness, think of SHA1, with 5-word hash output blocks and 16-word message blocks. Now, each of our superblocks from the first pass of hashing are offset five words into the next superblock. That means that the last colliding message block in each superblock needs to have no changed bits in its last 5 words. 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) Comments? >Hal --John Kelsey --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]