From: collins@newton.apple.com (Scott Collins)
To: cypherpunks@toad.com
Message Hash: 7b5e49a30d16ab144a4776631e8800698fbac65a3e35628ab349bf33f5ced999
Message ID: <9311051919.AA10041@newton.apple.com>
Reply To: N/A
UTC Datetime: 1993-11-05 19:27:47 UTC
Raw Date: Fri, 5 Nov 93 11:27:47 PST
From: collins@newton.apple.com (Scott Collins)
Date: Fri, 5 Nov 93 11:27:47 PST
To: cypherpunks@toad.com
Subject: Re: Hole in MD5 (Not)
Message-ID: <9311051919.AA10041@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain
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
Return to November 1993
Return to “collins@newton.apple.com (Scott Collins)”
1993-11-05 (Fri, 5 Nov 93 11:27:47 PST) - Re: Hole in MD5 (Not) - collins@newton.apple.com (Scott Collins)