RSA and Diffie-Hellman are slow, so computers use them only to agree on a secret key (the Diffie-Hellman guide shows how). From then on, Alice and Bob lock everything with AES, which is very fast. The same key locks and unlocks, so both of them hold a copy.

An AES key is 128 bits: 128 zeros and ones. Nobody can try that many keys (section 7). So that Eve has a chance, Redux gives her a head start: she knows the whole key except the last few bits. Real keys have no known bits; this is a shortcut to make the search small enough to watch.

AES is a symmetric block cipher: one key encrypts and decrypts, here AES-128 on a single 16-byte block. It has no algebraic weakness comparable to factoring or discrete logs; the best known attacks on the full cipher are barely better than exhaustive search. So Redux models the attack as a key search over a reduced key space: the attacker knows the key except its last k bits (1 ≤ k ≤ 20) and searches 2^k candidates.

Two instance forms. Message mode (keyHex,k,"TEXT"): Redux pads and encrypts the text and keeps only the ciphertext and the known key bits; the attacker recognizes the right key because the decryption reads as a message. Eve's view (knownKeyHex,k,plaintextHex,ciphertextHex): a known-plaintext attack, where the last k bits of the known key must be zero.

Computers store everything as bits, zeros and ones. Eight bits make a byte, which can hold a number from 0 to 255. Each letter has a standard byte (its ASCII code): H is 72, E is 69, a space is 32.

Bytes are usually written in hex, which counts in sixteens using 0 to 9 and then a to f (a = 10, ..., f = 15). Every byte is exactly two hex symbols: H, 72, is 4 × 16 + 8, written 48. So a 128-bit key is 32 hex symbols.

AES always locks exactly 16 bytes, a block. A shorter message is filled out with padding: if 5 places are left, each holds the number 5. Type a message to see its block:

Message mode upper-cases the text, writes it as ASCII and pads it to 16 bytes with PKCS#7 (n missing bytes, each equal to n; at least one, so at most 15 characters). AES treats each byte as an element of GF(2⁸), the field of polynomials over GF(2) modulo x⁸ + x⁴ + x³ + x + 1; addition is XOR.

AES mixes the key in with XOR: line up two bytes bit by bit, and write 0 where the bits match and 1 where they differ. Doing it again with the same key byte undoes it, which is part of how Bob unlocks. Here is the very first thing AES does, character by character:

The first operation is AddRoundKey with round key 0, the key itself: byte by byte, state ⊕ K. Pick a position:

AES arranges the 16 bytes in a 4 × 4 grid and then does 10 rounds. Each round has four moves:

• SubBytes: swap every byte for another, using a fixed table called the S-box.
• ShiftRows: slide row 1 one place to the left, row 2 two places, row 3 three places.
• MixColumns: stir each column, so every byte in it affects the other three.
• AddRoundKey: XOR in a round key, a new 16 bytes made from the main key.

Below is exactly what Redux shows for Alice's message, all 41 steps. Changed bytes are blue; the last grid is the scrambled message Eve intercepts.

AES-128 is 10 rounds of SubBytes (each byte through the S-box: the inverse in GF(2⁸) followed by an affine map), ShiftRows (row r rotated left by r), MixColumns (each column multiplied by the circulant matrix [2 3 1 1]; omitted in round 10) and AddRoundKey, after an initial AddRoundKey. The key schedule expands K into 11 round keys with RotWord, SubWord and round constants. The replay below is Redux's AES Round-by-Round Encryption visualization, frame by frame.

After ten rounds every byte depends on every byte of the message and of the key. Change one letter, or one bit of the key, and about half of the 128 bits of the result change. That is called the avalanche effect, and it is why Eve can't tell that a key is "close": a nearly right key gives complete gibberish. Try it:

Full diffusion after two rounds: each output bit depends on every input and key bit. Changing one plaintext or key bit flips each ciphertext bit with probability close to 1/2, so the ciphertext gives no gradient toward the key.

Eve knows all of the key except the last 8 bits, the last two hex symbols. 8 bits can take 8 twos multiplied together = 256 different values, 00 to ff. So she tries them in order: complete the key, unlock the intercepted block, and look at the result. A wrong key gives gibberish; the right one gives letters and spaces followed by proper padding.

