AES Bit Operations

AES at the Bit Level: An Overview

AES operates on a 4x4 matrix of 16 bytes called the state. Every round applies four operations in sequence: SubBytes (byte substitution via S-box), ShiftRows (byte transposition), MixColumns (matrix multiplication in GF(2^8)), and AddRoundKey (XOR with the round key). The number of rounds depends on the key size: 10 for AES-128, 12 for AES-192, and 14 for AES-256.

What I found remarkable when I first studied AES is that every single operation can be expressed in terms of XOR, table lookups, and byte-level shifts. There is no multiplication in the traditional sense. Even MixColumns, which sounds mathematically heavy, is implemented as a few XOR operations and conditional branches. This is why AES is so fast in both hardware and software.

While implementing AES-128 from a spec sheet, I learned that the MixColumns step multiplies each column by a polynomial in GF(2^8). The bitwise XOR of shifted values in this step was the most intricate bit manipulation I had coded up to that point.

SubBytes: The S-Box Substitution

SubBytes replaces each byte of the state with a value from a fixed 256-byte lookup table called the S-box. The S-box is constructed from two GF(2^8) operations: computing the multiplicative inverse of the byte, then applying an affine transformation (a bitwise matrix multiplication plus XOR with a constant).

In practice, SubBytes is implemented as a simple table lookup:

// AES S-box (simplified — only showing first 16 entries)
static const uint8_t sbox[256] = {
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5,
    0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    // ... all 256 entries ...
};

void sub_bytes(uint8_t state[4][4]) {
    for (int r = 0; r < 4; r++)
        for (int c = 0; c < 4; c++)
            state[r][c] = sbox[state[r][c]];
}

The inverse S-box (used for decryption) is similarly constructed by applying the inverse affine transform first, then the multiplicative inverse. The choice of the specific affine constant 0x63 was designed to eliminate fixed points — values where S-box[x] == x.

ShiftRows: Byte Rotation

ShiftRows cyclically shifts the bytes in each row of the state to the left. Row 0 is not shifted, row 1 shifts by 1 byte, row 2 by 2 bytes, and row 3 by 3 bytes. This is purely a byte-level transposition — no bit manipulation within bytes, just rearranging bytes within the 128-bit state.

ShiftRows ensures that columns of the state are mixed together in the following MixColumns step. Without ShiftRows, each column would be processed independently, and AES would not achieve its diffusion properties.

MixColumns: Matrix Multiplication with XOR and Shifts

MixColumns multiplies each column of the state by a fixed 4x4 matrix. The multiplication and addition operations are in GF(2^8) — XOR for addition, and a combination of left shift and conditional XOR for multiplication by specific constants. The matrix is chosen so that each output byte depends on all four input bytes in the column.

// MixColumns: multiply each column by the fixed matrix
// [2, 3, 1, 1]   [s0]   [s'0]
// [1, 2, 3, 1] * [s1] = [s'1]
// [1, 1, 2, 3]   [s2]   [s'2]
// [3, 1, 1, 2]   [s3]   [s'3]

// GF(2^8) multiplication by 2 (left shift + conditional XOR with 0x1B)
uint8_t xtime(uint8_t a) {
    uint8_t result = a << 1;
    if (a & 0x80) result ^= 0x1B;  // reduction polynomial
    return result;
}

// GF(2^8) multiplication by 3 = xtime(a) ^ a
// (because 3*a = 2*a + a in GF(2^8))

// One column of MixColumns
void mix_column(uint8_t col[4]) {
    uint8_t a = col[0], b = col[1], c = col[2], d = col[3];
    col[0] = xtime(a) ^ xtime(b) ^ c ^ d ^ b ^ d;
    // Equivalent to: (2*a) ^ (3*b) ^ (1*c) ^ (1*d)
    col[1] = xtime(b) ^ xtime(c) ^ d ^ a ^ c ^ a;
    col[2] = xtime(c) ^ xtime(d) ^ a ^ b ^ d ^ b;
    col[3] = xtime(d) ^ xtime(a) ^ b ^ c ^ a ^ c;
}

The magic constant 0x1B in xtime is the irreducible polynomial x^8 + x^4 + x^3 + x + 1, which defines GF(2^8) for AES. It is the binary equivalent of reducing a polynomial that overflows beyond 8 bits back into the field. Decryption uses InvMixColumns with constants 14, 11, 13, 9, which are the inverses of 2, 3, 1, 1 in GF(2^8).

AddRoundKey: The XOR Step

AddRoundKey is the simplest operation in AES. It XORs the entire 128-bit state with the 128-bit round key for the current round. Since XOR is its own inverse, the same operation is used for both encryption and decryption.

// AddRoundKey in C
void add_round_key(uint8_t state[4][4], const uint8_t round_key[4][4]) {
    for (int r = 0; r < 4; r++)
        for (int c = 0; c < 4; c++)
            state[r][c] ^= round_key[r][c];
}

AddRoundKey is applied at three points in AES: an initial AddRoundKey before the first round, after each round's MixColumns (except the last round, which skips MixColumns), and as the final operation. This is the only operation that directly involves the key, which is why the key schedule is so important.

The Key Schedule: Expanding the Cipher Key

The AES key schedule expands the cipher key into round keys using XOR, byte rotation, and S-box substitution. For AES-128, the first 16 bytes of the expanded key are the cipher key itself, and each subsequent 16-byte round key is derived from the previous one.

// AES-128 key schedule (generates 11 round keys of 16 bytes each)
// Total: 11 * 16 = 176 bytes of expanded key

// For each 4-byte word W[i]:
if (i % 4 == 0) {
    // Every 4th word is transformed:
    // 1. RotWord: rotate left by 1 byte
    // 2. SubWord: apply S-box to each byte
    // 3. XOR with Rcon[i/4]
    W[i] = W[i-4] ^ SubWord(RotWord(W[i-1])) ^ Rcon[i/4];
} else {
    W[i] = W[i-4] ^ W[i-1];
}

// Rcon values (powers of 2 in GF(2^8)):
// Rcon[1] = 0x01000000, Rcon[2] = 0x02000000,
// Rcon[3] = 0x04000000, Rcon[4] = 0x08000000, ...

The Complete AES Round in Binary

Putting it all together, here is what one complete AES encryption round looks like at the bit level. Every operation is either a byte replacement (SubBytes), a byte rearrangement (ShiftRows), a combination of XOR and conditional shift (MixColumns), or plain XOR (AddRoundKey).

// One complete AES round (Round 1 through 9 for AES-128)
void aes_round(uint8_t state[4][4], const uint8_t round_key[4][4]) {
    sub_bytes(state);         // S-box lookup (bit-level affine transform)
    shift_rows(state);        // Byte rotation (transposition)
    mix_columns(state);       // GF(2^8) multiplication (XOR + xtime)
    add_round_key(state, round_key);  // XOR with round key
}

// Final round (Round 10 for AES-128) — no MixColumns
void aes_final_round(uint8_t state[4][4], const uint8_t round_key[4][4]) {
    sub_bytes(state);
    shift_rows(state);
    add_round_key(state, round_key);
}

The total operation count for AES-128 encryption: 10 SubBytes passes (160 S-box lookups), 10 ShiftRows passes (16 byte swaps each), 9 MixColumns passes (16 XOR + 16 xtime ops each), and 11 AddRoundKey passes (16 XOR ops each). Every operation is trivially parallelizable at the hardware level.