More problems with hash functions

[Hal Finney]

Jerry Leichter writes:
> However ... *any* on-line algorithm falls to a Joux-style attack.  An
> algorithm with fixed internal memory that can only read its input linearly,
> exactly once, can be modeled as an FSM.  A Joux-style attack then is:  Find
> a pair of inputs M1 and M1' that, starting from the fixed initial state, both
> leave the FSM in state S.  Now find a pair of inputs M2 and M2' that, starting
> from S, leave the FSM in state S'.  Then for the cost of finding these two
> collisions, we have *four* distinct collisions as before.  More generally,
> by just continuing from state S' to S'' and so on, for the cost of k
> single collision searches, we get 2^k collisions.

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.  Basically if
the hash output width is n, and the internal width is 2n, then it will
take 2^n to find an internal collision.  And the overall hash strength
is never more than 2^n against any attack, since you can exhaustively
invert the function for that effort.  So nothing based on internal
collisions can weaken a hash built around this principle.

It's not a particularly appealing design strategy due to its apparent
inefficiency.  But if you're right about the general vulnerability of
hashes that support incremental hashing, as any useful hash surely must,
then perhaps it is worth exploring.

Hal Finney

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