4003-482/4005-705 -- Cryptography

Alan Kaminsky

•

Department of Computer Science

•

Rochester Institute of Technology

•

4486 + 2220 = 6706

Home Page

Cryptography

•

4003-482-01/4005-705-01

•

Spring Quarter 2013

Course Page

4003-482-01/4005-705-01 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 program to generate random known plaintext-ciphertext pairs

Class PtCt (download)
Class Present (download)
Class Oracle01 (download)

$ java Oracle01 1 10 142857
Key = DB2AB91E8CFFD22C7555 (Shhh!)
Round  0 subkey = DB2AB91E8CFFD22C
Round  1 subkey = 3EAABB655723D19F
66B00FF580266641        8334CB94231083BA
4CD889F1452736ED        F2EE6F86EE539BA2
FAD1CE0FB755ECFB        22537456F7999E20
4FA23DF5BF583A95        FB593B54EFC6AF63
1D61F599CCBD178A        47493E3F1530FA3D
85EC44B91EE73D90        2D289C8449F796A7
32715EFFCFA633FF        6A7BFE7317705E50
AC3605B4F3D7B606        F5274CC65458320A
5AB5F0661BFA318D        104CDD86E2A51AD0
1612BF79C6E64A6C        1171721C217FA079

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
- Take a known plaintext P and the corresponding known ciphertext C
- Guess a value for the round 0 subkey bits (3, 2, 1, 0)
- Guess a value for the round 1 subkey bits (48, 32, 16, 0)
- Compute S-box inputs from P and round 0 subkey
- Compute S-box outputs from C and round 1 subkey
- Check whether the S-box maps that input to that output
- If so, increment a counter associated with this particular subkey guess
- Repeat all the above for every possible subkey guess (256 possibilities)
- Repeat all the above for every known plaintext-ciphertext pair
- If the subkey guess is wrong, then there is a 1 in 16 chance that the S-box mapping is correct, and the counter will be about 1/16 the number of plaintext-ciphertext pairs
- If the subkey guess is correct, then there is a 100% chance that the S-box mapping is correct, and the counter will equal the number of plaintext-ciphertext pairs
- So whichever counter "sticks out" tells the correct round 0 subkey bits (3, 2, 1, 0) and round 1 subkey bits (48, 32, 16, 0)

Attack program

Class Attack01 (download)
Attacker queries the oracle and performs the attack on the oracle's output
In this case, the query is "Give me n random plaintexts and the corresponding ciphertexts encrypted with the (secret) key"

$ java Attack01 10 142857 0 1 2 3 0 16 32 48 > out01.txt
Key = DB2AB91E8CFFD22C7555 (Shhh!)
Round  0 subkey = DB2AB91E8CFFD22C
Round  1 subkey = 3EAABB655723D19F
$ cat out01.txt
    Subkey 0    Subkey 1
  3  2  1  0 48 32 16  0  Count
  0  0  0  0  0  0  0  0      0
  0  0  0  0  0  0  0  1      0
  0  0  0  0  0  0  1  0      3
  . . .
  1  1  0  0  0  1  0  0      0
  1  1  0  0  0  1  0  1      0
  1  1  0  0  0  1  1  0      0
  1  1  0  0  0  1  1  1     10 ***
  1  1  0  0  1  0  0  0      0
  1  1  0  0  1  0  0  1      0
  1  1  0  0  1  0  1  0      0
  . . .
  1  1  1  1  1  1  0  1      1
  1  1  1  1  1  1  1  0      0
  1  1  1  1  1  1  1  1      0

The attack on the whole cipher
- Repeat the above for all 16 S-boxes

Attack program

Class Attack02 (download)

