AES key schedule
The AES key schedule, formally known as the KeyExpansion algorithm, is the process by which the Advanced Encryption Standard (AES) derives a series of subkeys, or round keys, from an initial cipher key to support the cipher's iterative encryption and decryption rounds.[1] This symmetric block cipher, standardized by the National Institute of Standards and Technology (NIST) in 2001 as FIPS 197, operates on 128-bit blocks using cipher keys of 128, 192, or 256 bits, corresponding to variants AES-128, AES-192, and AES-256.[2]
The key schedule expands the cipher key into an array of 44, 52, or 60 words (each 32 bits) for AES-128, AES-192, and AES-256, respectively, yielding 11, 13, or 15 round keys of 128 bits each to cover the initial state addition plus 10, 12, or 14 transformation rounds.[1] It begins by copying the first 4, 6, or 8 words (denoted Nk) directly from the cipher key into an expanded key array w to w[Nk-1].[1] Subsequent words are generated iteratively for i from Nk to 4(Nr+1)-1, where Nr is the number of rounds: each new word w is computed as w[i-Nk] XORed with a temporary value derived from w[i-1], ensuring dependency on prior key material.[1]
To introduce diffusion and non-linearity, the temporary value undergoes specific transformations: if i modulo Nk equals 0, it is the result of RotWord (a cyclic left shift of the word's bytes) followed by SubWord (S-box substitution on each byte) and XORed with a round constant Rcon[i/Nk], where Rcon consists of powers of 2 in the finite field GF(2^8) as [rc, 00, 00, 00] with rc[3]=01 and subsequent values obtained by doubling modulo x^8 + x^4 + x^3 + x + 1.[1] Otherwise, the temporary value is simply w[i-1], except in AES-256 (Nk=8), where an additional SubWord is applied if i modulo 8 equals 4 to further enhance security through extra non-linearity.[1] Round keys are then formed by taking consecutive groups of 4 words from this expanded array.[1]
Designed by cryptographers Joan Daemen and Vincent Rijmen as part of the Rijndael block cipher submitted to NIST's AES selection process, the key schedule prioritizes high diffusion to propagate changes from the cipher key across all round keys, invertibility for efficient decryption, computational efficiency in software and hardware, and resistance to attacks such as related-key differentials by avoiding linear structures and symmetries through the use of round constants.[4] Rijndael's key schedule supports flexible block and key sizes but was fixed in AES to 128-bit blocks with the specified key lengths, enabling on-the-fly computation with minimal storage (just an Nk-word buffer) while providing strong security boundaries, as evidenced by its unchanged core in the 2023 update to FIPS 197.[4][2]
Background and Purpose
Role in AES Encryption
The Advanced Encryption Standard (AES) is a symmetric block cipher that processes data in fixed 128-bit blocks using secret keys of 128, 192, or 256 bits in length, corresponding to 10, 12, or 14 rounds of transformation, respectively.[1] In the AES encryption process, the plaintext state undergoes a series of operations including SubBytes, ShiftRows, MixColumns, and AddRoundKey in each round, with the key schedule playing a pivotal role by providing distinct subkeys for the AddRoundKey step.[1]
The key schedule, known as KeyExpansion in the AES specification, derives a series of round keys from the initial cipher key to prevent the reuse of the same key material across multiple rounds, thereby enhancing security through per-round XOR operations with the evolving state.[1] This derivation ensures that each round incorporates unique key material, which is XORed into the state at the beginning of the round (initial whitening) and after the final round's transformations, facilitating the overall cipher's resistance to cryptanalytic attacks.[4]
Designed by Joan Daemen and Vincent Rijmen as part of the Rijndael algorithm, which was selected by NIST in 2001 to become AES, the key schedule incorporates mechanisms for diffusing key material across all rounds to achieve high nonlinearity and eliminate symmetries that could weaken the cipher.[1] The overall flow proceeds from the input cipher key through the KeyExpansion process to generate an expanded key array, from which round keys are sequentially extracted—one for the initial AddRoundKey, one per subsequent round, and one for the final AddRoundKey—integrating seamlessly into the block encryption pipeline.[4]
Key and Round Key Definitions
The cipher key in the AES key schedule is the initial secret key used to derive the round keys, consisting of a sequence of 128, 192, or 256 bits, corresponding to 16, 24, or 32 bytes, respectively.[5] It is represented as a rectangular array of bytes with four rows and Nk columns, where Nk equals 4, 6, or 8, and each column forms a 32-bit word treated as four bytes in column-major order.[5] This structure facilitates processing in the key expansion routine, aligning with the AES block size of 128 bits organized into Nb = 4 words.[5]
A word in the AES key schedule is defined as a 32-bit entity, equivalent to four bytes, which serves as the basic unit for key manipulation.[5] The expanded key schedule produces a linear array of these words, denoted as w to w[Nb × (Nr + 1) - 1], where Nb = 4 and Nr is the number of rounds (10 for 128-bit keys, 12 for 192-bit keys, and 14 for 256-bit keys), resulting in a total of 44, 52, or 60 words, respectively.[5]
Round keys are the subkeys derived from the cipher key, each comprising 128 bits or 4 words, with a total of Nr + 1 round keys generated to support the AddRoundKey transformation in each AES round, including the initial round before the main iterations.[5] These round keys are typically represented either as byte arrays for direct state XOR operations or as column-major word arrays to match the internal processing of the cipher key.[5] In the context of AES encryption, this multiplicity of round keys ensures that distinct subkeys are applied across rounds to enhance security through varied inputs to the cipher operations.[5]
Round Constants
Computation Method
The round constants, denoted as RC or Rcon, are single-byte values computed as elements in the finite field GF(2^8), serving to introduce non-linearity during the AES key expansion process by breaking symmetry in round key generation.[6] These constants are derived from powers of the primitive element x = {02} (representing the polynomial x in hexadecimal notation) modulo the irreducible polynomial defining the field.[6]
Mathematically, the i-th round constant is given by RC = x^{i-1} for i ≥ 1, where computations occur in GF(2^8) with the irreducible polynomial
m(x) = x^8 + x^4 + x^3 + x + 1
(equivalent to 0x11b in hexadecimal).[6] This polynomial ensures all field elements can be represented as polynomials of degree less than 8 with coefficients in GF(2), and reduction modulo m(x) maintains the field's structure.[6] The choice of x as a primitive element guarantees that its powers cycle through all nonzero field elements before repeating, providing the necessary diffusion properties.[6]
The computation begins with initialization: RC[3] = x^0 = 0x01.[6] For subsequent values up to the number of rounds Nr (e.g., 10 for AES-128), each RC is obtained by multiplying RC[i-1] by x in GF(2^8), equivalent to a field doubling operation.[6] This doubling is performed byte-wise as follows:
- Left-shift the byte value by one bit (multiply by 2 in integer arithmetic).
- If the most significant bit (bit 7) of the original byte was set (indicating a carry from the shift), XOR the result with 0x1b (the hexadecimal representation of m(x) without the leading x^8 term).
This step ensures reduction modulo m(x), preventing overflow beyond degree 7.[6] For example, starting from RC[3] = 0x01, the left shift yields 0x02 (no XOR needed), giving RC[7] = 0x02; then RC[8] = 0x04, and so on, with the XOR applied when the shifted value exceeds 0xFF or triggers the carry condition.[6]
Precomputed Values and Usage
In the AES key schedule, round constants (denoted as RC or Rcon, where i starts from 1) are predefined 32-bit values used to introduce non-linearity during key expansion. These constants are derived as the first byte being the (i-1)-th power of x = 0x02 in the finite field GF(2^8), with the remaining three bytes set to 0x00, and are precomputed for efficiency in implementations.[6]
The following table lists the first 10 round constants in hexadecimal notation, as specified in the AES standard:
| i | RC |
|---|
| 1 | 0x01000000 |
| 2 | 0x02000000 |
| 3 | 0x04000000 |
| 4 | 0x08000000 |
| 5 | 0x10000000 |
| 6 | 0x20000000 |
| 7 | 0x40000000 |
| 8 | 0x80000000 |
| 9 | 0x1B000000 |
| 10 | 0x36000000 |
Key Expansion Algorithm
The AES key expansion begins with the input cipher key, which is divided into the first N_k words of the expanded key array w{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} to w[N_k - 1], where each word consists of four bytes.[5] The process then iteratively generates subsequent words up to a total of N_b (N_r + 1) words, where N_b = 4 represents the block length in 32-bit words and N_r is the number of rounds, ensuring sufficient round keys for the encryption process.[5]
The core transformations rely on three primary operations applied to intermediate values during expansion. RotWord performs a cyclic left shift on a word by one byte, transforming a word [a_0, a_1, a_2, a_3] into [a_1, a_2, a_3, a_0].[5] SubWord applies the AES S-box substitution to each of the four bytes in a word independently, introducing non-linearity derived from the finite field operations in the main AES algorithm.[5] Rcon denotes the round constant array, where each entry \text{Rcon} is a word with the round constant value \text{RC} in the most significant byte and zeros in the remaining bytes; these constants are precomputed using powers of 2 in the finite field \text{GF}(2^8).[5]
The expansion proceeds via a loop that computes each new word as the XOR of a prior word and a transformed temporary value, promoting diffusion by propagating changes across the key material. The pseudocode for this core loop is as follows:
for i = N_k to N_b*(N_r + 1) - 1
temp ← w[i - 1]
if i mod N_k = 0 then
temp ← SubWord(RotWord(temp)) ⊕ Rcon[i / N_k]
else if N_k > 6 and i mod N_k = 4 then
temp ← SubWord(temp)
w[i] ← w[i - N_k] ⊕ temp
for i = N_k to N_b*(N_r + 1) - 1
temp ← w[i - 1]
if i mod N_k = 0 then
temp ← SubWord(RotWord(temp)) ⊕ Rcon[i / N_k]
else if N_k > 6 and i mod N_k = 4 then
temp ← SubWord(temp)
w[i] ← w[i - N_k] ⊕ temp
This structure ensures that every new word derives from earlier ones through XOR operations, with periodic transformations to avoid linear patterns and enhance the dependence on the initial key.[5]
Procedure for 128-Bit Keys
For the AES key schedule with 128-bit keys, the input cipher key consists of N_k = 4 words (each 32 bits), and the algorithm generates an expanded key array of N_b \times (N_r + 1) = 4 \times 11 = 44 words, where N_b = 4 is the number of words in the block and N_r = 10 is the number of rounds; this produces 176 bytes total, sufficient for 11 round keys of 16 bytes each.[6]
The procedure begins by copying the 128-bit cipher key directly into the first four words of the expanded key array, denoted as w{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} to w{{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}}, where each w is a 32-bit word formed by taking four consecutive bytes from the key in column-major order. Subsequent words are generated iteratively for i = 4 to $43 using the following steps: set a temporary word \textit{temp} = w[i-1]; if i \mod N_k = 0 (i.e., every fourth word starting at i=4), apply the core transformation by first performing \textit{RotWord}(\textit{temp}) to cyclically permute the bytes left by one position, then \textit{SubWord} to substitute each byte using the AES S-box, and finally XOR the result with the round constant Rcon[i/N_k]; otherwise, set \textit{temp} = w[i-1] without transformation; finally, compute w = w[i - N_k] \oplus \textit{temp}. This process ensures diffusion across the key material while reusing prior words to expand the key efficiently.[6]
The resulting 44-word expanded key array is then partitioned sequentially into 11 round keys, each comprising four consecutive words (w[4j] to w[4j+3] for round input j = 0 to $10), which are XORed with the state during the AddRoundKey step of AES encryption and decryption.[6]
To illustrate, consider the example cipher key $0x2b7e151628aed2a6abf7158809cf4f3c, which yields initial words w{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} = 0x2b7e1516, w{{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} = 0x28aed2a6, w{{grok:render&&&type=render_inline_citation&&&citation_id=2&&&citation_type=wikipedia}} = 0xabf71588, and w{{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}} = 0x09cf4f3c. For i=4, \textit{temp} = w{{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}} = 0x09cf4f3c; since $4 \mod 4 = 0, apply RotWord to get $0xcf4f3c09, then SubWord using the S-box to obtain $0x8a84eb01, XOR with Rcon{{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} = 0x01000000 to yield $0x8b84eb01, and finally w{{grok:render&&&type=render_inline_citation&&&citation_id=4&&&citation_type=wikipedia}} = w{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} \oplus 0x8b84eb01 = 0xa0fafe17. The next words follow without the transformation: w{{grok:render&&&type=render_inline_citation&&&citation_id=5&&&citation_type=wikipedia}} = w{{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} \oplus w{{grok:render&&&type=render_inline_citation&&&citation_id=4&&&citation_type=wikipedia}} = 0x28aed2a6 \oplus 0xa0fafe17 = 0x88542cb1, w{{grok:render&&&type=render_inline_citation&&&citation_id=6&&&citation_type=wikipedia}} = w{{grok:render&&&type=render_inline_citation&&&citation_id=2&&&citation_type=wikipedia}} \oplus w{{grok:render&&&type=render_inline_citation&&&citation_id=5&&&citation_type=wikipedia}} = 0xabf71588 \oplus 0x88542cb1 = 0x23a33939, and w{{grok:render&&&type=render_inline_citation&&&citation_id=7&&&citation_type=wikipedia}} = w{{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}} \oplus w{{grok:render&&&type=render_inline_citation&&&citation_id=6&&&citation_type=wikipedia}} = 0x09cf4f3c \oplus 0x23a33939 = 0x2a6c7605; the first round key (after the initial key) is thus w{{grok:render&&&type=render_inline_citation&&&citation_id=4&&&citation_type=wikipedia}} to w{{grok:render&&&type=render_inline_citation&&&citation_id=7&&&citation_type=wikipedia}}. This pattern continues up to w{{grok:render&&&type=render_inline_citation&&&citation_id=43&&&citation_type=wikipedia}}, deriving all round keys from the single cipher key.[6]
Procedures for 192- and 256-Bit Keys
For cipher keys of 192 bits, the key expansion algorithm uses N_k = 6 words from the initial key and generates a total of N_b \times (N_r + 1) = 4 \times 13 = 52 words for the expanded key schedule, where N_b = 4 is the block size in words and N_r = 12 is the number of rounds.[6] The process begins by loading the first N_k words directly from the cipher key into the array w{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} to w{{grok:render&&&type=render_inline_citation&&&citation_id=5&&&citation_type=wikipedia}}. For subsequent words where i ranges from 6 to 51, each new word w is computed as w = w[i - N_k] \oplus \text{temp}, with \text{temp} initialized to w[i-1]. A transformation is applied to \text{temp} only if i \mod N_k = 0: \text{temp} = \text{SubWord}(\text{RotWord}(\text{temp})) \oplus \text{Rcon}[i/N_k], where RotWord cyclically shifts the bytes left by one position, SubWord substitutes each byte using the AES S-box, and Rcon is the round constant array. No additional transformations are applied for 192-bit keys beyond this periodic step every six words.[6]
In contrast, for 256-bit cipher keys, the expansion uses N_k = 8 initial words and produces $4 \times 15 = 60 words total, supporting N_r = 14 rounds. The initial loading and general XOR recursion remain the same, with i from 8 to 59. However, the transformations differ: when i \mod 8 = 0, \text{temp} undergoes the standard \text{SubWord}(\text{RotWord}(\text{temp})) \oplus \text{Rcon}[i/8]. Additionally, when N_k = 8 and i \mod 8 = 4, an extra non-linear step applies \text{temp} = \text{SubWord}(\text{temp}) without rotation or round constant XOR. This introduces further substitution midway through each cycle of eight words. For example, at i = 12, \text{temp} = \text{SubWord}(w{{grok:render&&&type=render_inline_citation&&&citation_id=11&&&citation_type=wikipedia}}), and then w{{grok:render&&&type=render_inline_citation&&&citation_id=12&&&citation_type=wikipedia}} = w{{grok:render&&&type=render_inline_citation&&&citation_id=4&&&citation_type=wikipedia}} \oplus \text{temp}, which enhances the mixing of prior key material.[6]
The inclusion of this extra SubWord operation specifically for 256-bit keys (and more generally for N_k > 6 in the Rijndael design) aims to bolster non-linearity in the longer key schedule, thereby improving diffusion of key differences and mitigating potential linear approximations or structures that could arise from extended linear dependencies in the expansion.[11] This design choice aligns with the wide trail strategy, ensuring robust resistance to differential and linear cryptanalysis across varying key lengths.[11]
Security and Properties
Diffusion and Non-Linearity
The AES key schedule achieves diffusion through a combination of linear XOR operations that chain dependencies across consecutive words and periodic applications of the core transformation every four words, ensuring that changes in the cipher key propagate widely to the generated round keys. This recursive structure spreads a single bit difference in the input key to influence subsequent round key words, with the transformations preventing localized effects and promoting broad distribution. Specifically, the XOR chaining causes a bit change to affect all downstream words until interrupted by the non-linear core step, resulting in each bit change in the cipher key affecting approximately half of the bits in the round keys on average, akin to the strict avalanche criterion observed in the main cipher rounds.[4][10]
Non-linearity in the key schedule is primarily introduced by the SubWord operation, which applies the same bijective S-box used in the cipher's byte substitution to one word every four words, providing confusion that resists linear approximations. The RotWord step complements this by cyclically shifting the word bytes, which permutes positions to disrupt any potential alignment or periodicity in the key material. Additionally, the round constant Rcon, a predefined non-zero value XORed into the transformed word, further breaks regularity and enhances the non-linear mixing without introducing weaknesses. These elements collectively ensure the key schedule's high non-linearity, making linear cryptanalysis on the expanded keys improbable.[4]
Although the key schedule transformations—SubWord via the invertible S-box, RotWord as a permutation, and XOR with Rcon—are all reversible, the overall expansion is designed for one-way generation in practice, where the full set of round keys is derived from the compact cipher key but recovery requires knowledge of sufficient consecutive words to invert the process backward. This invertibility property allows reconstruction of the original cipher key from any Nk consecutive expanded words (where Nk is the number of 32-bit words in the cipher key), but the diffusion and non-linearity ensure that partial information does not easily compromise the entire schedule.[4]
Related-key attacks exploit predictable relationships between multiple encryption keys to recover secret information about the cipher's key schedule, potentially compromising the overall security of the block cipher. In the context of AES, the key expansion algorithm has been analyzed for such vulnerabilities, revealing weaknesses in reduced-round variants but maintaining robustness for the full number of rounds. While the linear structure of the key schedule in early rounds can allow attackers to predict subkey differences under certain key relations, the introduction of non-linear operations like SubBytes ensures that these differences propagate in a way that resists recovery in the complete 14-round AES-256 or 13-round AES-192 configurations.[9]
A notable analysis by Biryukov, Khovratovich, and Nikolić in 2009 demonstrated a related-key boomerang attack on the full AES-256, achieving key recovery with a time and data complexity of approximately 2^{99.5} and memory of 2^{77}, which is impractical for real-world adversaries. For reduced-round scenarios, subsequent work by Bogdanov, Khovratovich, and Rechberger in 2010 presented a more efficient attack on 9-round AES-256 using only two related keys, requiring 2^{39} time and negligible memory, highlighting the key schedule's relative weakness when fewer rounds are present. These attacks leverage differential properties across the key schedule but fail against the full cipher due to the cumulative non-linearity and diffusion introduced by multiple SubWord and ShiftRow operations.[9]
The AES key schedule incorporates specific design features to mitigate related-key threats. The round constants (Rcon) are added during key expansion to break potential periodicity in the subkeys, thereby preventing sliding attacks where an attacker shifts the key stream to align rounds. For the 256-bit key variant, an additional SubWord operation is applied every eighth word (when the word index modulo Nk equals 4, where Nk=8), which introduces extra non-linearity to counter linear approximations that could otherwise facilitate related-key differentials. These elements ensure that even if keys are related, the expanded round keys diverge sufficiently to thwart key recovery.
No practical related-key attacks have been found for the full AES key schedule across all variants, and post-analysis evaluations affirm its security. The National Institute of Standards and Technology (NIST) reviewed these attacks in 2021 and concluded that AES remains secure for its intended key sizes (128, 192, and 256 bits), with a sufficient security margin of 3-4 rounds beyond the attacked reduced variants, provided keys are generated randomly without exploitable structure. This security was reaffirmed in the 2023 update to FIPS 197, which left the key schedule unchanged.[14][2]