More problems with hash functions

[bear]

On Fri, 27 Aug 2004, Hal Finney wrote:

>Jerry Leichter writes:
>> However ... *any* on-line algorithm falls to a Joux-style attack.

>That's an interesting point.  One counter example I can offer is my
>earlier suggestion to use a wide path internally between the stages.
>The analysis suggested that if the internal path was twice the width
>of the output of the hash, the Joux attack was avoided.

"Avoided" is too strong a term here.  What you're doing is making
the course twice as long because now the runners are twice as fast.
The Joux attack still "works" in principle, in that finding a series
of k block collisions gives 2^k message collisions; All that you're
doing by making the internal path wider is making the block collisions
harder to find.

When you make them harder to find in such a way as to compensate
exactly for the advantage from the Joux attack, you're not "avoiding"
the attack so much as "compensating for" it.

Still, it looks like you're exactly right that that's one good way
to have an online algorithm that the Joux attack doesn't give any
advantage against; if you want a 256-bit hash, you pass at least 512
bits of internal state from one block to the next.

I had another brainstorm about this last night, which was to use
an encryption algorithm for the block function; that way there are
no block-level collisions in the first place.

Unfortunately, that doesn't cut it; even if there are no block-level
collisions on the state passed forward, there can still be collisions
on state passed forward for every two blocks.  Instead of searching
for a collision of internal state in single blocks, the attacker
would then be searching for it in block pairs.  Given the same amount
of internal state passed between blocks, the search would be no more
difficult than it is now; for the price of finding k block-length
collisions, the attacker gets 2^k colliding sequences.

So far, your suggestion of passing twice as much internal state
between blocks looks like the only sound and simple solution yet
proposed.

					Bear

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