A splint for broken hash functions

[Hal Finney]

Bear writes:
> This construction takes slightly more than twice as
> much work and twice as much internal state as a
> conventional hash function (embrace it guys, I don't
> think there's a way around it).
>
>    H2(H1) = H1( H1(M)  xor  H1( TT( M)))
>
>  TT denotes some trivial transformation
>  (I propose swapping high and low halves
>  of the first block).  H1 is a conventional
>  hash function and H2 is, I believe, fully
>  resistant to the Joux attack.

Keep in mind that there are two different attacks here.  One is Joux's
multicollision weakness in iterated hash functions, which is primarily
of theoretical interest.  The other is the recent work by Wang et al,
Joux, and Biham which shows genuine attacks on weakened and full versions
of presently-used hash functions.

I think John Denker's suggestion was originally intended to make the
class of practical attacks harder, by requiring them to solve two
problems at once which interact with each other.  Then he showed how
to accomplish this while allowing incremental hashing, and indeed that
construction appears to resist the Joux multicollision attack as well.
It is that multicollision attack that we are focusing on here.

I would suggest a further generalization of your approach:

	Hash ( Hash1(M) || Hash2(M) )

where Hash1 and Hash2 are different n-bit hash functions, and the outer
Hash() takes a 2n-bit input to an n-bit output.  As I suggested in my
previous mail, I propose that Hash1 and Hash2 can be as similar as SHA-1
with two different IV's.

This model captures John Denker's idea, yours above, as well as my
suggestion in the previous mail.

It is somewhat ironic to propose this, since Joux's paper had two
main results: first, that iterated hash functions have too many
multicollisions; and second, that as a result, parallel iterated hash
functions are no stronger than the individual components.  Yet here I
have proposed exactly that construction, parallel iterated hash functions
in the form of Hash1 || Hash2.  The difference is that I don't try to
get 2n strength out of it, I accept that it has only n bits of strength,
and in fact collapse it down to n bits to make that explicit.  So I have
used Joux's forbidden construction to avoid Joux's attack.

That it avoids his attack is seen as I argued before:

  (IV1) -> B1 -> B2 -> B3 -> ... Bk -> H1
  (IV2) -> B1 -> B2 -> B3 -> ... Bk -> H2

The state functions that chain between the blocks will be different
between the two lines, hence a block collision on one line will not be
a collision on the other and Joux's multicollision construction will
not work.  The exception would be if a collision between the lines can
be found, so that the top and bottom state functions become identical
at some point.  From that point on, the subsequent blocks can collide
on both lines and the multicollision construction could work.

To find such a collision between the lines we must find a block which
maps two different chaining inputs to the same output.  But a random
compression function with two chaining inputs is like two different
random functions.  So we must find an input which causes two different
n-bit random functions to collide.  The chance of this happening for
any input is 1/2^n so it will take about 2^n work to find one.  This is
the work necessary to find a collision between the lines.  This level of
work is greater than that needed to invert the overall hash construction
hence does not represent an attack.

Hal Finney

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