Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

CSCI 662—Foundations of Cryptography Structural Attacks on Block Ciphers Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

Attack on 1-Round PRESENT

• A known plaintext attack
• Given a number of plaintext-ciphertext pairs encrypted with the same (unknown) key . . .
• Find the two round subkeys
• If Harry knows the subkeys, he can encrypt or decrypt anything without needing the actual key
• Or, Harry can deduce the actual key from the subkeys

• Oracle class to generate random known plaintext-ciphertext pairs
```\$ java KnownPtOracle "Present80(1)" a690e1d67c9f52c99423 142857 10
Oracle internal settings: (shhh!)
Key = a690e1d67c9f52c99423
i   Subkey[i]
0   a690e1d67c9f52c9
1   b28474d21c3acf93
Plaintext -- Ciphertext
2c5541edfb958a90 -- fdf518abd6a7054f
ff068d6c588d90f5 -- c9c6116f65accef1
595a392dd38a4dea -- a3054c78c2fdd33a
af3b76afa40e434f -- 4da59b6e75d9e94d
df8f27cc70a21cc0 -- 772f9f01490b6caf
806557ab19ee2174 -- fc2af7ebf9bfccae
08923557ff099f3b -- 16f4cdff86cd0057
1b3987c875e7437c -- 0e66063e606aacaf
50128d5df3240d7a -- fbb760d2e6ffed12
```

• Consider the rightmost S-box
• Its inputs are associated with plaintext and round 0 subkey bits (3, 2, 1, 0)
• Its outputs are associated with ciphertext and round 1 subkey bits (48, 32, 16, 0)

• The attack on the rightmost S-box
• Get a known plaintext-ciphertext from the oracle
• Guess a value for the subkey 0 bits, compute the associated value for the subkey 1 bits
• subkey 1 = S[plaintext xor subkey 0] xor ciphertext
• Repeat for each possible value for subkey 0
• At this point all 16 guesses for subkey 0 are viable
• Get another known plaintext-ciphertext from the oracle
• For each guess, check whether the plaintext bits map through to the ciphertext bits
• Does (S[plaintext xor subkey 0] xor subkey 1) = ciphertext?
• If not, eliminate the guess
• Repeat with more known plaintexts-ciphertexts from the oracle until only one guess is left standing

• The attack on the whole cipher
• Repeat the above in parallel for each S-box

• Attack program
```\$ java Attack01 a690e1d67c9f52c99423 142857
Oracle internal settings: (shhh!)
Key = a690e1d67c9f52c99423
i   Subkey[i]
0   a690e1d67c9f52c9
1   b28474d21c3acf93
1. pt = 2c5541edfb958a90, ct = fdf518abd6a7054f, viable subkey guesses:
S-box 0: 0/3 1/a 2/9 3/4 4/6 5/f 6/5 7/2 8/c 9/1 a/0 b/7 c/b d/8 e/e f/d
S-box 1: 0/9 1/4 2/f 3/8 4/0 5/3 6/5 7/6 8/2 9/b a/c b/1 c/7 d/e e/a f/d
S-box 2: 0/4 1/3 2/8 3/5 4/a 5/9 6/f 7/c 8/d 9/0 a/7 b/e c/1 d/6 e/2 f/b
S-box 3: 0/6 1/b 2/a 3/d 4/1 5/2 6/4 7/7 8/9 9/0 a/3 b/e c/c d/5 e/f f/8
S-box 4: 0/8 1/1 2/5 3/2 4/d 5/4 6/3 7/e 8/f 9/c a/a b/9 c/6 d/b e/0 f/7
S-box 5: 0/0 1/d 2/6 3/1 4/9 5/a 6/c 7/f 8/b 9/2 a/5 b/8 c/e d/7 e/3 f/4
S-box 6: 0/1 1/6 2/7 3/a 4/b 5/8 6/e 7/d 8/2 9/f a/c b/5 c/4 d/3 e/9 f/0
S-box 7: 0/c 1/f 2/9 3/a 4/6 5/1 6/0 7/d 8/3 9/4 a/e b/7 c/5 d/8 e/b f/2
S-box 8: 0/e 1/d 2/b 3/8 4/7 5/a 6/1 7/6 8/9 9/0 a/4 b/3 c/c d/5 e/2 f/f
S-box 9: 0/3 1/0 2/6 3/5 4/d 5/a 6/1 7/c 8/8 9/f a/b b/2 c/4 d/9 e/e f/7
S-box 10: 0/e 1/7 2/0 3/d 4/b 5/2 6/6 7/1 8/5 9/8 a/3 b/4 c/c d/f e/9 f/a
S-box 11: 0/5 1/c 2/6 3/1 4/0 5/9 6/a 7/7 8/8 9/b a/d b/e c/f d/2 e/3 f/4
S-box 12: 0/e 1/7 2/3 3/4 4/b 5/2 6/5 7/8 8/9 9/a a/c b/f c/0 d/d e/6 f/1
S-box 13: 0/8 1/1 2/5 3/2 4/d 5/4 6/3 7/e 8/f 9/c a/a b/9 c/6 d/b e/0 f/7
S-box 14: 0/e 1/d 2/b 3/8 4/9 5/4 6/5 7/2 8/3 9/a a/0 b/7 c/6 d/f e/c f/1
S-box 15: 0/c 1/1 2/6 3/f 4/0 5/7 6/3 7/a 8/5 9/2 a/9 b/4 c/b d/8 e/e f/d
2. pt = ff068d6c588d90f5, ct = c9c6116f65accef1, viable subkey guesses:
S-box 0: c/b 9/1
S-box 1: c/7 a/c 5/3 3/8
S-box 2: 9/0 8/d 2/8 3/5
S-box 3: 7/7 6/4 5/2 4/1
S-box 4: f/7 7/e
S-box 5: d/7 c/e 9/2 8/b
S-box 6: f/0 c/4
S-box 7: d/8 c/5 7/d 6/0
S-box 8: b/3 a/4 7/6 6/1
S-box 9: d/9 5/a
S-box 10: d/f 1/7
S-box 11: f/4 e/3 2/6 3/1
S-box 12: 0/e 3/4
S-box 13: c/6 9/c
S-box 14: 6/5 5/4
S-box 15: a/9 7/a
3. pt = 595a392dd38a4dea, ct = a3054c78c2fdd33a, viable subkey guesses:
S-box 0: 9/1
S-box 1: c/7
S-box 2: 2/8
S-box 3: 5/2
S-box 4: f/7
S-box 5: d/7 c/e 9/2 8/b
S-box 6: c/4
S-box 7: 7/d
S-box 8: b/3 a/4 7/6 6/1
S-box 9: d/9
S-box 10: 1/7
S-box 11: e/3
S-box 12: 0/e
S-box 13: c/6 9/c
S-box 14: 6/5
S-box 15: a/9
4. pt = af3b76afa40e434f, ct = 4da59b6e75d9e94d, viable subkey guesses:
S-box 0: 9/1
S-box 1: c/7
S-box 2: 2/8
S-box 3: 5/2
S-box 4: f/7
S-box 5: 9/2
S-box 6: c/4
S-box 7: 7/d
S-box 8: 6/1
S-box 9: d/9
S-box 10: 1/7
S-box 11: e/3
S-box 12: 0/e
S-box 13: 9/c
S-box 14: 6/5
S-box 15: a/9
Attack results:
i   Subkey[i]
0   a690e1d67c9f52c9
1   b28474d21c3acf93
```

