The Fortress and the Afterthought: How AES Would Break at Its Key Schedule

1. The Cipher That Guards the Internet#

Every time you open a bank app, unlock a laptop, or load a padlocked website, you are trusting AES -- and in twenty-five years of public assault, no one has come close to breaking it in the way that would matter. It underpins TLS sessions ^[1], the full-disk encryption on laptops and phones, secure messaging, and the tunnels inside most VPNs. So this article does not ask whether AES is broken. It isn't. It asks a sharper, more honest question: if it ever broke, where would the very first crack appear -- and the answer is not the part everyone admires.

The Advanced Encryption Standard was chosen in an open, international contest run by the U.S. National Institute of Standards and Technology between 1997 and 2001, precisely so the world's cryptanalysts could attack the candidates before one became the standard ^[2]. The winner, Rijndael, has since absorbed a quarter-century of that attention. Textbooks celebrate two of its parts above all: the S-box, a slice of finite-field algebra, and MixColumns, a diffusion layer with a provable mixing guarantee. If you asked most engineers where a future break might begin, they would point at that famous mathematics.

They would be pointing at the wrong place. The strongest results against full-round AES do not touch the S-box or MixColumns at all. They exploit the humblest component in the design -- the key schedule, the little routine that stretches your 128-, 192-, or 256-bit key into the sequence of round keys the cipher actually uses. It is fast, simple, and almost entirely linear, and it is exactly where every sub-brute-force full-round result lives or leans.

The AES round function is the most-analyzed, most-trusted primitive in symmetric cryptography, and it has held. The key schedule is its least-designed, most-linear component. If AES ever falls, the accumulated evidence says the first crack starts there -- not at the celebrated mathematics, but at the afterthought bolted beside it.

That gap between "the best attack we have" and "trying every key" has a name, and it is the ruler this entire article uses.

One boundary before we start. This is a structural story -- about the mathematics of the algorithm itself. The attacks that actually steal data in the real world -- cache-timing side channels, fault injection, repeated GCM nonces, padding oracles, key-reinstallation attacks like KRACK -- never touch the cipher's math at all. Those belong to this article's empirical sibling; here, we stay inside the equations.

To see why the key schedule is the suspect, you first have to see what the designers built -- and what they admitted they left cheap.

2. A Cipher Designed Against Its Own Attack#

By the late 1990s the old standard was dying in public. In 1998 the Electronic Frontier Foundation built a purpose-made machine called Deep Crack and brute-forced a DES key in a matter of days, proving a 56-bit key was no longer enough ^[3]. DES had been the U.S. standard since 1977 ^[3]. Deep Crack's public key recovery in 1998 was the exclamation point on years of warnings, and it set the clock ticking on the AES competition.

NIST's response was radical for a spy-adjacent agency: instead of designing a replacement behind closed doors, it announced an open, international contest and invited the world to break the candidates first ^[2]. Fifteen submissions were cut to five finalists -- MARS, RC6, Rijndael, Serpent, and Twofish -- and in October 2000 NIST named the Belgian design Rijndael the winner ^{[4] [5]}.

Here is the part of the story that plants this article's thesis. Daemen and Rijmen did not come to the contest cold. In 1997 they had co-designed an earlier cipher, Square, and -- unusually -- had published the strongest attack against it themselves: the Square attack, a structural technique that tracks a carefully chosen set of inputs through the cipher's byte operations ^[6]. They arrived at the AES competition already knowing the best way to attack their own architecture, and they engineered Rijndael's round function specifically to resist it.

The tool they used was the wide-trail strategy, and it is the reason the round function has held for twenty-five years.

The key schedule got the opposite treatment. Where the round function was engineered against a known attack with a provable bound, the key expansion was designed for speed and simplicity: enough structure to break symmetry between rounds and eliminate equivalent keys, and no more. It is built almost entirely from XOR and word rotation, with only an occasional column of S-box nonlinearity to break symmetry. The designers concentrated their genius on the round function and, by their own account, left the key schedule cheap. Twenty years later, peer-reviewed work put the consequence bluntly.

