Dealing with S-boxes in F_2

The corresponding source file is available online on github.

Preamble

Let \(F_p\) be the finite field with \(p\) elements, \(p\) being a prime number (often, \(p=2\), but not always!). sboxU is a library built to study S-boxes: we call S-box a function S satisfying the two following conditions: - it maps \(F_p^m\) to \(F_p^n\), where both \(n\) and \(m\) are integers - its input size is small enough that that, in practice, it possible to precompute and store in memory all of its outputs.

There is a simple mapping \(\lambda\) between the integers between 0 and \(p^n-1\) and the elements of \(F_p^n\). We then call the lookup table of S the sequence \(S(\lambda(0)), ..., S(\lambda(p^n-1))\).

In sboxU, the goal is to generate the LUT of a function in order to study it. This LUT is then wrapped in dedicated classes: S_box for S-boxes defined over vector spaces of \(F_2\) (or, equivalently, over bitstrings), and Fp_S_box for other primes.

Let’s see how this can be done in practice.

Basic functionalities of the S_box class

An S_box instance can be easily created using the LUT of the function investigated. For example, here is how to initialize an S_box instance operating on \(F_2^6\) that is simply the multiplication by 5 over the integers.

N = 6
s = get_sbox([5*x % 2**N for x in range(0, 2**N)])

We can simply print s to see again the LUT, but it is more interesting to pretty print it using the pprint function.

print("basic list representation:")
print(s)
print("\npretty printing the same information:")
pprint(s)

Queries

It is possible to query the content of the lookup of an S-box using the operator \([]\). The operator \(()\) can also work but it offers additional functionalities (see the section on “Linear Casts”).

For the all 0 vector, we have:

if s[0] == 0:
    success("the output of s on the all zero bit string is indeed {}".format(s[0]))
else:
    fail("s[0] should be 0, something went wrong")

and for the vector (1, 0, ..., 0), we need to use the integer 1 as the query. We get:

if s[1] == 5:
    success("the output of s on (1,0,...,0) is indeed {}".format(s[0]))
else:
    fail("s[1] should be 5, something went wrong")

Basic quantities

input length
output length
input space
input space size
is_permutation

Coordinates and Components

Polynomial representations

algegraic normal form
univariate

Building an S-box

The case of S-boxes from the literature

SUppose that you want to study the S-box of the AES (it has its own wikipedia page. sboxU knows about the literature, and it is thus possible to write

s = get_sbox("AES")

This will retrieve the LUT of the S-box of the AES from its internal database, and generate an object of the class S_box (which is assigned to s). Thus, the following snippet grabs several S-boxes from the literature (namely, from the AES [1], Ascon [2], and PRESENT [3].

for test in [("AES", 4),
             ("PRESENT", 4),
             ("Ascon", 8)]:
    name, expected_uniformity = test
    u = differential_uniformity(get_sbox(name))
    if u == expected_uniformity:
        success("{} S-box differential uniformity is indeed {}".format(
            name,
            expected_uniformity
        ))
    else:
        fail("{} S-box differential uniformity should be {}, not {}".format(
            name,
            expected_uniformity,
            u
        ))

Univariate polynomials

field = GF(2**5)
g = field.gen()
X = PolynomialRing(field, "x").gen()
cube = get_sbox(X**3)
cube_plus = get_sbox(X**3 + g*X)

Operations on S-boxes

Addition

It is possible to add to S-boxes.

diff = cube + cube_plus
is_linear = (differential_uniformity(diff) == 2**5)
if is_linear:
    success("the sum of X^3 and X^3+gX is indeed an affine function")
else:
    fail("something went wrong, gX should be affine")