• We were able to recover the subkeys with just 4 encryptions (oracle queries)
• This is way fewer than the 280 encryptions required for a brute force key search

• For one-round PRESENT, this is an easy attack

Meet-In-The-Middle Attack on 2-Round PRESENT

• Point A is the middle

• Known plaintext attack involving round-1 S-boxes 0-3 and round-2 S-boxes 0, 4, 8, and 12
• Get a known plaintext-ciphertext from the oracle
• Guess a value for the sixteen subkey 0 bits, . . .
• Compute the outputs for round-1 S-boxes 0-3, and . . .
• Carry out the single-round attack for round-2 S-boxes 0, 4, 8, and 12
• Repeat for each possible value for subkey 0
• At this point all 65536 guesses for subkey 0 are viable
• Get another known plaintext-ciphertext from the oracle
• For each subkey 0 guess, . . .
• Compute the outputs for round-1 S-boxes 0-3, and . . .
• Carry out the single-round attack for round-2 S-boxes 0, 4, 8, and 12
• This eliminates non-viable subkey 0 guesses
• Repeat with more known plaintexts-ciphertexts from the oracle until only one subkey 0 guess is left standing

• The attack on the whole cipher
• Repeat the above in parallel for each group of four round-1 S-boxes

• Attack program
```\$ java MitmAttack01 a690e1d67c9f52c99423 142857
Oracle internal settings: (shhh!)
Key = a690e1d67c9f52c99423
i   Subkey[i]
0   a690e1d67c9f52c9
1   b28474d21c3acf93
1. pt = 2c5541edfb958a90, ct = ae317ce8687b0d34
Number of viable first / second round subkey guesses:
S-boxes 0-3: 65536 / 1048576 1048576 1048576 1048576
S-boxes 4-7: 65536 / 1048576 1048576 1048576 1048576
S-boxes 8-11: 65536 / 1048576 1048576 1048576 1048576
S-boxes 12-15: 65536 / 1048576 1048576 1048576 1048576
2. pt = ff068d6c588d90f5, ct = ffebda69dd384fa3
Number of viable first / second round subkey guesses:
S-boxes 0-3: 3584 / 7168 7680 7168 7168
S-boxes 4-7: 64 / 128 1024 256 256
S-boxes 8-11: 5376 / 17984 10752 12544 11520
S-boxes 12-15: 448 / 1056 928 7168 1152
3. pt = 595a392dd38a4dea, ct = 474c90894fe58899
Number of viable first / second round subkey guesses:
S-boxes 0-3: 1 / 1 1 1 2
S-boxes 4-7: 8 / 8 24 32 8
S-boxes 8-11: 8 / 8 8 8 8
S-boxes 12-15: 2 / 2 2 8 2
4. pt = af3b76afa40e434f, ct = 03dd5ee5e4afa22d
Number of viable first / second round subkey guesses:
S-boxes 0-3: 1 / 1 1 1 2
S-boxes 4-7: 1 / 1 1 4 1
S-boxes 8-11: 1 / 1 1 1 1
S-boxes 12-15: 1 / 1 1 1 1
5. pt = df8f27cc70a21cc0, ct = 67b1dd36b2d18204
Number of viable first / second round subkey guesses:
S-boxes 0-3: 1 / 1 1 1 1
S-boxes 4-7: 1 / 1 1 1 1
S-boxes 8-11: 1 / 1 1 1 1
S-boxes 12-15: 1 / 1 1 1 1
Attack results:
i   Subkey[i]
0   a690e1d67c9f52c9
1   b28474d21c3acf93
```

• We were able to recover the subkeys with just 5 encryptions (oracle queries)
• This is way fewer than the 280 encryptions required for a brute force key search

• For two-round PRESENT, this is an easy attack

• The meet-in-the-middle attack can be extended to more rounds
• But then we have to guess many more subkey bits
• For PRESENT, the attack becomes impractical with 3 or more rounds
• This is due to PRESENT's fast diffusion from the bit permutation layer

• The meet-in-the-middle attack may be practical for more rounds for other block ciphers with slower diffusion

Linear Approximation of the S-Box

