AES notes

Chapter 7: Advanced Encryption Standard (AES)

7.1 Introduction

History & Basics

• Replacement for DES, selected by NIST in 2001 (FIPS 197).
• Winning algorithm: Rijndael.
• Symmetric-key block cipher.
• Non-Feistel structure.
• Block Size: 128 bits.
• Key Sizes & Rounds ($N_r$):
  • AES-128: 128-bit key, $N_r=10$ rounds.
  • AES-192: 192-bit key, $N_r=12$ rounds.
  • AES-256: 256-bit key, $N_r=14$ rounds.

Data Units

• Byte: 8 bits.
• Word: 32 bits (4 bytes).
• Block: 128 bits (16 bytes).
• State: 128 bits arranged as a 4x4 matrix of bytes. $$S=\left(\begin{array}{cccc}{s}_{0,0}& s_{0,1}& s_{0,2}& s_{0,3}\\ s_{1,0}& s_{1,1}& s_{1,2}& s_{1,3}\\ s_{2,0}& s_{2,1}& s_{2,2}& s_{2,3}\\ s_{3,0}& s_{3,1}& s_{3,2}& s_{3,3}\end{array}\right)$$
• Block-to-State Conversion: Fill state column by column.
  • Input block: $b_0,b_1,...,b_{15}$
  • State: $s_{r,c}=b_{4c+r}$

  Example (Fig 7.4): “AESUSESAMATRIXZZ”

  • Hex: 00 04 12 14 12 04 12 00 OC 00 13 11 08 23 19 19
  • State: $$S=\left(\begin{array}{cccc}00& 12& 0C& 08\\ 04& 04& 00& 23\\ 12& 12& 13& 19\\ 14& 00& 11& 19\end{array}\right)$$

Round Structure (Encryption)

1. Pre-round: AddRoundKey.
2. Rounds 1 to $N_r-1$:
   • SubBytes
   • ShiftRows
   • MixColumns
   • AddRoundKey
3. Final Round ($N_r$):
   • SubBytes
   • ShiftRows
   • AddRoundKey (No MixColumns)

7.2 Transformations

Operations are performed on the State matrix.

SubBytes (Substitution)

• Purpose: Non-linear byte substitution for confusion.
• Process: Replace each byte $s_{r,c}$ using a fixed S-box (Table 7.1). $s_{r,c}^{\prime }=\text{S-box}[s_{r,c}]$.
• GF($2^8$) View:
  1. Find multiplicative inverse of the byte in $GF(2^8)$ with irreducible polynomial $m(x)=x^8+x^4+x^3+x+1$. (Inverse of $00$ is $00$). Let the inverse be $b^{\prime }$.
  2. Apply affine transformation: $s_{r,c}^{\prime }=X\cdot (b^{\prime })\oplus y$, where $b^{\prime }$ is treated as a column vector of its bits, $\oplus$ is bitwise XOR. $$X=\left(\begin{array}{cccccccc}1& 0& 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 0& 1& 1\\ 1& 1& 1& 1& 0& 0& 0& 1\\ 1& 1& 1& 1& 1& 0& 0& 0\\ 0& 1& 1& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 1& 1& 1\end{array}\right),y=\left(\begin{array}{c}1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0\end{array}\right)\text{ (0x63)}$$
• InvSubBytes: Use Inverse S-box (Table 7.2) or inverse affine transformation: $b^{\prime }=X^{-1}(s_{r,c}^{\prime }\oplus y)$. Then find multiplicative inverse of $b^{\prime }$.

Example (Byte 0C → FE):

1. Byte is $0C=(00001100{)}_2$.
2. Multiplicative inverse in $GF(2^8)$ is $B0=(10110000{)}_2$. Let $b^{\prime }=(0,0,0,0,1,1,0,1{)}^T$ (LSB top).
3. Matrix multiplication $X\cdot b^{\prime }$ (details omitted) gives $c=(10011101{)}_2$.
4. XOR with $y=0x63=(01100011{)}_2$: $d=(10011101{)}_2\oplus (01100011{)}_2=(11111110{)}_2=FE$.

ShiftRows (Permutation)

