Jim Huggins (jkhuggins) wrote,
Jim Huggins

  • Mood:

Cryptography and CS and Politics (sort-of)

Ok ... if you're not a CS geek, you may want to skip this ...

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.
Tags: cs

  • An open letter to my colleagues in academia

    Dear colleagues, This week, I had three different students visit my office hours (or "student hours", as the trendy schools are calling them these…

  • Perseverance

    In sixth grade, I was a student in Mrs. Fitzpatrick's class at Harrison Elementary School in Inkster, MI. One day, substantially into the year, we…

  • I miss harmony.

    (Warning, long, self-indulgent, emo post. Read on at your own risk.) Several years ago, as my patient family will attest, I fell into a YouTube…

  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.