• Truth table for the S-box, inputs X1 X2 X3 X4, outputs Y1 Y2 Y3 Y4
```X1X2X3X4 | Y1Y2Y3Y4
---------+----------
0 0 0 0 |  1 1 0 0
0 0 0 1 |  0 1 0 1
0 0 1 0 |  0 1 1 0
0 0 1 1 |  1 0 1 1
0 1 0 0 |  1 0 0 1
0 1 0 1 |  0 0 0 0
0 1 1 0 |  1 0 1 0
0 1 1 1 |  1 1 0 1
1 0 0 0 |  0 0 1 1
1 0 0 1 |  1 1 1 0
1 0 1 0 |  1 1 1 1
1 0 1 1 |  1 0 0 0
1 1 0 0 |  0 1 0 0
1 1 0 1 |  0 1 1 1
1 1 1 0 |  0 0 0 1
1 1 1 1 |  0 0 1 0
```

• Consider a linear approximation involving certain input and output bits
• For example, X3 + X4 = Y2 + Y3
• + is modulo 2 addition, i.e., xor
• Equivalently, X3 + X4 + Y2 + Y3 = 0
• X3 + X4 is the input sum
• Y2 + Y3 is the output sum

• For all possible inputs, count the number of times the input sum equals the output sum
```X1X2X3X4 | Y1Y2Y3Y4 | X3+X4 | Y2+Y3 | Equal?
---------+----------+-------+-------+-------
0 0 0 0 |  1 1 0 0 |   0   |   1   |
0 0 0 1 |  0 1 0 1 |   1   |   1   |  Yes
0 0 1 0 |  0 1 1 0 |   1   |   0   |
0 0 1 1 |  1 0 1 1 |   0   |   1   |
0 1 0 0 |  1 0 0 1 |   0   |   0   |  Yes
0 1 0 1 |  0 0 0 0 |   1   |   0   |
0 1 1 0 |  1 0 1 0 |   1   |   1   |  Yes
0 1 1 1 |  1 1 0 1 |   0   |   1   |
1 0 0 0 |  0 0 1 1 |   0   |   1   |
1 0 0 1 |  1 1 1 0 |   1   |   0   |
1 0 1 0 |  1 1 1 1 |   1   |   0   |
1 0 1 1 |  1 0 0 0 |   0   |   0   |  Yes
1 1 0 0 |  0 1 0 0 |   0   |   1   |
1 1 0 1 |  0 1 1 1 |   1   |   0   |
1 1 1 0 |  0 0 0 1 |   1   |   0   |
1 1 1 1 |  0 0 1 0 |   0   |   1   |
```

• For a random input, the probability that X3 + X4 + Y2 + Y3 = 0 is p = 4/16

• The probability bias ε, or just bias, of this linear approximation is ε = p − 1/2 = −4/16

• If ε = 0 (p = 1/2), then the linear approximation is a bad approximation of the S-box

• If ε = 1/2 (p = 1), then the linear approximation is a perfect approximation of the S-box

• If ε = −1/2 (p = 0), then the linear approximation is also a perfect approximation of the S-box
• It's actually a perfect affine approximation: X3 + X4 + Y2 + Y3 = 1

• If ε ≠ 0 (p < 1/2 or p > 1/2), then the linear approximation is a good approximation of the S-box
• The higher the magnitude of the bias |ε|, the better the approximation
• The linear attack is based on high-bias linear approximations

• We can compute the bias of every possible linear approximation of the PRESENT S-box
• "Input sum" row label indicates which inputs are included in the input sum
• E.g., input sum = 3 hex = 0011 binary → X1 not included, X2 not included, X3 included, X4 included → X3 + X4
• "Output sum" column label indicates which outputs are included in the output sum
• E.g., output sum = 6 hex = 0110 binary → Y1 not included, Y2 included, Y3 included, Y4 not included → Y2 + Y3
• Table lists biases for each possible input sum and output sum
• Zero biases omitted
• Denominator of /16 omitted
```\$ java PresentLinearApprox
Input   Output Sum
Sum   0   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
0  +8   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
1   .   .   .   .   .  -4   .  -4   .   .   .   .   .  -4   .  +4
2   .   .  +2  +2  -2  -2   .   .  +2  -2   .  +4   .  +4  -2  +2
3   .   .  +2  +2  +2  -2  -4   .  -2  +2  -4   .   .   .  -2  -2
4   .   .  -2  +2  -2  -2   .  +4  -2  -2   .  -4   .   .  -2  +2
5   .   .  -2  +2  -2  +2   .   .  +2  +2  -4   .  +4   .  +2  +2
6   .   .   .  -4   .   .  -4   .   .  -4   .   .  +4   .   .   .
7   .   .   .  +4  +4   .   .   .   .  -4   .   .   .   .  +4   .
8   .   .  +2  -2   .   .  -2  +2  -2  +2   .   .  -2  +2  +4  +4
9   .  +4  -2  -2   .   .  +2  -2  -2  -2  -4   .  -2  +2   .   .
A   .   .  +4   .  +2  +2  +2  -2   .   .   .  -4  +2  +2  -2  +2
B   .  -4   .   .  -2  -2  +2  -2  -4   .   .   .  +2  +2  +2  -2
C   .   .   .   .  -2  -2  -2  -2  +4   .   .  -4  -2  +2  +2  -2
D   .  +4  +4   .  -2  -2  +2  +2   .   .   .   .  +2  -2  +2  -2
E   .   .  +2  +2  -4  +4  -2  -2  -2  -2   .   .  -2  -2   .   .
F   .  +4  -2  +2   .   .  -2  -2  -2  +2  +4   .  +2  +2   .   .
```

Sums of Linear Approximations

• Consider a linear approximation for some S-box
• Bias = ε1
• Probability[insum1 + outsum1 = 0] = p1 = 1/2 + ε1
• Probability[insum1 + outsum1 = 1] = 1 − p1 = 1/2 − ε1

