Cryptography and CS and Politics (sort-of)

Some smart CS folks, claiming omniscence, have predicted exactly who will win the 2008 U.S. Presidential Election.  Except that, of course, they don't want to tip their hands to the betting public.  So, instead, they created a document containing their prediction, saved it, computed an MD5 hash of the prediction file, and published the MD5 hash on their webpage.  Once the election happens, they'll publish their prediction file, and anyone can run MD5 on the file to verify that they had made the prediction a full year before the election.

Except, of course, they haven't.  What they have done is taken a previously-published vulnerability with the MD5 algorithm and executed a dramatic proof-of-concept.  They've created twelve different prediction files, very carefully, in such a way so that all twelve files have exactly the same MD5 hash.  Thus, it doesn't matter who wins; they'll take whoever wins and publish his/her prediction file.

In cryptography, we call this situation a collision: a case where two (or more) inputs to a hash function produce the same output.  Cryptographic hash functions are frequently used like signatures to verify the integrity of a message. It is thus important that such functions be collision-resistant: that is, it should be extremely difficult to find (or construct) a collision for a given hash function.

I could spend a lot of time writing formulas on a whiteboard illustrating the concept.  But these folks have done it far more dramatically.  Cool.