How Belgium and a Rainy Doll Secured The World

How Belgium and a Rainy Doll Secured The World

We live in a world which is driven by standards, but who is the one that actually defines the standard? The NSA? No! Governments of the world? No!! The EU? No!!! The IEEE? Yes. Maybe! The IETF? Yes. Maybe!

Well, NIST is one of the most trusted standards agencies in the world, and they had a dream which would build a more security (and more compatible) world. So around the turn of the millennium there was a real lack of compatibility in the encryption of data using symmetric key encryption. The industry was pushing a whole lot of methods: DES, 3-DES, RC5, CAST, TWOFISH, SERPENT, and many more. Some were under licence, and where their usage was restricted, while others were free.

But which was best? Which was the fastest? And, most importantly, which was the most secure? The symmetric method is the core of security, and any flaws would lead to a large-scale lack of trust, especially as we move into cloud-based systems.

So NIST created the race for AES (Advanced Encryption Standard). It would be a prize that the best in the industry would join, and the winner would virtually provide the core of the industry.

So, in 1997, NIST announced the open challenge for a block cipher that could support 128-bit, 192-bit and 256-bit encryption keys. The key evaluation factors were:

Security:

• The would rate the actual security of the method against the others submitted.
• This would method the entropy in the ciphertext — and show that it was random for a range of input data.
• The mathematical foundation of the method.
• A public evaluation of the methods, and associated attacks.

Cost:

• The method would be provide a non-exclusive, royalty-free basis licence across the world;
• It would be computationally and memory efficiency.

Algorithm and implementation characteristics:

• It would be flexible in its approach, and possibly offer different block sizes, key sizes, convertible into a stream cipher, and so on.
• Be ready for both a hardware and software implementation, for a range of platforms.
• Be simple to implement.

Round 1

The call was issued on 12 Sept 1997 with a deadline of June 1998, and a range of leading industry players rushed to either create methods or polish down their existing ones. NIST the announced the shortlist of candidates at a conference in August 1998, and which included some of the key leaders in the field such as Ron Rivest, Bruce Schneier, and Ross Anderson (University of Cambridge) [report]:

• Australia LOKI97 (Lawrie Brown, Josef Pieprzyk, Jennifer Seberry).
• Belgium RIJNDAEL (Joan Daemen, Vincent Rijmen).
• Canada: CAST-256 (Entrust Technologies, Inc), DEAL (Richard Outerbridge, Lars Knudsen).
• Costa Rica FROG (TecApro Internacional S.A.).
• France DFC (Centre National pour la Recherche Scientifique).
• Germany MAGENTA (Deutsche Telekom AG).
• Japan E2 (Nippon Telegraph and Telephone Corporation)
• Korea CRYPTON (Future Systems, Inc.)
• USA: HPC (Rich Schroeppel), MARS IBM, RC6(TM) RSA Laboratories [try here], SAFER+ Cylink Corporation, TWOFISH (Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson) [try here].
• UK, Israel, Norway SERPENT (Ross Anderson, Eli Biham, Lars Knudsen).

One country, the USA, had five short-listed candidates, and Canada has two. The odds were thus on the USA to come through in the end and define the standard. The event, too, was a meeting of the stars of the industry. Ron Rivest outlined that RC6 was based on RC5 but highlighted its simplicity, speed, and security. Bruce Schneier outlined that TWOFISH had taken a performance driven approach to its design, and Eli Biham outlining that SERPENT and taken an ultra-conservative philosophy for security, in order for it to be secure for decades.

Round 2

And so the second conference was arrange for 23 March 1999, after which, on 9 August 1999, the five AES finalists were announced:

• Belgium RIJNDAEL (Joan Daemen, Vincent Rijmen).
• USA: MARS IBM, RC6(TM) RSA Laboratories, TWOFISH (Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson)
• UK, Israel, Norway SERPENT (Ross Anderson, Eli Biham, Lars Knudsen).
• Canada: CAST-256 (Entrust Technologies, Inc),

The big hitters were now together in the final, and the money was on them winning through. Ron Rivest, Ross Anderson and Bruce Schiener all made it through, and with half of the candidates being sourced from the USA, the money was on MARS, TWOFISH or RC6 winning the coveted prize. While the UK and Canada had both had a strong track record in the field, it was the nation of Belgium that surprised some and had now pushed itself into the final [here].

While the other cryptography methods which tripped off the tongue, the RIJNDAEL (‘Rain-doll’) method took a bit of getting used too, with its name coming from surnames of the creators: Vincent Rijmen and Joan Daemen.

Ron Rivest — the co-creator of RSA, had a long track record of producing industry standard symmetric key methods, including RC2, and RC5, along with creating on of the most widely used stream cipher methods: RC4. His name was on standard hashing methods too, including: MD2, MD4, MD5 and MD6. Bruce Schneier, too, was one of the stars of the industry, with a long track record of creating useful methods, including TWOFISH and BLOWFISH.

Final

After nearly two years of review, NIST opened up to comments on the method and which ran until May 2000. A number of submissions were taken, and the finalist seemed to be free from attacks, with only a few simplified method attacks being possible:

The industry then held its breath for the final announcement, and on 2 October 2000 it surprised the security world with the selection of the Rijndael method .. the rest is history.

The Winner

As we can see in Table 1, the methods had different numbers of rounds: 16 (Twofish), 32 (Serpent), 10, 12 or 14 (Rijndael), 20 (RC6), and 16 (MARS). Rijndael had a diffenent number of rounds for different key sizes, with 10 rounds for 128-bit key and 14 for a 256 bit key. Its reduced number of rounds made it a strong candidate for being a winner.

Well, here is an outline of the method:

The details of AES are defined here.

Conclusions

Rijndael has since gone on to conquer the world, and has become the industry standard it was meant to be. Before then many applications used different symmetric key methods, and which made it difficult to transfer encrypted data. Rijndael changed that, and where there was only one real standard for symmetric key encryption. While DES, 3DES, RC5 and many others still exist in the industry, it is AES which is the most supported of all.

After the great success of the AES competition, NIST followed up with a standard for SHA-3, and where Bruce Schiener pitched Skein, but it was those Belgium’s who came good again with the Keccak method: