Tutorial on S-box Analysis

Sage provides a class dedicated to the analysis of S-boxes: crypto.sage.sbox.SBox. Its documentation is available here. To be able to use it, you need to import it. To do so, add the following line at the top of your script:

from crypto.sage.sbox import SBox

Objects of the class SBox contain the lookup table of said S-box along with many useful methods. Some of them are listed below. If you want to print the lookup table of an SBox instance, you can simply print it:

# if s is an SBox instance
print s

When interacting with S-boxes in practice, it is far more convenient to intepret them as functions mapping \(\mathbb{Z}/2^m\mathbb{Z}\) to \(\mathbb{Z}/2^n\mathbb{Z}\) as we can then use integers to represent their inputs and outputs. That is what SBox does by default.

If you want to access the content of an SBox instance, you can use brackets as if it where an array or parenthesis as if it where a function; both work just the same:

# if s is an SBox instance
print s[1] # prints the output of s on the input of \{0, ..., 0, 0, 1\}
print s(2) # prints the output of s on the input of \{0, ..., 0, 1, 0\}

To see the expected lengths of the input and output, use respectively s.m and s.n.

I you know the lookup table of an S-box then it is trivial to initialize an instance. For example, to initialize an S-box containing the S-box of the PRESENT block cipher, simply use:

s = SBox([0xC,0x5,0x6,0xB,0x9,0x0,0xA,0xD,0x3,0xE,0xF,0x8,0x4,0x7,0x1,0x2])

During my PhD, I made a list of all the S-boxes that I was aware of, i.e. of all those that were used in ciphers and hash functions from the literature. Friedrich Wiemer then picked it up, added many S-boxes to it from the literature on Boolean functions, and got the result added into SAGE! It corresponds to crypto.sage.sboxes module. Thus, to obtain the S-box of PRESENT, we can also use

from crypto.sage.sboxes import PRESENT as s

which will import the SBox object called "PRESENT" and assign it to the variable s. There are many S-boxes in this list. To print it, use:

print dir(crypto.sage.sboxes)

When doing research in finite fields (of characteristic 2), or when studying S-boxes with a strong algebraic structure, it is convenient to use SAGE's support of finite field arithmetic. To interact with a finite field, we first need to declare a variable containing said finite field. If we want a degree of \(n\), we can use

F = GF(2**n)

SAGE will automatically choose a primitive polynomial to set it up. To access it, use F.modulus(). By default, for \(n=8\), the modulus is \(X^8 + X^4 + X^3 + X^2 + 1\) (it is the smallest primitive polynomial in lexicographic order with a weight of only 5, which is the minimum).

If you want to specify a particular modulus, adapt the following snippet:

X = GF(2).polynomial_ring().gen()
F = GF(2**8, name="a", modulus=X^8 + X^6 + X^5 + X^4 + 1)

the name will be used when printing field elements. It has to be specified manually when the modulus is imposed.

In order to generate elements of the finite field, two methods are possible. You can use powers of the primitive element F.gen() or you can use the trivial mapping integers of \(\mathbb{Z}/2^n\mathbb{Z}\) and \(\mathbb{F}_{2^n}\) defined as follows. Let \(\alpha\) be a root of the primitive polynomial used to define the finite field (it is the output of F.gen()). Then there is a bijection between the following integer, finite field element and bitstring: $$ \mathsf{bstr} = (x_0, ..., x_{n-1})~, ~ \mathsf{int} = \sum_{i=0}^{n-1}x_i \times 2^i~, ~ \mathsf{elm} = \sum_{i=0}^{n-1}x_i \times \alpha^i ~, $$ where \(\mathsf{bstr} \in \{ 0,1 \}^n\), \(\mathsf{int} \in \mathbb{Z}/2^n\mathbb{Z}\), and \(\mathsf{elm} \in \mathbb{F}_{2^n}\).

This mapping is already supported by SAGE, along with all the basic arithmetic and Boolean operations. To get the element from the finite field F that corresponds to the integer x, use F.fetch_int(x). To get the integer corresponding to an element y of F, use y.integer_representation(). We then for example have that F.gen()==F.fetch_int(2) is True.

Let us now create a function that returns and S-box corresponding to the multiplicative inverse in a finite field of degree \(n\). Said function is a power function with exponent \(2^n-2\).

def get_inverse_sbox(n):
    F = GF(2**n)
    lut = []
    for x in xrange(0, 2**n):
        x_ff = F.fetch_int(x) # x_ff is an element in the finite field
        y_ff = x_ff**(2^n-2)  # y_ff is the inverse of x_ff
        lut.append(y_ff.integer_representation()) # we add the integer corresponding to y_ff
    return SBox(lut)

The Difference Distribution Table (DDT) captures how good an S-box \(S : \{ 0,1 \}^n \to \{ 0,1 \}^m\) is at preventing differential cryptanalysis [1]. It is defined by $$ \textrm{DDT}_{S}[a, b] ~=~ \#\big\{x \in \{ 0,1 \}^n ~|~ S(x \oplus a) \oplus S(x) = b \big\} ~, $$ where \(\oplus\) denotes the exclusive OR (what is implemented by ^^ in SAGE). In SAGE, it is implemented by the difference_distribution_table method which returns a matrix. For example, running

from sage.crypto.sboxes import PRESENT as s
print s.difference_distribution_table()

yields

