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_{1} and x_{2}, the differential is defined as
x_{1} âŠ• 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 keymixing 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
 Sboxes are not perfect. It is possible to statistically predict inputoutput pairs if we know the differentials of the inputs and outputs.
When Can We Do a Differential Attack?
Let us merge the first R1 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 3bit 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 XY 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 XY
Standard algorithms are publicly available. Hence, we will have access to the functions, such as Sboxes, that are being used in the ciphers. So, we can create a simple frequency table.
Let us assume that the Sboxes 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 015. Choose any input string a, and calculate b =aâŠ•x. aâŠ•b will now be equal to x.

Calculate the outputs of the Sbox 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 XY.
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 R1 rounds will have a differential of Y. This is because our input strings have a differential X, and XY 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 R1 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 (R1)^{th} round,(R2)^{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 Sboxes always have input and output sizes the same?
No, this is not always true. Sboxes 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 encryptiondecryption 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.