• Consider a linear approximation for some other S-box
• Bias = ε2
• Probability[insum2 + outsum2 = 0] = p2 = 1/2 + ε2
• Probability[insum2 + outsum2 = 1] = 1 − p2 = 1/2 − ε2

• What is the bias of the sum of the two linear approximations?
• Assuming the linear approximation probabilities are independent

• Probability[insum1 + outsum1 + insum2 + outsum2 = 0]
= Probability[(insum1 + outsum1 = 0 and insum2 + outsum2 = 0) or (insum1 + outsum1 = 1 and insum2 + outsum2 = 1)]
= p1p2 + (1 − p1)(1 − p2)
= (1/2 + ε1)(1/2 + ε2) + (1/2 − ε1)(1/2 − ε2)
= 1/2 + 2ε1ε2

• Therefore, bias[insum1 + outsum1 + insum2 + outsum2 = 0]
= 1/2 + 2ε1ε2 − 1/2
= 2ε1ε2

• Piling-Up Lemma
• Generalization of the above
• The bias of the sum of n linear approximations is 2n−1ε1ε2⋅⋅⋅εn

Linear Attack on Two-Round PRESENT

• Consider the high-bias linear approximation X2 + X3 + Y3 + Y4 = 0
• Input sum label = 6, output sum label = 3, ε = −4/16

• Consider the following pathway involving that linear approximation in round 1
• The pathway hits round 1 rightmost S-box
• Inputs X2 and X3 come from plaintext bits 2 and 1
• Outputs Y3 and Y4 go to round 2 input bits 16 and 0
• The pathway hits round 1 second rightmost S-box
• Inputs X2 and X3 come from plaintext bits 6 and 5
• Outputs Y3 and Y4 go to round 2 input bits 17 and 1
• The pathway hits round 2 rightmost S-box
• Its outputs go to ciphertext bits (48, 32, 16, 0)
• The pathway hits round 2 fourth-rightmost S-box
• Its outputs go to ciphertext bits (52, 36, 20, 4)

• We approximate each of the two round 1 S-boxes with the linear approximation X2 + X3 + Y3 + Y4 = 0
• The bias of each is ε1 = ε2 = −4/16 = −1/4
• The bias of the sum of both is ε = 2ε1ε2 = +1/8

• To this linear approximation we add round 0 subkey bits (6, 5, 2, 1) and round 1 subkey bits (17, 16, 1, 0)
• These subkey bits are unknown
• However, their effect is to add a total of either 0 or 1 to the linear approximation

• If we add 0 to the linear approximation, the bias remains +1/8

• If we add 1 to the linear approximation:
• We get linapprox + 1 = 0
• Equivalently, linapprox = 1
• Probability[linapprox = 1] = 1 − Probability[linapprox = 0] = 1 − p = 1 − (ε + 1/2) = 3/8
• Therefore, the bias of [linapprox = 1] is 3/8 − 1/2 = −1/8

• Bottom line, the bias of [linapprox = 0] at the round 2 input is ±1/8
• No matter what the round 0 and 1 subkeys are

• We exploit this nonzero bias to find selected bits of the round 2 subkey

