Key Schedules: Why Subkeys Cannot Be Independent

A block cipher with a 128-bit key runs ten or more rounds, and each round XORs a full block’s worth of key material into the state. Ten rounds of AES consume 176 bytes of expanded key from a 16-byte secret. The naive solution — derive each round key as an independent hash of the master key — would work, but it would double the cost of the cipher in software and require the hash itself to be a cryptographic primitive, which is circular when the cipher is the primitive the system trusts. Real schedules instead compute subkeys from each other by a chain of simple transformations.

That choice introduces the cipher’s most underappreciated failure surface. The schedule is a deterministic function from a small secret to a long sequence of related values, and the relations between those values are public. An attacker who can reason about how subkey $i+1$ relates to subkey $i$ can sometimes cancel rounds against each other.

What the expansion has to accomplish

Three requirements pull in different directions. First, the schedule must be cheap, because it runs on every key setup and is repeated for every block in modes that rekey frequently. Second, it must produce round keys that are, as far as an attacker can tell, independent — no linear relation between two subkeys that would let a pair of rounds cancel. Third, it must be invertible in the direction that matters: given the last round key and knowledge of the schedule, the master key should not be recoverable more cheaply than by brute force over the key space.

The second requirement is the hard one, and it is why nearly every schedule includes a nonlinear step. A purely linear expansion, such as deriving subkey $i$ by rotating and XORing constants into the master key, produces subkeys that are affine functions of the master key. The cipher then becomes, in a precise sense, a cipher whose rounds differ only by known affine offsets, which is exactly the situation slide attacks and related-key differentials exploit.

The AES expansion in detail

AES-128 expands 16 bytes into 176 by processing the key as four 32-bit words and generating forty more. Words $w_0$ through $w_3$ are the key itself. For $i$ from 4 to 43:

$$w_i = w_{i-4} \oplus \mathrm{step}(w_{i-1})$$

where $\mathrm{step}$ is the identity for three out of every four words, and every fourth word is transformed before use. The transformed case applies RotWord (a one-byte left rotation within the word), SubWord (the AES S-box to each of the four bytes), and XORs a round constant.

The round constant is a byte in the top position, with the rest zero. It is generated in $\mathrm{GF}(2^8)$ by repeated multiplication by $x$: the sequence begins 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, then reduces modulo the field polynomial to 0x1b, 0x36, and continues. Its purpose is to break the symmetry between rounds. Without it, a key of all zeros would expand to a sequence with repeating structure, and a key consisting of a repeated word would produce round keys with visible periodicity.

The S-box in SubWord is the nonlinearity. Because it is applied only once per four words, the expansion is not uniformly nonlinear — $w_4$ depends nonlinearly on $w_3$, but $w_5$ depends linearly on $w_4$ and $w_1$, and so on. This is intentional: full nonlinearity at every step would cost four times as much, and the designers’ argument is that the nonlinearity propagates through the chain, so that after a few steps every word depends nonlinearly on the original key.

For AES-192 and AES-256 the loop changes: 192-bit keys process six words per group and apply the transform every sixth word, while 256-bit keys apply an extra SubWord to $w_{i-4}$ on every fourth word. That extra substitution in AES-256 is the reason its related-key behaviour differs from AES-128’s.

/* AES-128 key expansion: 44 words from 4. The S-box and round constants
   supply the only nonlinearity and the only per-round variation. */
static void expand_key(const uint8_t key[16], uint8_t rk[176])
{
    uint32_t w[44];
    for (int i = 0; i < 4; i++)
        w[i] = load_be32(key + 4 * i);

    uint8_t rcon = 1;
    for (int i = 4; i < 44; i++) {
        uint32_t t = w[i - 1];
        if (i % 4 == 0) {
            t = (t << 8) | (t >> 24);            /* RotWord */
            t = sub_word(t);                      /* SubWord */
            t ^= (uint32_t)rcon << 24;            /* round constant */
            rcon = xtime(rcon);
        }
        w[i] = w[i - 4] ^ t;
    }
    for (int i = 0; i < 44; i++)
        store_be32(rk + 4 * i, w[i]);
}