Redux's only solver (and its default). For x = 0, 1, ..., 2^k − 1 it forms K' = known bits ‖ x, decrypts C, and accepts when the block parses as PKCS#7-padded upper-case letters and spaces (in Eve's view: when AES_K'(P) = C). Up to 2^k AES operations, about 3.6 µs each in Redux's Release build, which is why k is capped at 20 (a few seconds).

Here is Eve's notebook, the same table Redux shows, with Redux's own explanations.

The step table replays the solver's recorded steps for the default instance, with Redux's own text.

Here is the AES page in Redux, and what each part does.

The AES page (/AES in Redux_Frontend). The parts below map onto Redux's problem interface: the instance, the solver, the chosen visualization, and the verifier.

Checking an answer

The verifier

The Result panel shows the answer and lets you check any answer you type. Redux calls a proposed answer a certificate: here, the full key and the message, (2b7e151628aed2a6abf7158809cf4f3c,"HELLO WORLD"). Redux checks two things: the key agrees with every bit Eve already knew, and locking your message with it gives exactly the intercepted block.

The Default AES Verifier checks that the proposed key agrees with the known bits, then pads and encrypts the proposed message (in Eve's view, the known plaintext) and compares with C: one AES encryption. Checking is cheap, finding is 2^k, so the problem is declared in NP: AES = {<K, k, P, C> | some key K' that agrees with K except in its last k bits has AES-128_K'(P) = C}.

A wrong key turns the block into 16 random-looking bytes. To fool Eve, those bytes would have to end in proper padding and have nothing but capital letters and spaces before it. The chance of that is about 1 in 100,000,000,000,000,000. Here is what three wrong keys give, next to the right one:

For a random 16-byte block, the probability of parsing as n bytes of padding after 16 − n allowed characters (27 of 256 byte values) is Σ_n=1..15 256⁻ⁿ (27/256)¹⁶⁻ⁿ ≈ 9.0 × 10⁻¹⁸, dominated by n = 1. Even at k = 20 the expected number of false keys is about 10⁻¹¹. Decryptions under three wrong keys and the right one:

Sometimes Eve knows a piece of the message and its locked version, for example a standard greeting at the start of every file. Then she doesn't need to recognize letters: she locks the known piece with each candidate key and checks for an exact match. Redux calls this Eve's view and writes it with four values: the known key bits (with the unknown bits written as zeros), how many are unknown, the known message block and its locked block. Section 9 has an example from the official AES standard.

Eve's view is a known-plaintext attack: accept K' when AES_K'(P) = C. For one block and k ≤ 20 the key is unique with overwhelming probability. The last k bits of knownKeyHex must be zero, otherwise the instance would contain its own answer. The example is FIPS 197 Appendix B: P = 3243f6a8885a308d313198a2e0370734, C = 3925841d02dc09fbdc118597196a0b32.

Each extra unknown bit doubles the number of keys. Redux stops at 20 unknown bits, about a million keys, which takes a few seconds. A real AES key has 128 unknown bits. Slide to see what that means for a computer trying a billion keys every second.

Exhaustive search costs about 2^k AES operations; Grover's algorithm needs about (π/4)·2^k/2 iterations, each evaluating AES (and its inverse, to uncompute) as a reversible circuit. The vertical axis is logarithmic. Grover's iterations are sequential, and splitting the search over M machines leaves each one about √(N/M) iterations, so the quantum speed-up parallelizes far worse than classical search.

For RSA and Diffie-Hellman, a big quantum computer would be a disaster. For AES it is only a speed-up. In 1996 Lov Grover found a quantum method for searching, now called Grover's algorithm, that needs only about the square root of the number of tries. For 256 keys the square root is 16, and in fact 12 rounds are enough, instead of up to 256 tries. That sounds huge, but for a 128-bit key it still leaves about 64 twos multiplied together, far too many. With a 256-bit key, AES stays out of reach even for Grover's algorithm.

Grover's algorithm finds the one candidate that passes the test among N = 2^k with about (π/4)√N oracle calls instead of up to N classical tries: 12 for N = 256 (success probability 0.99995), about 1.45 × 10¹⁹ for k = 128. The oracle has to compute AES reversibly, which dominates the cost. The speed-up is quadratic, not exponential as Shor's algorithm is for RSA and Diffie-Hellman, so AES-256 keeps about 128 bits of security against it.