Unit 2: Modern Symmetric-key Encipherment

CSE403 — Network Security And Cryptography 9 min read

I. Foundations of Modern Symmetric-key Encipherment

Modern symmetric-key encipherment protects digital data by applying the same secret key to encryption and decryption. Modern block ciphers process fixed-size blocks through repeated substitution, permutation, and key-mixing operations, aiming to provide confusion and diffusion while remaining efficient in hardware and software.

Shared secret: The sender and receiver possess the same key, or keys that can be efficiently derived from one another.
Block operation: A block cipher maps an (n)-bit plaintext block (P) to an (n)-bit ciphertext block (C):
TEXT
```
  C = E_K(P)
  P = D_K(C)
```
Here, (E_K) is encryption under key (K), and (D_K) is the corresponding decryption operation.
Invertibility: For every valid key and plaintext block, (D_K(E_K(P))=P).
Confusion: The relationship between the key and ciphertext is made complex, commonly through nonlinear substitution boxes.
Diffusion: Each plaintext bit influences many ciphertext bits through permutations and linear mixing.
Product cipher: Security results from repeatedly combining individually simple transformations in multiple rounds.
Avalanche effect: Changing one plaintext or key bit should change approximately half the output bits.
Kerckhoffs's principle: Security must depend on secrecy of the key, not secrecy of the algorithm.
Practical requirement: A block cipher must be used with a secure mode of operation, proper key management, and correctly generated initialization values or nonces.

II. Finite-field Arithmetic — Mathematical Basis of Block Ciphers

A. GF(2^n) Fields

A Galois field (GF(2^n)) is a finite field containing (2^n) elements, represented as binary polynomials of degree less than (n).

Element representation: A bit string (b_{n-1}\ldots b_1b_0) represents:
TEXT
```
  b(x) = b_(n-1)x^(n-1) + ... + b_1x + b_0
```
Each coefficient (b_i) belongs to (GF(2)={0,1}).
Addition: Polynomial coefficients are added modulo 2, making field addition equivalent to bitwise XOR:
TEXT
```
  1011 XOR 0110 = 1101
```
No carry is produced because (1+1=0) in (GF(2)).
Subtraction: Addition and subtraction are identical because every element is its own additive inverse:
TEXT
```
  a(x) - b(x) = a(x) + b(x)
```
Multiplication: Polynomials are multiplied normally, with coefficients reduced modulo 2, and the result is divided by an irreducible polynomial (m(x)).
Modular reduction: In (GF(2^n)), the relation (m(x)=0) reduces products of degree (n) or higher to degree below (n).
Field condition: The modulus (m(x)) must be irreducible over (GF(2)); otherwise, some nonzero elements would lack multiplicative inverses.
Multiplicative inverse: Every nonzero element (a(x)) has a unique (a^{-1}(x)) satisfying:
TEXT
```
  a(x)a^(-1)(x) mod m(x) = 1
```
AES field: AES treats each byte as an element of (GF(2^8)), using:
TEXT
```
  m(x) = x^8 + x^4 + x^3 + x + 1
```
Its binary representation is 100011011, commonly written as hexadecimal 0x11B.
Cryptographic role: AES uses field inversion in SubBytes and field multiplication in MixColumns, providing nonlinear confusion and linear diffusion.

III. Data Encryption Standard — Feistel-based Encipherment

DES was standardized in 1977 and encrypts 64-bit blocks using a 64-bit supplied key, of which 56 bits are cryptographically effective and eight are parity bits.

A. DES Structure

DES is a 16-round Feistel cipher in which each round transforms two 32-bit halves while using a different 48-bit round key.

Initial processing: The 64-bit plaintext undergoes the Initial Permutation (IP) and is divided into (L_0) and (R_0).
Round equations: For round (i), where (1\leq i\leq16):
TEXT
```
  L_i = R_(i-1)
  R_i = L_(i-1) XOR F(R_(i-1), K_i)
```
Here, (L_i) and (R_i) are 32-bit halves, (F) is the round function, and (K_i) is a 48-bit subkey.
Expansion permutation: The expansion function (E) expands (R_{i-1}) from 32 to 48 bits by repeating selected boundary bits.
Key mixing: The expanded value is XORed with the round key:
TEXT
```
  X = E(R_(i-1)) XOR K_i
```
S-box substitution: Eight S-boxes each convert a 6-bit input into a 4-bit output, reducing 48 bits to 32 bits and introducing nonlinearity.
- The first and sixth input bits select the S-box row.
- The middle four bits select its column.
Permutation: The 32 S-box output bits undergo permutation (P), spreading each S-box's influence across later rounds.
Key schedule: Permuted Choice 1 discards eight parity bits and splits the remaining 56 bits into two 28-bit halves. Left rotations and Permuted Choice 2 generate sixteen 48-bit subkeys.
Final processing: After round 16, the halves are swapped and the inverse permutation (IP^{-1}) produces the ciphertext.
Decryption: The Feistel structure uses the same algorithm with subkeys applied in reverse order, (K_{16},\ldots,K_1).

