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