• Purpose: Diffusion across bytes in a row.
• Process: Cyclically shift bytes in rows to the left:
  • Row 0: No shift.
  • Row 1: Shift 1 byte left.
  • Row 2: Shift 2 bytes left.
  • Row 3: Shift 3 bytes left.
  $$s_{r,c}^{\prime }=s_{r,(c+\text{shift}(r))(\mathrm{mod}4)}$$ where $\text{shift}(0)=0,\text{shift}(1)=1,\text{shift}(2)=2,\text{shift}(3)=3$.
• InvShiftRows: Shift rows to the right by the same offsets.

Example (Fig 7.10):

• Input State: $\left(\begin{array}{cccc}63& C9& FE& 30\\ F2& F2& 63& 26\\ C9& C9& 7D& D4\\ FA& 63& 82& D4\end{array}\right)$
• ShiftRow 1 left by 1: F2 63 26 F2
• ShiftRow 2 left by 2: 7D D4 C9 C9
• ShiftRow 3 left by 3: D4 FA 63 82
• Output State: $\left(\begin{array}{cccc}63& C9& FE& 30\\ F2& 63& 26& F2\\ 7D& D4& C9& C9\\ D4& FA& 63& 82\end{array}\right)$

MixColumns (Mixing)

• Purpose: Diffusion across bytes within a column.
• Process: Treat each column as a vector and multiply by a constant matrix $C$ in $GF(2^8)$. $$\left(\begin{array}{c}{s}_{0,c}^{\prime }\\ s_{1,c}^{\prime }\\ s_{2,c}^{\prime }\\ s_{3,c}^{\prime }\end{array}\right)=\left(\begin{array}{cccc}02& 03& 01& 01\\ 01& 02& 03& 01\\ 01& 01& 02& 03\\ 03& 01& 01& 02\end{array}\right)\left(\begin{array}{c}{s}_{0,c}\\ s_{1,c}\\ s_{2,c}\\ s_{3,c}\end{array}\right)$$
  • Addition is XOR ($\oplus$).
  • Multiplication is in $GF(2^8)$ (mod $x^8+x^4+x^3+x+1$).
    • $01\cdot a=a$
    • $02\cdot a=\text{xtime}(a)$ (left shift, if original MSB was 1, XOR with $0x1B=(00011011{)}_2$).
    • $03\cdot a=(02\oplus 01)\cdot a=(\text{xtime}(a))\oplus a$.
• InvMixColumns: Multiply by $C^{-1}$ (See Fig 7.12 for $C^{-1}$).
• Note: Skipped in the last round.

Example (Mix one column element): $s_{0,c}^{\prime }=(02\cdot s_{0,c})\oplus (03\cdot s_{1,c})\oplus (01\cdot s_{2,c})\oplus (01\cdot s_{3,c})$

• Let $s_{0,c}=87=(10000111{)}_2$, $s_{1,c}=6E=(01101110{)}_2$.
• $02\cdot 87=\text{xtime}(87)$: $(10000111{)}_2\ll 1=(00001110{)}_2=0E$ (MSB was 1, but overflow bit is lost, no need to XOR with 1B? Wait, xtime is shift then XOR if needed).
  • Correct xtime: $87=(10000111{)}_2$. MSB is 1. Left shift: $(00001110{)}_2$. XOR with $1B=(00011011{)}_2$. $(00001110{)}_2\oplus (00011011{)}_2=(00010101{)}_2=15$. So $02\cdot 87=15$.
• $03\cdot 6E=(02\cdot 6E)\oplus 6E$.
  • $02\cdot 6E=\text{xtime}(6E)$: $6E=(01101110{)}_2$. MSB is 0. Left shift: $(11011100{)}_2=DC$. So $02\cdot 6E=DC$.
  • $03\cdot 6E=DC\oplus 6E=(11011100{)}_2\oplus (01101110{)}_2=(10110010{)}_2=B2$.

AddRoundKey

• Purpose: Combine the round key with the state.
• Process: XOR the state matrix with the current round key matrix (128 bits). $$S_{\text{new}}=S_{\text{old}}\oplus K_{\text{round}}$$ Each byte $s_{r,c}^{\prime }=s_{r,c}\oplus k_{r,c}$ (where $k_{r,c}$ is the corresponding byte of the round key).
• Self-Inverse: $A\oplus K\oplus K=A$.

7.3 Key Expansion

