Differential cryptanalysis of 3-round SDES
Because XOR is addition modulo 2 and subtraction is the same operation as addition modulo 2, we can freely rearrange XORed terms as in the following:
𝑥 ⊕ 𝑦 = 𝑧 ⟹ 𝑦 ⊕ 𝑧 = 𝑥, 𝑥 ⊕ 𝑧 = 𝑦
The attack being used here is a known-plaintext attack. Eve knows the inputs (𝐿1, 𝑅1) and the outputs (𝐿4, 𝑅4). These variables will be used throughout:
– 𝑅𝑖 : right half produced by round 𝑖
– 𝐿𝑖 : left half produced by round 𝑖
– 𝐾 : sub-key used in round 𝑖 𝑖
Because we are using a Feistel network, in all cases 𝑅𝑖−1 = 𝐿𝑖. Remember that we are starting at round 2 to cryptanalyze
rounds 2 to 4 of SDES.
Eve chooses a second plaintext 𝐿1𝑅1. Think of there being two
SDES encryption circuits, one with 𝐿1𝑅1 as the input, the other ∗∗∗
with 𝐿1𝑅1 as the input. The variables 𝐿𝑖 , 𝑅𝑖 represent the left and right inputs to each round in the second circuit. But note that the same key is used in both circuits.
The idea behind differential cryptanalysis is to compute values that are the XOR of values at the same place in each circuit.
∗
Round 4 in each circuit
At round 4, the input to the 𝑓-function (because it’s a Feistel network) in each circuit is:
∗∗ 𝑅3 =𝐿4,𝑅3 =𝐿4
The output of the 𝑓-function in each circuit is: ∗
𝑓(𝐿 ,𝐾 ),𝑓(𝐿 ,𝐾 ) 44 44
The output of the XOR below that is:
In each circuit, we don’t know the output of that circuit’s 𝑓- function but we DO know the XOR of the outputs of the 𝑓- functions in both circuits:
𝑅 =𝐿 ⊕𝑓(𝐿,𝐾),𝑅 =𝐿 ⊕𝑓(𝐿,𝐾) 43444344
∗∗∗
∗′′
𝑓(𝐿,𝐾)⊕𝑓(𝐿,𝐾)=𝑅 ⊕𝐿 444441
The derivation showing that is the following:
𝑅 =𝐿 ⊕𝑓(𝑅,𝐾)⊕𝑓(𝑅,𝐾) 411234
∗∗∗
𝑅 =𝐿 ⊕𝑓(𝑅,𝐾)⊕𝑓(𝑅,𝐾) 411234
𝑅′ =𝑅 ⊕𝑅∗ 444
∗
⊕(𝑓(𝑅 ,𝐾 )⊕𝑓(𝑅∗,𝐾 )) 34 34
=(𝐿 ⊕𝐿 )⊕(𝑓(𝑅 ,𝐾 )⊕𝑓(𝑅 ,𝐾 )) 111212
′∗
=𝐿 ⊕𝑓(𝑅,𝐾)⊕𝑓(𝑅,𝐾) 13434
′
We can move 𝐿1 to the other side to get:
′′∗
𝑅 ⊕𝐿 =𝑓(𝐿,𝐾)⊕𝑓(𝐿,𝐾) 414444
This gives us an expression in variable whose values we know for the XOR of the outputs of the 𝑓-functions in each circuit.
∗
Now we look inside the 𝑓-function. We know 𝑅 and 𝑅∗
33 because they are 𝐿4 and 𝐿4. The expander output is also
known. But because we don’t know 𝐾 , we don’t know the 4
output of the XOR with 𝐾 . But, again, we DO know the XOR of 4
the output of that XOR in both circuits (which is also the input to the S-boxes). Here’s why.
The output of each expander is:
𝐸(𝑅3) = 𝐸(𝐿4)
∗∗ 𝐸(𝑅3) = 𝐸(𝐿4)
∗
We know 𝐿4, 𝐿4 so we know one of the inputs going into the
XOR with 𝐾 . In each circuit, the output of the XOR with the 4
key is:
𝐸(𝐿 )⊕𝐾 44
∗
𝐸(𝐿 )⊕𝐾 44
Without knowing 𝐾 , we have little hope of knowing these two 4
values independently. But if we combine them with XOR we get:
∗
appears twice and a value XORed with itself is 0, we can simplify the above to:
∗ 𝑥 = 𝐸(𝐿4) ⊕ 𝐸(𝐿4)
Because 𝐾 4
𝐸(𝐿 )⊕𝐾 ⊕𝐸(𝐿 )⊕𝐾 4444
With 𝐾 removed, that’s a value we know! (I’ve labeled it 𝑥 so 4
that I can refer to it below). In other words, we’ve just shown that we can compute the XOR of the inputs to the S-boxes even if we don’t know each input to the S-boxes in their own circuit.
Now let’s tackle the S-boxes. As the book does, we’ll look at solving 𝑆 . The solution on 𝑆 will follow the same procedure.
12
The leftmost 4 bits of 𝑥 is the XOR of leftmost 4 bits going
into 𝑆 for the circuit encrypting 𝐿 𝑅 and the leftmost 4 bits
111
∗
We don’t know the output of the two 𝑆 boxes but we do know 1
their XOR. Above we showed that:
going into 𝑆 for the circuit encrypting 𝐿 𝑅 . 111
∗′′
𝑓(𝐿,𝐾)⊕𝑓(𝐿,𝐾)=𝑅 ⊕𝐿 =𝑦 444441
Again, for convenience, I will call that value 𝑦.
To review, we know the XOR of the values going into the S-
boxes and we know the XOR of the values coming out of the S-
boxes. If we didn’t know anything about the outputs, we would
have to try all possible 4-bits values going into the 𝑆 in each 1
circuit. That would be 28 = 256 different possibilities.
Except that we know their XOR. Say, for example, the XOR is 1011. Then for each possible 4-bit value in the first circuit, there could be only one possible 4-bit value in the other. If the first circuit’s actual input is 0011, the second circuit would have to have as input 1000. This reduces the number of possibilities to 24 = 16.
Of those 16 pairs, which one is correct? That’s where knowing
the XOR of the outputs of the S-boxes comes in. For each pair
of values, run each through its 𝑆 and XOR the outputs. The 1
correct pair will produce outputs that, when XORed, will equal the first 3 bits of 𝑦.
Use the same approach for 𝑆2.
This tells us the inputs to the S-boxes in each circuit. Take one
in the circuit encrypting 𝐿1𝑅1, XOR it with 𝐸(𝐿4) and that will
give us 𝐾 . 4