Linear Cryptanalysis - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 139

Generalizing this, with an n -bit S-box ( n -bit input, n -bit output), we have to perform several operations equal
to 2 3 n .
Using our previous idea (from Chapter 5) that 2 40 is not too taxing an amount of work, we find n such that
2 3n = 2 40
This gives us n = 13, which would mean we could reasonably analyze all of the relationships in a 13-bit S-box.
The industry standard seems to be to use 8-bit S-boxes or less, so we are all right for now.
Now that we understand calculating biases for linear expressions, we can then choose every possible linear
expression. As such, we will be left with a large listing of biases, as shown in Table 6-1 .

Table 6-1 A Few of the Linear Expressions from a Simple 3-Bit S-Sox
EQUATION BIAS (ε)

0 = 0 1/2

X 0 = Y 0 0

X 0 = Y 1 0

X 0 = Y 0 ⊕ Y 1 0

X 0 = Y 2 1/2

X 1 = Y 0 -1/2

X 2 = Y 1 ⊕ Y 2 -1/4

A few things to note: The highest value is (positive) 1/2, and the smallest is -1/2, which are both good values
(they mean that the equation is always true or always false, respectively). However, the valid linear expression
0 = 0, while always true (with bias 1/2), is meaningless; of course, it is always true, but it yields no information.
In general, we want to focus on the values that have a high bias and that involve the least possible number of
bits. Involving fewer bits in the input and the output helps us to manage the eventual linear cryptanalysis, which
is composed of many of the linear expressions built on each other.
However, the syntax shown in Table 6-1 is a bit cumbersome. It's good to see exactly which bits affect which
bits, along with the associated bias, but it isn't very easy to parse.
A notation used by Matsui is very helpful in this case. The representation of the input and output bits will
be a pair of numbers (usually written in hexadecimal). A bit being present in the linear expression would be
translated to a 1 (in the binary representation) of the number, and a bit not being present translates to a 0.
For example, if the input side is X 0 ⊕ X 2 ⊕ X 3 ⊕ X 6 , we would use the binary number 01001101 , or 4D
in hexadecimal. For no particular reason, we usually write the linear expression starting with subscript 0, then
1, and so forth, while we translate this to mean bit 0, bit 1, and so forth, which are normally represented in most
significant bit order in the final number.
Therefore, for the last row in Table 6-1 , we have the expression X 2 = Y 1 ⊕ Y 2 . This would correspond to the
number pair ( 3,5 ).
The above compact form of representing the equations can allow us to more easily analyze S-boxes by con-
structing tables, with the row number representing the input bits, the column number representing the output
bits,andtheentryinthetable corresponding tothebias.Forexample, Table 6-2 showsthecomplete setoflinear
expressions of the previous 3-bit S-box.

Table 6-2 Complete Set of Biases for All Possible Linear Expressions on the Sample 3-Bit S-Box