AES Block Cipher

As discussed in Cryptography: Week Two

Triple-DES is too slow in modern hardware, so a new standard was developed, the Advanced Encryption Standard or AES.

Process started in 1997, in 2000 it adopted Rijndael as AES.

Block size is 128 bits, key sizes are 128, 192, and 256 bits.

The assumption: the larger the key sizes the more secure, but the slower it becomes.

AES is built as a substitution permutation network (not a Feistel network).

In a Feistel network, half the bits were unchanged from round to round. In a substitution permutation network, all the bits are changed in every round.

In the first round, we xor the input wtih the first round key, then we go through a substitution layer where the bits are replaced by other bits depending on what the substitution table says. Finally we go through a permutation layer where bits are permuted.

We repeat in subsequent rounds:

Every step needs to be reversible, so that the whole network is reversible.

AES works on 128 bit blocks, which is 16 bytes.

We write the 16 bytes as a 4 x 4 matrix. Each matrix cell is a byte.

We xor with the first round key then apply a trio of functions, byte substitution, shift row, and mix the column.

We repeat 10 times, though in the final round the mix column step is missing:

So what about the three functions?

ByteSub - 1 byte S-box. 256 byte table. It’s a lookup.

Shift rows: we do a cyclic shift. Different rows shifted different amounts.

Mix columns: linear transformation on each column independently.

Very easily computable.

You have different implementations available depending on environment, you can pre-compute the tables if you want so runtime computation is just lookups and xors.

Or you can not precompute in which case the algorithm is very small, but runtime is longer.

For browser environments, you can ship the code without pre-computation, then as soon as it arrives on the browser you precompute them, and then runtime encryption is fast.

AES is in hardware now given it’s so popular.

Intel and AMD CPUs have instructions to do one round of AES or key expansion.