Block Ciphers and Modes: Build AES, Then Reason About Its Use

This module has four connected exercises: aes-128-block, cbc-pkcs7, ctr-mode, and cbc-bitflip. First make one 16-byte transformation correct. Then use it to encrypt messages, and finally demonstrate why confidentiality alone does not prevent modification.

Check your starting point

You should be comfortable with hexadecimal bytes, XOR, indexing an array, and integer shifts. Check 0x57 XOR 0x83 = 0xd4 and explain why (x XOR k) XOR k = x. If that cancellation is unfamiliar, trace it bit by bit before implementing a mode.

AES with a fixed key is a permutation of 16-byte blocks: encryption is invertible and deterministic. AES-128 has a 16-byte key and ten rounds. A block operation has no nonce, padding, or authentication. Those belong to surrounding constructions. The exercise supplies S-box tables; you will implement their use, the linear transformations, key expansion, and the inverse cipher.

Map bytes to the state

Keep the state in a flat [16]byte, indexed as state[r + 4*c]. Each group of four consecutive input bytes fills one column, not one row. For plaintext 00112233445566778899aabbccddeeff, the state is:

       c=0 c=1 c=2 c=3
r=0     00  44  88  cc
r=1     11  55  99  dd
r=2     22  66  aa  ee
r=3     33  77  bb  ff

For example, row 2, column 1 lives at flat index 6 and holds 66. Printing the flat state as hex still yields the original input string. Choose one convention and preserve it in every helper; otherwise a final ciphertext mismatch gives little guidance about which stage transposed the bytes.

All complete-state hex strings below are serialized in this same column order. The algorithm definitions and indexing follow NIST FIPS 197, §§3–5.

Build the four transformations

AddRoundKey XORs each byte with the corresponding round-key byte. With key 000102030405060708090a0b0c0d0e0f, the initial XOR produces 00102030405060708090a0b0c0d0e0f0. XOR is its own inverse.

SubBytes replaces each byte using the supplied 256-entry S-box. For example, SBox[00]=63, SBox[10]=ca, and SBox[20]=b7. Apply it to all 16 bytes. For decryption, use the supplied inverse table; do not assume the forward S-box is self-inverse.

ShiftRows rotates row r left by r columns. For a source copy old, the forward mapping is new[r+4*c] = old[r+4*((c+r)%4)]. Row 0 stays fixed. Row 1's flat positions 1,5,9,13 take old values at 5,9,13,1. Writing directly over values that later assignments still need loses information; use a temporary state or deliberate rotations.

MixColumns independently transforms each four-byte column. For input [a,b,c,d], its first output is 2*a XOR 3*b XOR c XOR d, where multiplication is in the AES field. The other three rows of coefficients are [1,2,3,1], [1,1,2,3], and [3,1,1,2]. Keep the input column intact while computing all four outputs.

Derive the field operation

AES bytes represent polynomials over bits; addition is XOR. Multiplying by x shifts left. If the old top bit was set, reduce by x^8+x^4+x^3+x+1, represented as 0x11b. For byte arithmetic, discard the ninth bit and XOR 0x1b when reduction is needed:

xtime(0x53): 0xa6                     (old top bit is 0)
xtime(0x83): 0x106 XOR 0x11b = 0x1d   (old top bit is 1)
3*a = xtime(a) XOR a

The reduction decision uses the old high bit. Checking after truncating the left shift loses that information. A generic multiply helper can repeatedly accumulate a when the low bit of b is set, replace a with xtime(a), and shift b right; eight iterations suffice for byte operands.

For the first column [63,53,e0,8c] after the first round's row shift:

2*63 = c6
3*53 = (2*53) XOR 53 = a6 XOR 53 = f5
first output = c6 XOR f5 XOR e0 XOR 8c = 5f

Compute the remaining outputs with the other coefficient rows. The complete column is [5f,72,64,15]. An ordinary integer multiplication, such as treating 2*e0 as an unrestricted integer product, will not implement this field operation.

Expand the key by words

A word here is a group of four bytes, represented without host-endian integer assumptions. AES-128 expands four initial words into 44 words, which form eleven round keys. Round key r consists of words w[4*r] through w[4*r+3].

For each i from 4 through 43, start with temp=w[i-1]. Only when i is divisible by 4, rotate temp left by one byte, apply the S-box to each byte, and XOR Rcon[i/4] into its first byte. Then w[i]=w[i-4] XOR temp. Rcon's first values in hex are 01,02,04,08,10,20,40,80,1b,36.

Derive the first expanded key for our running example:

Step	Four-byte value
w[0], w[1], w[2], w[3]	00010203, 04050607, 08090a0b, 0c0d0e0f
Rotate w[3]	0d0e0f0c
Substitute each byte	d7ab76fe
XOR first Rcon into first byte	d6ab76fe
XOR with w[0] to obtain w[4]	d6aa74fd
w[5] = w[1] XOR w[4]	d2af72fa
w[6] = w[2] XOR w[5]	daa678f1
w[7] = w[3] XOR w[6]	d6ab76fe

The concatenated round-1 key is d6aa74fdd2af72fadaa678f1d6ab76fe. The schedule's recurrence uses newly generated words: applying the special rotation to every word, or repeatedly XORing the original last word, produces a different algorithm.

Check a complete first round

Use the running plaintext and key. Compare at each boundary, so a failure points to one transformation:

