?splints for broken hash functions

[bear]

On Sat, 28 Aug 2004, John Denker wrote:

>Jerry Leichter writes:
> >> However ... *any* on-line algorithm falls to a Joux-style attack.

>Hal Finney wrote:

>> ... hashes that support incremental hashing, as any useful hash surely must,

>If you insist on being able to hash exceedingly long strings
>(i.e. longer than your storage capacity) here is a modification
>of the "splint" I proposed earlier.

>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.

>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.



You realize that passing two internal-states forward at each
step is entirely isomorphic to Hal's suggestion of passing
twice as large an internal state forward at each step?

Effectively, you're agreeing with him.  Good hash functions
*do* evidently cost twice as much work and (at least) twice
as much internal storage as we thought before now to compute.

Your proposal triples the amount of state required through
the process (two one-block internal states, and the initial
block), whereas Hal's proposal only doubles it.

			Bear








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