# SboxU: S-box Analysis Utils

## Table of Contents

**Work in progress**

`sboxU`

is a library containing various routines that are intended to
be helpful when looking at S-boxes and other vectorial Boolean
functions.

Unlike the builtin utilities in SAGE, `sboxU`

has the advantage of
implementing some of the latest discoveries in the area of Boolean
functions. The reason is simple: it is the area I work in, and I have
to implement those in order to move forward with my own
research. Instead of reimplementing it each time, I try and write a
proper implementation of each algorithm once and for all so that I
don't need to worry about it again. `sboxU`

started as a collection of
such algorithms.

Another aspect of `sboxU`

is a focus on performance: I write
sub-routines in `C++`

if it gives a performance advantage (if it is
not too cumbersome), and use multi-threading if relevant.

Overall, `sboxU`

tends to use simpler types internally (for easier
interface with `C++`

when relevant and to remove some performance
overheads). For instance, the output of the `ddt`

function is not a
SAGE-style `Matrix`

but simply of Python `list`

where each entry is
itself a `list`

. Thus, if `d`

is an output of this function then you
have that `d[a][b]`

is the DDT entry corresponding to input difference
`a`

and output difference `b`

. Similarly, functions are represented as
lists corresponding to their lookup tables.

## 1 Installation

### 1.1 Dependencies

The `SboxU`

library was only tested on Linux (Ubuntu 16.04). To
install it, you only need sage! Older versions relied on `libboost`

to
provide the interface between `C++`

and `Python`

; this task is now
offloaded to `cython`

, a tool built into `SAGE`

.

sage

### 1.2 Download

To retrieve this library, use the following command:

git clone https://github.com/lpp-crypto/sboxU/

Then, move to the `sbox-utils/sboxU/sboxU_{cython}` directory and run:

sage setup.py build_ext --inplace [11:15:10]

This compiles the C++ part of `sboxU`

and allows it to be called from
a SAGE script.

### 1.3 Usage

To use it in your project, simply move the `sboxU`

folder to your
project's directory. You can then import `sboxU`

like any other python
module. As an example of the functions provided by `sboxU`

, the SAGE
script `example.py`

stored alongside the folder `sboxU`

generates
random permutations and tests their affine equivalence.

The simplest is to create a symbolic from the `sboxU`

folder (the one
full of `.cpp`

, `.hpp`

and `.py`

files) to the folder where you put
your scripts. Alternatively, you can start SAGE from the directory
containing said `sboxU`

folder.

Then, either in your script or in the SAGE prompt, use

from sboxU import *

to be able to use all the functions from `sboxU`

.

## 2 Functions Provided

You can use the functions that are already included in SAGE for finite
field arithmetic. `sboxU`

provides the following additional functions.

#### 2.0.1 Basic Cryptographic Properties

`ddt`

`ddt(s)`

returns the DDT of the function whose LUT is the list`s`

. Assumes that the function maps`n`

bits to`n`

, where`n`

is the base-2 logarithm of the length of`s`

.`differential_spectrum`

`differential_spectrum(s)`

is a`dictionnary`

containing the differential spectrum of the function whose LUT is the list`s`

(where the first row of the DDT is omitted). For instance,`differential_spectrum(range(0, 4))`

is`{0: 9, 4: 3}`

.`lat`

`lat(s)`

returns the LAT of the function whose LUT is the list`s`

. Assumes that the function maps`n`

bits to`n`

, where`n`

is the base-2 logarithm of the length of`s`

.`walsh_spectrum`

`differential_spectrum(s)`

is a`dictionnary`

containing the Walsh spectrum of the function whose LUT is the list`s`

(where the first column of the LAT is omitted). For instance,`walsh_spectrum(range(0, 4))`

is`{0: 9, 4: 3}`

.Recall that the Walsh coefficients are signed.

`algebraic_normal_form`

- returns a list containing the ANF of each
coordinate of
`s`

. The ANFs are SAGE-style`boolean_function`

instances, meaning that are internally viewed as polynomials rather than LUTs.

#### 2.0.2 Display Related Functions

`pretty_vector`

- returns a string where each number in the list input to the function is represented in hexadecimal.
`pretty_spectrum`

- use it to generate nice string representations of
differential or Walsh spectra. Use the optionnal argument
`absolute=True`

to sum the entries`c: k`

and`-c:l`

into`c:k+l`

(i.e. in practice if you want the extended Walsh spectrum instead of the plain one). `save_pollock`

- saves the Pollock representation of a list of list into a file.

## 3 References

- Xavier Bonnetain, Léo Perrin, and Shizhu Tian.
**Anomalies and Vector Space Search: Tools for S-Box Analysis**. In Steven Galbraith and Shiho Moriai, editors,*Advances in Cryptology – ASIACRYPT 2019, Part I*, volume 11921 of*Lecture Notes in Computer Science*, pages 196–223. Springer, Heidelberg, December 2019. link to eprint.iacr.org.