More problems with hash functions

Jerrold Leichter jerrold.leichter at smarts.com
Sat Aug 28 07:08:11 EDT 2004


| > 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.
It all depends on how you define an attack, and how you choose to define your
security.  I explored the "outer edge":  Distinguishability from a random
function.  For a random function from {0,1}*->{0,1}^k, we expect to have to do
2^k work (where the unit of work is an evaluation of the function) per
collision.  The collisions are all "independent" - if you've found N, you have
... N.  The next one you want still costs you 2^k work.  However ... no on-
line function can actually be this hard, because a Joux-style attack lets you
combine collisions and find them with much less than the expected work.
Because a Joux-style attack works exponentially well, the cost for a very
large number of collisions is arbitrarily small.  Note that this has nothing
to do with the number of internal states:  One can distinguish random on-line
functions (in the sense I defined) from random functions (My criterion of
"infinitely many extendible collision pairs" may be too generous; you may need
some kind of minimum density of "extendibile collision pairs".)

You can certainly "de-rate" such a function by discarding some of the bits
of the output and considering the range of the output to be {0,1}^l, l < k.
But I don't see how that helps:  In the limit, collisions become arbirarily
cheap, and making collisions easier can only decrease the cost of finding
them.

If the question is how close to the ultimate limit you can get a function
*constructed in a particular way*, then, yes, passing more internal state may
help.  In fact, it's the only thing that can, if you want an on-line
algorithm - you have nothing else available to vary!  A full analysis in this
direction, though, should have *two* security parameters:  The current one,
the size of the output; and the amount of memory required.  After all, MD5
(for example) is only defined on inputs of up to 2^64 bytes.  If I allow 2^64
bytes of internal state, then the "on-line" qualifier becomes meaningless.

							-- Jerry

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



More information about the cryptography mailing list