Rijndael, or how Belgium quietly became the world's locksmith
In June 1998, a machine called Deep Crack — assembled by a team of engineers at the Electronic Frontier Foundation for roughly $250,000 — recovered a Data Encryption Standard key by brute force. It took fifty-six hours. The cipher protecting American bank transactions and government cables, in service since 1977, had been cracked by hardware that cost less than a Manhattan studio apartment. NIST, which had been hedging on DES for years, stopped hedging.
The solution NIST reached for was unusual: throw the problem open to the world. In September 1997, the institute issued a public call for candidate algorithms and ran, over the next three years, the most transparent cipher competition in history. Fifteen complete proposals arrived from cryptographers across ten countries. NIST held public conferences at major cryptography gatherings — Ventura, Rome, New York — invited hostile scrutiny, and let the global community do what cryptographers do: attack. Three years of analysis narrowed fifteen to five finalists: MARS, RC6, Rijndael, Serpent, and Twofish. All five survived serious cryptanalysis. The final decision came down to something more prosaic than mathematical beauty — which one ran fastest on the most hardware?
Joan Daemen and Vincent Rijmen had built their cipher with that question in mind. Rijndael — the name is a portmanteau of their surnames, Daemen and Rijmen flipped and fused — operated through a sequence of mathematical transformations on a 4×4 grid of bytes: rows shifted, columns mixed through a linear operation over a finite field, each byte substituted via a lookup table, a round key folded in. On a 32-bit processor it was fast. On an 8-bit smart card it was fast. In dedicated hardware it was fast. At the third public conference, in April 2000, the five finalist submitters were asked which algorithm they would choose if they could not choose their own. Four of the five named Rijndael.
Here is the detail that some in the room had not entirely anticipated. The NSA — wary of appearing to tilt the competition — had declined to submit a candidate at all. The assumption in certain corners was that a standard destined for classified American communications would end up built by Americans. On November 26, 2001, FIPS PUB 197 became law. The cipher now approved by the NSA for top-secret data had been designed in the Belgian city of Leuven by two men whose names, combined, literally formed the word in the title. Bruce Schneier, whose own Twofish algorithm had lost, wrote the day Rijndael was announced that he doubted anyone would ever find an attack allowing someone to read its traffic. A quarter century later, that sentence has not been revised.
AES does not sit in government systems alone. It is embedded in every TLS handshake, every WiFi session encrypted under WPA2, every file locked on an iPhone, every message encrypted on a modern messenger. A 2018 economic impact study estimated the net present value of the AES standard at up to $250 billion. That is a notable return on a cipher competition with fifteen entrants and three rounds of public conferences.
The next serious challenge to AES will not come from a machine costing $250,000, or from a mathematician with a clever differential attack. It will come from machines that do not yet exist.
Sources
- Advanced Encryption Standard — Wikipedia — competition timeline, FIPS 197 standardization, NSA top-secret approval, successor to DES.
- Development of the Advanced Encryption Standard — PMC — NIST competition structure, 15 candidates from 10 countries, finalist conferences and selection criteria, Rijndael’s performance advantages, economic impact study.
- FIPS PUB 197 — NIST — the November 26, 2001 publication establishing AES as a federal standard.