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 Algorithms, Competitive Programming, System 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!!
84+ registered