Symmetric Cryptography

Before building secure systems, we need to know what secure even means. Claude Shannon's 1949 paper "Communication Theory of Secrecy Systems" gave us the answer: a cipher is perfectly secret if observing the ciphertext gives an adversary zero information about the plaintext, regardless of their computational power.

Formally, a cipher (E, D) over key space K, plaintext space M, and ciphertext space C achieves perfect secrecy if for every plaintext m and every ciphertext c:

$$\Pr[E(k, m) = c] = \Pr[E(k', m') = c]$$

for all m, m' and uniformly random k, k'. Equivalently: the distribution over ciphertexts is the same no matter what plaintext was encrypted.

Shannon also proved the lower bound: any perfectly secret cipher requires |K| ≥ |M|. The key space must be at least as large as the message space. This is a devastating result: you can never have perfect secrecy and a short key.

The one-time pad (OTP) achieves this bound exactly. To encrypt an n-bit message m with an n-bit key k chosen uniformly at random:

c = m XOR k

Decryption is identical: m = c XOR k. XOR is its own inverse.

Proof of perfect secrecy: For any fixed c, the equation c = m XOR k has exactly one solution k for each m (namely k = m XOR c). Since k is uniform over {0,1}^n, each plaintext is equally likely. The adversary learns nothing.

Why is the OTP impractical? The key must be (1) as long as the message, (2) truly random, (3) never reused, and (4) transmitted securely. If you can send the key securely, why not just send the message that way? The OTP solves the wrong problem. But it defines the goal: all practical ciphers try to approximate perfect secrecy under computational assumptions.

# One-Time Pad in Python
import os

def otp_encrypt(plaintext: bytes) -> tuple[bytes, bytes]:
    key = os.urandom(len(plaintext))  # truly random, same length
    ciphertext = bytes(p ^ k for p, k in zip(plaintext, key))
    return ciphertext, key

def otp_decrypt(ciphertext: bytes, key: bytes) -> bytes:
    return bytes(c ^ k for c, k in zip(ciphertext, key))

# Danger: reusing a key leaks plaintext XOR plaintext'
msg1 = b'ATTACK AT DAWN  '
msg2 = b'RETREAT TO BASE!'
c1, key = otp_encrypt(msg1)
c2 = bytes(p ^ k for p, k in zip(msg2, key))  # reusing key!
leak = bytes(a ^ b for a, b in zip(c1, c2))   # = msg1 XOR msg2
# An attacker with c1, c2 computes the same leak

If perfect secrecy is unachievable with short keys, what should we aim for instead? Shannon gave us the engineering answer in the same 1949 paper: two properties that a cipher should have to resist statistical attacks.

Confusion means that the relationship between the key and the ciphertext should be as complex and involved as possible. Each bit of the ciphertext should depend on many bits of the key in a highly non-linear, tangled way. This prevents an adversary from deducing key bits by examining ciphertext statistics. The mechanism that implements confusion in modern block ciphers is the substitution box (S-box) — a fixed, carefully chosen nonlinear lookup table.

Diffusion means that each bit of the plaintext should influence many bits of the ciphertext (ideally all of them), and conversely. Changing one plaintext bit should flip roughly half the ciphertext bits — the avalanche effect. This destroys statistical structure in the plaintext and spreads it across the ciphertext. The mechanism is a permutation or linear mixing layer.

Neither property alone is sufficient:

• Confusion without diffusion: a cipher based only on independent S-boxes (like a simple substitution cipher) can be attacked one symbol at a time. Statistical structure in the plaintext survives because symbols don't interact.
• Diffusion without diffusion (linear transformations alone): linear algebra attacks work. A linear cipher can be broken with enough plaintext-ciphertext pairs by solving a system of equations.

The key insight is that iterating confusion and diffusion in alternating rounds breaks down both properties simultaneously. After enough rounds, every output bit is a complex nonlinear function of every input bit and every key bit. This is the architecture of every modern block cipher: a substitution-permutation network (SPN).

# Illustrating diffusion with a toy 8-bit SPN round
# S-box: nonlinear lookup (confusion)
SBOX = [0xE,0x4,0xD,0x1,0x2,0xF,0xB,0x8,
        0x3,0xA,0x6,0xC,0x5,0x9,0x0,0x7]

def sub_nibble(n):
    return SBOX[n & 0xF]

# Bit permutation: spreads bits across positions (diffusion)
PERM = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]

def perm_bits(state16):
    out = 0
    for i, p in enumerate(PERM):
        bit = (state16 >> (15 - p)) & 1
        out |= (bit << (15 - i))
    return out