• The linear attack
• Take a known plaintext P and the corresponding ciphertext C
• Compute sum of active plaintext bits (6, 5, 2, 1)
• Guess a value for the round 2 subkey bits (48, 32, 16, 0)
• Compute round 2 first S-box outputs from C and subkey guess
• Compute round 2 first S-box inputs from outputs (inverse S-box)
• Accumulate round 2 first S-box active inputs into sum
• Guess a value for the round 2 subkey bits (52, 36, 20, 4)
• Compute round 2 second S-box outputs from C and subkey guess
• Compute round 2 second S-box inputs from outputs (inverse S-box)
• Accumulate round 2 second S-box active inputs into sum
• Check whether sum = 0
• If so, increment a counter associated with these subkey guesses
• Repeat all the above for every possible combination of subkey guesses (256 possibilities)
• Repeat all the above for every known plaintext-ciphertext pair
• For each subkey guess, the measured bias is (counter)/(# of pairs) − 1/2
• If the subkey guess is wrong, then there is a 50-50% chance that linapprox = 0, and the measured bias will be close to 0
• If the subkey guess is correct, then linapprox = 0 with bias ±1/8, and the measured bias will be far from 0
• So whichever counter "sticks out" tells the correct round 2 subkey bits (52, 48, 36, 32, 20, 16, 4, 0)

• Attack program
```\$ java LinearAttack01 2 a690e1d67c9f52c99423 142857 1000 1,2,5,6 0,16,32,48 3 4,20,36,52 3 > out04.txt
Oracle internal settings: (shhh!)
Key = a690e1d67c9f52c99423
i   Subkey[i]
0   a690e1d67c9f52c9
1   b28474d21c3acf93
Final round subkey bits
48 32 16  0 52 36 20  4       Count        Bias
1  0  0  0  0  1  0  1         405   -0.095000
1  0  0  0  0  1  0  0         416   -0.084000
1  0  1  1  0  1  1  0         428   -0.072000
. . .
0  1  1  1  0  1  1  0         565    0.065000
1  0  0  0  1  0  0  1         590    0.090000
1  0  0  0  0  1  1  0         645    0.145000    <-- (correct subkey)
```

• Here's another pathway involving the same linear approximation

```\$ java LinearAttack01 2 a690e1d67c9f52c99423 142857 1000 17,18,21,22 1,17,33,49 3 5,21,37,53 3 > out05.txt
Oracle internal settings: (shhh!)
Key = a690e1d67c9f52c99423
i   Subkey[i]
0   a690e1d67c9f52c9
1   b28474d21c3acf93
Final round subkey bits
49 33 17  1 53 37 21  5       Count        Bias
1  0  1  1  0  0  0  0         363   -0.137000    <-- (correct subkey)
1  0  1  1  1  1  1  1         421   -0.079000
0  1  0  0  0  0  0  0         422   -0.078000
. . .
1  0  1  1  0  0  1  1         582    0.082000
1  0  1  1  1  1  0  0         584    0.084000
0  1  1  1  0  0  0  0         589    0.089000
```

• The attack on the whole cipher
• Repeat the above for other high-bias pathways that involve the remaining round 2 subkey bits
• Eventually we learn the entire round 2 subkey
• Now we can decrypt any ciphertext back through round 2 to the output of round 1
• This reduces the problem to one we know how to solve, namely, the attack on one-round PRESENT

• We were able to recover the round 2 subkey with far fewer encryptions than the 280 required for a brute force key search
• We did need more known plaintexts than the attack on one-round PRESENT, e.g. 1,000 plaintexts
• To ensure the correct subkey "signal" rises above the incorrect subkey "noise"

• For two-round PRESENT, this is still a fairly easy attack

Linear Attack on Three-Round PRESENT

• Here's a pathway that involves:
• Two round 1 linear approximations X1 + X3 + Y3 = 0, ε = +4/16
• Two round 2 linear approximations X3 + Y3 + Y4 = 0, ε = +2/16
• Overall bias = 24−1(+4/16)(+4/16)(+2/16)(+2/16) = +1/128
• Ciphertext output bits (53, 49, 37, 33, 21, 17, 5, 1)
```\$ java LinearAttack01 3 a690e1d67c9f52c99423 142857 100000 5,7,21,23 1,17,33,49 3 5,21,37,53 3 > out06.txt
Oracle internal settings: (shhh!)
Key = a690e1d67c9f52c99423
i   Subkey[i]
0   a690e1d67c9f52c9
1   b28474d21c3acf93
3   4b3e55a966ca11d2
Final round subkey bits
49 33 17  1 53 37 21  5       Count        Bias
1  0  1  1  1  1  0  0       49320   -0.006800    <-- (correct subkey)
1  1  0  0  1  1  0  0       49378   -0.006220
0  0  1  1  1  1  0  0       49389   -0.006110
. . .
0  0  1  0  1  1  0  0       50508    0.005080
1  0  0  1  1  1  0  0       50581    0.005810
1  0  0  0  1  1  0  0       50923    0.009230
```

• After we recover the complete round 3 subkey, we use the previous attacks on rounds 1 and 2

• We were still able to recover the round 3 subkey with fewer encryptions than 280
• But we needed still more known plaintexts than the attack on two-round PRESENT, e.g. 100,000 plaintexts
• Because the three-round pathway's bias is smaller, more trials are needed to raise the signal above the noise

Linear Attack on More Rounds

• As we scale the linear attack up to more rounds . . .

• More S-boxes get involved
• Because the pathway goes through more rounds (S-boxes)
• Because the permutation layer scatters each S-box's output across the state

• The bias of the overall linear approximation, ε, becomes smaller
• Because of more terms in the Piling-Up Lemma

• It takes more known plaintext-ciphertext pairs for the correct subkey signal to rise above the noise

• Eventually, we reach a point where more than 280 pairs are needed
• PRESENT with that many rounds or more is immune to a linear attack

• More precisely, the number of pairs needed is about 1/ε2 (see Matsui's paper)

• Complexity of a linear attack on the full PRESENT (see PRESENT paper)
• The maximum bias of any 4-round linear approximation is 1/27
• Then by the Piling-Up Lemma, the maximum bias of any 28-round linear approximation is 26⋅(1/27)7 = 1/243
• Then about 286 pairs are needed to do a linear attack on 28-round PRESENT
• This is already more than the 280 needed for a brute force attack
• And the full PRESENT has 3 more rounds, 31 rounds total

Differential Characteristics of the S-Box

• Truth table for the S-box, inputs X1 X2 X3 X4, outputs Y1 Y2 Y3 Y4
```X1X2X3X4 | Y1Y2Y3Y4
---------+----------
0 0 0 0 |  1 1 0 0
0 0 0 1 |  0 1 0 1
0 0 1 0 |  0 1 1 0
0 0 1 1 |  1 0 1 1
0 1 0 0 |  1 0 0 1
0 1 0 1 |  0 0 0 0
0 1 1 0 |  1 0 1 0
0 1 1 1 |  1 1 0 1
1 0 0 0 |  0 0 1 1
1 0 0 1 |  1 1 1 0
1 0 1 0 |  1 1 1 1
1 0 1 1 |  1 0 0 0
1 1 0 0 |  0 1 0 0
1 1 0 1 |  0 1 1 1
1 1 1 0 |  0 0 0 1
1 1 1 1 |  0 0 1 0
```

• Consider two S-box inputs, X = X1 X2 X3 X4 and X' = X'1 X'2 X'3 X'4

• The inputs X and X' are related by a fixed, specified input difference ΔX
• ΔX = X ⊕ X'
• Equivalently, X' = X ⊕ ΔX
• For example, let ΔX = 0001; then X' is the same as X with the rightmost bit flipped

• Now consider the S-box outputs
• Y = Y1 Y2 Y3 Y4 = S-box(X)
• Y' = Y'1 Y'2 Y'3 Y'4 = S-box(X')

• The outputs Y and Y' are related by some output difference ΔY
• ΔY = Y ⊕ Y' = S-box(X) ⊕ S-box(X')
• ΔY is not fixed, but depends on what X and X' are

