Wednesday, August 18, 2004

On hash function security

Researchers have found flaws in the MD5 and SHA0 hash functions. A hash function is a function which takes a large amount of data (a document, say) and from it generates a much smaller number. Ideally, it should be very hard to find a collision, or two inputs which generate the same output. The recently-discovered flaws in MD5 and SHA0 mean that it's possible to find collisions in these functions much more quickly than anyone had previously realized.

Cryptographically secure hash functions are key to generating digital signatures. To digitally sign a document D, I would compute a hash function H(D), then compute another function S(H(D), K) based on my secret key K. Only I can easily evaluate S, but anyone can check to see that what I've evaluated is correct. We evaluate S(H(D), K) instead of S(D, K) because the output of S is the same size as the input, and we don't want a signature that takes as much space as the original document. Also, we can compute S much more quickly if the input is small. However, we don't want it to be easy for someone to cut our signature and attach it to another document, which they could do if the fake document F had the same hash as D does (i.e. H(D) = H(F)). That's why finding these collisions is considered a big deal.

However, the sky is not falling (except insofar as the sky is always falling locally in areas where convection cycles in the atmosphere produce a downdraft). If I can come up with an input file that produces the same MD5 hash as the mortgage you digitally signed, then I could replace your mortgage with my file, and the signature would still check. But finding some input file that produces the same MD5 hash as your mortgage is a far cry from finding some meaningful input file that produces the same MD5 hash as your mortgage. For the time being, the easiest way to forge an electronic signature on a document in which you will me all your money is to hire goons to steal your key.

  • Currently drinking: Black coffee (Peet's African blend)
  • Current password: Squeamish ossifrage