A splint for broken hash functions

[John Denker]

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)))
         ^

>  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.
...
> 
> This is based on John Denker's second proposal.
> But this proposal uses a trivial transformation
> to force divergence in internal states rather
> than using a reordering of blocks.

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.

At the very (!) least, we should call the two parallel
hash operations H1 and H1prime, and give H1prime a
different initialization vector.  This has considerable
benefits at essentially zero cost, which makes for a
nice cost/benefit ratio.

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

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.

===============

It should go without saying that if you start with two different
hash functions (H1 and H2) which are not assumed strong but
are expected (hoped?) to not have the same weaknesses, you
want to use one of each:
      Hnew(M)  = H1(M  (+)  H2(TT(M)))

===============

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.

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

I reiterate my preference for having the transformation include
a _long-range_ permutation.  My previous suggestion of relocating
an entire block is sub-optimal;  bear's half-block suggestion is
better (since it works for short one-block messages) and indeed
you could pick a smaller chunk, maybe 24 bytes.  But do not restrict
it to a short-range permutation i.e. within a given block; cut a
chunk off the front of the second stream and paste it onto the
very end.  This works well enough for one-block strings, but works
even better for longer messages, by destroying the prefix property,
thereby increasing the attacker's work ... out of all proportion
to the legit user's work.

My guess is that using a TT function consisting of a permutation
plus a change in IV should be enough to keep the attackers at bay
for a few years at least (hopefully long enough for us to invent,
validate, and deploy some intrinsically non-broken hash functions).
However, in the spirit of belt-and-suspenders, we might consider
including a lightweight block cipher (with a widely-known key)
as part of the TT function.

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