Approximations of S-boxes linearly in Cryptography

Linear Approximation of S-boxes

Consider an S-box that:

• Takes a binary string of length m as input.
   
• Outputs a binary string of length n.
   
• m may or not be equal to n.
   

Let us take an input string X = (x₁,x₂,.....x_m). For each x_i, there is a random variable X_i that can take the values 0 or 1. Since we are equally likely to choose 0 or 1, the bias of X_i is 0. Also, all the X_i variables are independent of each other.

Similarly, we define an output string Y = (y₁,y₂,.....y_n). There are n random variables Y_i that can be 0 or 1. However, the bias of Y_i may or may not be 0, and they may or may not be independent of each other. That will depend on the S-box. 

Let us take an example. 

Consider the following S-box. 

It takes a binary input of length 4 and outputs a binary string of length 4. For simplicity, the binary strings are represented in hexadecimal form. 

The table below shows the value of the random variables X_i and Y_i for all possible cases.

Let's say we want to find the bias of the random variable X₁ ⊕ X₄ ⊕ Y₂ . Bias is useful because when the value of bias is away from zero (i.e, the random variable tends to bias towards certain values, compared to others), then we can launch a linear attack. A perfect random variable would have a bias of zero, which means it is equally likely to hold any possible value.

We can do calculate the bias by counting the number of rows in which this variable is 0, and dividing by 16(the total number of rows in the table). This will give us p_i for this variable, and using that, we can easily calculate bias. 

The number of rows in which  X₁ ⊕ X₄ ⊕ Y₂ =0 is 8. 

Therefore, the probability of it being 0 = 8/16 =1/2.

This makes the bias as 0. 

In this way, we can calculate the bias of all random variables. 

Let us represent the random variables in this format: 

 a₁X₁ ⊕ a₂X₂ ⊕ a₃X₃ ⊕ a₄X₄ ⊕ b₁Y₁ ⊕ b₂Y₂ ⊕ b₃Y₃ ⊕ b₄Y₄ 

Where a_i and b_i can be 0 or 1. 

This may seem confusing. But it's simply a way of representation. 

For example, in our earlier example,, we took the random variable X₁ ⊕ X₄ ⊕ Y₂. 

To represent it in the new format, we would simply take a₁=1, a₄=1,b₂ =1, and all the other values of a_i and b_i as 0. This gives us a common representation for all random variables. 

It also allows us to create the Linear Approximation Table for an S-box. The binary value of (a₁,a₂,a₃,a₄) gives the row number. This is also called the input sum. The binary value of (b₁,b₂,b₃,b₄) gives the column number. This is also called the output sum. The value in the table with that row and column will be the number of rows in which that random variable is equal to zero. Since we have binary string of length 4, we will represent it in hexadecimal for simplicity. 

For example, in our earlier example:

a₁ =1, a₂₌0, a₃ =0, a₄₌1.

The input sum will be (1,0,0,1), which is 9 in hexadecimal. 

b₁ =0, b₂₌1, b₃ =0, b₄₌0.

The output sum will be (0,1,0,0), which is 4 in hexadecimal. 

The number of rows with  X₁ ⊕ X₄ ⊕ Y₂ =0 is 8. 

The input sum (9 in our case) gives the row. The output sum (4 in our case) gives the column. Thus, the value at row number 9 and column number 4 of our table will be 8.

Similarly, we can calculate the same for all other values. The complete table is given below. 

Frequently Asked Questions

Do S-boxes perform only permutations?

No, S-boxes can transform the data using any method. It is possible that they do a permutation, but it is not necessary. In fact, for S-boxes where m and n are different, it is impossible that the S-box does a permutation.

Where is the Linear Approximation Table used?

The linear approximation table can be used to find out the bias for certain inputs and outputs. A bias means that the random variable is more likely to take on some values as compared to others.This is useful during the Linear cryptanalysis attack.

What is linear cryptanalysis?

Linear cryptanalysis is a known plaintext attack on ciphers. It involves looking at probabilistic linear relationships between the plaintext and the ciphertext to find weaknesses. We try to find out the probability that a particular plaintext will produce a certain ciphertext.

Conclusion

This blog has explored approximation of S-boxes linearly in Cryptography. We have seen the basic probability and statistics required for it. We have looked into bias, and constructed the linear approximation table for an example S-box.

If you liked this article, check out our other articles on Cryptography:

• 💡What is Cryptography?
• 💡Cryptography digital signature.
• 💡What is Linear Cryptanalysis

You can practice questions on various problems on Coding Ninjas Studio, 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.