Differential Cryptanalysis 101
Exploring Differential Methods in Block Ciphers
Cryptanalysis has been playing an essential role in the security of both software and hardware systems for decades and now more than ever. Many knows the essentials of cryptography through school, trainings or self learning, but very few know the ways of cryptanalysis, which is equally as important ! In this article, I will give you the basics to understand one of the widely known ways of analyzing block ciphers, Differential Cryptanalysis!
What is Cryptanalysis
Cryptanalysis is basically the ‘offensive’ side of cryptology. Cryptography focuses on building news ways of protecting data (encryption, integrity and authentication) while on the other hand, Cryptanalysis focuses on using and creating ways of attacking Cryptography. Both work hands in hands as to build reliable cryptography, cryptanalysis has to be performed.
Here we are going to focus on a specific subset of cryptanalysis that mainly focuses symmetric-key algorithms : Differential Cryptanalysis.
Symmetric-Key Algorithms
Description
A symmetric-key algorithm is a cipher that uses the same key both to encrypt and decrypt. It exist two main families for these algorithms : block ciphers and stream ciphers. The former operates on predefined size blocks (128 bits for example) of the plaintext and apply the cipher on each block, while the latter operates bit by bit. Here we will mainly focus on Block Ciphers.
Sources of security in Block Ciphers
All algorithms used in modern block ciphers follow the Kerchoffs’ principle. They are created to be secure by design and not by obscurity. Thus, we assume here that the cryptanalyst has full knowledge of the functioning of the algorithm and the only secret information is the secret key.
To provide security , symmetric ciphers rely on two major concepts : Diffusion and Confusion.
- Diffusion : One could describe this as the “avalanche effect”, it means that changing a single bit in the plaintext should have effect on a significant part of the ciphertext (ideally at least half the bits of the ciphertext).
- Confusion : This represent the process of making it hard for an attacker to know the relations between bits of the key and those of the ciphertext.
Construction of Block Ciphers
How are Confusion and Diffusion injected into the building blocks of symmetric ciphers ? Well, it depends on the construction. We have two main families of possible construction while building a block cipher :
- SPN (Substitution permutation network)
- Feistel Network
Here is a great illustration of the difference between the two :
Feistel Cipher on the left, SPN based Cipher on the right
More formally, we can explain the functioning of each structure like this :
Basics blocks that can be used both:
- Permutation Boxes : Pure bit shuffling following certain permutations.
- Substitution Boxes : Table to map bits or block of bits to other values.
In a Feistel Cipher :
- Let
Fbe the round function and K₀, K₁, …, Kₙ the subkeys for the n rounds. - Split the block plaintext into two blocks (L₀, R₀).
- For each round i, compute Lᵢ₊₁ = Rᵢ ; Rᵢ₊₁ = Lᵢ ⊕ F(Rᵢ, Kᵢ).
- Lᵢ and Rᵢ being respectively the left and right part of the current ciphertext after i-1 rounds.
- Your final ciphertext will be (Rₙ₊₁, Lₙ₊₁).
This is the basis of a Feistel Cipher, and what really makes a specific Feistel cipher like DES is the round function F which is the very heart of it. It is going to provide all the confusion and diffusion needed in this construction.
For instance, let’s take a look at the DES round function:
We see here the different important component to bring confusion and diffusion in the cipher construction at each round. Expansion P-boxes and P-boxes are responsible for increasing the diffusion and S-Boxes for increasing the confusion.
In a SPN-based Cipher:
- The SPN approach is basically just having a big round function that stacks layers of S-Boxes and permutations to provide diffusion and confusion. The substitution layers act on much smaller units of data. The most famous famous example of a SPN cipher is AES.
PS : You can notice that the F round function of Feistel Networks are small SPNs.
What is Differential Cryptanalysis ?
Differential ?
Within modern cryptanalysis of symmetric-key algorithms exist various ways of proceeding depending on your target cryptosystem or the attack model for example.
Doing Cryptanalysis on block ciphers means searching for a mean to recover at least partially or totally the private key given an attack model. Technically, a brute force attack is cryptanalysis. A terribly inefficient one in most cases but still valid. Known efficient techniques of cryptanalysis for Symmetric-Key algorithms in general are Linear attacks, Differential attacks, Integral attacks, Algebraic attacks …
Here we consider the CPA (Chosen Plaintext Attack) model.
Let’s have a very brief overview of the two most popular methods before focusing on one : Differential attacks and Linear attacks.
Linear cryptanalysis mainly focuses on finding and exploiting frequent linear relations between plaintext, ciphertext and the subkeys. If a relation shows a high probability of holding then it shows poor functioning of the internal capabilities from the cipher and may be exploited. So usually the process is :
- we construct multiple linear approximations (for the S boxes for example) to have one that approximately represent the whole cipher
- we extract information on subkeys once we have a sufficiently probable approximations over a certain number of rounds
Differential cryptanalysis on the other hand focuses on analyzing how differences in plaintext pairs propagate through the cipher and studying their corresponding ciphertext differences.
If we can find pairs of inputs with a specific difference that lead to a predictable output difference with high probability, we can potentially recover key information. The process for Differential cryptanalysis would be :
- Analyzing cipher structure
- Constructing input differences on our plaintexts
- Passing plaintexts through the cipher
- Constructing output differences from out ciphertexts
- Finding how probable a given output difference is, given an input difference.
- Choosing specific plaintexts to hold probable input differences in order to reduce key possibilities at maximum.
The association of an input difference to an output difference is called a differential , hence the name of the attack.
A Practical Example
Let’s do an application of Differential Cryptanalysis on a very simple cipher:.
with the S-box being :
sbox = [3, 14, 1, 10,
4, 9, 5, 6,
8, 11, 15, 2,
13, 12, 0, 7]
4, 9, 5, 6,
8, 11, 15, 2,
13, 12, 0, 7]
So it gives this mapping :
0 -> 3
1 -> 14
2 -> 1
3 -> 10
4 -> 4
5 -> 9
6 -> 5
7 -> 6
8 -> 8
9 -> 11
10 -> 15
11 -> 2
12 -> 13
13 -> 12
14 -> 0
15 -> 7
Now let’s follow our process with additional information:
First, analyzing the cipher structure. Here the cipher is a simple SPN with 2 rounds that takes nibble sized blocks with an 8 bits key that is separated in two subkeys.
However, with the known information , we can eliminate the very last operation as we can have access to the s-box it does not provide any additional security (we know the s-box). So we’re left with this cipher :
Next, constructing our differentials characteristics. Basically this means computing all possible xor between two nibble inputs to the S-box, passing each pair of inputs to the S-box and computing the xor of the pair of output.
Throughout the process we build an histogram of possible differentials.
Finally the suitable differentials will be the highest values in our histogram.
In our case we get 4:7 appearing 6 times. 4 being the input difference and 7 the output difference.
Now we can start the fun part . We need to find all possible pairs of plaintext that match this differential. There are 6 possible values that we know from our step where we computed our differentials. Here we use 5,1.
Let’s explain what is happening here.
On both sides of the input of the S-Box, we put the possible values out of the 6 that can produce our differential. Notice that the XOR with the key keeps the differential because (a⊕k)⊕(b⊕k)=a⊕b.
So here, we know the input plaintexts and would like to know the values of K₀ and K₁. To get the value of K₁, we only need to have the value of K₀ because of the construction (we know the S-Box and the output), and to get the value of K₀, we only need to know the input of the S-Box. Now guess what? Computing the differentials left us with only 6 possible values at the entry of the S-Box. Then, we just have to take at most 6 guesses to get a probability of 6/16 (number of occurrences of the differential / number of differentials) of recovering the key with a single chosen plaintext pair. In this case, just a few pairs are sufficient to get a 100% success rate in getting the key.
So we can clearly see that instead of having to test the 2⁸ possible keys (2⁴ with a smarter brute force), we are only left with a few possibilities (6) in each case, which is a drastic improvement.
Applications on modern Block ciphers
This method has been proven as one of the most efficient to evaluate security of block ciphers throughout the time . The most famous example of a modern cipher broken by this attack is the FEAL block cipher (which was originally proposed as an alternative to DES). FEAL-4, FEAL-6 and FEAL-8 were broken with this attack with only respectively 1000,10000 and 2^15 known plaintexts.
Conclusion
Differential cryptanalysis demonstrates how seemingly secure ciphers can be broken through simple analysis rather than brute force. As shown in our practical example, with a very simplified way of doing differential cryptanalysis, this technique significantly reduces the keys possibility required to crack a block cipher. Understanding this technique and its variants helps properly evaluating cryptographic security and reinforces the modern constructions of block ciphers.
Sources
Matteo Ahouanto / @fr0mars_
Patrick Ventuzelo / @Pat_Ventuzelo
About Us
Founded in 2021 and headquartered in Paris, FuzzingLabs is a cybersecurity startup specializing in vulnerability research, fuzzing, and blockchain security. We combine cutting-edge research with hands-on expertise to secure some of the most critical components in the blockchain ecosystem.
Contact us for an audit or long term partnership!
