Anatomy of AES

From DES to AES: context and structure

In 1997, a challenge issued by a security company was met: the DES cipher, the official standard of the United States since 1977, was broken by brute force. A successor was needed.

The aging of DES

DES (Data Encryption Standard) encrypted 64-bit blocks with an effective key of 56 bits. At its birth, going through the 2^56 possible keys was out of reach. But Moore's law did its work: in 1998, the EFF's Deep Crack machine, built for 250,000 dollars, recovered a DES key in a few days. A standard whose key can be broken by brute force is no longer one.

Stopgaps like triple DES (encrypting three times in a row) prolonged its life, but at the cost of a penalizing slowness. It was necessary to start from scratch.

The NIST competition

Rather than imposing an algorithm in secret, the NIST (the American standardization institute) organized an open competition in 1997. Any team in the world could propose a candidate, provided that everything was public: the design, the code, the analysis. This is Kerckhoffs's principle pushed to its limit — security must come only from the key, never from the secrecy of the algorithm.

Fifteen candidates were submitted, then publicly analyzed for three years by the global cryptographic community. In October 2000, the winner was announced: Rijndael, designed by two Belgians, Joan Daemen and Vincent Rijmen. In 2001, it officially became the AES (Advanced Encryption Standard).

The structure of AES

AES encrypts blocks of a fixed size: 128 bits, or 16 bytes. The key, however, can have three sizes, which gives three variants:

Variant	Key size	Number of rounds
AES-128	128 bits	10 rounds
AES-192	192 bits	12 rounds
AES-256	256 bits	14 rounds

A round is a series of operations repeated several times. The longer the key, the more rounds are added to mix the data further.

The state: a 4x4 matrix of bytes

During encryption, the 16 bytes of the block are not processed in a line, but arranged in a grid of 4 rows by 4 columns, called the state. The bytes are placed column by column:

        col0   col1   col2   col3
lig0  [ o0  |  o4  |  o8  |  o12 ]
lig1  [ o1  |  o5  |  o9  |  o13 ]
lig2  [ o2  |  o6  |  o10 |  o14 ]
lig3  [ o3  |  o7  |  o11 |  o15 ]

Each cell contains one byte (8 bits). All AES operations transform this matrix, round after round, up to the final encrypted block. This grid organization is not decorative: it allows acting sometimes on the rows, sometimes on the columns, to mix the information in both directions.

In summary