Cryptanalysis is the process by which we analyze information to gain access to the hidden aspects of a system. In simple words, through cryptanalysis, even if we don't know the secret cryptographic key, one can breach the system to understand the encrypted messages.
To get the most out of this blog, you must be well-equipped with linear cryptanalysis and SPN(Substitution-Permutation Networks). So, do check out these blogs, and let's move ahead. In this article, we will learn how to launch a linear attack on an SPN.
Meaning Of Linear Attack On SPN
By linear attack, we mean that our goal is to recover the encryption key by breaking the SPN(Substitution-Permutation Networks) cipher through linear cryptanalysis.
First, let's see what does an SPN do?
An SPN takes plaintext blocks as input and combines them with a secret key to generate cipher text blocks as the output by applying many alternating rounds of substitution boxes and permutations.
The main goal of an SPN is to hide the linear relationships between plaintext and cipher text by using multiple rounds of substitution and permutation.
So, when the S-box is weaker or imperfect, it becomes easy to find useful linear approximations that help find the encryption key bits.
A linear attack on an SPN aims to find enough XOR equations between the bits of the plaintext, ciphertext, and key bits (the target variable we need to find) to find the key.
Let's understand this with an example of one such relationship.
Say, the XOR of the 2nd bit of plaintext, 4th bit of key, and 1st bit of ciphertext yields 1.
P2 ⊕ K4 ⊕ C1 = 1
A more formal term for this attack is linear cryptanalysis, which finds a set of linear approximations of S-boxes that can be used to derive a linear approximation of the entire SPN (excluding the last round).
Linear Attack On SPN
The following SPN will be used for illustrating the attack:
Here, l=m=N=4.
πS(z) and πP(z) are as shown below:
The structure of the linear approximation of the SPN that we will use is shown below:
The process of the linear attack is as follows:
In the above figure, the arrow lines point to the random variables involved in the linear approximation.
This approximation consists of four active S-boxes:
In S12 , the random variable T1 = U1 5 ⊕ U1 7 ⊕ U1 8 ⊕ V1 6 has bias ¼
In S22 , the random variable T2 = U2 6 ⊕ V2 6 ⊕ V2 8 has bias −1/4
In S32 , the random variable T3 = U3 6 ⊕ V3 6 ⊕ V3 8 has bias −1/4
In S34 , the random variable T4 = U3 14 ⊕ V3 14 ⊕ V3 16 has bias −1/4
We assume that these 4 random variables are independent and hence using the piling-up lemma we can find the bias of their xor.
The random variable T1 ⊕ T2 ⊕ T3 ⊕ T4 will have bias = 23 (1/4)(−1/4)3 = −1/32.
The value of T1 ⊕ T2 ⊕ T3 ⊕ T4 can be expressed in terms of the plaintext bits, the bits of u4, and the key bits.
From the above figure, the following relations exist:
On computing the xor value of RHS in the above relation, we find that the bias of the random variable X5 ⊕ X7 ⊕ X8 ⊕ V 3 6 ⊕ V 3 8 ⊕ V 3 14 ⊕ V 3 16 ⊕ K 1 5 ⊕ K 1 7 ⊕ K 1 8 ⊕ K 2 6 ⊕ K 3 6 ⊕ K 3 14 is -1/32.
Next, we replace all V3i in the above expression in terms of U4i and further key bits in the following way:
On substituting the above 4 expressions in the 7th equation, we get:
Assuming that the key bits are fixed, we can say that the value of the random variable is fixed 0 or 1.
Accordingly, the bias of the random variable shown below is ±1/32.
We see that the bias is bounded away from 0, hence we can carry out a linear attack.
Consider that we have T plaintext-ciphertext pairs and all of them use the same unknown key, K. Let's refer to these T pairs by W.
It is known that T should be approximately 8000 for the linear attack to be successful.
We can obtain the eight key bits in K 5 <2> and K 5 <4>, namely, K 5 5, K 5 6, K 5 7, K 5 8, K 5 13, K 5 14, K 5 15, and K 5 16 through the attack. These are the eight key bits that are XORed with the output of the S-boxes S 4 2 and S 4 4.
Now, there are 2^8 = 256 possibilities for the list of 8 key bits. Any binary 8-tuple is referred to as the candidate subkey.
For each (x, y) ∈ W and for each candidate subkey, we can compute partial decryption for y and obtain the resulting value for u 4 <2> and u 4 <4>.
Then the value of the random variable shown in point 11 can be computed.
We construct an array of counters of size 256 corresponding to the 256 candidate subkeys, where each index value is incremented whenever the equation in point 18 is 0.
At last, most of the counter values will be approximately T/2. The subkey having a counter value of approximately T/2 ± T/32 will be our correct candidate subkey allowing us to identify the eight subkey bits.
In the next section, we will see the algorithm🧾 for the linear attack.
Algorithm for Linear Attack On SPN
Let's understand the meaning of the variables used in this algorithm:
T represents the set of T plaintext-ciphertext pairs which we use in the linear attack.
The values of the variables L1 and L2 are hexadecimal in nature.
πS −1 refers to the permutation for the inverse of the S-box.
Finally, the maxkeyrepresents the eight subkey bits that we find in the attack.
Our goal is to compute the value of x5 ⊕ x7 ⊕ x8 ⊕ u 4 6 ⊕ u 4 8 ⊕ u 4 14 ⊕ u 4 16 for every pair (x,y) E T and for every possible candidate subkey (L1, L2).
The steps of the algorithm are as follows:
At first, the xors L1 ⊕ y<2> and L2 ⊕ y<4> are computed, and when (L1, L2) is the correct subkey, it gives us v 4 <2> and v 4 <4>.
Inverse S-box πS −1 then computes u 4 <2> and u 4 <4> from v 4 <2> and v 4 <4>. We get the correct values when (L1, L2) is the correct subkey.
Whenever the value of x5 ⊕ x7 ⊕ x8 ⊕ u 4 6 ⊕ u 4 8 ⊕ u 4 14 ⊕ u 4 16 is 0, the counter of the pair (L1, L2) is incremented.
Finally, the output of the above algorithm is nothing but the pair (L1, L2) having the maximum value of the counter.
Frequently Asked Questions
What are linear attacks?
Linear cryptanalysis is a known plaintext attack in which the attacker studies probabilistic linear relations (called linear approximations) between parity bits of the plaintext, the ciphertext, and the secret key.
What are substitution and permutation in cryptography?
Substitution replaces plaintext letters or strings of letters with letters or numbers, or symbols. Permutation uses plaintext message letters but rearranges their order.
Is substitution cipher symmetric or asymmetric encryption?
Substitution ciphers are examples of symmetric encryption because they use the same key for encryption and decryption.
Conclusion
In this article, we learned about launching a linear attack on an SPN. We started with a very brief introduction to SPN, the objectives of a good SPN, and we understood the meaning of linear attack. Finally, we learned the algorithm for the linear attack.
We hope this blog has helped you enhance your knowledge regarding the linear attack on an SPN.
8+ registered 