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