Re: Hole in MD5 (Not)

[collins@newton.apple.com (Scott Collins)]

What follows is a private e-mail exchange with Burt Kaliski (posted with
his permission), where he clarifies the 'hole in MD5' and shows that it
does not afford the attack I described previously.

Mike Ingle:
  >Recently there was a message here about MD5 having a hole in it.
  >Maybe this is what the person was talking about...

Bruce Schneier:
  [ describes Bart Preneel's Ph.D. thesis, which cites the work of
  den Boer and Bosselaer ]

Burt Kaliski:
  [ a LaTeX document noting the implications, or lack thereof, of den Boer
  and Bosselaers' work ]

Scott Collins:
  [ describes an attack on (e.g.) Bellcore's timestamp system; wonders
  if den Boer and Bosselaers' work makes this attack possible ]

Burt Kaliski (private response):
  >When operating on single blocks, MD5 computes a function z = f(x,y0), 
  >where x is the 512-bit message block, y0 is a fixed 128-bit value, and 
  >z is the 128-bit message digest.
  >
  >den Boer and Bosselaers found a way to construct a triple (x,y1,y2) 
  >such that f(x,y1) = f(x,y2). The y1 and y2 values are not the same as 
  >the fixed y0, so clearly this is different than an MD5 collision, 
  >which would have different message blocks.
  >
  >I'm not sure how this relates to the attack you have in mind, although 
  >I'd be interested in more details. Also, the attack you describe is 
  >"after-the-fact" in the sense that the target value h_N is already 
  >published. To forge a time-stamp at that point, what I need is not a 
  >collision, but an inversion. (I have to find something that hashes to 
  >h_N.) Collisions play a greater role "before-the-fact," where I might 
  >give Eve something to sign, where I happen to know another message 
  >with the same digest.
  >
  >-- Burt Kaliski
  >RSA Laboratories

Scott Collins:
  > [ ... ]
  >
  >Ahh. This is not (even close to) a big enough foothold to support my 
  >attack.  :-)
  >
  > [ ... ]
  >
  >The attack does, in fact, require inversion.  Since the verifier can't 
  >compare the depth of the alleged hash tree to the actual one, the attack is 
  >still possible even when only _some_ inversions are possible, as long as 
  >the attacker can find one along the actual path to the root (the degenerate 
  >case being when the attacker can find an inversion for the root itself).
  >
  >The attack only came to mind because the the depth cannot be verified, and 
  >so the attacker is not limited in the number of steps (in case she can only 
  >find inversions of a special form); the intermediate hash values are all of 
  >minimal size; the intermediate hash values are expected to be 'random', and 
  >so there is no constraint requiring human-readable inversions.  Thus, it 
  >seemed that if an the hash could be usefully inverted, this would be the 
  >situation that allowed it.
  >
  >Thanks for the clarification.  May I repost your answer, or at least _this_ 
  >message which quotes it, to the original distribution list of my question?

Permission was granted.


Scott Collins         | "Few people realize what tremendous power there
                      |  is in one of these things."     -- Willy Wonka
......................|................................................
BUSINESS.   voice:408.862.0540  fax:974.6094   collins@newton.apple.com
Apple Computer, Inc.   5 Infinite Loop, MS 305-2B   Cupertino, CA 95014
.......................................................................
PERSONAL.   voice/fax:408.257.1746    1024:669687   catalyst@netcom.com