$ java Attack02 10 142857 
Key = DB2AB91E8CFFD22C7555 (Shhh!)
Round  0 subkey = DB2AB91E8CFFD22C
Round  1 subkey = 3EAABB655723D19F
S-box  0, round 0 subkey = C, round 1 subkey = 7
S-box  1, round 0 subkey = 2, round 1 subkey = B
S-box  2, round 0 subkey = 2, round 1 subkey = 5
S-box  3, round 0 subkey = D, round 1 subkey = 9
S-box  4, round 0 subkey = F, round 1 subkey = 1
S-box  5, round 0 subkey = F, round 1 subkey = E
S-box  6, round 0 subkey = C, round 1 subkey = 4
S-box  7, round 0 subkey = 8, round 1 subkey = 9
S-box  8, round 0 subkey = E, round 1 subkey = 7
S-box  9, round 0 subkey = 1, round 1 subkey = E
S-box 10, round 0 subkey = 9, round 1 subkey = A
S-box 11, round 0 subkey = B, round 1 subkey = C
S-box 12, round 0 subkey = A, round 1 subkey = F
S-box 13, round 0 subkey = 2, round 1 subkey = C
S-box 14, round 0 subkey = B, round 1 subkey = 3
S-box 15, round 0 subkey = D, round 1 subkey = 5
Round 0 subkey = DB2AB91E8CFFD22C
Round 1 subkey = 3EAABB655723D19F

We were able to recover the subkeys with far fewer encryptions than the 2⁸⁰ 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
- Given a plaintext and the corresponding ciphertext
- Guess bits 0-15 of the round 0 subkey
- Encrypt the plaintext from the top down to Point A
  - Guess bits 0-3 of the round 1 subkey and bits 0, 16, 32, and 48 of the round 2 subkey
  - Decrypt the ciphertext from the bottom, through round-2 S-box 0, up to Point A
  - If state bits 0-3 are the same in both directions (if they meet in the middle), then this is a possible guess for the subkey bits
  - Otherwise, this is an impossible guess for the subkey bits
  - Repeat the above for all possible round-1 and round-2 subkey guesses (8 bits, 2⁸ operations)
  - This will rule out some subkey guesses
  - Repeat the above for round-2 S-boxes 4, 8, and 12
- Repeat the above for all possible round-0 subkey guesses (16 bits, 2¹⁶ operations)
  - This will rule out more subkey guesses
  - (Note: The round-0 subkey guess must work for all four round-2 S-boxes)
- Repeat the above for another plaintext/ciphertext
  - This will rule out more subkey guesses
- Continue until only one possible subkey guess is left
Total work per plaintext/ciphertext pair: 2¹⁶ ⋅ (2⁸ + 2⁸ + 2⁸ + 2⁸) = 2²⁶
We can reduce the work by splitting the attack into two parts
- Given a plaintext and the corresponding ciphertext
- Part 1:
  - Guess bits 0-3 of the round 1 subkey and bits 0, 16, 32, and 48 of the round 2 subkey (the "bottom-up guesses")
  - Decrypt the ciphertext from the bottom, through round-2 S-box 0, up to Point A
  - Store the results in a table
  - Repeat the above for all possible bottom-up guesses (8 bits, 2⁸ operations)
  - Repeat the above for round-2 S-boxes 4, 8, and 12
