Linear approximation table

Masks

Before we proceed with analysing an S-Box, we need a more concise and practical way of writing down linear approximations. This is the role of a (linear) mask.

Formally, suppose we have a Boolean function that takes as input an $n$-bit input vector $(x_0, \ldots, x_{n-1})$. We define a mask $\alpha = (\alpha_0, \ldots, \alpha_{n-1})$ as an $n$-bit vector such that each $\alpha_i \in {0,1}$. More often, we'll be interested in the dot product of the mask and the vector, expressed as: $$\alpha \cdot x = \bigoplus_{i=0}^{n-1} \alpha_i x_i$$ A mask just isolates which bits we consider "active", discarding the rest. Programmatically, it is the Boolean vector by which we may AND our vector.

As an example, the input and output masks $\alpha = {0, 0, 1, 0}$ and $\beta = {1,0,1,1}$ for a 4-bit Boolean function (e.g. PRESENT's S-Box) represent the following approximation: $$ x_2 = y_0 \oplus y_2 \oplus y_3 $$

The LAT

Thus far, we've been using bias and correlation to estimate our approximations, preferring it over raw probability. All of these stem from a more fundamental expression: the number of solutions, which is just for how many cases does the approximation hold for.

For a Boolean function $f$, a given input mask $\alpha$ and output mask $\beta$, we can formally write down the bias as $$\varepsilon_{\alpha, \beta} = \Pr[\alpha \cdot x = \beta \cdot f(x)] - \frac{1}{2}$$ and with $s$ we label the total number of solutions (i.e. inputs) for which the equality holds. $$ s = #{x\ |\ \alpha \cdot x = \beta \cdot f(x) } $$ One idea for representing the linearity of an S-Box may be to simply list out the total count of solutions. We prefer not to do this as, among other reasons, it doesn't capture the idea that an approximation having few solutions is as good as one having many. Instead, we have 0 be the worst i.e. random approximation, and have our "good" values go into the positives, and our "bad" values into the negatives. That is, we center our values around the expected average. This'll be made clear in a moment.

Similar to the Difference Distribution Table (DDT) for differential cryptanalysis, we now define the Linear Approximation Table (LAT) for linear cryptanalysis. The formula for computing it is $$ \text{LAT}[\alpha][\beta] = s - 2^{n-1} = 2^n \epsilon = 2^{n-1}\textbf{corr} $$ where $n$ is the input size of our Boolean function (in the case of PRESENT's S-Box, $n = 4$). Visually, this would look like the following:

α\β   0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
...
7 |  0  0  0  4  4  0  0  0  0 -4  0  0  0  0  4  0 
8 |  0  0  2 -2  0  0 -2  2 -2  2  0  0 -2  2  4  4 
...

Zero entries correspond to mask pairs that behave as a random function (i.e. aren't biased), so we only care about the non-zero values.

Task Generate a LAT for the S-Box of PRESENT, complementing the above output. You'll need it for later.

The LAT has some interesting properties at a glance. The most glaring is that every value is even. This makes sense if we take time to think about it. Each possible input $x$ for some mask either holds and increases the value, or doesn't hold and decreases the value. If the total amount of inputs is even (which it is, being $2^n$) then every entry must be even.

Sometimes (although not in the case of PRESENT), an S-Box may have an "ideal" approximation, i.e. some approximations always (or very frequently) hold. These are called (perfect) linear structures. As they aren't observable in PRESENT, we will be ignoring them for now, and mention them only for completeness sake.

Task In linear cryptanalysis, we're often more concerned about correlation than anything else. Rather than displaying the number of solutions, display the correlation that any given approximation holds. This is called a correlation table.