Fifteen-year-old Peter Schmidt-Nielsen spent only a month working on his submission, but he thinks he’s come up with something “unusual and new.” Never mind that he’s up against some of the most famous cryptographers in the world.
Schmidt-Nielsen is one of more than 60 entrants in what’s expected to be a four-year contest to pick a new hashing algorithm that will help lock down the cryptography used by everything from Web-based payment systems to secure e-mail to source-code management tools.
The contest, sponsored by the National Institute of Standards and Technology (NIST), hopes to find a new cryptographic hash algorithm to replace the SHA-2 (Secure Hash Algorithm – 2) algorithm that NIST published eight years ago. The deadline for SHA-3 submissions was Oct. 31, and NIST hopes to cut the field down to 15 or 20 contestants by next August. That’s when the hard work of hammering away at the submissions and knocking loose any flaws will really begin.
Schmidt-Nielsen and others are doing their work unpaid, competing mainly for prestige and the thrill of seeing their work analyzed by their peers. “I think it’s a ton of fun,” said Schmidt-Nielsen, who first got into cryptography at the tender age of 13. “It will be really fascinating to watch my algorithm get completely torn apart.”
Also in the running are famous cryptographers such as Bruce Schneier, BT’s chief security officer, and Ron Rivest, who invented the widely used MD5 hash algorithm.
But what is a hash algorithm anyway?
Hashing is computer talk for finding a way to take a message — an e-mail, for example — and representing it with a unique number that appears to be random. Hashing was developed as a way to reduce the computing overhead when programs are doing things like scanning files to see if they’ve been changed. It’s much quicker to compare two hash values than to scan through whole files for changes.
In a cryptographic hash, the number is encrypted, creating a digital signature that can be verified using public key cryptography. In practice, these digital signatures are used to confirm, for example, that a Web site really is the site it claims to be, or that an e-mail message is from the person who claims to have sent it, and that it hasn’t been tampered with along the way.
Starting in 2004, researchers led by Shandong University’s Wang Xiaoyun found weaknesses in the MD5 and SHA-1 hash algorithms. They discovered that it was easier than had been thought to create two numbers that share the same hash value. In cryptographic parlance this is called a collision, and it’s considered a very bad thing because it undermines the integrity of the cryptographic system.
“It’s made everybody nervous,” said Rivest, an engineering and computer science professor at the Massachusetts Institute of Technology. He led the team that submitted the MD6 algorithm in NIST’s contest.
The Nostradamus hack showed just why people were nervous: Using MD5, researchers were able to create different .pdf files that shared the same hash value. To illustrate why this is a problem, they published the hash value of the pdf file containing the name of their 2008 U.S. presidential election pick, and then created pdfs with the names of every single candidate, all of which shared that same hash.
That’s supposed to be virtually impossible to do under a secure hash algorithm.
If the Nostradamus people could use collisions to perform their attack, would criminals eventually be able to create fake digital signatures and make phoney phishing sites look exactly like, for example, www.bankofamerica.com?
Maybe some day, said Bill Burr, a manager with NIST’s Security Technology Group. “SHA-1 is not so broken at the moment that we think that people can do the collisions, but we’re expecting the collision any day,” he said. “The notion here is that we’ve got a dike and the dike is leaking, and we’re kind of afraid that we could really have a flood.”
Even though the latest SHA-2 algorithm “is likely to remain secure for the foreseeable future,” it has limitations and is based on old cryptographic techniques, said Schneier, who along with others has submitted a hashing algorithm called Skein. “I think there is good reason to do it.”
Picking the new hash algorithm won’t be done overnight. NIST’s Burr says he doesn’t expect to have a SHA-3 winner until 2012, and it may take a decade more for the algorithm to be widely adopted, he said.
But contests like NIST’s don’t come along everyday, and Burr says he’s impressed by the submissions. Many of them, including Rivest’s MD6 submission, take advantage of new multi-processor computers that are now commonly available and could be faster than today’s algorithms.
“It’s just amazing the amount of work that’s gone into some of these proposals,” Burr said.
“Some of them look fantastic, some of them look like maybe they were done by a 13-year-old kid, and there’s everything in between.”