Introduction to Differential Cryptanalysis

Basis Behind Differential Cryptanalysis

Differential Cryptanalysis is a chosen plaintext attack. This means - we have access to the complete function. We can use it to generate ciphertext for any plaintext of our choice. However, we cannot see the keys that are being used. 

Chosen Plaintext attacks use a carefully chosen input selection to gain information about the keys being used. 

In differential cryptanalysis, we use a differential to try to find something about the keys. 

For two inputs, x₁ and x₂, the differential is defined as 

x₁ ⊕ x_2.

The two main intuitions behind differential cryptanalysis are:

• Differentials are unchanged by key mixing. If a and b are two different inputs, and a' and b' are obtained on key-mixing with them, then: 
   

a⊕b = a'⊕b'

This can be easily proven. Let the key be k. 

a' = a⊕k

b' = b⊕k

a'⊕b' = (a⊕k)⊕(b⊕k) 

    = a⊕b⊕k⊕k
 

       = a⊕b

• S-boxes are not perfect. It is possible to statistically predict input-output pairs if we know the differentials of the inputs and outputs. 

When Can We Do a Differential Attack?

Let us merge the first R-1 Rounds are a single function - F. Let a and b be two inputs to F, that produce the outputs a' and b'. This situation is shown below. 

Let's say 

       a⊕b   =  X

and a'⊕b'  = Y

If we can find a value of X and Y such that this property holds in high probability for multiple values of a and b, then we can mount a differential attack. 

In other words,

For all inputs a and b that have an XOR of X - their outputs of the F function (a' and b') should have an XOR of Y with high probability (More than 50%). The output differential should be Y, with a high probability of input differential X. 

For example, let X = 5. Let's assume we are dealing with 3-bit numbers.

Many pairs of inputs will have an XOR of 5: (0,5), (4,1), (7,2), and (3,6).

Let us assume the F function transforms these into (1,2),(0,3),(2,0) and (4,7). 

The XORs for the outputs would be - 3,3,2 and 3. 

We can see that XOR value of 3 occurs with a high probability (75%). Thus, we can say we have found an X-Y pair, which is known as a differential trail. If such a pair did not exist, we would not be able to perform a differential attack against this cipher.

Mounting a Differential Attack

To mount a differential attack, a pair X,Y must exist as described in the previous section. 

Finding a Differential Trail X-Y

Standard algorithms are publicly available. Hence, we will have access to the functions, such as S-boxes, that are being used in the ciphers. So, we can create a simple frequency table. 

Let us assume that the S-boxes are operating in 4 bits - i.e, 16 possible X and Y values.

• Create a 16x16 table (or whatever size is necessary for your particular case). We are using size 16 in the rest of the steps. It should be followed for the size of your cipher.
   
• Choose an input value x from 0-15. Choose any input string a, and calculate b =a⊕x. a⊕b will now be equal to x. 
   
• Calculate the outputs of the S-box for a and b, say a' and b'. Find out a'⊕b'. Let a'⊕b' = y. Increase the count in the cell (x,y) in the table by one.
   
• Repeat for all values of x and sufficient values of input string a. We repeat until we get a majority in the frequency table. The values corresponding to the majority cell are our values for differential trail X-Y.
   

After calculating the differential trail, we perform the attack. The attack should follow the following steps.

• Choose a plaintext string a. We will repeat the attack for multiple input strings until we get a satisfactory result. Weaker algorithms need only a few input strings to break, while stronger algorithms will require many. 
   
• Calculate b as a⊕X. a⊕b will now be equal to X. 
   
• Pass a and b through the cipher. We will get the final ciphertext, say p and q respectively. p and q are the results of R rounds.
   
• We know that there is a high probability that the result of R-1 rounds will have a differential of Y. This is because our input strings have a differential X, and X-Y is a differential trail. 
  We assume a key K_r of the last round. We will create a frequency table with all values of K_r. We will choose multiple inputs of a and b, so we get multiple values of p and q.
   
• We will decrypt the ciphertexts p and q using F_r^-1 with each value of K_r. We perform F_r^-1 on p and q, using K_r as a key.
  
  Let us say F_r^-1(K_r,p) = p' and F_r^-1(K_r,q) = q'. 
  
  If p'⊕q' = Y, there is a chance that we have chosen the right key as K_r. This is because Y is the expected differential of R-1 rounds, which is the value we get. Every time p'⊕q' = Y for key K_r, we will increment the frequency table of K_r by 1. 
   
• Eventually, we will be able to get a key that has a higher frequency than all the other keys. This will be our actual key for the Rth round. 
   
• We can recursively compute the keys in (R-1)^th round,(R-2)^th round,etc. This way, we will get all the subkeys. 
   

Once we have all the subkeys, our cipher has successfully been broken.

Frequently Asked Questions

Is differential cryptanalysis still a useful method to attack ciphers?

Most modern ciphers, such as AES, are not vulnerable to differential cryptanalysis. This is a known technique, hence it is taken care that ciphers are not vulnerable to it. However, old ciphers such as DES can still be attacked using it.

Do S-boxes always have input and output sizes the same?

No, this is not always true. S-boxes are m to n, where m is not always equal to n.

Don't we need to calculate the subkeys' original key at the end?

Having the subkeys is actually enough to perform any encryption and decryption tasks. The key is only used once in most ciphers to generate the subkeys. Once that is done, the key has no further role. The subkeys perform the encryption-decryption tasks by themselves.

Conclusion

This blog has explored differential cryptanalysis, its basis, when it can be applied, and how we can mount a differential attack.

We hope you leave this article with a broader knowledge of ciphers, cryptography, and cryptanalysis. We recommend that you explore our different articles on these topics as well, such as:

What is Cryptography and why do we use it?

Cryptanalysis of Substitution Cipher

What are Basic Cryptography Tools?

You can practice questions on various problems on Coding Ninjas Studio, and attempt mock tests. You can also go through interview experiences, interview bundle, go along guided paths for preparations, and a lot more!

Keep coding, keep reading Ninjas.