The Encryption Algorithm Demolition Derby
Contestant would do it again 'in a second'
Last month we reported the triumph of two Belgian academics in the US encryption standard contest. But how was the contest organised? If you're not interested, stop reading now.
In the early seventies the US government put out a call for an encryption algorithm. It had no response. A year later in 1973 they tried again and got one response, from IBM. Then followed a bit of politicking, but by 1975 DES was born.
DES was initially a FIPS (Federal Information Procurement Standard), but was quickly adopted around the world as the de facto standard for encryption.
Certified for five years, DES and was checked regularly to make sure it was still strong enough. But in 1996 the US government decided it needed a new standard - an Advanced Encryption Standard or AES.
It convened a meeting of cryptographers and industry figures and, in a rare example of democracy in action, it asked them what they wanted in an encryption algorithm.
In June 1997 the government put out a call for algorithms. Candidates had to produce an algorithm with a 128-bit block, it had to have variable key lengths - 128-bit 192-bit and 256-bit, and had to be fast and flexible ("Whatever that meant," says Bruce Schneier, founder and CTO of security specialist Counterpane). Also it had to given royalty-free
Of the 21 submissions 15 met the entry criteria. Then began the process Schneier describes as a "demolition derby." All the competitors tried to break each other's algorithms with ever more sophisticated attacks. Scientific papers emerged from the debate and in August of 1998 the first ADS carrier conference met to continue the destruction.
Of the fifteen, fourteen had gone public after their acceptance. The only one that did not was a German entry called Magenta. Unfortunately for the German team this was broken during its announcement. Schneier said: "When a delegate at one of these things says: "Can you flip back to chart twelve?" you know nothing good is going to come of it."
Five "semi-finalists" were chosen to move into the second round of the demolition derby. Mars, RC6, Rijndael, Serpent and Twofish. None of the five were broken.
Of these remaining five, Schneier says that neither Mars nor RC6 was suitable for use on a smartcard - they required too much RAM. He says that any of the other three would have been a good choice. The NSA did some analysis and came back with the same opinion - all would work well.
Schneier says that he thinks the Belgian team's Rijndael algorithm was finally chosen as the winner because it was the fastest of them all. "It was a good way to make the choice," he said. "Anything else would have looked like second-guessing the NSA."
Rijndael has still some political hoops to jump through before it become a FIPS. "The secretary of the interior must agree to its implementation," Schneier says. "Like he cares."
"As a cryptographer, this is the most fun you can have," Schneier says. "I would do it all again in a second."
He thinks is a shame that the EC and Japan have set up their own contests. In his view the NIST process was fair and truly international - not at all US- proprietary. Fair comment, since a couple of Belgian academics won in the end. To that end his company Counterpane has not entered its algorithm, Twofish, in the European or Japanese contests.
It is unlikely that the new AES will become ubiquitous, he reckons "It is a very different world we live in now. People don't want to put all their eggs in one basket, and will use the algorithm they feel suits their needs best."