Hello,

We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not an Insider? Subscribe now for unlimited access to online articles.

A View from Erica Naone

The Nostradamus Attack

When does cryptography collide with the work of Nostradamus?

  • November 17, 2008

As early as November 2007, a group of security researchers predicted that Barack Obama would be elected president this month. But before you get too impressed, you should know that they also created predictions for John McCain, Ralph Nader, and Paris Hilton. Anyone can come up with a bunch of bum predictions, but what matters here is that the researchers came up with a scheme that could have allowed them to present any one of these predictions as their single guess.

The researchers created the scheme to illustrate a point about cryptographic hash functions, which are key building blocks of secure protocols on the Internet, including those used for e-commerce. Cryptographic hash functions reduce a message of any size to a “digital fingerprint” of a set size, which can then be used as a stand-in for the original. The idea is that, from the fingerprint, it won’t be possible to derive the original message. It also shouldn’t be easy to find “collisions”–two messages that produce the same fingerprint. These fingerprints can be used as digital signatures. In other words, I could send you the fingerprint as proof of my prediction, and then reveal the prediction itself at a later time.

The researchers’ predictions, which all look like perfectly ordinary PDF files, are a virtuosic example of producing collisions. Every one of the researchers’ predictions has the same fingerprint when using the cryptographic hash function MD5, which was broken in 2005 by Xiaoyun Wang, a professor at the Center for Advanced Study at Tsinghua University, in China, and her coauthors. The researchers’ Web page explains the work in more detail.

For more about cryptographic hash functions, look for a story tomorrow about the current search for a new standard algorithm.

Couldn't get to Cambridge? We brought EmTech MIT to you!

Watch session videos here
More from Intelligent Machines

Artificial intelligence and robots are transforming how we work and live.

Want more award-winning journalism? Subscribe and become an Insider.
  • Insider Plus {! insider.prices.plus !}* Best Value

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus the digital magazine, extensive archive, ad-free web experience, and discounts to partner offerings and MIT Technology Review events.

    See details+

    Print + Digital Magazine (6 bi-monthly issues)

    Unlimited online access including all articles, multimedia, and more

    The Download newsletter with top tech stories delivered daily to your inbox

    Technology Review PDF magazine archive, including articles, images, and covers dating back to 1899

    10% Discount to MIT Technology Review events and MIT Press

    Ad-free website experience

  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning print magazine, unlimited online access plus The Download with the top tech stories delivered daily to your inbox.

    See details+

    Print Magazine (6 bi-monthly issues)

    Unlimited online access including all articles, multimedia, and more

    The Download newsletter with top tech stories delivered daily to your inbox

  • Insider Online Only {! insider.prices.online !}*

    {! insider.display.menuOptionsLabel !}

    Unlimited online access including articles and video, plus The Download with the top tech stories delivered daily to your inbox.

    See details+

    Unlimited online access including all articles, multimedia, and more

    The Download newsletter with top tech stories delivered daily to your inbox

/3
You've read of three free articles this month. for unlimited online access. You've read of three free articles this month. for unlimited online access. This is your last free article this month. for unlimited online access. You've read all your free articles this month. for unlimited online access. You've read of three free articles this month. for more, or for unlimited online access. for two more free articles, or for unlimited online access.