SboxU: S-box Analysis Utils

1. Installation
2. Functions Provided
3. References

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.