Stage	Flat state in hex
Initial AddRoundKey	00102030405060708090a0b0c0d0e0f0
Round 1 SubBytes	63cab7040953d051cd60e0e7ba70e18c
Round 1 ShiftRows	6353e08c0960e104cd70b751bacad0e7
Round 1 MixColumns	5f72641557f5bc92f7be3b291db9f91a
Round 1 AddRoundKey	89d810e8855ace682d1843d8cb128fe4

Encryption begins with AddRoundKey using key 0. Rounds 1–9 apply SubBytes, ShiftRows, MixColumns, AddRoundKey. Round 10 applies SubBytes, ShiftRows, AddRoundKey, omitting MixColumns. The complete ciphertext is 69c4e0d86a7b0430d8cdb78070b4c55a.

For a partly completed trace, hide the table's last row. The first four bytes before AddRoundKey are 5f726415; the round key begins d6aa74fd. Calculate the next four bytes. Then calculate w[5] using the previous section without looking at its result.

Check the two missing steps

5f XOR d6=89, 72 XOR aa=d8, 64 XOR 74=10, 15 XOR fd=e8, giving 89d810e8. The next key word is 04050607 XOR d6aa74fd = d2af72fa.

Independently label a state with byte values 00 through 0f. Write the four rows, perform ShiftRows, and serialize it back into column order. Then undo your shift. This tests the indexing convention without relying on the supplied ciphertext.

Reverse the cipher in the right order

To decrypt, first XOR round key 10 into the ciphertext. For rounds 9 down to 1, apply InvShiftRows, InvSubBytes, AddRoundKey, InvMixColumns, in that order. Finish with InvShiftRows, InvSubBytes, and AddRoundKey using key 0.

The inverse row operation shifts right. Inverse MixColumns uses coefficient rows [0e,0b,0d,09], [09,0e,0b,0d], [0d,09,0e,0b], and [0b,0d,09,0e], all hexadecimal field multipliers. The original forward-expanded keys suffice for this ordering. Do not move AddRoundKey past InvMixColumns while keeping the keys unchanged.

A round-trip test alone is insufficient: matching forward and inverse mistakes can cancel. Check known ciphertexts and compare different keys/blocks with an independent AES implementation, as the exercise tests do. The table-based implementation here teaches the construction; production code needs vetted implementations with appropriate side-channel protections.

Extend one block into a message

The mode exercises supply the AES primitive, so you can debug message handling independently of your first implementation. Use the previous result as a conceptual dependency, not an instruction to copy private helper code between exercises.

For CBC, let C0=IV, Ci=Ekey(Pi XOR C(i-1)), and Pi=Dkey(Ci) XOR C(i-1). Encryption uses the preceding ciphertext, not the preceding plaintext. During in-place decryption, preserve that ciphertext before overwriting it. CBC requires an unpredictable IV; CTR requires that every full counter block be unique under the key across messages. These are different requirements. NIST SP 800-38A, §6 and Appendices B–C

cbc-pkcs7 pads with k copies of the byte k, where k=16-(length%16). Length 15 adds 01; length 16 adds sixteen 10 hex bytes; even empty input gets a full padding block. On decryption, reject empty or non-block-aligned ciphertext, a final k outside 1..16, or any mismatching suffix byte. A suffix 02 03 is not valid just because its last byte is in range. Padding validity is not authentication.

ctr-mode constructs nonce[8] || counter[8], encoding the counter big-endian. It encrypts that block and XORs at most sixteen keystream bytes with data. A 17-byte input starting at counter 7 uses counters 7 and 8; the second block contributes just one byte. No padding or AES block decryption is needed. Arithmetic wrap follows the exercise's unsigned counter, but a real key/nonce allocation scheme must prevent repeated counter blocks across all calls, including overlapping ranges. Starting a second message at 8 already overlaps the example's keystream.

Derive the integrity failure

For CTR, C=P XOR S and C'=P' XOR S under a repeated keystream imply C XOR C'=P XOR P'. The keystream cancels. Unique counters prevent this specific reuse failure; they do not authenticate ciphertext.

For CBC, changing the previous ciphertext byte by delta changes the corresponding next plaintext byte by that delta. Suppose the next plaintext byte is known to be ASCII 0 (30 hex), and you want 1 (31 hex). Choose delta=30 XOR 31=01 and XOR it into the preceding ciphertext byte. The target byte becomes 30 XOR 01=31. If you edit a ciphertext block, its own decrypted plaintext block is also corrupted unpredictably; editing the IV affects the first plaintext block without that preceding-block collateral damage.

Now derive the delta from a (61) to z (7a) yourself before implementing cbc-bitflip. The exercise asks for this algebraic modification, not a forged authenticated message. In deployed protocols, use an appropriate authenticated-encryption construction; different error messages alone are not the only possible padding-oracle channel, and a single generic error does not prove the whole implementation secure.

Practice in dependency order

1. In aes-128-block, check state layout, field multiplication, key words, the first-round table, the final vector, then independent decryption. If a vector fails, locate the earliest divergent stage.
2. In cbc-pkcs7, test lengths 0,15,16,17 and a deliberately invalid padding suffix. Keep IV and preceding ciphertext separate from plaintext output.
3. In ctr-mode, test 0,1,16,17 bytes and a counter carry; explain why decryption calls encryption.
4. In cbc-bitflip, predict both the controlled next-block change and collateral damage before running the code.

The quiz diagnoses construction and mode errors. After reviewing a linked concept, repeat the relevant transformation with different bytes; remembering one example's hex string is not the target skill.