A splint for broken hash functions

bear bear at sonic.net
Sun Aug 29 01:28:17 EDT 2004



Here's a handy way to build Joux-resistant hash
functions with existing tools.

This construction takes slightly more than twice as
much work and twice as much internal state as a
conventional hash function (embrace it guys, I don't
think there's a way around it).

   H2(H1) = 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.

Or, more precisely defined in the
scheme programming language:


;; joux-resistance takes a conventional
;; hash function and returns a joux-resistant
;; hash function derived from it.

(define joux-resistance
  (lambda (H1)
    (lambda (message)
      (H1 (xor (H1 message)
               (H1 (TT message)))))))


(define JR-MD5 (joux-resistance MD5))
(define JR-SHA1 (joux-resistance SHA1))
;; ... etc...

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.

Now the attacker has to find blocks that have
internal-state to internal-state collisions in
both H1(M) and H1(TT(M)) in order to use the
attack, which is the same work factor as finding
collisions in both mappings of start-to-end
states (Denker's reordering proposal) or finding
state-to-state collisions on an internal state
twice as long (Finney's wider internal path
proposal).

I think this is a refinement on Denker's
proposal because we don't have to store the
initial block while we're doing it and don't
have to make changes as deep into the existing
applications in order to implement it, and
more immediately usable than Finney's proposal
because we don't have to wait for the next
generation of hash functions to be written.

			Bear



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



More information about the cryptography mailing list