Joe.Buck at synopsys.COM
Thu Jan 25 13:25:17 PST 2007
On Thu, Jan 25, 2007 at 12:36:45PM -0800, Rick Moen wrote:
> To put this matter into further perspective: Let's say there's a legal
> document whose authenticity you're looking to attack in court -- and the
> canonical copy is in electronic form. Some high-tech notary public
> signed a statement saying that the canonical document's SHA-1 checksum
> is blah-blah, so you start using Xiaoyun Wang's techniques to find a
> hashspace collision. You start generating documents and calculating
> their hash values. On average, half a sextillion SHA-1 calculations
> later, a hit!
> Excited, you look at the document that generated the matching hash: Oh,
> damn, it's gibberish. Back to the calculations for another 10^18 trials
> or so, looking for another hit.
Ah, there's where you may be wrong, Rick.
The search space can be restricted to documents that are indistinguishable
from each other. For example, for an ASCII document, you could try adding
a space, or not, to each line, along with the extra zero for the amount
that you are to be paid for a contract. If there are 180 lines, then there are
2^180 different possible documents, but there are only 2^160 different
SHA1 hashes. That means that there are 2^20 possible fake documents that
have the same SHA1 sum as the original.
More information about the svlug