"The key schedule is arguably the weakest part of the AES." -- Gaëtan Leurent and Clara Pernot, EUROCRYPT 2021 ^[8]

That asymmetry -- a fortress round function bolted to a lightly-built key schedule -- is the seed of everything that follows. The competition worked exactly as intended: Rijndael was chosen after the community failed to break it and the round function proved resilient ^[9]. But "resilient round function" and "no weak spot anywhere" are different claims, and the next two decades of attacks would find the difference.

The whole arc, from the contest to the full-round results, fits on one timeline.

timeline
title The structural cryptanalysis of AES, 1997 to 2021
1997 : Square cipher and the Square attack, Rijndael's ancestor
2000 : Rijndael wins, round-function attacks reach 6 to 7 rounds
2001 : FIPS 197 standardizes AES
2008 : Single-key meet-in-the-middle line begins, still short of full rounds
2009 : Related-key attacks reach full AES-192 and AES-256
2011 : Biclique, the only single-key full-round result
2021 : New key-schedule structure found after 20 years

The designers told us where they concentrated their effort, and where they did not. To understand why that choice matters, open the machine up and look at the four operations inside.

3. Where the Strength Is, and Where It Isn't#

AES is four operations repeated ten to fourteen times. Three of them are among the most-analyzed primitives in cryptography. The fourth -- the one that stretches your key into round keys -- is the one nobody fortified.

Each round of AES transforms a 4-by-4 grid of 16 bytes through the same four steps ^[10]:

• SubBytes replaces every byte using the S-box, the cipher's only source of nonlinearity in the data path.
• ShiftRows rotates the rows of the grid by different offsets, spreading bytes across columns.
• MixColumns mixes each column through a fixed matrix so that one changed input byte disturbs all four output bytes.
• AddRoundKey XORs in the round key for that round.

AES-128 runs 10 rounds, AES-192 runs 12, and AES-256 runs 14. The count grows with the key because a longer key means a longer key schedule and more round keys to derive. ※ The original Rijndael also permitted 192- and 256-bit blocks, but AES fixes the block at 128 bits and varies only the key length. Throughout this article, "AES" means that fixed-block profile.

flowchart TD
A["State: 16 bytes in a 4x4 grid"] --> B["SubBytes: S-box on every byte"]
B --> C["ShiftRows: rotate each row"]
C --> D["MixColumns: mix each column, branch number 5"]
D --> E["AddRoundKey: XOR the round key"]
E --> F["Next round"]

Two of these steps are why AES is trusted. The S-box is not an arbitrary lookup table; it is algebra.

MixColumns is the diffusion partner. Its matrix is chosen so that changing a single input byte changes all four output bytes of the column. This is the maximum-distance-separable (MDS) property, summarized by a branch number of 5: the number of nonzero input bytes plus nonzero output bytes of MixColumns is always at least 5. It is what lets four rounds guarantee 25 active S-boxes, and it is unusually strong diffusion for such a cheap operation. Together, SubBytes and MixColumns make the round function mix so thoroughly that after just a couple of rounds every output bit depends on every input bit in a way no attacker has been able to shortcut. This is the fortress.

Now meet the protagonist. The key schedule -- the routine FIPS 197 calls key expansion -- is what turns your master key into the round keys that AddRoundKey consumes.

flowchart LR
W0["Word w0 to w3: the master key"] --> N["Once per group: RotWord, then SubWord, then XOR Rcon"]
N --> X["XOR into the next word"]
W0 --> X
X --> W1["Next four words: round key 1"]
W1 --> Y["Mostly plain XOR of earlier words"]
Y --> W2["Round key 2, and so on"]

Make the contrast visceral. The round function stirs the state with a nonlinear S-box on all 16 bytes and a strong diffusion layer, every single round. The key schedule stirs its state with XOR and rotation, and touches the S-box only four bytes at a time, once or twice per group of words. ※ A 32-bit word is one column of four bytes, and SubWord runs the S-box on all four at once -- so one word and one S-box column mean the same thing here. One mixes with a sledgehammer; the other barely swirls.

