Def: A δ-set (or Λ-set) is a set of 256 messages where
The 1st bytes take all possible values 00, …, ff (variable byte, denoted ★)
All other bytes do not change among different messages (constant bytes)
Consider any 2 (consecutive) rounds
3 of 9
Before round 1: 1st byte variable
After round 1: all bytes in 1st column variable
After round 2: all bytes variable
4 of 9
Square attack 1
Attack on 3-round AES
Chosen message attack: obtain 256 (message, ciphertext) pairs for messages in a δ-set
5 of 9
6 of 9
7 of 9
Structural property of AES 2
Structural property 1 says: There are 256 2nd round results for messages in a δ-set. Consider the 1st (or any position) bytes of them. They cover 00, …, ff
Not the case anymore in 3rd (normal) round result (disrupted by MixColumns in 3rd round)
New structural property: There are 256 3rd round results for messages in a δ-set. Consider the 1st (or any position) bytes of them. They XOR to 00
8 of 9
Square attack 2
Attack on 4-round AES
Chosen message attack: obtain 256 (message, ciphertext) pairs for messages in a δ-set (same setting as square attack 1)
Attack identical to square attack 1, except: In step 1, check if the 256 bytes XOR to 00, rather than cover 00, …, ff
False alarm rate higher
To rule out false alarm with very high probability, need 2 δ-sets
Can (somehow) extend to attacking 5-round AES or even further
9 of 9
Homework
(a) Prove “structural property of AES 2” (slide 7). (b) Before or after the proof, give a high-level, 1-3 sentence description of the idea behind the proof
Think about it on your own
No matter whether you can do it yourself or not, read pp.55-56 of the book which give a proof
REWRITE IT IN YOUR OWN WORDS AND ADD THE INTUITION
Submit a paper copy of your solution on 11/02 (Mon)