Block Cipher Attacks, PRF Constructions, and the Ideal Cipher Model
Stub. Beyond DES/AES's basic design (already covered): exhaustive key search and the DES challenges, the 3E (triple-encryption) construction for strengthening a cipher against brute force, sophisticated attacks (algorithmic, side-channel, fault injection, and quantum exhaustive search), building a PRF from a PRG via the GGM tree construction, and the ideal cipher model with the Even-Mansour construction (and its security proof).
Corresponds to Chapter 4 (sections beyond DES/AES’s design, already covered in block-cipher-constructions). DES’s 56-bit key succumbed to exhaustive search, demonstrated publicly by the DES challenges; the 3E (triple-encryption) construction is the standard fix, strengthening effective key length without redesigning the cipher. Covers “sophisticated” attacks beyond brute force — algorithmic attacks exploiting a cipher’s internal structure, side-channel attacks (see hardware-security-and-side-channels for the general treatment), fault injection specifically against AES, and quantum exhaustive search (Grover’s algorithm, giving only a quadratic speedup, unlike Shor’s exponential speedup against RSA/DH). The GGM tree construction builds a full pseudorandom function from a length-doubling PRG, and the ideal cipher model (treating a block cipher as a literal random permutation, an idealization like the random oracle model) is where the elegantly simple Even-Mansour construction (XOR a key before and after a single public random permutation) is proven secure.
Outline (TODO — flesh out each)
- Exhaustive search on DES; the DES challenges
- The 3E (triple-encryption) construction
- Algorithmic attacks on block ciphers
- Fault injection attacks on AES
- Quantum exhaustive search attacks
- Constructing PRFs from PRGs — the (GGM) tree construction
- Variable-length tree construction
- The ideal cipher model
- The Even-Mansour block cipher and the EX construction
- Proof of the Even-Mansour and EX theorems