The expansion is reversible. Given the last four words and the round constants, each earlier word follows from $w_{i-4} = w_i \oplus \mathrm{step}(w_{i-1})$, and SubWord inverts through the inverse S-box. This matters for a specific operational reason: implementations that store only the encryption round keys can derive the decryption keys on demand, and hardware that must support both directions can hold one set and generate the other. The equivalent inverse cipher formulation goes further and transforms the decryption round keys with InvMixColumns so that decryption reuses the encryption datapath with a different key order.

What weak expansion enables

The clearest historical example is not AES but IDEA, whose key schedule is a rotation of the 128-bit master key by 25 bits between each group of subkeys. Because the rotation is linear and the subkeys are overlapping windows of the same bit string, certain master keys produce subkeys with multiplicative relationships. Daemen, Govaerts, and Vandewalle identified classes of such weak keys, and the cipher’s resistance depends on those classes being small enough that random search does not find them. The lesson generalised: a linear schedule makes the set of “special” keys a structured algebraic variety rather than a scattering of isolated points.

Slide attacks exploit a different consequence of the same property. If two consecutive rounds use the same subkey, the pair of rounds is a fixed function applied twice, and an attacker can treat the cipher as a shorter cipher iterated. Schedules that derive subkeys by rotation alone can produce self-similar round keys for particular master keys; the attack then recovers the period and reduces the effective round count. Adding a round constant, as AES does, ensures that no two rounds are identical even for a key of all zeros. Feistel designs have an additional motive for this care, because their decryption path consumes the same subkeys in reverse order and any periodicity in the sequence makes the forward and backward paths coincide sooner; the shell itself is described in Feistel round invertibility.

Related-key attacks are the sharpest test. They assume the attacker can obtain encryptions under two keys whose difference is known and chosen, which is a strong assumption — it does not correspond to any standard threat model for a well-built protocol — but it is a useful measure of schedule quality because it isolates exactly the relations the schedule creates. Biryukov and Khovratovich showed that AES-256’s schedule, with its extra SubWord, admits related-key distinguishers over the full fourteen rounds with a complexity far below brute force, and that the same techniques reach reduced-round versions of the other key sizes. No practical attack on AES under a normal threat model follows from this, and the result is generally read as an argument that the 256-bit variant’s extra margin is partly spent on schedule structure rather than on the round function.

The design response in newer ciphers has been to make the schedule itself a strong function of the key, or to avoid key-dependent schedules entirely. Some designs derive all round keys from a single permutation of the key, so that subkeys are as unrelated as the permutation allows; others, particularly in the lightweight domain, accept a simpler schedule and add rounds to compensate. Threefish derives subkeys by adding a constant and rotating, then injects a per-block tweak, and its designers argue the round count covers the schedule’s weakness. The trade is always the same: schedule cost against round count against related-key margin.

Schedule cost in practice

The cost is not negligible. AES-128’s expansion requires 40 word operations, 10 S-box applications of four bytes each, and 10 field multiplications — roughly comparable to one and a half encryption rounds. In a protocol that derives a fresh key per message, that overhead is paid per message and can dominate for short payloads. This is why key derivation is often separated from encryption: derive one long key once, then slice it into per-message keys, so the expansion runs once per slice rather than once per message.

Modes that need many subkeys make the accounting visible. XTS derives two keys and uses them for tweak encryption and block encryption respectively; the tweak itself is computed by encrypting a sector number, so each sector costs one extra block encryption regardless of its length. Constructions that need a key per round or per block, such as some wide-block modes, multiply the expansion cost by the number of derived values.

There is a hardware dimension too. Round keys are often precomputed and stored, which means the expanded key sits in memory and becomes a target: a memory disclosure that exposes 176 bytes exposes the master key just as surely as one that exposes 16. Implementations that expand on the fly trade computation for a smaller exposure window. Where the expanded key is held, the same constant-time concerns that apply to the round function apply to the schedule — an S-box lookup in SubWord is a table access indexed by secret data, and the timing analysis in constant-time AES implementation applies to it directly. That is also the argument for expanding the key inside hardware instructions where they exist, since the expansion then never touches a table in memory.

The schedule is also where a cipher’s algebraic structure is most visible. Because subkeys are related by a public recurrence, any attack that can express the cipher as a system of equations in the master key’s bits gets additional low-degree relations for free. That is one reason algebraic attacks have been more productive against ciphers with simple schedules than against ciphers with complex ones, and it is a consideration that reaches beyond the round function’s own strength into how the S-box and the expansion interact.