That gap has a consequence worth holding onto: because the expansion is mostly linear, a difference injected into the key propagates through it predictably. If you know the difference going in, you can compute much of the difference coming out -- no probabilities required. Remember that when we reach the related-key attacks.

You can watch the slow, predictable diffusion yourself. The demo below injects a one-byte difference into a master key and follows it through the linear backbone of the expansion. Notice that the earliest words stay untouched, and that once the difference appears it propagates in a fixed, fully determined pattern rather than exploding into randomness the way the round function would scramble it.

// A deliberately simplified model of the AES key-expansion BACKBONE:
// new word = previous word XOR the word four positions back.
// (The real schedule adds one S-box column per group; we skip that
//  nonlinear part to expose why differences travel predictably.)
const Nk = 4;          // 128-bit key = 4 words
const totalWords = 44; // 11 round keys of 4 words each

function expandBackbone(seed) {
const w = seed.slice();
for (let i = Nk; i < totalWords; i++) {
  // linear step only: XOR of two earlier words
  w[i] = w[i - 1] ^ w[i - 4];
}
return w;
}

// Two master keys that differ in exactly ONE word (a single injected difference).
const keyA = [0x00000000, 0x11111111, 0x22222222, 0x33333333];
const keyB = [0x00000000, 0x11111111, 0x22222222, 0x33333333 ^ 0x01000000];

const a = expandBackbone(keyA);
const b = expandBackbone(keyB);

let firstTouched = -1, touchedCount = 0;
for (let i = 0; i < a.length; i++) {
const diff = a[i] ^ b[i];
if (diff !== 0) {
  touchedCount++;
  if (firstTouched === -1) firstTouched = i;
}
}
console.log("Injected a 1-word difference into word 3.");
console.log("First word carrying the difference: w" + firstTouched);
console.log("Words disturbed out of " + totalWords + ": " + touchedCount);
console.log("The difference is fully determined -- no guessing, no probability.");
console.log("A real attacker exploits exactly this predictability.");

A fortress bolted to an afterthought. For years, no attacker seemed to notice the afterthought -- they all threw themselves at the fortress. Here is what happened when they did.

4. The First Cracks, at Four to Seven Rounds#

The moment Rijndael became a finalist, the world's cryptanalysts opened fire. The first attacks worked -- and then hit a wall almost immediately, at a height that has barely moved since.

The opening salvo was the designers' own weapon, turned up to full power. Integral cryptanalysis -- the generalized Square attack -- does not chase a probabilistic pattern the way classical differential attacks do. It exploits a property that holds with certainty.

That balanced sum gives a 3-round distinguisher, which the Square attack extends by wrapping key-guessing rounds around it to break up to 6 rounds of AES at about $2^{72}$ work ^[6]. The invariant is simple enough that a student can implement it in a few lines.

// A Lambda-set's active byte takes all 256 values exactly once.
// Claim: after any bijective S-box, the XOR of all outputs is still 0.
// This is the "balance" property the Square attack sieves keys with.

// Build a toy S-box: a random permutation of 0..255 (a bijection like AES's).
const sbox = Array.from({length: 256}, (_, i) => i);
for (let i = 255; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[sbox[i], sbox[j]] = [sbox[j], sbox[i]];
}

// Active byte: all 256 values. XOR them before and after the S-box.
let xorInput = 0, xorOutput = 0;
for (let v = 0; v < 256; v++) {
xorInput ^= v;          // XOR of 0..255 is 0 by construction
xorOutput ^= sbox[v];   // a bijection just permutes those values
}
console.log("XOR of the active byte (input):  " + xorInput);   // 0
console.log("XOR after the bijective S-box:   " + xorOutput);  // still 0
console.log(xorOutput === 0 ? "Balanced: the distinguisher holds." :
                            "Broken balance (won't happen for a bijection).");

The Square attack's real bottleneck was not the distinguisher but the cost of the final key-guessing summation. In 2000, Niels Ferguson, John Kelsey, David Wagner and colleagues fixed exactly that with the partial-sums technique, reorganizing the summation to reuse intermediate results. It cut the 6-round work to roughly $2^{44}$ and bought one more round, reaching 7-round AES-128 at about $2^{120}$ using almost the entire codebook ^[12]. The same year, Henri Gilbert and Marine Minier found a different route to the same height: a collision attack on 7 rounds of Rijndael that exploited collisions between partial functions inside the cipher ^[13].