• Goal: Generate $N_r+1$ round keys ($K_0,...,K_{N_r}$) from the cipher key.
• Each round key is 128 bits (4 words). Total words $W_0,...,W_{4(N_r+1)-1}$.
• Uses RotWord, SubWord, and RCon (Round Constant).
  • RotWord: Circular left shift of bytes in a word. $[b_0,b_1,b_2,b_3]\to [b_1,b_2,b_3,b_0]$.
  • SubWord: Apply S-box to each byte of a word.
  • RCon${}_j=[R{C}_j,00,00,00]$: where $R{C}_j=x^{j-1}$ in $GF(2^8)$.
    • $R{C}_1=01,R{C}_2=02,R{C}_3=04,...,R{C}_9=1B,R{C}_{10}=36$. (See Table 7.4).

Key Expansion for AES-128 ($N_r=10$, $N_k=4$)

• Need 44 words ($W_0$ to $W_{43}$). Cipher key forms $W_0,W_1,W_2,W_3$.
• For $i=4$ to 43:
  • Calculate temp word $t=W_{i-1}$.
  • If $i(\mathrm{mod}4)=0$: $t=\text{SubWord}(\text{RotWord}(t))\oplus {\text{RCon}}_{i/4}$ $W_i=W_{i-4}\oplus t$
  • If $i(\mathrm{mod}4)\ne 0$: $W_i=W_{i-1}\oplus W_{i-4}$

Key Expansion for AES-192 ($N_r=12$, $N_k=6$)

• Need 52 words ($W_0$ to $W_{51}$). Cipher key forms $W_0..W_5$.
• For $i=6$ to 51:
  • $t=W_{i-1}$.
  • If $i(\mathrm{mod}6)=0$: $t=\text{SubWord}(\text{RotWord}(t))\oplus {\text{RCon}}_{i/6}$.
  • $W_i=W_{i-6}\oplus t$.

Key Expansion for AES-256 ($N_r=14$, $N_k=8$)

• Need 60 words ($W_0$ to $W_{59}$). Cipher key forms $W_0..W_7$.
• For $i=8$ to 59:
  • $t=W_{i-1}$.
  • If $i(\mathrm{mod}8)=0$: $t=\text{SubWord}(\text{RotWord}(t))\oplus {\text{RCon}}_{i/8}$.
  • Else if $i(\mathrm{mod}4)=0$: $t=\text{SubWord}(t)$. (Extra SubWord step specific to AES-256)
  • $W_i=W_{i-8}\oplus t$.

7.4 Ciphers (Encryption/Decryption)

Original Design

• Encryption: As described in Round Structure. Uses keys $K_0$ to $K_{N_r}$.
• Decryption: Inverse transformations applied in reverse order. Key schedule used in reverse ($K_{N_r}$ to $K_0$). Order within rounds differs from encryption.
  • Initial AddRoundKey ($K_{N_r}$)
  • Rounds 1 to $N_r-1$: InvShiftRows, InvSubBytes, AddRoundKey($K_{N_r-i}$), InvMixColumns.
  • Final Round ($N_r$): InvShiftRows, InvSubBytes, AddRoundKey($K_0$). (No InvMixColumns)

Alternative Design

• Goal: Make Decryption structure more similar to Encryption.
• Key Idea: Swap InvShiftRows/InvSubBytes (okay). Swap AddRoundKey/InvMixColumns by modifying the round keys used in decryption.
• Modified Decryption Keys: For rounds 1 to $N_r-1$ (of decryption), use $K_j^{\prime }=\text{InvMixColumns}(K_j)$. Keys $K_0$ and $K_{N_r}$ are used unchanged.
• Alternative Decryption Structure:
  • Initial AddRoundKey ($K_{N_r}$)
  • Rounds 1 to $N_r-1$: InvSubBytes, InvShiftRows, InvMixColumns, AddRoundKey($K_{N_r-i}^{\prime }$).
  • Final Round ($N_r$): InvSubBytes, InvShiftRows, AddRoundKey($K_0$). (No InvMixColumns)
  • Requires pre-computation of $K_1^{\prime },...,K_{N_r-1}^{\prime }$.

7.6 Analysis of AES

• Security: Strong against known attacks (brute-force, linear, differential, etc.). Large key space. Good diffusion and confusion. No weak keys.
• Implementation: Efficient in hardware and software (table lookups or GF math). Can be byte or word oriented.
• Simplicity: Relatively simple and elegant design.