Differential Cryptanalysis Demo
Differential cryptanalysis is of
interest in code making probably more so than for code breaking. In order to use differential cryptanalysis
to break 16-round, 56-bit DES an attacker would need 247 chosen
plaintexts (about 985 terabytes) and a computational effort on the order of 247. The number of chosen plaintexts needed is
dependent on the ability of XOR differences to propagate through a block cipher
algorithm (and therefore partly dependent on the number rounds) and the
computational effort comes from the size of the subkey used for each
round. The search space of differential
cryptanalysis is the subkey of the last round and not the encryption key.
Its also interesting to note that
the use of independent subkeys, in place of a 56-bit key and a subkey
generation algorithm to produce 16 48-bit subkeys, does not buy you much
against differential cryptanalysis.
Once an attacker has the subkey for the last round, they can attack the
second-to-the last round. They can
climb the rounds of your block cipher like a latter and recover all 16
independent subkeys without significantly more effort than if you had just used
a subkey generation algorithm. Your
768-bit encryption key can be broken in 48-bit chunks independent of one
another.
Following is a step-by-step
differential cryptanalysis on a modified version of SDES which has three
rounds, no initial or final permutation, and uses three independent subkeys.
Step 1: Choose an XOR difference for the plaintext pairs
Well go ahead and use an XOR difference of 10000000. This means that each of our plaintext pairs will differ in only the first bit. For example 00000000 will be paired with 10000000, 00000001 will be paired with 10000001, , 01100100 will be paired with 11100100, , and 01111111 will be paired with 11111111.
Step 2: Generate ciphertext pairs for some plaintext pairs
Differential cryptanalysis is a chosen plaintext attack, so well need access to the encryption equipment with the key installed. This doesnt mean we can see the key, though we just need to have access to the equipment.
Were going to encrypt 25 randomly chosen plaintext pairs from our plaintext pairs above, for a total of 50 encryptions. If our cipher had more rounds we would have to do a lot more work.
When we do these 50 encryptions we get 25 ciphertext pairs, paired by the fact that both ciphertexts in a pair came from one of the plaintexts of a plaintext pair.
Plaintext -> Ciphertext
One pair:
01111001 -> 11111001
11111001 -> 11111110
Another pair:
01000100 -> 10101100
11000100 -> 10011001
A third pair:
00000011 -> 01000010
10000011 -> 10110111
etc.
Step 3: Get 2 pieces of information out of each ciphertext pair
3.1) The first piece of information we want out of each ciphertext pair is what the input to E/P was for the last round. This is trivial. The right half of the ciphertext is what went into E/P. So, for the second pair, the two inputs to E/P were 1100 for the first ciphertext and 1001 for the second.
3.2) The second piece of information we need is not so trivial. Were going to have to find out what the expected XOR difference that came out of the S-boxes in the last round was. Lets do this for the second ciphertext pair. We already know that the left halves of our two ciphertexts for this pair are 1010 and 1001. Their XOR difference is 0011 then, because the second and third bits differ.
Now we want to know what kind of XOR difference went into the XOR4. Fortunately, differences propagate through XORs as if they themselves were being XORed. Lets say that A1, B1, C1, A2, B2, and C2 are all bits and that C1 = A1 XOR B1 and C2 = A2 XOR B2. If we know that A1 and A2 are different and B1 and B2 are the same, then we know that C1 and C2 are different. If A1 and A2 are different and B1 and B2 are also different, then we know that C1 and C2 are the same. Obviously, if A1 and A2 are the same and B1 and B2 are the same then C1 is the same as C2. So to know the XOR difference between C1 and C2 we just take the XOR difference between A1 and A2 and the XOR difference between B1 and B2 and XOR them.
We know that the left half of the plaintext was used as input to the XOR4 in the first round. The plaintext XOR difference for a pair is 10000000. The XOR difference of the output of the first round must also be 10000000 then. After the switch the XOR difference is 00001000. Round 2 doesnt touch the right half so the XOR output of round 2 is 00001000. After a switch we have the input to round 3 which is 10000000. So one input to the XOR4 was 1000 and the output was our 0011 from above. The XOR difference we would expect for the other input (the one coming out of P4) then is 1011.
P4 is not a problem, we just take its inverse to know what its input was.
P4-1(1011) = 1110.
Step 4: Try all possible values for the subkey K3
There are 256 possible values for subkey K3, 0 through 255 or 00000000 through 11111111. We have to try all 256 of them.
For every subkey, what we have to do is recreate E/P, the 8-bit XOR after E/P, and the S-boxes for each ciphertext pair. The reason we have to use 25 ciphertext pairs instead of just one is that there is a chance a false input might get lucky and produce the right output, but this wont happen 25 times. The number 25 has nothing to do with the key size or block size so it does not add to our measure of complexity.
Lets try a subkey of 10101010 with our second ciphertext pair. The inputs to E/P were 1100 and 1001, so the E/P outputs are 01101001 and 11000011. Now we XOR both of these to get 11010111 and 01101001. Lets put the first one through the S-boxes. S0(1101) = (row 3, column 2) = 11. S1(0111) = (row 1, column 3) = 11. So the output of the S-boxes is 1111. Do the same for the second to get: 1010. So the S-box outputs with this subkey for this ciphertext pair have an XOR difference of 0101. But we were expecting to get an XOR difference of 1110 so we can throw this subkey out. The subkey that doesnt get thrown out is the one that was used during encryption for out chosen plaintext/ciphertext pairs.
In a block cipher with more rounds we wouldnt be so sure what our expected XOR difference should be, but we would have a pretty good idea and we could do this same sort of thing probabilistically and pick the subkey that produced bad XOR differences the least.
Let's try a subkey of "10101111" with our second ciphertext pair. The outputs of E/P are the same, but then the inputs to the S-boxes are different because the subkey is different. Our new S-box inputs are 11000110 and 01101100. If we put these through the S-boxes we get 0111 and 1001. The XOR difference is 1110. This is the same as our expected XOR difference. If this subkey passes several such tests then we can be pretty sure that it is the right subkey for K3 that was used in encryption, which it is.
The reader might be wondering why it is necessary to use XOR differences between plaintext/ciphertext pairs instead of just using the actual plaintext/ciphertext values. The answer is that XOR differences propagate through DES more predictably than values. In 16-round DES we have no idea what might be used as input to the XOR4 in the last round, but we can make probabilistic guesses at what the XOR difference of this input might be. XOR differences propagate nicely through everything except for the S-boxes, and we can uses probabilities to get a handle on the S-boxes if there arent too many rounds. We would just have to build difference distribution tables for the S-boxes. XOR differences have no difficulty at all propagating through XORs and permutations.
Reduced round DES (7 or 8 rounds) does not stand up to differential cryptanalysis. 16-round DES does fine against differential cryptanalysis, though. Although differential cryptanalysis did not show up in the open literature until 1990, the designers of DES had it in mind when they designed the permutation P and the S-boxes. It is important to understand because any new proposed block cipher must be tested against differential cryptanalysis.