A third family arrived in parallel and turned differential logic inside out. Impossible-differential cryptanalysis of Rijndael originated with Eli Biham and Nathan Keller in an unpublished report at the Third AES Candidate Conference in 2000. That original Biham-Keller report was never formally published and is not indexed in the usual bibliographic databases, so this article attributes only the origin of the technique to it and takes every concrete figure from the peer-reviewed successors below. Precision about what is and is not on the record is part of honest cryptanalysis. Instead of a high-probability pattern, it uses one that occurs with probability exactly zero: AES has a 4-round differential that can never happen, so any key guess that would produce it is provably wrong and can be sieved out.

Jiqiang Lu, Orr Dunkelman, Nathan Keller and Jongsung Kim formalized and optimized the technique in 2008, as did Behnam Bahrak and Mohammad Reza Aref independently. It gave the best impossible-differential attacks of its era: 7 rounds of AES-128 and AES-192, and 8 rounds of AES-256 ^{[11] [14]}.

Step back and the pattern is unmistakable. Integral, partial sums, collision, impossible differential -- four different mechanisms, and every one of them targets the round function, and every one of them stalls far below the full 10 rounds. Around seven rounds, they all hit the same ceiling. Some of these are distinguishers (they tell real AES apart from a random permutation) and some are key recoveries (they actually extract key bytes), but the reach is the same either way.

Different attacks, one shared ceiling: about seven rounds. Was that a coincidence -- or was something stopping them?

5. Climbing the Round Ladder#

For fifteen years the single-key attacks improved -- new mechanisms, cleverer bookkeeping, automated search. And still they stalled around seven rounds. The reason they stalled is the whole point of this article.

The next mechanism traded probability for memory. If the distinguishers of Section 4 were too short, why not store a description of several middle rounds rather than propagate a pattern through them?

In 2008, Hüseyin Demirci and Ali Aydın Selçuk built the first MITM attack on AES, reaching 8 rounds of AES-256 -- past the seven-round wall. But there was a catch that makes the plateau vivid: the precomputed table held on the order of $2^{206}$ entries ^[15]. That is not a time cost you wait out; it is more storage than exists on Earth. The attack was structurally valid and physically impossible at once -- a memory catastrophe.

Two years later, Orr Dunkelman, Nathan Keller and Adi Shamir rescued it. Their differential-enumeration technique restricted the precomputed table to only the middle states actually reachable from a chosen truncated differential, and a compact "multiset" representation shrank it further -- collapsing the impossible $2^{206}$ down toward the attack's own time complexity and turning a physical impossibility into a coherent shortcut for 8-round AES-192 and AES-256 ^[16].

Then, in 2013, Patrick Derbez, Pierre-Alain Fouque and Jérémy Jean treated the search for the best MITM parameters as a computer-search problem, automating the exploration to squeeze out the best single-key numbers anyone has found: 7-round AES-128 with data, time and memory all under $2^{100}$; 8-round AES-192 and AES-256; and 9-round AES-256 ^[17].

Line the generations up and the shape of the wall becomes concrete.

Fifteen years, five mechanisms, and the frontier climbs from six rounds to nine and stops. It is tempting to read that trend line as a slow slide toward a break -- seven rounds today, ten rounds soon. That reading is exactly backwards.

The single-key plateau near seven rounds is not the attackers failing. It is the wide-trail round function succeeding. By provable design there is no long, high-probability characteristic to extend across the round function, so every single-key attack must bolt a few key-guessing rounds onto a short distinguisher -- and runs out of room. The plateau is evidence of strength, and it is precisely what forces every full-round result off the round function and onto the key schedule.

Not every idea in this era survived. The most famous casualty was an algebraic dream.

If the round function cannot be beaten in the ordinary attack model, there are exactly two ways forward, and both leave the round function untouched. The first is to change the rules of engagement.

