Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The Cipher
3.
Basis Behind Differential Cryptanalysis
4.
When Can We Do a Differential Attack?
5.
Mounting a Differential Attack
5.1.
Finding a Differential Trail X-Y
6.
Frequently Asked Questions
6.1.
Is differential cryptanalysis still a useful method to attack ciphers?
6.2.
Do S-boxes always have input and output sizes the same?
6.3.
Don't we need to calculate the subkeys' original key at the end?
7.
Conclusion
Last Updated: Mar 27, 2024
Hard

Introduction to Differential Cryptanalysis

Author Satvik Gupta
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Cryptography is an essential tool in the modern day of networking. It helps keep our data secure when we send it over the Internet. To ensure that no attackers can get access to it, we need to make sure our cryptographic methods are secure.

Introduction to Differential Cryptanalysis

Cryptanalysis is a way to break ciphers. It's a way to read encrypted data without having access to the keys used to encrypt it. 

Differential Cryptanalysis is one way to do this. It is generally used for block ciphers, although we can also apply it to stream ciphers. It was proposed in the 1990s and broke many ciphers of that time. Let's understand how it works.

The Cipher

Before we look at how differential cryptanalysis works, let us see the cipher we will use in the rest of this article.

Instead of using a specific cipher, we will use a generic l-bit, r-round cipher. This means that the cipher operates in r rounds and uses l-bit keys and l-bit data. We are assuming that this is a symmetric cipher - i.e., the same key is used for encryption and decryption.

Cipher Description Diagram

The cipher uses a key K. A Key Scheduling Algorithm takes the key K and converts it into R subkeys. Generally, the size of the subkeys is smaller than the size of the key K. For example, DES(Data Encryption Standard) converts a 64-bit key to 48-bit subkeys.

Each key is used in each round. F1, F2, F3, etc., specify the encryption functions of each round. Each encryption function, Fi, also has a corresponding decryption function, Fi-1, that performs the steps in Fi in reverse. The output of each round is used as the input for the next round. Thus, the inputs and outputs of each round are the same in size. 

These functions can be anything. However, a common pattern in ciphers is using key-mixing and S-boxes. Key mixing involves XORing an input with a key.

For example, key mixing in round one would XOR the plaintext with K1. The second round would XOR the output of F1 with K2, and so on. 

S-boxes are substitution boxes that map a set of bits to a set of different bits.

For our example, we will assume the cipher uses some S-boxes and key-mixing techniques. However, differential cryptanalysis can be extended to other methods as well.

The key scheduling algorithm and encryption/decryption functions (including S-boxes) are made publicly available for standard ciphers. We will assume this is the case for our cipher as well. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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, x1 and x2, the differential is defined as 

x1 ⊕ x2.

The two main intuitions behind differential cryptanalysis are:

  • Differentials are unchanged by key mixing. If a and 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. 

Diagram of F and Fr producing ciphertext

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 =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 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 Kr of the last round. We will create a frequency table with all values of Kr. 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 Fr-1 with each value of Kr. We perform Fr-1 on p and q, using Kr as a key.

    Let us say Fr-1(Kr,p) = p' and Fr-1(Kr,q) = q'. 

    If p'⊕q' = Y, there is a chance that we have chosen the right key as Kr. 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 Kr, we will increment the frequency table of Kr 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. 

Previous article
What is Linear Cryptanalysis?
Next article
Can You Tell us What is the Difference Between Differential and Linear Cryptanalysis?
Live masterclass