• Truth table for the S-box, calculating output difference ΔY for each input X with input difference ΔX = 0001
```X X X X | Y Y Y Y | X'X'X'X'| Y'Y'Y'Y'| ΔYΔYΔYΔY
1 2 3 4 | 1 2 3 4 | 1 2 3 4 | 1 2 3 4 | 1 2 3 4
--------+---------+---------+---------+--------
0 0 0 0 | 1 1 0 0 | 0 0 0 1 | 0 1 0 1 | 1 0 0 1
0 0 0 1 | 0 1 0 1 | 0 0 0 0 | 1 1 0 0 | 1 0 0 1
0 0 1 0 | 0 1 1 0 | 0 0 1 1 | 1 0 1 1 | 1 1 0 1
0 0 1 1 | 1 0 1 1 | 0 0 1 0 | 0 1 1 0 | 1 1 0 1
0 1 0 0 | 1 0 0 1 | 0 1 0 1 | 0 0 0 0 | 1 0 0 1
0 1 0 1 | 0 0 0 0 | 0 1 0 0 | 1 0 0 1 | 1 0 0 1
0 1 1 0 | 1 0 1 0 | 0 1 1 1 | 1 1 0 1 | 0 1 1 1
0 1 1 1 | 1 1 0 1 | 0 1 1 0 | 1 0 1 0 | 0 1 1 1
1 0 0 0 | 0 0 1 1 | 1 0 0 1 | 1 1 1 0 | 1 1 0 1
1 0 0 1 | 1 1 1 0 | 1 0 0 0 | 0 0 1 1 | 1 1 0 1
1 0 1 0 | 1 1 1 1 | 1 0 1 1 | 1 0 0 0 | 0 1 1 1
1 0 1 1 | 1 0 0 0 | 1 0 1 0 | 1 1 1 1 | 0 1 1 1
1 1 0 0 | 0 1 0 0 | 1 1 0 1 | 0 1 1 1 | 0 0 1 1
1 1 0 1 | 0 1 1 1 | 1 1 0 0 | 0 1 0 0 | 0 0 1 1
1 1 1 0 | 0 0 0 1 | 1 1 1 1 | 0 0 1 0 | 0 0 1 1
1 1 1 1 | 0 0 1 0 | 1 1 1 0 | 0 0 0 1 | 0 0 1 1
```

• Note that not all possible values of ΔY are equally likely
• Probability of occurrence p of ΔY for a random input X with ΔX = 0001:
• ΔY = 0011, p = 4/16
• ΔY = 0111, p = 4/16
• ΔY = 1001, p = 4/16
• ΔY = 1101, p = 4/16
• ΔY = otherwise, p = 0

• A particular choice of (ΔX, ΔY) is called a differential

• We can compute the probability of every possible differential of the PRESENT S-box
• Table lists probabilities for each possible differential
• Zero probabilities omitted
• Denominator of /16 omitted
```\$ java PresentDifferential
Input   Output Delta
Delta   0   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
0  16   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
1   .   .   .   4   .   .   .   4   .   4   .   .   .   4   .   .
2   .   .   .   2   .   4   2   .   .   .   2   .   2   2   2   .
3   .   2   .   2   2   .   4   2   .   .   2   2   .   .   .   .
4   .   .   .   .   .   4   2   2   .   2   2   .   2   .   2   .
5   .   2   .   .   2   .   .   .   .   2   2   2   4   2   .   .
6   .   .   2   .   .   .   2   .   2   .   .   4   2   .   .   4
7   .   4   2   .   .   .   2   .   2   .   .   .   2   .   .   4
8   .   .   .   2   .   .   .   2   .   2   .   4   .   2   .   4
9   .   .   2   .   4   .   2   .   2   .   .   .   2   .   4   .
A   .   .   2   2   .   4   .   .   2   .   2   .   .   2   2   .
B   .   2   .   .   2   .   .   .   4   2   2   2   .   2   .   .
C   .   .   2   .   .   4   .   2   2   2   2   .   .   .   2   .
D   .   2   4   2   2   .   .   2   .   .   2   2   .   .   .   .
E   .   .   2   2   .   .   2   2   2   2   .   .   2   2   .   .
F   .   4   .   .   4   .   .   .   .   .   .   .   .   .   4   4
```

Differential Attack on Two-Round PRESENT

• Consider the high-probability differential (ΔX, ΔY) = (0001, 0011), p = 4/16

• Consider the following pathway (a.k.a. differential characteristic) involving that differential in round 1
• The pathway hits round 1 rightmost S-box
• ΔX = 0001 → input X4 flipped
• ΔY = 0011 → outputs Y3 and Y4 flipped
• Input X4 comes from plaintext bit 0
• Outputs Y3 and Y4 go to round 2 input bits 16 and 0
• The pathway hits round 1 second rightmost S-box
• ΔX = 0001 → input X4 flipped
• ΔY = 0011 → outputs Y3 and Y4 flipped
• Input X4 comes from plaintext bit 4
• Outputs Y3 and Y4 go to round 2 input bits 17 and 1
• The pathway hits round 2 rightmost S-box
• Its outputs go to ciphertext bits (48, 32, 16, 0)
• The pathway hits round 2 fourth-rightmost S-box
• Its outputs go to ciphertext bits (52, 36, 20, 4)
• The dark lines in round 1 show which bits are flipped if the differential occurs
• The dark lines in round 2 show which ciphertext bits are affected by the differential

