From: collins@newton.apple.com (Scott Collins)
Date: Tue, 2 Nov 93 01:34:52 PST
To: cypherpunks@toad.com
Subject: Re: Hole in MD5
Message-ID: <9311020930.AA05211@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain


Kaliski's response (re: den Boer and Bosselaers' recent work) sounds
reasonable when applied to real life 'human readable' messages typically
comprising many blocks.  I wonder, though, if this technique admits a
reasonable attack on single-block, offline hashing schemes like Bellcore's
timestamping system.

I am a little unsure of the details of their system, but I think I
correctly present the gist of it in the following.

Bellcore's timestamping system is 'offline' in that all the information a
verifier gets is from the prover (except, perhaps, double-checking the root
hash with some public archive).  Most of the important information is
already gone: the maximum depth of that day's hash-tree; the hash-tree
itself; the actual depth of any given timestamp; et al.

Eve has a document, allegedly timestamped with the Bellcore system.  To
prove it to me, she gives me the document (doc), a date/time, and a list of
N hashes, h_1..h_N, where h_N is the root hash for that date (verifable
from some widely published event on that date).  I call Bellcore, or look
in some archives to get the published root hash (root) for that date/time.

        h <- MD5(doc)
        For i<-1..N-1
          h<-MD5(h concatenated with h_i)

When I'm done, if h = h_N, then the timestamp is valid.

Since I don't know the actual depth of Eve's timestamp, her hash sequence
can have any number of elements.  If Eve can produce a collision for
digests the size of the internal nodes in the daily timestamp hash-tree,
even if she can't do it with a single direct collision, she can spoof me. 
(Of course, if she gives me some number of hashes such that 2 to that power
<the number of documents stamped that day> is greater than the number of
people in the U.S., I might smell a rat.)  I haven't yet seen the paper, so
this may be an unreasonable conclusion.

I gathered from Bellcore's presentation at the last RSA conference that
they don't sign the timestamps because "you could always bribe the
timestamper".  They rely completely on the security of the chosen hash
function, and the idea of a 'widely published event'.

If anybody has better/more specific info on Bellcore's system, or den Boer
and Bosselaers work, or Preneel's paper, I would be interested.


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