# One round: XOR with round key, substitute, permute
def round_fn(state, rkey):
    state ^= rkey
    # apply S-box to each nibble
    s = (sub_nibble(state >> 12) << 12 |
         sub_nibble((state >> 8) & 0xF) << 8 |
         sub_nibble((state >> 4) & 0xF) << 4 |
         sub_nibble(state & 0xF))
    return perm_bits(s)

A block cipher is a keyed function E: K × {0,1}^n → {0,1}^n where for every key k, the map E(k, ·) is a permutation (bijection) on n-bit blocks. The block size n (typically 128 bits for AES) is fixed. The key size (128, 192, or 256 bits for AES) determines the security level.

The formal security notion is that a block cipher should be a pseudorandom permutation (PRP). Informally, no efficient adversary should be able to distinguish E(k, ·) from a uniformly random permutation, even given oracle access to the encryption function (adaptive chosen-plaintext queries). This is formalized as the PRP game:

1. Challenger picks either a random permutation π or E(k, ·) for a random k.
2. Adversary queries the oracle on chosen plaintexts.
3. Adversary guesses which it got.

A block cipher is a secure PRP if the adversary's advantage (probability of guessing correctly minus 1/2) is negligible.

Why permutations? Decryption must be possible: E(k, ·) must have an inverse D(k, ·). Not every function is invertible; permutations are invertible by definition.

Key schedule: the raw key is expanded into multiple round keys via a key schedule algorithm. Each round gets its own derived round key, preventing the same key material from appearing in multiple rounds (which would create exploitable structure).

How rounds work: a block cipher runs the input through r rounds of confusion+diffusion+key-mixing. More rounds = more security but more latency. AES-128 uses 10 rounds. The choice of round count is the result of cryptanalytic analysis: how many rounds does it take before no known attack works faster than brute force?

# Abstract block cipher interface
from abc import ABC, abstractmethod

class BlockCipher(ABC):
    block_size: int  # in bytes
    key_size: int    # in bytes

    @abstractmethod
    def encrypt_block(self, key: bytes, plaintext: bytes) -> bytes:
        """Encrypt a single block. len(plaintext) == self.block_size"""
        ...

    @abstractmethod
    def decrypt_block(self, key: bytes, ciphertext: bytes) -> bytes:
        """Decrypt a single block. len(ciphertext) == self.block_size"""
        ...

# PRP distinguishing game (conceptual)
def prp_game(adversary, cipher, security_param):
    import os, random
    bit = random.randint(0, 1)          # 0 = random perm, 1 = cipher
    key = os.urandom(cipher.key_size)
    def oracle(pt):
        if bit == 1:
            return cipher.encrypt_block(key, pt)
        else:
            # truly random permutation (huge table in theory)
            return random_perm_eval(pt)
    guess = adversary(oracle, security_param)
    return guess == bit  # adversary wins if correct

AES (FIPS 197, 2001) is the result of a public competition run by NIST from 1997–2000. The winner, Rijndael (by Daemen and Rijmen), beat 14 other candidates on security, speed, and simplicity. It operates on 128-bit blocks with 128-, 192-, or 256-bit keys (giving 10, 12, or 14 rounds respectively).

State: AES treats the 128-bit block as a 4×4 matrix of bytes (the state).

Each of the 10 rounds (except the last) consists of four operations:

1. SubBytes — Apply a fixed 8-bit S-box to every byte independently. The AES S-box is constructed algebraically over GF(2^8): take the multiplicative inverse in the field (x → x^{-1}), then apply an affine transformation over GF(2). This algebraic structure guarantees desirable cryptographic properties (high nonlinearity, no fixed points, no 'anti-fixed points') and was deliberately constructed to resist differential and linear cryptanalysis. This is the confusion layer.

2. ShiftRows — Cyclically shift the bytes in each row of the state by 0, 1, 2, 3 positions respectively. This ensures bytes from different columns are mixed together in subsequent rounds. This is the beginning of diffusion.

3. MixColumns — Treat each column of the state as a 4-element vector over GF(2^8) and multiply by a fixed 4×4 matrix. This is a linear transformation that guarantees that each output byte depends on all four input bytes in that column. Combined with ShiftRows, after two rounds every output byte depends on every input byte. This is the primary diffusion layer. The matrix is chosen so that the transformation has a high branch number (= 5, meaning any nonzero input with w nonzero bytes produces an output with at least 5-w nonzero bytes).

4. AddRoundKey — XOR the state with the 128-bit round key derived from the key schedule. This is where the secret key enters. Without this step, the cipher would be a public permutation.

The final round omits MixColumns (this is a design choice that makes encryption and decryption structurally symmetric and simplifies hardware).

