?splints for broken hash functions

[John Kelsey]

>From: "\"Hal Finney\"" <hal at finney.org>
>Sent: Sep 1, 2004 1:55 PM
>To: cryptography at metzdowd.com, kelsey.j at ix.netcom.com
>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 majordomo at metzdowd.com