?splints for broken hash functions

[John Denker]

I agree with 99% of what Hal Finney wrote.  I won't repeat
the parts we agree on.

But let's discuss these parts:

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

I'd say the answer is at most 2^160, possibly 2^160, but not provably
2^160.  Every amateur cryptographer who combines two methods expects
to get a multiplicative increase in strength ... but cryptanalysts
earn their living by finding ways to kill multiple birds with one
stone.

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

Righto.

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

I don't think that last question is the right question.  Journeyman
cryptographers check that their work is resistant to *known* attacks.
Master cryptographers design stuff that is resistant to attacks that
are not known, and not really even conceived of.

I don't claim to be much of a cryptographer, so I suppose I'd better
answer the question :-).

*Ideally* just changing the IV should be sufficient.  But *ideally*
the basic hash function wouldn't be broken and wouldn't need splinting.

I strongly prefer my long-range permutation trick, for the simple(?)
reason that I just don't like the prefix property.  It's a gut reaction.
My intuition is screaming at me:  bad design, bad design, asking for
trouble, asking for trouble.

Here is a barely-conceivable attack, offered as an a-posteriori
parable in support of the just-mentioned intuition.  Suppose we
have a long input string.  And suppose there are some initialization
vectors that are somehow "weak".  Further suppose somebody jiggers
the first block to make a weak IV for the second block, then jiggers
the second block to make an even weaker IV for the third block, and
so on.  Finally the IV for the last block is so weak that any desired
final result can be achieved.  (I'm not saying that there's the
slightest reason to believe such an attack is possible ... remember
this is just a parable.)  The point of the story is that maybe long
messages are more vulnerable to attack than short messages.  They
offer a bigger target.  [End of parable.]

In any case, I reeeally don't like the prefix property.  And the
cost of eliminating it is incredibly small ... so why not?  Just
apply the long-range permutation, i.e. cut a few bytes off the
front of the second string and paste them onto the end

So I still prefer the scheme in my previous email.  In its
simplest version, the diagram is:

    IV1 (h) B1  (h) B2  (h) B3  (h) ... Bk  -> H1
    IV2 (h) B1' (h) B2' (h) B3' (h) ... Bk' (h) H1 -> H2 = final

where processing proceeds left-to-right, both rows can be
computed in parallel, (h) denotes the elementary hash-a-block
operation, and the primes on the second stream indicate that
it has been subjected to the long-range permutation operation.

For that matter, it wouldn't hurt my feelings if you applied
long-range permutations to *both* strings.  (Not the same
permutation, of course.)  Did I mention that I really don't
like the prefix property?

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