• Oracle for a differential attack
• Generates a random plaintext P
• Generates a second plaintext P', which equals P with certain bits flipped
• Encrypts P using the secret key to get ciphertext C
• Encrypts P' using the secret key to get ciphertext C'
• Reports (P, C, P', C')
```\$ java ChosenPtOracle "Present80(2)" a690e1d67c9f52c99423 142857 0,4 10
Oracle internal settings: (shhh!)
Key = a690e1d67c9f52c99423
i   Subkey[i]
0   a690e1d67c9f52c9
1   b28474d21c3acf93
Input delta = 0000000000000011
Plaintext_1 -- Ciphertext_1 -- Plaintext_2 -- Ciphertext_2
2c5541edfb958a90 -- ae317ce8687b0d34 -- 2c5541edfb958a81 -- be317de9797a0c34
ff068d6c588d90f5 -- ffebda69dd384fa3 -- ff068d6c588d90e4 -- ffebdb69cd295eb2
595a392dd38a4dea -- 474c90894fe58899 -- 595a392dd38a4dfb -- 564c90895ee58998
af3b76afa40e434f -- 03dd5ee5e4afa22d -- af3b76afa40e435e -- 13cd4ff4e5aeb23d
df8f27cc70a21cc0 -- 67b1dd36b2d18204 -- df8f27cc70a21cd1 -- 66b1cd37a2d08304
806557ab19ee2174 -- b829421e36485585 -- 806557ab19ee2165 -- b829430f37595585
08923557ff099f3b -- fd06ba6de94ad717 -- 08923557ff099f2a -- ed06ba7ce84ac607
1b3987c875e7437c -- 13b1be0eb821009c -- 1b3987c875e7436d -- 13a1af1fa820119c
50128d5df3240d7a -- d10b215705ef5108 -- 50128d5df3240d6b -- d10b314714ee4019
418d6ad271c444ce -- b0a61df31b9571fd -- 418d6ad271c444df -- a1a60cf30b8570ec
```

• Consider the effect of the round 0 subkey bits on the rightmost round 1 S-box
• We have two plaintexts P and P' with ΔP = P ⊕ P' = 0001
• The two S-box inputs are X = (P ⊕ subkey) and X' = (P' ⊕ subkey)
• The input difference ΔX = X ⊕ X' = (P ⊕ subkey) ⊕ (P' ⊕ subkey) = P ⊕ P' = 0001
• This is the desired input difference for our differential
• Bottom line: The round 0 subkey doesn't matter (it cancels out)

• So we can take our input difference to be before the round 0 subkey addition
• That is, the plaintext difference

• By the same logic, we can take our output difference to be after the round 1 subkey addition
• That is, the difference at the round 2 input

• For a random known plaintext input:
• The probability that the desired differential occurs in the first S-box is p = 4/16
• The probability that the desired differential occurs in the second S-box is p = 4/16
• The probability that the desired differential occurs in both S-boxes is (4/16)⋅(4/16) = 1/24
• We exploit this high-probability differential to find selected bits of the round 2 subkey

• The differential attack
• Take known plaintext-ciphertexts (P, C) and (P', C'), where P' = P with bits 0 and 4 flipped
• Check whether all bits of C and C' other than bits (52, 48, 36, 32, 20, 16, 4, 0) are the same
• If the desired differential has occurred, then ciphertext bits not in the pathway will not flip
• Therefore, if any ciphertext bit not in the pathway has flipped, the desired differential has not occurred, and we try the next known plaintext
• Otherwise, we continue
• Guess a value for the round 2 subkey bits (48, 32, 16, 0)
• Compute round 2 first S-box outputs from C and subkey guess
• Compute round 2 first S-box inputs from outputs (inverse S-box)
• Guess a value for the round 2 subkey bits (52, 36, 20, 4)
• Compute round 2 second S-box outputs from C and subkey guess
• Compute round 2 second S-box inputs from outputs (inverse S-box)
• Do the same using C' instead of C
• We now have pathway outputs Z and Z'
• Compute output difference = Z ⊕ Z' for both S-boxes
• Check whether observed difference = desired difference (0011) for both S-boxes
• If so, increment a counter associated with these subkey guesses
• Repeat all the above for every possible combination of subkey guesses (256 possibilities)
• Repeat all the above for every known plaintext-ciphertext pair
• If the subkey guess is wrong:
• Z and Z' will be random 8-bit numbers at the two S-box inputs
• With probability 1/28, the desired output difference will be observed
• The counter for the subkey guess will be small
• If the subkey guess is correct:
• Z and Z' will be the correct round 1 outputs
• With probability 1/24, the desired output difference will be observed
• The counter for the subkey guess will be large
• So whichever counter "sticks out" tells the correct round 2 subkey bits (52, 48, 36, 32, 20, 16, 4, 0)

• Attack program
```\$ java DifferentialAttack01 2 a690e1d67c9f52c99423 142857 1000 0,4 0,16,32,48 3 4,20,36,52 3 > out07.txt
Oracle internal settings: (shhh!)
Key = a690e1d67c9f52c99423
i   Subkey[i]
0   a690e1d67c9f52c9
1   b28474d21c3acf93
Input delta = 0000000000000011
Final round subkey bits
48 32 16  0 52 36 20  4       Count        Prob
1  0  0  0  0  1  1  0          63    0.063000    <-- (correct subkey)
1  0  0  0  0  1  0  1          27    0.027000
1  0  1  1  0  1  1  0          22    0.022000
1  0  0  0  0  0  0  0          17    0.017000
1  1  1  0  0  1  1  0          17    0.017000
1  0  0  0  0  0  1  1          17    0.017000
. . .
```

• The attack on the whole cipher
• Repeat the above for other high-probability differentials that involve the remaining round 2 subkey bits
• Eventually we learn the entire round 2 subkey
• Now we can decrypt any ciphertext back through round 2 to the output of round 1
• This reduces the problem to one we know how to solve, namely, the attack on one-round PRESENT

• We were able to recover the round 2 subkey with far fewer encryptions than the 280 required for a brute force key search
• We did need more known plaintexts than the attack on one-round PRESENT, e.g. 1000 plaintexts
• To ensure the correct subkey "signal" rises above the incorrect subkey "noise"

• For two-round PRESENT, this is still a fairly easy attack

Differential Attack on Three-Round PRESENT

• Consider the following pathway:

• Round 1 differential in two S-boxes: (ΔX, ΔY) = (1111, 0001), p = 4/16

• Round 2 differential in two S-boxes: (ΔX, ΔY) = (0001, 0011), p = 4/16

• Probability of observing the desired differential at the input to round 3 when the subkey guess is correct
= (4/16)⋅(4/16)⋅(4/16)⋅(4/16) = 1/28

