# Linear Approximation Table of S-Box for SPN

I havejust gotten to Linear Cryptanalysis and I'm studying some material on Linear Attack's against SPN.

I see here http://www.cs.bc.edu/~straubin/crypto2017/heys.pdf on page 11

that they calculate the Linear Approximation Table but I am completely lost how they got the values in the table.

Could someone give me an example of how one of those values are calculated? I understand it has something to do with the bias, but I have yet to see any actual example of someone calculating a value in that table which I would like to see.

In Howard Heys' tutorial, the S-box $S$ maps 4 bits to 4 bits. It is defined by the following lookup table:

x    | 0 1 2 3 4 5 6 7 8 9 a b c d e f
S(x) | e 4 d 1 2 f b 8 3 a 6 c 5 9 0 7


This can be split in 4 Boolean component functions, by considering the output bits separately. Here, the subscript 1 refers to the least significant bit:

x      | 0 1 2 3 4 5 6 7 8 9 a b c d e f
S(x)   | e 4 d 1 2 f b 8 3 a 6 c 5 9 0 7
S_1(x) | 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1
S_2(x) | 1 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1
S_3(x) | 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1
S_4(x) | 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0


The bias of a Boolean function expresses how 'imbalanced' a function is. In other words, how far away it is from a balanced function, i.e. one that is as often 0 as it is 1. The bias $\mathcal{E}$ of an $n$-bit Boolean function $f$ can be computed using:

$\mathcal{E}(f) = \sum_{x\in\mathbb{F}_2^n} (-1)^{f(x)} = 2^n - 2\mathrm{hw}(f)$.

Here, $\mathrm{hw}$ denotes the Hamming weight of a function, i.e. the number of times a 1 appears. For example, $S_1(x)$ has a bias of 0, but $S_4$ has a bias of 2, as its Hamming weight is 7.

Linear cryptanalysis exploits the most biased linear relation between its input and output. However, it doesn't only consider the full input and the full output, but sums of specific bits are selected in both the input and the output that have a strong bias. These bits are selected using masks $a,b$. The masks have a 1 for the bits that we want to consider and a 0 otherwise.

For any pair of masks $a,b$, the linear approximation table (LAT) contains the bias of $S_b + \varphi_a$, where $\varphi_a$ maps $x$ to $ax$. (The bias of this value is also often referred to as the Walsh coefficient of $S_b$ at $a$.)

Now for a concrete example: take $a = 12$, or $1100$ in binary, and $b = 1$, or $0001$ in binary. Then $\mathcal{E}(a,b) = \mathcal{E}(\varphi_a + S_b(x)) = \mathcal{E}(x_3 + x_4 + S_1(x))$. Because this is math in $\mathbb{F}_2$, these $+$'s should be read as XORs.

x      | 0 1 2 3 4 5 6 7 8 9 a b c d e f
----------------------------------------
x_3    | 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x_4    | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
S_1(x) | 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1
------------------------------- +
0 0 1 1 1 0 0 1 0 1 1 1 1 1 0 1


The bottom row has a Hamming weight of 10, so $\mathcal{E}(a,b) = 2^4 - 2*10 = -4$.

Now if you look at the tutorial on page 11, there is actually the value $-2$ for an input sum of 0xC and an output sum of 1. This might have caused some confusion. Sometimes, all values are already divided by 2. Then it corresponds better to the probability, as the probability is now simply the number in the LAT divided by 16. It is a matter of definition whether you prefer to have $+16$ in the top left ($a = 0, b = 0$) or $+8$, although I guess the latter is more common.

If you prefer to look at Python code, a very simple script (not mine) that computes the LAT can be found here.

• This code you linked gives the second category, right ($+8$ instead of $+16$)? – hola Sep 19 '18 at 19:52