Cryptography
Attacks on Symmetric Ciphers
DES was designed in 1977 with differential cryptanalysis resistance built in - the S-boxes were specifically chosen to minimize differential probability. The NSA knew about the attack 13 years before Biham and Shamir publicly discovered it. Understanding symmetric attacks means understanding why every AES design decision (S-box choice, MixColumns, ShiftRows) was made to resist these three fundamental analysis techniques.
- **DES S-box design**: S-boxes were optimized for differential resistance in 1977. IBM/NSA knew the attack but kept it classified for national security reasons.
- **WEP broken in minutes (2001)**: Fluhrer-Mantin-Shamir attack on RC4 related keys via IV concatenation. 200,000 packets sufficient. WEP completely deprecated by 2004.
- **NIST AES competition (1997-2000)**: all 15 submitted ciphers were evaluated for differential, linear, and integral resistance. Rijndael won partly due to the Wide Trail Strategy providing provable bounds.
- **ASCON (NIST lightweight standard 2023)**: designed with integral and differential resistance for IoT. 128-bit security with formal analysis bounds.
Differential Cryptanalysis
Differential cryptanalysis (Biham & Shamir, 1990) exploits non-random behavior in how differences propagate through a cipher. By choosing pairs of plaintexts with specific XOR differences, an attacker can determine key bits by analyzing difference patterns in ciphertexts.
DES was designed in 1977 with differential cryptanalysis resistance built in - the S-boxes were specifically chosen to minimize differential probability. This was only revealed publicly in 1990 when Biham and Shamir independently discovered the attack.
What property must a cipher S-box have to resist differential cryptanalysis?
Linear Cryptanalysis
Linear cryptanalysis (Matsui, 1993) finds linear approximations between plaintext bits, ciphertext bits, and key bits. A linear approximation holds with probability 1/2 + epsilon. With enough known plaintexts, statistical analysis recovers key bits.
Matsui used linear cryptanalysis in 1994 to demonstrate a practical attack on full 16-round DES using 2^43 known plaintexts - the first experimental cryptanalysis of DES. AES S-boxes (Rijndael S-box) achieve optimal linear approximation resistance.
What property of AES S-boxes makes it resistant to linear cryptanalysis?
Related-Key Attacks
Related-key attacks assume the attacker can observe cipher behavior under multiple related keys (e.g., keys differing in a few known bits). While unrealistic for most applications, related-key attacks break AES-256 faster than brute force and expose weaknesses in key schedule design.
WEP (Wired Equivalent Privacy) was broken by a related-key attack: the 24-bit IV is concatenated to the RC4 key, creating millions of related keys per day. The Fluhrer-Mantin-Shamir attack (2001) recovers the WEP key from ~200,000 packets - feasible in minutes with modern hardware.
Why is AES-256 theoretically weaker than AES-128 against related-key attacks?
Integral Attacks and the Square Attack
Integral cryptanalysis (Knudsen & Wagner, 2002) exploits the algebraic structure of block ciphers. An integral distinguisher tracks the sum of all ciphertext values when all plaintext values in some dimension are enumerated. The XOR of all outputs is predictable for reduced-round ciphers.
The original AES competition submission (Rijndael) was the first cipher explicitly designed with integral attack resistance. The Wide Trail Strategy (Daemen & Rijmen) provides formal bounds on differential and linear characteristics across multiple rounds.
What makes an integral distinguisher effective against reduced-round ciphers?
Key Ideas
- **Differential cryptanalysis**: input difference pairs -> ciphertext difference statistics. S-box max differential probability must be minimized.
- **Linear cryptanalysis**: plaintext-ciphertext-key linear approximation with bias epsilon. Data: 1/epsilon^2. AES S-box achieves optimal 2^-3 max bias.
- **Related-key attacks**: attacker observes cipher under related keys. Breaks AES-256 in 2^99.5; impractical in standard deployment but relevant for WEP-style IV designs.
- **Integral attacks**: balanced sets maintain XOR structure through few rounds. Effective on reduced-round ciphers; full AES resists via Wide Trail Strategy.
Related Topics
Symmetric attacks shaped the design of every modern cipher:
- Security Models — Differential and linear attacks operate in the CPA model: chosen plaintexts with known relationships.
- Side-Channel Attacks — Beyond mathematical attacks, implementation attacks (timing, power) break ciphers not attackable mathematically.
- Asymmetric Attacks — Algebraic attacks on lattices and RSA share structural analysis principles with integral attacks.
Вопросы для размышления
- AES-128 is resistant to differential and linear cryptanalysis with a safety margin of 4 rounds (128-bit security with 10 rounds; attacks stop at 6-7). What does this safety margin provide?
- WEP used RC4 with IV concatenation. Design an improved key derivation that would have prevented the Fluhrer-Mantin-Shamir attack.
- The integral attack exploits XOR-balanced sets. Why does this technique generalize to any cipher with a linear layer (like AES MixColumns)?