The escape route through that model runs directly through the key schedule's linearity: because the expansion is mostly XOR, a difference injected into the key travels through it predictably and can be arranged to cancel a difference in the data over a few rounds -- a "local collision" that, chained, lets a usable characteristic span the entire cipher for the first time. The second escape gives up on beating brute force outright and instead accelerates it, with a structure called a biclique that leans on how slowly the key schedule diffuses. We will need one more idea for both roads.

Both escapes were walked between 2009 and 2011. Neither one beat the round function. Both went for the key schedule.

flowchart TD
S["AES cryptanalysis"] --> A["Single-key round-function line"]
S --> B["Full-round results"]
A --> A1["Integral, partial sums, impossible differential"]
A1 --> A2["MITM and automated MITM"]
A2 --> A3["Plateau near 7 to 9 rounds: the round function holding"]
B --> B1["Related-key: local collisions in the linear key schedule"]
B --> B2["Biclique: leans on slow key-schedule diffusion"]
A3 --> K["The key schedule"]
B1 --> K
B2 --> K

6. Two Ways Past the Full Cipher#

In 2009 and 2011, three papers did what nobody had managed in a decade: they reached all the way through AES faster than brute force. Neither road beat the round function. Both went for the key schedule -- one breaking it head-on, one leaning on it.

Road one: related-key attacks break the key schedule directly#

The first road exploits the linearity you watched in Section 3. Because AES-256's key schedule is so close to linear, a difference injected into the key propagates through it predictably, and it can be arranged to cancel a difference that the round keys introduce into the data.

In 2009, Alex Biryukov, Dmitry Khovratovich and Ivica Nikolić delivered the first full-round result of any kind. They defined a differential q-multicollision and showed AES-256 admits them in about $q \cdot 2^{67}$ operations, against a provable lower bound of roughly $q \cdot 2^{((q-1)/(q+1)) \cdot 128}$ for an ideal cipher -- a gap wide enough to prove, in their words, that AES-256 "can not model an ideal cipher" ^[21].

From that they built the first attack on all 14 rounds: a related-key distinguisher working for 1 out of every $2^{35}$ keys using $2^{120}$ data, convertible to a key recovery at $2^{131}$ time and $2^{65}$ memory ^[21]. It was a weak-key-class result -- powerful, but not yet a universal key recovery.

Months later, Biryukov and Khovratovich closed that gap and extended it. Combining local collisions with the boomerang attack and a trick called boomerang switching -- which buys free middle rounds by reconciling two short differentials where they meet -- they produced a key recovery on the full AES-256 that works for all keys, at $2^{99.5}$ time and data, using four related keys ^[20]. The same machinery gave the first cryptanalysis of the full AES-192, at complexity $2^{176}$ ^[20]. The paper notes the AES-256 figure improves to $2^{99}$. Two precision points that matter: the attack uses four related keys, and the $2^{99.5}$ (or $2^{99}$) number belongs to AES-256 alone. The full AES-192 result is $2^{176}$ -- never attach the AES-256 figure to AES-192.

Sit with what that means, because it inverts a near-universal assumption. AES-256 has more rounds and a longer key than AES-128, and everyone treats it as the stronger choice. Yet under related keys it is weaker: its longer key schedule is more linear structure to exploit, and no comparable all-keys full-round attack exists against AES-128. This is the thesis in its most literal form -- more key material bought more exploitable structure, and the longer key schedule breaks worse.

flowchart TD
A["Attacker injects a known key difference"] --> B["Linear key schedule propagates it predictably"]
B --> C["Round-key difference cancels the state difference: local collision"]
C --> D["Chain local collisions across rounds"]
D --> E["Boomerang switching joins two short trails, buys free middle rounds"]
E --> F["Characteristic spans full AES-192 and AES-256"]

Road two: biclique leans on the key schedule's slow diffusion#

The second road answers a different question. Related-key attacks need a strong model no protocol grants. Could anything reach the full cipher in the ordinary single-key model? In 2011, Andrey Bogdanov, Dmitry Khovratovich and Christian Rechberger answered yes -- with an important asterisk.

