AES stands for the “Advanced Encryption Standard”, which was established by NIST in 2001.
The underlying algorithm is Rijndael, a block cipher used for symmetric-key encryption, with 3 different key lengths, 128, 192, 256 bits and with block sizes of 128 bits.
AES obsoletes the previous standard from 1977, DES. DES was deemed insecure – it supported key sizes of 56 bits and had to be run three times to be considered secure, which is called 3DES (Triple-DES). This is computationally very slow, so AES improves upon this.
An encryption algorithm should aim to make the plaintext as different
from its generated ciphertext as possible. Claude Shannon codified these
in two terms, Confusion and Diffusion.
Confusion means that each output bit of the ciphertext should ideally depend on several parts of the key, making it hard to figure out the connection between the pair.
Diffusion means that changing any part of the plaintext should change half of the ciphertext, and vice-versa. This diffuses the changes between the bits, making it hard to see the relation between the bits on the input and output.
AES does the following steps:
KeyExpansion: AES expands the given cipher key into many keys – the number of keys required depends on the rounds, and is the number of rounds + 1.
AddRoundKey: Each byte of the state is combined with a byte of the round key by XOR’ing.
for all but the last round:
S_BOX.For the final round:
In the final round, MixColumns is skipped because it doesn’t add any additional security.
In code:
fn aes_encrypt(block: &[u8; AES_BLOCK_SIZE], key: &[u8]) ->
Result<[u8; AES_BLOCK_SIZE], Box<dyn Error>> {
` let expanded_key = expand_key(key, nk, nr);
let (nk, nr) = calculate_parameters(key_len);
let mut state = copy_block_to_state(block);
add_round_key(0, &mut state, &expanded_key);
for round in 1..nr {
sub_bytes(&mut state);
shift_rows(&mut state);
mix_columns(&mut state);
add_round_key(round, &mut state, &expanded_key);
}
// Final round (without mix_columns)
sub_bytes(&mut state);
shift_rows(&mut state);
add_round_key(nr, &mut state, &expanded_key);
Ok(state)
}The SubBytes step maps a byte to another byte, using a 256-bit lookup
table. The lookup table is public knowledge and can be used as is, but
under the hood is implemented as the multiplicative inverse in
GF(2^8). It can be calculated by combining the
multiplicative inverse with an affine transformation.
If implemented with the lookup table:
const S_BOX: [u8; 256] = [
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab,
0x76, 0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4,
0x72, 0xc0, 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71,
0xd8, 0x31, 0x15, 0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2,
0xeb, 0x27, 0xb2, 0x75, 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6,
0xb3, 0x29, 0xe3, 0x2f, 0x84, 0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb,
0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, 0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45,
0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5,
0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, 0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44,
0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a,
0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, 0xe0, 0x32, 0x3a, 0x0a, 0x49,
0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, 0xe7, 0xc8, 0x37, 0x6d,
0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, 0xba, 0x78, 0x25,
0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, 0x70, 0x3e,
0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, 0xe1,
0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb,
0x16,
];
fn sub_bytes(state: &mut AesBlock) {
for i in 0..4 {
for j in 0..4 {
state[i][j] = S_BOX[state[i][j] as usize];
}
}
}Or using the affine transformation:
fn affine_transform(c: u8) -> u8 {
let mut x = find_inverse(c);
let s = x;
for i in 1..5 {
x ^= left_circular_shift(s, i);
}
x ^= 0x63;
x
}
for c in 0..16 {
ciphertext[c] = affine_transform(ciphertext[c]);
}ShiftRows is a simple left rotation on all bytes in the state by column.
pub fn shift_rows(state: &mut [[u8; 4]; 4]) {
state[1].rotate_left(1);
state[2].rotate_left(2);
state[3].rotate_right(3);
}MixColumns XORs each column of the state where each column is transformed using a fixed matrix in a Galois Field.
\[ \left[\begin{array}{cccc} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{array}\right] \]
This can be implemented with a lookup table:
fn mix_columns(state: &mut AesBlock) {
for i in 0..4 {
// Iterate over each column
let t = state[0][i];
let tmp = state[0][i] ^ state[1][i] ^ state[2][i] ^ state[3][i];
let mut tm = state[0][i] ^ state[1][i];
tm = mul(tm, 2);
state[0][i] ^= tm ^ tmp;
tm = state[1][i] ^ state[2][i];
tm = mul(tm, 2);
state[1][i] ^= tm ^ tmp;
tm = state[2][i] ^ state[3][i];
tm = mul(tm, 2);
state[2][i] ^= tm ^ tmp;
tm = state[3][i] ^ t;
tm = mul(tm, 2);
state[3][i] ^= tm ^ tmp;
}
}Or manually:
// Multiplication in the Galois Field is defined as a * b ^ p
fn multiply_gf(a: u8, b: u8) -> u8 {
let (mut a, mut b) = (a, b);
let mut p = 0x00;
for _ in 0..8 {
if 0x01 & b != 0 {
p ^= a; // p + a
}
b >>= 0x01;
let carry = 0x80 & a; // x^7
a <<= 1;
if carry != 0 {
a ^= 0x1b;
}
}
p
}
fn mix_columns(word: [u8; 4]) -> [u8; 4] {
let mds = [[2, 3, 1, 1], [1, 2, 3, 1], [1, 1, 2, 3], [3, 1, 2, 2]];
let mut new_word = [0, 0, 0, 0];
for i in 0..4 {
let mds_row = mds[i];
let mut result = multiply_gf(mds_row[0], word[0]);
for c in 1..4 {
let multiple = multiply_gf(mds_row[c], word[c]);
result ^= multiple;
}
new_word[i] = result;
}
new_word
}The AddRoundKey XORs each byte of the state with its current round key.
That looks like this:
fn add_round_key(round: usize, state: &mut AesBlock, expanded_key: &[u8; 240]) {
for i in 0..4 {
for j in 0..4 {
state[j][i] ^= expanded_key[round * COL_SIZE * 4 + i * COL_SIZE + j];
}
}
}