Peter, Since this description is of a more general interest, I am cc'ing this thread back to the list.
Yes, but inverting a hash function isn't necessarily a problem. Inverting an encryption function is. With hash functions, we really want to know it is hard to take message A and append something B so that f(AB)=f(C). Now, ideally people have always thought that it was bad if given C, one could come up with a D such that f(C)=f(D). But I haven't figured out how that can affect practical problems. Did I miss something?
Let {x} be a hash on x. Let S_A{x} be encryption of the hash of x with Alice's secret key, i.e., Alice's signature over x. Thus, a signed 'thing' is (x, S_A{x}). If {x} yields the function f(y) which tells how different y is from x (ostensibly to measure what damage x sustained in transit, to become y), then f(y) can be exploited to find y such that {y} = {x} (this is, after all, the design criteria behind f(y)). If {x} = {y} then S_A{y} = S_A{x}, and therefore I can publish a document signed by Alice (y, S_A{y}), without her knowledge (both meanings) or cooperation. Someone on the list showed a few months back that provably few errors (or abitrary attacker introduced changes) are needed to get to a matching hash, but finding the changes to introduce is expensive. Building a hash function such that a distance measure is easy to calculate and exploit, makes finding the right errors easier, and thus allows falsified signatures. I take x, introduce my required changes yielding y, and then exploit f(y) with say a genetic search, or simulated annealing, to find y' such that {y'} = {x}, then I republish (y', S_A{x}): my altered document/image/whatever, + some errors to make the hashes match, + Alice's original signature. The signature is verifiable. 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