?splints for broken hash functions

Hal Finney hal at finney.org
Sun Aug 29 12:50:12 EDT 2004


John Denker writes:
> Run two hash-machines in parallel.  The first one operates
> normally.  The second one puts the first block of the string
> into a buffer (bounded size!) and then proceeds to hash the
> rest of the string, starting with the second block.  At the
> end of the message, it appends the saved block to the tail of
> the message and hashes it.
>
> The two results are combined in some nonlinear way, perhaps
> by appending the other machine's hash onto this machine's
> input string.

To represent this pictorially, where the Bi are the input blocks:

  (IV) -> B1 -> B2 -> B3 -> ... Bk -> H1
  (IV) -> B2 -> B3 -> ... Bk -> B1 -> H2

then we combine H1 and H2 nonlinearly.


> The strength here comes from the idea the that you cannot
> engineer a collision in the "saved" block in the second
> machine until you have engineered the collision in the
> first machine, and then if you change the saved block to
> engineer a collision in the second machine you have to
> redo everything you did in the first machine.

Another attack approach though would be to fix B1, so we have
in effect:

  (IV') -> B2 -> B3 -> ... Bk -> H1
  (IV)  -> B2 -> B3 -> ... Bk -> B1 -> H2

where IV' is the output of (IV)->B1.  Now we might try to find two B2
values which simultaneously collided on IV and IV'.  This will be harder
than finding two values which collide just on IV, but how much harder?

Well, probably a lot.  Finding a regular B2 collision in a perfect
160 bit hash compression function takes 2^80 work.  Finding a double
collision like this is essentially the same as finding a collision on
a double-width hash function and takes 2^160 work, enormously more.
Of course we don't know for sure that there is no short-cut attack
that exploits the weakness of the compression function to allow double
collisions to be attacked, but it certainly appears to be much harder.

If this is in fact true, how about this simpler construction?

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

and again combine H1 and H2.  Here we run a hash function twice in
parallel but with two different IV values.  Superficially it looks weaker
than John Denker's construction, because the blocks line up nicely, but
as I have rearranged John's construction above they may not really be that
different.  Is there an attack against this version that John's resists?

Hal Finney

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



More information about the cryptography mailing list