Applied to full AES with no related keys assumed, the biclique attack recovers keys at $2^{126.1}$ for AES-128, $2^{189.7}$ for AES-192, and $2^{254.4}$ for AES-256 ^[22]. Those are the only single-key, full-round results faster than brute force that exist.

And here is where the savings come from: between neighboring keys in a group, so few round-key and state bytes change that most of the computation can be reused -- and that is a consequence of the key schedule's slow diffusion, the same sluggish mixing we watched in Section 3. Where the related-key road exploits the schedule's linearity, the biclique road exploits its slowness.

But the honest framing is load-bearing, and this article treats it as non-negotiable.

The authors said as much themselves, and it is the most important sentence in the whole biclique story.

The biclique attacks on full AES "do not threaten the practical use of AES in any way." -- Bogdanov, Khovratovich, and Rechberger, ASIACRYPT 2011 ^[22]

flowchart TD
A["Partition the key space into groups"] --> B["Build a biclique over a few rounds per group"]
B --> C["Precompute partial encryptions once per group"]
C --> D["Neighboring keys differ in few bytes: slow key-schedule diffusion"]
D --> E["Reuse precomputation, recompute only what changed"]
E --> F["Each key costs less than one full encryption"]
F --> G["Full-round key recovery, about a factor of 4 under brute force"]

Put the two roads side by side and the article's claim stops being rhetoric.

The only two ways anyone has reached full-round AES faster than brute force both run through the key schedule. The related-key attacks break it head-on, chaining local collisions through its linearity to recover keys on full AES-192 and AES-256. The biclique attack leans on it, exploiting its slow diffusion to shave a factor of four off exhaustive search in the single-key model. The celebrated S-box and MixColumns are untouched in both. The crack starts at the part nobody fortified.

Two roads to the full cipher, both paved by the key schedule -- one breaking it, one leaning on it. So where exactly does AES stand today?

7. Where AES Stands Today#

Strip away the drama and put the numbers on one table. That table is the clearest statement of where AES is strong and where it is thin.

Three ceilings orient everything: brute force costs $2^{128}$, $2^{192}$, and $2^{256}$ for the three key sizes. Every result below is measured against those.

Read the columns and the whole argument snaps into focus. The single-key reduced-round column stalls at 7, 8, and 9 rounds out of 10, 12, and 14 -- and it has not moved since 2013 ^[17]. The single-key full-round column sits about two bits under the ceiling, a factor of roughly four, courtesy of biclique ^[22]. Tao and Wu refined the biclique complexities in 2015, nudging the last digits and cutting the attack's storage requirement, but the headline numbers barely moved -- evidence that the single-key full-round margin has been essentially static for over a decade ^{[23] [24]}. The related-key column is the outlier: $2^{99}$ against a $2^{256}$ ceiling for AES-256 is an enormous complexity gap -- but only in a model real deployments deny.

The frontier keeps yielding small refinements, and where they land is telling. In 2018, Achiya Bar-On, Orr Dunkelman, Nathan Keller, Eyal Ronen and Adi Shamir cut the best 5-round single-key attack from about $2^{32}$ to under $2^{22}$ -- practical enough to run -- and gave the best practical-data attacks on 7-round AES-192 ^[25].

And in 2021, Gaëtan Leurent and Clara Pernot found that the AES-128 key schedule can be split into four independent parallel computations on 32-bit chunks, up to linear transformation -- a structural fact, in their words, "not described in the literature after more than 20 years" of analysis ^[8]. Twenty years on, the fresh cryptanalytic advantage still comes from the key schedule.

So the margin is asymmetric. In rounds reached, the related-key model gets uncomfortably close to full coverage while the single-key model plateaus a few rounds short. In complexity, the numbers are astronomically wide everywhere except the related-key AES-256 corner. And even that "best" single-key number is not remotely a threat.

One table, two full-round winners, one common thread. Line them up as competing methods and the thesis stops being a claim and becomes a pattern.

8. Single-Key, Related-Key, and the Common Thread#

These attack families are not really competitors -- they optimize for different things. Put them on shared axes and you can see exactly what each one buys, what it costs, and what it leans on.