- Part 2:
  - Guess bits 0-15 of the round 0 subkey (the "top-down" guesses)
  - Encrypt the plaintext from the top down to Point A
  - Query the table to see which bottom-up guesses are possible or impossible (that do or don't meet in the middle)
  - Repeat the above for all possible top-down guesses (16 bits, 2¹⁶ operations)
- Repeat the above for another plaintext/ciphertext
- Continue until only one possible subkey guess is left
Total work per plaintext/ciphertext pair: (2⁸ + 2⁸ + 2⁸ + 2⁸) + 2¹⁶ < 2²⁶

Attack program

Class MitmAttack01 (download)

$ java MitmAttack01 142857
Key = DB2AB91E8CFFD22C7555 (Shhh!)
Round  0 subkey = DB2AB91E8CFFD22C
Round  1 subkey = 3EAABB655723D19F
Round  2 subkey = 1F48A7D5576CAAE5
N     Plaintext           Ciphertext          # subkeys
1     66B00FF580266641    681FAD64B5A15B88    1048576  1048576  1048576  1048576
2     4CD889F1452736ED    1656E7DE98779837    7424  6656  6400  5888
3     FAD1CE0FB755ECFB    02316FAE86D6B6A1    2  4  2  2
4     4FA23DF5BF583A95    4253B7FDCF33A36C    1  2  1  1
5     1D61F599CCBD178A    E57EF7404C434442    1  1  1  1
Subkey 0 = ................................................1101001000101100
Subkey 1 = ............1010............0101............0011............1111
Subkey 2 = ...1...1...0...0...0...1...1...1...1...1...0...0...0...0...0...1

The attack on the whole cipher
- Repeat the above for each S-box in round 2
We were able to recover the subkeys with far fewer encryptions than the 2⁸⁰ 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

X X X X | Y Y Y Y
1 2 3 4 | 1 2 3 4
--------+--------
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

Class PresentLinearApprox (download)
"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 = ε₁
- Probability[insum₁ + outsum₁ = 0] = p₁ = 1/2 + ε₁
- Probability[insum₁ + outsum₁ = 1] = 1 − p₁ = 1/2 − ε₁
Consider a linear approximation for some other S-box
- Bias = ε₂
- Probability[insum₂ + outsum₂ = 0] = p₂ = 1/2 + ε₂
- Probability[insum₂ + outsum₂ = 1] = 1 − p₂ = 1/2 − ε₂
What is the bias of the sum of the two linear approximations?
- Assuming the linear approximation probabilities are independent
Probability[insum₁ + outsum₁ + insum₂ + outsum₂ = 0]
= Probability[(insum₁ + outsum₁ = 0 and insum₂ + outsum₂ = 0) or (insum₁ + outsum₁ = 1 and insum₂ + outsum₂ = 1)]
= p₁p₂ + (1 − p₁)(1 − p₂)
= (1/2 + ε₁)(1/2 + ε₂) + (1/2 − ε₁)(1/2 − ε₂)
= 1/2 + 2ε₁ε₂
Therefore, bias[insum₁ + outsum₁ + insum₂ + outsum₂ = 0]
= 1/2 + 2ε₁ε₂ − 1/2
= 2ε₁ε₂
Piling-Up Lemma
- Generalization of the above
- The bias of the sum of n linear approximations is 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 ε₁ = ε₂ = −4/16 = −1/4
- The bias of the sum of both is ε = 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

Class LinearAttack01 (download)

$ java LinearAttack01 2 1000 142857 0 16 32 48 3 4 20 36 52 3 1 2 5 6 > out04.txt
Key = DB2AB91E8CFFD22C7555 (Shhh!)
Round  0 subkey = DB2AB91E8CFFD22C
Round  1 subkey = 3EAABB655723D19F
Round  2 subkey = 1F48A7D5576CAAE5
$ cat out04.txt
Final round subkey bits
 48 32 16  0 52 36 20  4       Count      |Bias|
  0  0  0  0  0  0  0  0         503    0.003000
  0  0  0  0  0  0  0  1         486    0.014000
  0  0  0  0  0  0  1  0         505    0.005000
  . . .
  0  1  0  1  0  0  0  1         502    0.002000
  0  1  0  1  0  0  1  0         479    0.021000
  0  1  0  1  0  0  1  1         484    0.016000
  0  1  0  1  0  1  0  0         617    0.117000 ***
  0  1  0  1  0  1  0  1         545    0.045000
  0  1  0  1  0  1  1  0         466    0.034000
  0  1  0  1  0  1  1  1         444    0.056000
  . . .
  1  1  1  1  1  1  0  1         482    0.018000
  1  1  1  1  1  1  1  0         497    0.003000
  1  1  1  1  1  1  1  1         526    0.026000

Here's another pathway involving the same linear approximation

$ java LinearAttack01 2 1000 142857 1 17 33 49 3 5 21 37 53 3 17 18 21 22 > out05.txt
Key = DB2AB91E8CFFD22C7555 (Shhh!)
Round  0 subkey = DB2AB91E8CFFD22C
Round  1 subkey = 3EAABB655723D19F
Round  2 subkey = 1F48A7D5576CAAE5
$ cat out05.txt
Final round subkey bits
 49 33 17  1 53 37 21  5       Count      |Bias|
  0  0  0  0  0  0  0  0         465    0.035000
  0  0  0  0  0  0  0  1         458    0.042000
  0  0  0  0  0  0  1  0         531    0.031000
  0  0  0  0  0  0  1  1         620    0.120000 ***
  0  0  0  0  0  1  0  0         499    0.001000
  0  0  0  0  0  1  0  1         487    0.013000
  0  0  0  0  0  1  1  0         524    0.024000
  . . .
  1  1  1  1  1  1  0  1         495    0.005000
  1  1  1  1  1  1  1  0         452    0.048000
  1  1  1  1  1  1  1  1         463    0.037000

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 2⁸⁰ 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 = 2⁴⁻¹(+4/16)(+4/16)(+2/16)(+2/16) = +1/128
Ciphertext output bits (53, 49, 37, 33, 21, 17, 5, 1)

$ java LinearAttack01 3 100000 142857 1 17 33 49 3 5 21 37 53 3 5 7 21 23 > out06.txt
Key = DB2AB91E8CFFD22C7555 (Shhh!)
Round  0 subkey = DB2AB91E8CFFD22C
Round  1 subkey = 3EAABB655723D19F
Round  2 subkey = 1F48A7D5576CAAE5
Round  3 subkey = FF4663E914FAAAEC
$ cat out06.txt
Final round subkey bits
 49 33 17  1 53 37 21  5       Count      |Bias|
  0  0  0  0  0  0  0  0       49825    0.001750
  0  0  0  0  0  0  0  1       49987    0.000130
  0  0  0  0  0  0  1  0       50032    0.000320
  . . .
  1  0  1  0  0  1  0  0       50510    0.005100
  1  0  1  0  0  1  0  1       50498    0.004980
  1  0  1  0  0  1  1  0       49556    0.004440
  1  0  1  0  0  1  1  1       49206    0.007940 ***
  1  0  1  0  1  0  0  0       49472    0.005280
  1  0  1  0  1  0  0  1       49822    0.001780
  1  0  1  0  1  0  1  0       50462    0.004620
  . . .
  1  1  1  1  1  1  0  1       50044    0.000440
  1  1  1  1  1  1  1  0       49813    0.001870
  1  1  1  1  1  1  1  1       49919    0.000810

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 2⁸⁰
- 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 2⁸⁰ 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/ε² (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/2⁷
- Then by the Piling-Up Lemma, the maximum bias of any 28-round linear approximation is 2⁶⋅(1/2⁷)⁷ = 1/2⁴³
- Then about 2⁸⁶ pairs are needed to do a linear attack on 28-round PRESENT
- This is already more than the 2⁸⁰ 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

X X X X | Y Y Y Y
1 2 3 4 | 1 2 3 4
--------+--------
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

Class PresentDifferential (download)
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')
Class PtCtDiff (download)
Class Oracle02 (download)

$ java Oracle02 2 10 142857 0 4
Key = DB2AB91E8CFFD22C7555 (Shhh!)
Round  0 subkey = DB2AB91E8CFFD22C
Round  1 subkey = 3EAABB655723D19F
Round  2 subkey = 1F48A7D5576CAAE5
66B00FF580266641        681FAD64B5A15B88        66B00FF580266650        681FAD74B4B15A99
4CD889F1452736ED        1656E7DE98779837        4CD889F1452736FC        1646E7CE88668836
FAD1CE0FB755ECFB        02316FAE86D6B6A1        FAD1CE0FB755ECEA        02316EAF87D7B7B0
4FA23DF5BF583A95        4253B7FDCF33A36C        4FA23DF5BF583A84        5253A6FCCF22B37D
1D61F599CCBD178A        E57EF7404C434442        1D61F599CCBD179B        E57EF6514D524452
85EC44B91EE73D90        16974B8EAD02F976        85EC44B91EE73D81        16974B9FAC02F876
32715EFFCFA633FF        EC39C5249E6CCD01        32715EFFCFA633EE        ED29D4258E7DDC00
AC3605B4F3D7B606        060391D2F671B2BC        AC3605B4F3D7B617        171381C2F771A2AD
5AB5F0661BFA318D        7E6D7BBA580A044B        5AB5F0661BFA319C        7E7D7BAB490B155A
1612BF79C6E64A6C        3767583A53F5508F        1612BF79C6E64A7D        3767583A43F5408E

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/2⁴
- 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/2⁸, 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/2⁴, 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

Class DifferentialAttack01 (download)

$ java DifferentialAttack01 2 100 142857 0 16 32 48 3 4 20 36 52 3 0 4 > out07.txt
Key = DB2AB91E8CFFD22C7555 (Shhh!)
Round  0 subkey = DB2AB91E8CFFD22C
Round  1 subkey = 3EAABB655723D19F
Round  2 subkey = 1F48A7D5576CAAE5
$ cat out07.txt
Final round subkey bits
 48 32 16  0 52 36 20  4       Count
  0  0  0  0  0  0  0  0           0
  0  0  0  0  0  0  0  1           1
  0  0  0  0  0  0  1  0           1
  . . .
  0  1  0  1  0  0  0  1           2
  0  1  0  1  0  0  1  0           2
  0  1  0  1  0  0  1  1           0
  0  1  0  1  0  1  0  0           5 ***
  0  1  0  1  0  1  0  1           0
  0  1  0  1  0  1  1  0           0
  0  1  0  1  0  1  1  1           3
  . . .
  1  1  1  1  1  1  0  1           0
  1  1  1  1  1  1  1  0           0
  1  1  1  1  1  1  1  1           0

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 2⁸⁰ required for a brute force key search
- We did need more known plaintexts than the attack on one-round PRESENT, e.g. 100 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/2⁸
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/2⁸
Probability of observing the desired differential at the input to round 3 when the subkey guess is incorrect
= 1/2¹⁶
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

Class DifferentialAttack02 (download)

$ java DifferentialAttack02 3 1000 142857 0 16 32 48 3 4 20 36 52 3 8 24 40 56 3 12 28 44 60 3 12 13 14 15 28 29 30 31 > out08.txt
Key = DB2AB91E8CFFD22C7555 (Shhh!)
Round  0 subkey = DB2AB91E8CFFD22C
Round  1 subkey = 3EAABB655723D19F
Round  2 subkey = 1F48A7D5576CAAE5
Round  3 subkey = FF4663E914FAAAEC
$ cat out08.txt
Final round subkey bits
 48 32 16  0 52 36 20  4 56 40 24  8 60 44 28 12       Count
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0           0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1           0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0           0
  . . .
  0  1  0  0  0  0  1  0  1  1  0  0  0  1  1  1           0
  0  1  0  0  0  0  1  0  1  1  0  0  1  0  0  0           1
  0  1  0  0  0  0  1  0  1  1  0  0  1  0  0  1           5
  0  1  0  0  0  0  1  0  1  1  0  0  1  0  1  0           9 ***
  0  1  0  0  0  0  1  0  1  1  0  0  1  0  1  1           2
  0  1  0  0  0  0  1  0  1  1  0  0  1  1  0  0           6
  0  1  0  0  0  0  1  0  1  1  0  0  1  1  0  1           0
  . . .
  1  1  1  1  1  1  1  1  1  1  1  1  1  1  0  1           0
  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  0           0
  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1           0

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 2⁸⁰
- 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. 1000 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 2⁸⁰ 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/p_d (see Heyes's paper)
- p_d 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/2²
- Therefore, any five-round differential characteristic's probability is at most (1/2²)¹⁰ = 1/2²⁰
- Therefore, any 25-round differential characteristic's probability is at most (1/2²⁰)⁵ = 1/2¹⁰⁰
- Then about 2¹⁰⁰ pairs are needed to do a differential attack on 25-round PRESENT
- This is already more than the 2⁸⁰ 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/ε² comfortably greater than 2ⁿ
- ε = 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/p_d comfortably greater than 2ⁿ
- p_d = 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

SAT Solver Attacks

Express the PRESENT algorithm (circuit), reduced to a certain number of rounds, as a giant Boolean expression
Variables in the Boolean expression represent:
- Plaintext input bits
- Key input bits
- Intermediate values inside the circuit
- Ciphertext output bits
By design, the Boolean expression will be true when the plaintext variable values, encrypted with the key variable values, yield the ciphertext variable values
Set the plaintext and ciphertext variable values to a known plaintext-ciphertext pair
Optionally, set some of the key variable values
Hand the Boolean expression to a SAT solver program
- The SAT solver finds values for all the variables to make the Boolean expression true ("satisfied")
The SAT solver does a backtracking search
- Tentatively set each variable to 0 or 1, one at a time
- If the Boolean expression becomes false, it is a conflict
- When a conflict occurs, backtrack and try the opposite value for the variable
- Eventually, all the variables are set with no conflicts
The key variable values in the final solution recover the key
Some preliminary research results
- Parallel SAT solver running on the tardis.cs.rit.edu 40-core cluster
- Average over 10 PRESENT instances
- K = Number of missing key bits being searched for
- Trials = Average number of steps in the search
- Confs = Average number of conflicts (backtracks) in the search
- Green = Average number of "conflict clauses" added to the Boolean expression
- Msec = Average run time in milliseconds

One-round PRESENT:

 K  Trials  Confs  Green   Msec
 4     0.0    0.0    0.0  583.4
 8     0.0    0.0    0.0   79.8
12     0.0    0.0    0.0   94.8
16     0.0    0.0    0.0  106.1
20     0.0    0.0    0.0   90.1
24     0.0    0.0    0.0   85.6
28     0.0    0.0    0.0   88.2
32     0.0    0.0    0.0   73.6
36     0.0    0.0    0.0   88.3
40     2.1    0.7    1.5  112.0
44     2.1    1.0    1.8  158.7
48     5.0    2.2    3.0  105.5
52    16.0    7.1    6.4  115.9
56    76.3   29.0   26.1  176.1
60   143.4   51.1   48.7  155.1
64   362.4  168.4  129.6  118.8
68   411.5  211.2  151.0  212.5
72   263.8  103.2   78.6  120.1
76   321.2  125.5   93.3   77.9
80   278.4   93.1   68.7   94.3

Two-round PRESENT:

 K    Trials     Confs   Green     Msec
 4       0.0       0.0     0.0    579.1
 8       0.0       0.0     0.0    128.9
12       0.0       0.0     0.0     70.3
16       0.0       0.0     0.0     83.6
20       0.0       0.0     0.0     97.8
24       0.0       0.0     0.0     80.7
28       0.8       0.4     2.0    122.1
32      19.5       5.2     4.7    152.5
36      43.5      10.5     9.9    166.5
40     113.6      30.8    26.1    134.5
44     138.7      31.0    25.8     90.0
48     325.9     120.0    96.1    187.4
52     783.5     356.9   239.4    213.5
56    2321.5    1248.8   654.4    324.2
60    7602.8    5056.5  1547.6    927.2
64   65905.2   52819.2  5240.3  19401.6
68   68028.7   54932.5  4806.4  19653.5
72   49216.7   38616.7  3403.4  10942.2
76  129185.8  105346.1  5238.1  51255.3
80   97825.8   80464.1  3951.7  38631.4

Three-round PRESENT:

 K     Trials      Confs     Green         Msec
 4        0.0        0.0       0.0        632.6
 8        0.0        0.0       0.0         87.0
12        3.7        1.0       1.2        213.2
16       24.6        4.8       4.5        159.0
20       36.9        7.4       7.0        117.6
24       57.1       10.0       9.3        113.9
28      100.3       19.6      17.4        138.4
32      184.0       38.3      34.7        144.4
36      336.0       62.8      51.7        159.3
40      695.9      176.1     117.1        176.3
44     1337.0      428.7     249.9        174.9
48     5158.1     2669.5     962.7        539.1
52    24204.9    16368.0    3187.3       3852.3
56   220047.5   173606.4   12887.8     165689.6
60  2725013.3  2293931.4   69933.4   26109676.5
64  7417622.0  6269241.5  111690.8  105327287.8
68  9397425.0  8023027.0  119269.0  150076739.0

The SAT solver finds the solution with much less work (conflicts) than a brute force search
The SAT solver takes a long time for PRESENT with three or more rounds

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
- H. Heyes. A tutorial on linear and differential cryptanalysis. April 29, 2004. http://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf
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).

Cryptography • 4003-482-01/4005-705-01 • Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2012 Alan Kaminsky. All rights reserved. Last updated 13-Dec-2012. Please send comments to ark@cs.rit.edu.

4003-482-01/4005-705-01 Cryptography Structural Attacks on Block Ciphers Lecture Notes

Attack on 1-Round PRESENT

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

Linear Approximation of the S-Box

Sums of Linear Approximations

Linear Attack on Two-Round PRESENT

Linear Attack on Three-Round PRESENT

Linear Attack on More Rounds

Differential Characteristics of the S-Box

Differential Attack on Two-Round PRESENT

Differential Attack on Three-Round PRESENT

Differential Attack on Three-Round PRESENT, Take 2

Differential Attack on More Rounds

Implications for Block Cipher Design

SAT Solver Attacks

For Further Information

4003-482-01/4005-705-01 Cryptography
Structural Attacks on Block Ciphers
Lecture Notes