Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Linear Cryptanalysis?
3.
How does Linear Cryptanalysis work?
3.1.
Example
4.
The Piling-up lemma
4.1.
Derivation
5.
Frequently Asked Questions
5.1.
What do you mean by Bias of a random Variable?
5.2.
What is the Piling-up lemma?
5.3.
What is a Block Cipher?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

What is Linear Cryptanalysis?

Author Nidhi Kumari
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The two components of cryptology are cryptanalysis and cryptography. Cryptosystems encrypt and decrypt information using cryptographic algorithms, or cyphers, to secure communications between computer systems, devices, and applications.

Cryptography focuses on creating secret codes, and cryptanalysis studies the cryptographic algorithm.

In this article, we will learn about Linear Cryptanalysis. Further, we will discuss the Piling-up lemma in Linear Cryptanalysis.

What is Linear Cryptanalysis?

What is Linear Cryptanalysis?

Matsui introduced linear cryptanalysis as a powerful cryptanalysis technique of block ciphers in 1993. Linear cryptanalysis is a known plaintext attack(KPA). It involves the attacker looking at probabilistic linear relationships between the parity bits of the plaintext, the ciphertext, and the secret key.

  • ☑️ Plaintext: Plaintext is typically readable text in the basic form before converting it into ciphertext or readable text decrypted. 
     
  • ☑️ Ciphertext: Ciphertext is plaintext encrypted using a cryptographic algorithm.
     
  • ☑️ Secret key: The information is shared between the sender and receiver of encrypted data and is encrypted and decrypted using a secret key.
Linear Cryptanalysis

In this method, the attacker computes the parity bits of the known plaintexts and ciphertexts to obtain high-probability approximations for the parity bit of the secret key. The attacker can extend the attempt to find additional bits of the secret key by using a number of approaches, including the auxiliary technique.

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

How does Linear Cryptanalysis work?

In general, linear cryptanalysis consists of two steps. 

💡 Step 1: Create a linear equation.

The first step is to create linear equations with a significant bias related to plaintext, ciphertext, and secret key bits, meaning that their probability of holding is as close as possible to 0 or 1.
 

💡 Step 2: Drive secret key bits.

The second step is that these linear equations be used to drive secret key bits along with known plaintext-ciphertext combinations.

Example

Consider a known-plaintext attack in which the attacker has a large collection of plaintext-ciphertext pairings that are all encrypted with the same secret key K. We will start by employing all potential secret keys for the last round of the cypher to decrypt the ciphertext for each pair of plaintext and ciphertext.

We calculate the values of the relevant state bits involved in the linear equation for each secret key and then check to see if the linear relationship is still valid. We increase a counter for the specific secret key every time it does. 

We predict that after this procedure, the candidate key whose frequency count is farthest from 1/2 times the number of plaintext-ciphertext pairs will include the correct values for these key bits.

To explain the attack's strategies, we must verify several probability theory results. 

The Piling-up lemma

The piling-up lemma is a cryptanalysis principle applied to linear cryptanalysis to create linear approximations to block cipher actions. 

A block cipher is a method. A block cipher encrypts data in blocks to create ciphertext using a cryptographic key and algorithm.

According to the lemma, the bias of a linear Boolean function (XOR-clause) of independent binary random variables is correlated to the product of the input biases.

On the other hand, the input variables are not independent if the lemma does not hold.

Derivation

Assume that X1, X2,... are independent random variables that only accept values between 0 and 1.

Consider p1, p2,... to be real values such that 0 ≤ pi ≤ 1 for all i.

Also, Pr[Xi = 0] = pi and Pr[Xi = 1] = 1 − pi.

Let's assume that i ≠  j. Since Xi and Xj are independent:

  • Pr[Xi = 0, Xj = 0] = pi pj.
     
  • Pr[Xi = 0, Xj = 1] = pi(1 − pj).
     
  • Pr[Xi = 1, Xj = 0] = (1 − pi)pj and
     
  • Pr[Xi = 1, Xj = 1] = (1 − pi)(1 − pj).
     

After that, consider the discrete random variable Xi  ⊕ Xj (also known as Xi + Xj mod 2). It is clear that the probability distribution for Xi ⊕ Xj is as follows:

Pr[Xi ⊕ Xj = 0] = pi pj + (1 − pi)(1 − pj)

Pr[Xi ⊕ Xj = 1] = pi(1 − pj) + (1 − pi)pj

The bias of the distribution is frequently used to express a probability distribution of a random variable with values between 0 and 1. The quantity Єi = pi- 1/2 is used to define the bias of Xi.

 

Consider the following details: 

For -1/2 ≤ Єi ≤ 1/2,

Pr[Xi = 0] = 1/2 + Єi and Pr[Xi = 1] = 1/2 - Єi, respectively, for i = 1, 2,... The piling-up lemma refers to the following conclusion, which provides a formula for the bias of the random variable Xi1⊕…..⊕Xik.

[1] Let the bias of the random variables Xi1⊕…..⊕Xik is denoted by Єi1, i2, i3……..ik then,

Єi1, i2, i3……..ik =  2k-1  ∏Єij for j = 1 to k.

[2] Let the bias of the random variables Xi1⊕…..⊕Xik is denoted by Єi1, i2, i3……..ik and Єij = 0 for some j. Then, Єi1, i2, i3……..ik = 0.

 

For example:

Take independent random variables X1 and X2.

Let Pr[X1 = 0] = p1 => Pr[X1 = 1] = 1 - p1 

and  Pr[X2 = 0] = p2 => Pr[X2 = 1] = 1 - p2.

Therefore, Pr[X1 ^ X2 = 0] = p1p2 + (1-p1)(1-p2).

 

Now, let the bias values of the random variables:

Є1 = p1 - 1/2 and Є2 = p2 - 1/2

Hence, Pr[X1 ^ X2] = 0 = 2 * Є1Є2.

Frequently Asked Questions

What do you mean by Bias of a random Variable?

The bias of the distribution is frequently used to express a probability distribution of a random variable with values between 0 and 1. It has to do with the uniform probability of certain values. Bias is the idea that some values are more likely to show up than a random distribution would expect.

What is the Piling-up lemma?

The piling-up lemma is a cryptanalysis principle applied to linear cryptanalysis to create linear approximations to block cipher actions. According to the lemma, the bias of a linear Boolean function (XOR-clause) of independent binary random variables is correlated to the product of the input biases.

What is a Block Cipher?

A block cipher is a method. A block cipher encrypts data in blocks to create ciphertext using a cryptographic key and algorithm. We require a block cypher mode of operation to encode and decode messages of any size and content without leaving ourselves vulnerable to attack.

Conclusion

We discussed Linear Cryptanalysis and how it works with an example. Further, we discussed the Piling-up Lemma and the derivation of the formula for bias of the random variables in the Piling-up Lemma.

We hope this blog has helped you. We recommend you visit our articles on different topics of Cryptography, such as

🔥 What is Cryptography?

🔥 Cryptographic System.

🔥 Cryptosystem.

If you liked our article, do upvote our article and help other ninjas grow.  You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more!

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!!

Happy Reading!!

Previous article
Substitution-Permutation Networks(SPN) in Cryptography
Next article
Introduction to Differential Cryptanalysis
Live masterclass