The two full-round rows and the two reduced-round rows tell opposite halves of the same story. The reduced-round families cannot cross the wide-trail wall no matter how cleverly they are automated or how practical their data becomes -- they top out short of the full cipher because the round function gives them nothing longer to work with.

The full-round families cross it only by refusing to fight the round function at all. One changes the model to attack the key schedule's linearity; the other accepts brute-force complexity and mines the key schedule's slow diffusion for a discount. Every entry in the "leans on key schedule?" column is a yes or a trending-toward-yes.

AES-256 has more rounds and a longer key than AES-128 -- and under related keys, that longer, still-linear key schedule is exactly what makes it weaker. More key material, more structure to exploit.

The honest caveat rides along in the table too. Biclique's "yes" in the last column is an enabling dependence -- it needs the schedule to diffuse slowly so its precomputation can be reused -- not the structural collapse that the related-key row represents. Reading the two together is the point: the key schedule is the common thread of every full-round result, but it is threaded two different ways, and only one of them is a direct break.

The pattern is undeniable, but a pattern is not a proof. How close can cryptanalysis get -- and could we ever prove it can get no closer?

9. How Close Can Cryptanalysis Get?#

Here is the uncomfortable truth that separates cryptography from mathematics: nobody can prove AES is secure. Not "has not proven it yet" -- cannot, even in principle, in the way we mean it for public-key systems.

RSA and Diffie-Hellman rest on the assumed hardness of a specific, well-studied problem -- integer factoring, or the discrete logarithm -- that the world's mathematicians have failed to solve efficiently for decades, and some public-key schemes (Rabin, or lattice systems) provably reduce to such problems. Their security is anchored to a famous open question. Block ciphers have no such anchor.

AES's security is not reducible to any problem believed hard; it rests entirely on the fact that very smart people have attacked it for twenty-five years and failed. That is strong evidence, but it is not a proof, and it means a future structural break can never be ruled out -- only measured, as a margin.

The nearest thing to a proof AES has is a design-level bound, and it is precisely bounded in what it covers.

That gap is the article's most counterintuitive lesson. Security is not a binary a cipher passes or fails; it is a measured quantity, and the measurement keeps coming back thinnest at the key schedule. Worse for intuition: the AES-256-versus-AES-128 result shows that adding key material can lower the margin rather than raise it, because a longer linear key schedule is more structure to attack. The one genuine impossibility result we do have points the same way -- Biryukov, Khovratovich and Nikolić proved AES-256 cannot instantiate an ideal cipher, using the very key-schedule structure the related-key attacks ride ^[21].

What about quantum computers -- surely they change the answer? For AES, structurally, they do not.

Grover's algorithm gives a generic square-root speedup for key search: $2^{n/2}$ instead of $2^{n}$, so AES-128 drops to roughly $2^{64}$ and AES-256 to roughly $2^{128}$ ^[27]. Crucially, that speedup is independent of AES's internal structure -- it applies to any cipher, treating AES as a black box. It does not touch the key schedule, the S-box, or MixColumns; it does not care how AES is built.

That is exactly why Grover sits outside this article's thesis: it is a generic key-search discount, not a structural break. And Shor's algorithm ^[28], which shatters RSA and elliptic curves, attacks the hidden-subgroup structure of public-key math and simply does not apply to symmetric ciphers.

No proof, a thin single-key margin, and a key schedule that keeps yielding fresh structure twenty years on. So what would it actually take to break AES?

10. What Would Actually Break AES#

If you wanted to be the person who genuinely dented AES, here is the to-do list -- and why every item on it has resisted the field's best for more than a decade.

Close the single-key reduced-round gap. The frontier has sat at 7, 8, and 9 rounds since 2013, despite automated search tools purpose-built to push it ^[17]. Nobody has extended the single-key attacks by even one round in over ten years. Either a genuinely new distinguisher is needed, or the round function really does leave nothing longer to exploit.

Migrate the key-schedule attacks into the single-key model. The related-key attacks reach the full cipher, but only under a model real protocols deny. Can their key-schedule insight be recast into an attack that needs no related keys? So far, no -- and this is the single most important open question for the thesis. If it ever happened, the crack really would start where this article predicts, in a model that matters.