[16  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  4  0  0  0  4  0  4  0  0  0  4  0  0]
[ 0  0  0  2  0  4  2  0  0  0  2  0  2  2  2  0]
[ 0  2  0  2  2  0  4  2  0  0  2  2  0  0  0  0]
[ 0  0  0  0  0  4  2  2  0  2  2  0  2  0  2  0]
[ 0  2  0  0  2  0  0  0  0  2  2  2  4  2  0  0]
[ 0  0  2  0  0  0  2  0  2  0  0  4  2  0  0  4]
[ 0  4  2  0  0  0  2  0  2  0  0  0  2  0  0  4]
[ 0  0  0  2  0  0  0  2  0  2  0  4  0  2  0  4]
[ 0  0  2  0  4  0  2  0  2  0  0  0  2  0  4  0]
[ 0  0  2  2  0  4  0  0  2  0  2  0  0  2  2  0]
[ 0  2  0  0  2  0  0  0  4  2  2  2  0  2  0  0]
[ 0  0  2  0  0  4  0  2  2  2  2  0  0  0  2  0]
[ 0  2  4  2  2  0  0  2  0  0  2  2  0  0  0  0]
[ 0  0  2  2  0  0  2  2  2  2  0  0  2  2  0  0]
[ 0  4  0  0  4  0  0  0  0  0  0  0  0  0  4  4]

The maximum coefficient for \(a \neq 0\) is the differential uniformity of \(S\). The lower it is, the better. The lowest possible is 2; a function reaching this bound is called Almost Perfect Non-linear (APN). The differential uniformity is returned using the differential_uniformity() method.

For linear attacks [3], the relevant table is the Linear Approximation Table (LAT). It is defined by: $$ \textrm{LAT}_{S}[a, b] ~=~ \sum_{x \in \{0,1\}^n} (-1)^{a \cdot x + b \cdot S(x)} ~, $$ where "\(\cdot\)" denotes the scalar product: if \(a = (a_0,...,a_{n-1})\) and \(b = (b_0,...,b_{n-1})\) then \(a \cdot b = \bigoplus_{i=0}^{n-1}a_ib_i\), so that \(a \cdot b \in \{ 0,1 \}\).

It quantifies how close each component of \(S\), i.e. each function \(x \mapsto c \cdot S(x)\), is to each Boolean linear function. Unlike the DDT, its coefficients are signed. The maximum absolute value of the LAT coefficients is called the linearity. Like the differential uniformity, the lower it is the better.

The method returning this table is linear_approximation_matrix(). It has some optional parameters so that, by default, it returns a table where the coefficients are half of those specified above. Running

from sage.crypto.sboxes import PRESENT as s
print s.linear_approximation_table()

yields

[ 8  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0 -4  0 -4  0  0  0  0  0 -4  0  4]
[ 0  0  2  2 -2 -2  0  0  2 -2  0  4  0  4 -2  2]
[ 0  0  2  2  2 -2 -4  0 -2  2 -4  0  0  0 -2 -2]
[ 0  0 -2  2 -2 -2  0  4 -2 -2  0 -4  0  0 -2  2]
[ 0  0 -2  2 -2  2  0  0  2  2 -4  0  4  0  2  2]
[ 0  0  0 -4  0  0 -4  0  0 -4  0  0  4  0  0  0]
[ 0  0  0  4  4  0  0  0  0 -4  0  0  0  0  4  0]
[ 0  0  2 -2  0  0 -2  2 -2  2  0  0 -2  2  4  4]
[ 0  4 -2 -2  0  0  2 -2 -2 -2 -4  0 -2  2  0  0]
[ 0  0  4  0  2  2  2 -2  0  0  0 -4  2  2 -2  2]
[ 0 -4  0  0 -2 -2  2 -2 -4  0  0  0  2  2  2 -2]
[ 0  0  0  0 -2 -2 -2 -2  4  0  0 -4 -2  2  2 -2]
[ 0  4  4  0 -2 -2  2  2  0  0  0  0  2 -2  2 -2]
[ 0  0  2  2 -4  4 -2 -2 -2 -2  0  0 -2 -2  0  0]
[ 0  4 -2  2  0  0 -2 -2 -2  2  4  0  2  2  0  0]

As the DDT and the LAT can be too big to be displayed conveniently, even for \(n=m=4\), I suggested the use of what I called the "Jackson Pollock representation" in [2]. It is simply a picture where each absolute value has a color associated to it, the table then consisting in \(2^n \times 2^m\) pixels. For example, a Pollock representation LAT of the Russian S-box π is given in Figure 1.

The color scheme plays a crucial as some patterns may be visible with some color schemes but not with others! A list of all color schemes is available on this page. A handy SAGE function handling the generation of such a picture is given below.

The built-in method component_function returns a component of the corresponding S-box. More precisely, if s is an S-box instance with an \(m\)-bit input and if \(c < 2^m\) is an integer then s.component_function(c) is a sage.crypto.boolean_function instance corresponding to the function \(x \mapsto c \cdot S(x)\).

In order to get the algebraic nomal form of a sage.crypto.boolean_function instance, we can simply use the built-in algebraic_normal_form function. Thus, to get the ANF of an S-box, we can use the following function.

def anf(s):
    result = []
    for i in xrange(0, s.m):
        result.append(s.component_function(1 << i).algebraic_normal_form())
    return result