B. Analysis and Security of DES

DES has a carefully designed round structure, but its 56-bit effective key is too short for present-day security.

Brute-force complexity: Exhaustive search requires at most (2^{56}) trials and about (2^{55}) trials on average.
Historical break: The Electronic Frontier Foundation's DES Cracker recovered a DES key in 1998 in approximately 56 hours, demonstrating practical exhaustive search.
Avalanche behavior: DES's S-boxes and permutations cause a one-bit input difference to affect many output bits after several rounds.
Differential cryptanalysis: The attacker studies how chosen plaintext differences influence ciphertext differences. Full 16-round DES was designed to resist this technique better than reduced-round variants.
Linear cryptanalysis: Approximate linear relationships among plaintext, ciphertext, and key bits can reveal key information when sufficiently many known plaintext-ciphertext pairs are available.
Weak keys: Four DES keys generate identical subkeys in all rounds; semi-weak key pairs generate only two distinct subkeys. Secure implementations reject these rare values.
Complementation property: If (C=E_K(P)), then:
TEXT
```
  complement(C) = E_complement(K)(complement(P))
```
This property can reduce some exhaustive-search work but is not the primary weakness.
Block-size limitation: A 64-bit block size leads to significant collision risk after roughly (2^{32}) blocks under one key and mode context.
Triple DES: TDEA applies DES three times, usually in encrypt-decrypt-encrypt form, but remains slow and retains the 64-bit block limitation.
Security conclusion: DES and Triple DES are unsuitable for new systems; AES or another approved modern cipher should replace them.

IV. Advanced Encryption Standard — Substitution-Permutation Encipherment

AES, standardized by NIST in 2001 from the Rijndael algorithm, is a substitution-permutation network operating on 128-bit blocks with 128-, 192-, or 256-bit keys.

A. AES Introduction

AES arranges each 128-bit block as a (4\times4) byte state and repeatedly transforms that state using key-dependent rounds.

State arrangement: Input bytes fill the state column by column:
TEXT
```
  State[r,c] = input[4c + r]
```
Here, (r) is the row index and (c) is the column index, each from 0 to 3.
Round counts: AES-128 uses 10 rounds, AES-192 uses 12, and AES-256 uses 14.
Key words: If (N_k) is the number of 32-bit key words, AES-128, AES-192, and AES-256 use (N_k=4,6,8), respectively.
Architecture: AES is not a Feistel cipher; every transformation operates on the complete state, and decryption uses inverse transformations.
Initial stage: Encryption begins with AddRoundKey.
Standard round: Each nonfinal round applies SubBytes, ShiftRows, MixColumns, and AddRoundKey.
Final round: The final round omits MixColumns.
Security margin: No practical attack is known against correctly implemented full-round AES with secure keys; implementation failures are the more common threat.

B. AES Transformations

AES combines nonlinear byte substitution, byte movement, column mixing, and key addition to produce confusion and diffusion.

SubBytes: Each byte is replaced using a fixed 256-entry S-box constructed from multiplicative inversion in (GF(2^8)), followed by an affine transformation.
ShiftRows: Rows 0, 1, 2, and 3 are cyclically shifted left by 0, 1, 2, and 3 bytes, respectively.
MixColumns: Each state column is multiplied over (GF(2^8)) by:
TEXT
```
  |02 03 01 01|
  |01 02 03 01|
  |01 01 02 03|
  |03 01 01 02|
```
Hexadecimal coefficients represent field elements; multiplication is reduced modulo 0x11B.
AddRoundKey: The state is XORed with a 128-bit round key:
TEXT
```
  State = State XOR RoundKey
```
Combined effect: SubBytes supplies nonlinearity, while ShiftRows and MixColumns spread local changes across columns and rounds.
Inverse operations: Decryption uses InvShiftRows, InvSubBytes, AddRoundKey, and InvMixColumns; XOR-based AddRoundKey is self-inverse.
Implementation concern: Table-based software can leak information through cache timing; constant-time instructions such as AES-NI reduce this side-channel exposure.

C. AES Key Expansion and Ciphers

AES key expansion derives a distinct 128-bit round key for every encryption round from the original cipher key.

Expansion size: AES requires (N_b(N_r+1)) words, where (N_b=4) state columns and (N_r) is the number of rounds.
Core operations:
- RotWord cyclically rotates a four-byte word.
- SubWord applies the AES S-box to every byte.
- Rcon supplies round-dependent field constants.

AES-128 rule: For word (w_i):

TEXT

  temp = w_(i-1)
  if i mod 4 = 0:
      temp = SubWord(RotWord(temp)) XOR Rcon[i/4]
  w_i = w_(i-4) XOR temp

Here, (i) is the word index and (w_i) is a 32-bit expanded-key word.

Cipher sequence: