A splint for broken hash functions

[bear]

On Sun, 29 Aug 2004, John Denker wrote:

>bear wrote:
>>
>>    H2(H1) = H1( H1(M)  xor  H1( TT( M)))
>
>I think that was intended to be something like
>
>      H2(M)  = H1( H1(M)  xor  H1( TT( M)))
>         ^

Actually, it was intended to take a hash function
as an argument and define a new hash function which
is Joux-resistant in terms of it.

Perhaps

    JR(H1)(M) = H1( H1 (M) xor H1( TT( M)))

would have communicated the intent more clearly.

Anyway, functions on functions that return functions
kind of need lambda calculus for clear expression,
which is why there was scheme pseudocode restating
the definition following this.

>OK, it looks like we are in agreement on the general
>outline of a reasonable method for splinting broken hash
>functions.

>However I think the given example of a  "Trivial Transformation"
>is _too_ trivial.  There are too many common strings for which
>swapping halves of the first block leaves the string unchanged.

Good point.  I don't want to mess with the IV's though,
because some hash functions may depend for their security
on the exact value of the IV.

> Also, I don't like the XOR function suggested above.  It
> is linear and totally lacking in one-wayness.

That's compensated, I think, by the outer application of H1.
But Hal Finney's response proposes using a 2n-bit to n-bit
hash function on the concatenation of the two H1 results,
which is definitely better.

> That means
> that an attacker has the option of making equal-and-opposite
> (or in the case of XOR, just equal :-) changes in the H1
> output and the H1prime output, leaving the result of the
> XOR unchanged.

It still requires finding a double collision, so the work
factor should be the same.

> Therefore I restate my preference for combining the H1 and
> H1 prime results nonlinearly, perhaps like this:
>      Hnew(M)  = H1(M  (+)  H1prime(TT(M)))
> where (+) denotes the string-concatenation operator.

Okay, if your H1 and H1prime are nonidentical hash
functions, I don't think you're getting any added
security from the trivial-transformation here; Its
purpose in my construction was to force divergence
of the internal state between the two hash functions;
why is it included in yours?

>In case anybody didn't notice, bear's idea of applying the TT
>operator within a given block has some good properties.  In
>particular it strengthens the hashing of short messages,
>including one-block messages.
>
>However IMHO using a truly "trivial" transformation is really
>under-doing it.  Perhaps we should be thinking in terms of
>Tasteful Transformations rather than Trivial Transformations.

:-)  You're right about that; a trivial transformation
makes it too easy to construct an attack by constructing
a block that reads the same under transformation as it
does plaintext.  Instead of swapping first and second halves
of the block, probably the first block of the message should
be replaced by its hash.

Responding to your issue about xor being too insecure, by
taking Hal Finney's suggestion of using a wider hash function
to combine the outputs,  And redefining TT for greater
strength, the construction becomes

H2(M) = Hnew (H1 (M) + H1( TT(M)))

Where H2 is the Joux-resistant version of H1, which is our
desired objective.  TT now means replacing the first block of the
message by its hash value under H1, and + denotes concatenation.
However, this requires implementing an Hnew, which must take a
*single* large block of input (the size of two H1 blocks) and
produce a single H1-sized block of output.

Since we all seem to agree that an Hnew is needed to make the
suggestion concrete, what definition of Hnew do you prefer?

> Also I suggest the transformation should be applied to each
> and every block of the second stream, not just the first
> block.

Why?  Divergence in internal state ought to be complete after
the first block; constructing a message that would force the
internal states of the two hash functions to ever reconverge
would require the same work factor either way.  I don't think
a long-range permutation buys us anything.

It's cheap and it doesn't hurt. We can include it if it makes
us feel any more secure; but why should it make us feel any
more secure?

				Bear

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