Key schedule: the original 128-bit key is expanded to 11 × 128-bit round keys using a combination of SubBytes, a rotation, and XOR with round constants (Rcon). The round constants prevent related-key symmetries.

Why is AES secure? The best known attack on full AES-128 is a biclique attack (Bogdanov et al., 2011) with complexity ~2^126.1 — essentially brute force. AES has no known practical weakness after 25+ years of cryptanalysis.

# AES using Python's cryptography library (production-quality)
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
import os

def aes_ecb_encrypt_block(key: bytes, block: bytes) -> bytes:
    """Encrypt a single 16-byte block with AES in ECB mode."""
    assert len(key) in (16, 24, 32), "Key must be 128/192/256 bits"
    assert len(block) == 16, "Block must be 128 bits"
    cipher = Cipher(algorithms.AES(key), modes.ECB())
    enc = cipher.encryptor()
    return enc.update(block) + enc.finalize()

# Demonstrating the avalanche effect:
key = os.urandom(16)
block_a = bytes(16)           # 16 zero bytes
block_b = bytes([1]) + bytes(15)  # flip one bit

ct_a = aes_ecb_encrypt_block(key, block_a)
ct_b = aes_ecb_encrypt_block(key, block_b)
diff = bin(int.from_bytes(ct_a, 'big') ^ int.from_bytes(ct_b, 'big')).count('1')
print(f"Bits flipped in ciphertext: {diff} / 128")  # Expect ~64

A block cipher only encrypts 128-bit blocks. Real messages are longer (and often not multiples of 128 bits). Modes of operation specify how to apply a block cipher to arbitrary-length messages. The choice of mode is critical: a wrong mode can completely destroy security even if the underlying cipher is perfect.

ECB (Electronic Codebook) — Encrypt each block independently: C_i = E(k, P_i). This is the naively obvious approach and it is catastrophically insecure for any structured data. Identical plaintext blocks produce identical ciphertext blocks, leaking all structural information. The famous ECB-encrypted Linux Tux penguin image (still recognizable after encryption) is the canonical demonstration. Never use ECB.

CBC (Cipher Block Chaining) — C_i = E(k, P_i XOR C_{i-1}), with C_0 = IV (a random initialization vector). Each ciphertext block depends on all previous plaintext blocks. This hides identical blocks. Security requires a random, unpredictable IV. Decryption: P_i = D(k, C_i) XOR C_{i-1}. CBC was the standard mode for years but has a subtle weakness: a padding oracle attack (POODLE, Lucky13) can decrypt ciphertext if the server reveals whether padding is valid. Also, CBC is inherently sequential (cannot be parallelized for encryption).

CTR (Counter Mode) — Generate a keystream: K_i = E(k, nonce || counter_i), then C_i = P_i XOR K_i. This turns a block cipher into a stream cipher. Key advantages: fully parallelizable, no padding required, encryption and decryption use the same operation, random access is possible. Security requires that the nonce is never reused with the same key (nonce reuse is as catastrophic as OTP key reuse: two ciphertexts XOR to give the XOR of two plaintexts).

GCM (Galois/Counter Mode) — CTR mode for encryption combined with a GHASH polynomial-evaluation MAC for authentication. This gives authenticated encryption with associated data (AEAD): the ciphertext is both confidential and integrity-protected. GCM is the standard choice for TLS 1.3 and modern protocols. It is not just confidential: if even one ciphertext bit is flipped, decryption fails with a detectable error.

Padding: CBC (and ECB) require the plaintext to be a multiple of the block size. PKCS#7 padding appends N bytes of value N (e.g., if 3 bytes are needed, append 0x03 0x03 0x03). Modes like CTR and GCM do not require padding.

# CBC vs CTR: same key, same plaintext, very different properties
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives import padding
import os

key = os.urandom(16)
plaintext = b'Attack at dawn! ' * 2  # identical blocks

# --- CBC ---
iv = os.urandom(16)
padder = padding.PKCS7(128).padder()
padded = padder.update(plaintext) + padder.finalize()
cipher = Cipher(algorithms.AES(key), modes.CBC(iv))
enc = cipher.encryptor()
cbc_ct = enc.update(padded) + enc.finalize()
print("CBC blocks same?", cbc_ct[:16] == cbc_ct[16:32])  # False — chaining hides it

# --- ECB (DON'T USE) ---
cipher_ecb = Cipher(algorithms.AES(key), modes.ECB())
enc_ecb = cipher_ecb.encryptor()
ecb_ct = enc_ecb.update(padded) + enc_ecb.finalize()
print("ECB blocks same?", ecb_ct[:16] == ecb_ct[16:32])  # True — disaster!