Prove that a nonlinear key schedule would have mattered. Would a heavier, nonlinear key expansion have removed both the related-key local collisions and biclique's recomputation discount? There is strong circumstantial evidence it would: Leurent and Pernot's 2021 discovery that the AES-128 schedule still splits into four independent 32-bit computations shows the linearity keeps handing attackers structure two decades on ^[8].

Find a real single-key shortcut on full AES-128. Not biclique's two bits -- an attack meaningfully below $2^{126}$ that reflects a structural weakness rather than an accounting trick. None is known.

Push the new structural distinguishers deeper. In 2017, Lorenzo Grassi, Christian Rechberger and Sondre Rønjom found an unexpected structural-differential property of 5-round AES, which Bar-On and colleagues then turned into the best practical 5-round attack ^{[29] [25]}. Can such properties reach 6, 7, or more rounds? So far they have not.

None of these five is close to solved. The standing challenge is stark: outside the related-key model, and beyond biclique's two-bit shave, nothing has meaningfully dented full-round single-key AES-128 in the entire history of its public analysis. Which is exactly why, for everyone who actually ships software, the right question is not "when will AES break?" but "what should I do today?"

11. What This Means for You#

Strip all of it down to what changes your decisions. For almost everyone, the answer is: nothing -- and understanding why nothing changes is the real payoff.

AES is not broken. Every structural result in this article is astronomically infeasible, the strongest single-key full-round attack shaves a factor of four off a number no machine will ever reach, and the related-key attacks need access that correctly built systems never grant. Keep using AES.

On key size, choose deliberately rather than superstitiously. AES-128 and AES-256 are both effectively unbreakable in the single-key model your systems actually run in; the related-key paradox that makes AES-256 "weaker" lives entirely in a model deployments deny ^[20].

Prefer AES-256 when you want long-term or post-quantum margin, because Grover's generic square-root speedup halves the effective key length and a $2^{128}$ quantum margin is more comfortable than $2^{64}$ ^[27]. Prefer AES-128 when you want raw speed and a post-Grover margin of $2^{64}$ is ample for your threat model. Both are sound; the choice is about margin, not about one being broken.

The one pitfall worth internalizing is the related-key boundary.

You can make the margin tangible with a few lines of arithmetic. The calculator below reads the AES-128 single-key margin both ways the article measures it: as rounds reached versus total, and as the best full-round complexity versus the brute-force ceiling.

// Two ways to feel the margin, using the numbers from this article.
const totalRounds = 10;
const bestSingleKeyRounds = 7;         // best single-key reduced-round (DFJ 2013)
const bruteForceExponent = 128;        // brute-force ceiling for AES-128
const bestFullRoundExponent = 126.1;   // biclique (BKR 2011)

// 1) Round margin: how many full rounds still resist single-key attack.
const roundMargin = totalRounds - bestSingleKeyRounds;
console.log("Rounds still beyond the best single-key attack: " + roundMargin +
          " of " + totalRounds);

// 2) Complexity margin: how much "faster than brute force" biclique really is.
const speedupFactor = Math.pow(2, bruteForceExponent - bestFullRoundExponent);
console.log("Biclique speedup over brute force: about " +
          speedupFactor.toFixed(1) + "x");
console.log("Brute force itself: 2^128, roughly 1 followed by 38 zeros.");
console.log("A 3.7x discount on a never-finishable computation is still never-finishable.");

Return to the question this article opened with: not whether AES is broken, but where the first crack would appear if it ever were. The evidence has answered it.

The AES round function is the most-analyzed, most-trusted primitive in symmetric cryptography, and twenty-five years of single-key attacks have plateaued a few rounds short of it -- the wide-trail design working exactly as intended. Every full-round result faster than brute force lives somewhere else: the related-key attacks break the linear key schedule head-on, reaching full AES-192 and AES-256, and the biclique attack leans on its slow diffusion to shave a factor of four off exhaustive search. The S-box and MixColumns are untouched. If AES ever falls, the evidence says the first crack starts at the key schedule -- the least-designed, most-linear component -- bounded by the honest caveat that biclique leans on the schedule rather than breaking it.