Lecture 5 - Combining Confidentiality and Integrity

eecs-388Sep 15, 2026

Ciphertext Malleability

many encryption methods are malleable - can transform a ciphertext into another ciphertext that decrypts to a related plaintext, without knowing the plaintext
- in CBC mode decryption, flipping bits in ciphertext block $i$ $i$ will:
  - completely corrupt decrypted block $i$
  - flip corresponding bits in decrypted block $i+1$
- in counter mode decryption, flipping bits anywhere in the ciphertext will flip corresponding bits in decrypted plaintext

two general approaches:
- generically compose encryption and MAC
- build “all-in-one” primitive that does both
syntax:
- $c := E_k(p)$
- $p / \text{"fail"} := D_k(c)$ (decryption can fail; analogous to Bob rejecting verifier)
security definition:
1. let $k$ be a secret key
2. toss a coin (in secret) to get bit $b$
3. if $b = 0$ $b = 0$ :
  - $G() := E_k(); H() := D^*_k()$ $G () := E_{k} (); H () := D_{k}^{*} ()$
    - - modified to return “fail” on previous $E()$ outputs if $b = 1$ :
  - $G() := \text{random bits}; H() := \text{"fail"}$
4. give Mallory $G()/H()$ oracles (Mallory gets to repeatedly query them)
5. Mallory guesses $b$ in polynomial time
we say AE is secure if Mallory can’t do meaningfully better than guessing

note that we use two keys here
- integrity: if one key leaks, the other is still strong
- generic composition: individual functions do not make any promises about what happens if you use the same key for both of them (individually, the functions may be strong; but together, they may leak some information about the key)

safest approach
only approach that guarantees that ciphertext has not been tampered with when we go to decrypt it
aka, for all other approaches, we must decrypt first then check if it’s valid, leaving us open to padding oracle attacks
- the oracle doesn’t necessarily need to explicitly return “MAC error” vs “Padding error”; something as simple as taking a few extra milliseconds is enough

integrity and encryption in a single primitive:
- $c,v := seal(k,p,[\text{associated data}])$ $c, v := se a l (k, p, [associated data])$
  - encrypts plaintext $p$ and returns ciphertext $c$ and verifier $v$ (“tag”)
- $p, \text{err} := unseal(k,c,v,\text{[associated data]})$ $p, err := u n se a l (k, c, v, [associated data])$
  - returns $p$ or an error if $v$ doesn’t match supplied $c$ and associated data
- optional associated data:
  - covered by verifier but not encrypted
  - useful for binding data to its context
examples:
- AES-GCM (Galois Counter Mode), hardware accelerated in recent CPUs
- ChaCha20-Poly1305, common on mobile

most widely used AEAD cipher mode
non-generic composition of AES in CTR mode for encryption and a special MAC based on polynomials over finite (Galois) fields
note: GCM violates principle of key separation
warning: can construct GCM ciphertexts that decrypt under many keys (differently, but without error)
warning: GCM nonce reuse is catastrophic; encrypting two ciphertexts with the same (k, nonce) leaks the plaintext and the MAC key

choose $|k|$ to resist brute force attacks, even as computers becomef aster
for ciphers/PRG keys:
- want to resist exhaustive search for $k$
- 128 bits considered “classically” safe
- for quantum-resistance, use 256 bits
for hash functions:
- want collision resistance (CR)
- need 2n bits of output for n bits of CR, due to “birthday” attacks
estimating what’s feasible to compute:
- CPU mining: ~ $10^8$ SHA-256/s
- GPU mining: ~ $10^{11}$ SHA-256/s
- ASIC mining: ~ $10^{14}$ SHA-256/s
- CPU mining: ~ $10^{21}$ SHA-256/s
birthday attack:
- generate random values, look for collision
- requires $2^{|k|/2}$ time, $2^{|k|/2}$ space
- for 128-bit output, takes $2^{64}$ steps; doable