# --- CTR (preferred for confidentiality alone) ---
nonce = os.urandom(16)
cipher_ctr = Cipher(algorithms.AES(key), modes.CTR(nonce))
enc_ctr = cipher_ctr.encryptor()
ctr_ct = enc_ctr.update(plaintext) + enc_ctr.finalize()  # no padding needed

A common beginner mistake is thinking that encryption provides integrity. It does not — at least, not unless you use a mode designed for it. Consider CBC: an adversary who flips a bit in ciphertext block C_i causes predictable corruption in P_{i+1} (the decrypted output of C_{i+1} depends on C_i via XOR). This allows bit-flipping attacks on structured data without knowing the key.

The classic attack: a bank transfer message Amount: $1000.00. Flip the right bits in the ciphertext to change the decrypted amount to $9000.00. The decryption succeeds; the padding may even be valid. Without a MAC, the receiver cannot detect this.

Authenticated Encryption (AE) provides both confidentiality and integrity simultaneously. The canonical construction is Encrypt-then-MAC (EtM): first encrypt, then compute a MAC over the ciphertext, append the MAC tag. The receiver verifies the tag before attempting decryption. This is the cryptographically correct order: if the MAC fails, no decryption happens (preventing padding oracle attacks).

AEAD (Authenticated Encryption with Associated Data) also authenticates unencrypted header data (like a packet header) while only encrypting the payload. AES-GCM is the standard AEAD algorithm:

• Encryption: C = CTR_k(P, nonce), Tag = GHASH_H(A, C) XOR E(k, nonce||0)
• A = associated data (authenticated but not encrypted)
• Verification is done in constant time to prevent timing attacks

Using AES-GCM correctly requires: (1) a fresh random nonce for every encryption, (2) never reusing a (key, nonce) pair — nonce reuse in GCM is catastrophic, revealing the authentication key H.

# AES-GCM: authenticated encryption (preferred modern approach)
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
import os

key = AESGCM.generate_key(bit_length=128)
aesgcm = AESGCM(key)

nonce = os.urandom(12)  # GCM standard: 96-bit nonce
aad = b'packet-header-123'  # associated data: authenticated, not encrypted
plaintext = b'Transfer $1000 to Alice'

ciphertext_tag = aesgcm.encrypt(nonce, plaintext, aad)
print(f"Ciphertext+tag length: {len(ciphertext_tag)} bytes")  # len(pt) + 16

# Decryption + verification (raises InvalidTag if tampered)
try:
recovered = aesgcm.decrypt(nonce, ciphertext_tag, aad)
    print("Decrypted:", recovered)
except Exception:
    print("Tampered! Decryption rejected.")

# Demonstrate: flipping one ciphertext bit → authentication failure
tampered = bytearray(ciphertext_tag)
tampered[0] ^= 0x01
try:
    aesgcm.decrypt(nonce, bytes(tampered), aad)
except Exception as e:
    print("Bit flip detected:", e)

A stream cipher generates a pseudorandom keystream from a key (and usually a nonce) and XORs it with the plaintext one bit or byte at a time. Unlike a block cipher in CTR mode (which is actually a stream cipher!), a dedicated stream cipher is designed specifically for this purpose and may be significantly faster.

The security model: if the keystream K is truly random and as long as the message, this is the OTP (perfect secrecy). A stream cipher approximates this using a pseudorandom generator (PRG): a deterministic function that stretches a short seed into a long bitstring indistinguishable from random by any efficient algorithm.

RC4 (1987) — A historically important software stream cipher (used in WEP, early SSL). Its internal state is a permutation of 256 bytes. It is now broken: the first few bytes of the keystream are biased and correlate with the key, and WEP's IV reuse made attacks practical. RC4 is completely deprecated.

Salsa20 and ChaCha20 (Bernstein, 2005/2008) — The modern standard. ChaCha20 operates on a 512-bit state (4×4 matrix of 32-bit words), initialized with the 256-bit key, a 32-bit counter, and a 96-bit nonce. It applies 20 rounds of the quarter-round operation (add, XOR, rotate — all over 32-bit integers, no lookup tables, fast on CPUs without AES-NI). ChaCha20 is used in TLS 1.3 (paired with Poly1305 MAC), WireGuard VPN, and QUIC.

ChaCha20-Poly1305 is the AEAD construction: ChaCha20 for encryption, Poly1305 (a polynomial MAC over a prime field) for authentication. It is preferred over AES-GCM when hardware AES acceleration is unavailable (e.g., mobile devices, IoT) because it is constant-time by design and has no timing side-channel risk.