• But this is the same as the probability of observing the desired differential at the input to round 3 when the subkey guess is incorrect

• So this pathway will not let us distinguish the correct subkey guess

• To fix this problem, the pathway must hit more S-boxes in round 3

Differential Attack on Three-Round PRESENT, Take 2

• Consider the following pathway:

• Round 1 differential in two S-boxes: (ΔX, ΔY) = (1111, 0001), p = 4/16

• Round 2 differential in two S-boxes: (ΔX, ΔY) = (1000, 1111), p = 4/16

• Probability of observing the desired differential at the input to round 3 when the subkey guess is correct
= (4/16)⋅(4/16)⋅(4/16)⋅(4/16) = 1/28

• Probability of observing the desired differential at the input to round 3 when the subkey guess is incorrect
= 1/216

• So this pathway will let us distinguish the correct subkey guess . . .

• But we have to guess 16 bits of the round 3 subkey at a time, instead of 8 bits

• Attack program
```\$ java DifferentialAttack02 3 a690e1d67c9f52c99423 142857 10000 12,13,14,15,28,29,30,31 0,16,32,48 3 4,20,36,52 3 8,24,40,56 3 12,28,44,60 3 > out08.txt
Oracle internal settings: (shhh!)
Key = a690e1d67c9f52c99423
i   Subkey[i]
0   a690e1d67c9f52c9
1   b28474d21c3acf93
3   4b3e55a966ca11d2
Input delta = 00000000f000f000
Final round subkey bits
48 32 16  0 52 36 20  4 56 40 24  8 60 44 28 12       Count        Prob
0  1  0  0  1  0  0  1  1  1  0  1  0  1  0  1          47    0.004700    <-- (correct subkey)
0  1  0  0  1  0  1  0  1  1  0  1  0  1  0  1          27    0.002700
0  1  0  0  1  0  0  1  1  0  1  1  0  1  0  1          21    0.002100
0  1  0  0  1  1  1  1  1  1  0  1  0  1  0  1          21    0.002100
0  1  0  0  1  0  0  1  1  1  0  1  0  1  1  0          19    0.001900
0  1  0  0  1  1  0  1  1  1  0  1  0  1  0  1          18    0.001800
. . .
```

• After we recover the complete round 3 subkey, we use the previous attacks on rounds 1 and 2

• We were still able to recover the round 3 subkey with fewer encryptions than 280
• But we needed to guess 16 subkey bits at a time instead of 8
• We had to search 65,536 possible subkeys instead of 256
• Also, we needed more known plaintexts than the attack on two-round PRESENT, e.g. 10000 plaintexts
• To ensure the correct subkey "signal" rises above the incorrect subkey "noise"

Differential Attack on More Rounds

• As we scale the differential attack up to more rounds . . .

• More S-boxes get involved
• Because the pathway goes through more rounds (S-boxes)
• Because the permutation layer scatters each S-box's output across the state

• The probability of the differential characteristic becomes smaller
• Because of more S-box probabilities multiplied together

• It takes more known plaintext-ciphertext pairs for the correct subkey signal to rise above the noise

• Also, we have to guess more subkey bits at a time

• Eventually, we reach a point where more than 280 pairs are needed
• PRESENT with that many rounds or more is immune to a differential attack

• More precisely, the number of pairs needed is about c/pd (see Heyes's paper)
• pd is the differential characteristic's probability
• c is a small constant

• Complexity of a differential attack on the full PRESENT (see PRESENT paper)
• Any five-round differential characteristic has at least 10 active S-boxes
• The maximum probability of any differential is 1/22
• Therefore, any five-round differential characteristic's probability is at most (1/22)10 = 1/220
• Therefore, any 25-round differential characteristic's probability is at most (1/220)5 = 1/2100
• Then about 2100 pairs are needed to do a differential attack on 25-round PRESENT
• This is already more than the 280 needed for a brute force attack
• And the full PRESENT has 6 more rounds, 31 rounds total

Implications for Block Cipher Design

• To resist linear and differential attacks, a block cipher should:

• Have a nonlinear substitution layer with linear approximation biases as small as possible
• PRESENT, AES: S-boxes

• Have a substitution layer with differential probabilities as small as possible
• PRESENT, AES: S-boxes

• Have a diffusion layer that spreads the substitution layer outputs as widely as possible
• PRESENT: Bit permutation
• AES: ShiftRows, MixColumns

• Have enough rounds to make 1/ε2 comfortably greater than 2n
• ε = Maximum bias of any full-round linear approximation
• n = Number of key bits
• Makes the linear attack need more encryptions (known plaintext-ciphertext pairs) than a generic brute force attack

• Have enough rounds to make 1/pd comfortably greater than 2n
• pd = Maximum probability of any full-round differential characteristic
• n = Number of key bits
• Makes the differential attack need more encryptions (known plaintext-ciphertext pairs) than a generic brute force attack

• There should be more than just the minimum required number of rounds -- security margin

For Further Information

• Original differential cryptanalysis paper
• E. Biham and A. Shamir. Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology, 4(1):3-72, 1991.

• Original linear cryptanalysis paper
• M. Matsui. Linear cryptanalysis method for DES cipher. In Advances in Cryptology -- EUROCRYPT '93, pages 386-397, 1993.

• Simplified explanation

• PRESENT specification
• A. Bogdanov, L. Knudsen, G. Leander, C. Paar, A. Poschmann, M. Robshaw, Y. Seurin, and C. Vikkelsoe. PRESENT: an ultra-lightweight block cipher. In P. Paillier and I. Verbauwhede, eds. 9th International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2007), Springer LNCS 4727, 2007.

• Recent paper on meet-in-the-middle attacks
• T. Isobe and K. Shibutani. All subkeys recovery attack on block ciphers: extending meet-in-the-middle approach. 2012 Conference on Selected Areas in Cryptography, 2012 (preprint PDF).

 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005