Security requirement: like CTR mode, a stream cipher's (key, nonce) pair must never be reused. Reuse gives the attacker the XOR of two plaintexts, which is often enough to reconstruct both.

# ChaCha20-Poly1305 AEAD (modern, recommended)
from cryptography.hazmat.primitives.ciphers.aead import ChaCha20Poly1305
import os

key = ChaCha20Poly1305.generate_key()   # 32 bytes = 256 bits
chacha = ChaCha20Poly1305(key)

nonce = os.urandom(12)  # 96-bit nonce, must be unique per message
plaintext = b'Hello from a resource-constrained device!'
aad = b'device-id:0xDEAD'

ciphertext = chacha.encrypt(nonce, plaintext, aad)
recovered  = chacha.decrypt(nonce, ciphertext, aad)
assert recovered == plaintext

# ChaCha20 quarter round (conceptual — shows add-rotate-XOR structure)
def quarter_round(a, b, c, d):
    MASK = 0xFFFFFFFF
    rot = lambda x, n: ((x << n) | (x >> (32 - n))) & MASK
    a = (a + b) & MASK; d ^= a; d = rot(d, 16)
    c = (c + d) & MASK; b ^= c; b = rot(b, 12)
    a = (a + b) & MASK; d ^= a; d = rot(d,  8)
    c = (c + d) & MASK; b ^= c; b = rot(b,  7)
    return a, b, c, d

Understanding attacks is as important as understanding constructions — cipher designers must internalize attacker capabilities to make the right trade-offs.

Brute-force / exhaustive key search: try every possible key. An n-bit key has 2^n possibilities. AES-128's 2^128 keyspace is computationally infeasible: 2^128 / (10^18 ops/sec × 3×10^7 sec/year) ≈ 10^{13} years. The birthday bound tells us brute force becomes practical at roughly 2^{n/2} queries when searching for collisions, but for key search it is 2^n.

Differential cryptanalysis (Biham-Shamir, 1990) — a chosen-plaintext attack that studies how differences in input pairs propagate through the cipher. If you know ΔP = P XOR P', you can sometimes predict the difference ΔC = E(k,P) XOR E(k,P') with non-trivial probability, leaking information about the last round key. AES's S-box and MixColumns were designed to minimize differential probabilities (each S-box has maximum differential probability 2^{-6}).

Linear cryptanalysis (Matsui, 1993) — a known-plaintext attack that finds linear approximations: equations of the form P_{i1} XOR P_{i2} XOR ... XOR C_{j1} XOR ... = K_{k1} XOR ... that hold with probability 1/2 + ε. With ~1/ε^2 plaintext-ciphertext pairs, the approximation reveals key bits. AES's nonlinear layer is designed to minimize the linear approximation bias.

Related-key attacks — assume the adversary can query E(k, ·) and E(k', ·) where k and k' have a known relationship (e.g., differ in one bit). AES-256 was found to be vulnerable to a related-key attack (Biryukov-Khovratovich, 2009) with 2^{99.5} complexity — still impractical, but theoretically concerning. This is why the key schedule matters.

Side-channel attacks — not against the mathematical structure but against the physical implementation: timing variations, power consumption, electromagnetic emissions, cache access patterns. Cache-timing attacks on table-based AES are real threats. Modern hardware (AES-NI x86 instructions) eliminates these by implementing AES in constant time with dedicated hardware.

How many rounds is enough? For AES-128 with 10 rounds, the best known attack on the full cipher is marginally better than brute force (~2^{126}). Attack complexity grows exponentially with rounds; going from 6 to 10 rounds makes the best attacks from 2^{44} to 2^{126}. This is the security margin AES designers built in.

# Illustrating differential analysis intuition on a toy 4-bit S-box
SBOX = [0xE,0x4,0xD,0x1,0x2,0xF,0xB,0x8,
        0x3,0xA,0x6,0xC,0x5,0x9,0x0,0x7]

# Difference distribution table: DDT[dx][dy] = # x s.t. SBOX[x]^SBOX[x^dx]=dy
def build_ddt(sbox):
    n = len(sbox)
    ddt = [[0]*n for _ in range(n)]
    for dx in range(n):
        for x in range(n):
            dy = sbox[x] ^ sbox[x ^ dx]
            ddt[dx][dy] += 1
    return ddt

ddt = build_ddt(SBOX)
max_diff = max(ddt[dx][dy] for dx in range(1,16) for dy in range(16))
print(f"Max differential probability: {max_diff}/16 = {max_diff/16:.3f}")
# Good S-boxes have low max; AES S-box has max 4/256 = 0.015625