sboxUv2.statistics package

This module provides tools to study the “statistical” properties of vectorial Boolean functions.

“Statistical” should be understood in the sense of “statistical cryptanalysis”, i.e., differential and linear attacks along with all of their variants (boomerang, etc). In practice, this module provides functions that compute the main tables: DDT, LAT, BCT (as well as others), and tools to make sense of their content.

When possible the functions are multi-threaded. In particular, computing “spectra” (i.e., the number of occurrences of the coefficients in a table) is not done by first generating the full table and then counting; instead, rows are generated in parallel, which saves space and increases speed.

Submodules

sboxUv2.statistics.anomalies module

It is possible to investigate to define and to compute the probability that a given S-box is “at least as good” or “at least as bad” as a random permutation or function, as explained in [AC:BonPerTia19].

This reasoning is based on the probabilities for the DDT and LAT given in [JMC:DaeRij07], while the probabilities from the BCT are from [AC:BonPerTia19].

sboxUv2.statistics.anomalies.bct_coeff_probability(in_length, out_length, c, precision=120)

The non-trivial coefficients of the BCT of a permutation behave like samples from independent and identically distributed random variables following the same distribution, as explained in [AC:BonPerTia19] (where said distribution is also given).

If in_length != out_length, raises an error: the BCT is not defined in this case.

Parameters:

• in_length (int) – the input bit-length

• out_length (int) – the output bit-length

• c (int) – the absolute value of the BCT coefficient value whose probability we want

• precision (int) – a facultative argument corresponding to the level of precision to use for the floating point arithmetic.

Returns:

The probability that a coefficient of the BCT of a permutation operating on in_length bits has an absolute value equal to c.

Return type:

RealNumber

sboxUv2.statistics.anomalies.ddt_coeff_probability(in_length, out_length, c, precision=120)

The coefficients of the DDT of a random function can be modeled like independent and identically distributed random variables following a specific Poisson distribution [JMC:DaeRij07]. This function returns this probability.

This probability is identical for a random permutation and a random non-bijective function, and it corresponds to a Poisson distribution.

Parameters:

• in_length (int) – the input bit-length

• out_length (int) – the output bit-length

• c (int) – the DDT coefficient value whose probability we want

• precision (int) – a facultative argument corresponding to the level of precision to use for the floating point arithmetic.

Returns:

The probability that a coefficient of the DDT of a function mapping in_length bits to out_length is equal to coeff.

Return type:

RealNumber

sboxUv2.statistics.anomalies.expected_boomerang_uniformity_distribution_permutation(in_length, out_length, vmin=2, vmax=28)

The coefficients of the BCT of a random function can be modeled like independent and identically distributed random variables following a specific Poisson distribution [AC:BonPerTia19]. As a consequence, we can estimate the value of the maximum coefficient.

Parameters:

• in_length (int) – the number of bits in the input

• out_length (int) – the number of bits in the output

• vmin (int) – the minimum value of the differential uniformity to consider

• vmax (int) – the maximum value of the differential uniformity to consider

Returns:

A dictionary d such that d[i] is the probability that an F_2 S-box mapping in_length bits to out_length has a boomerang uniformity equal to i.

Return type:

dict

sboxUv2.statistics.anomalies.expected_differential_uniformity_distribution_permutation(in_length, out_length, vmin=2, vmax=28)

The coefficients of the DDT of a random function can be modeled like independent and identically distributed random variables following a specific Poisson distribution [JMC:DaeRij07]. As a consequence, we can estimate the value of the maximum coefficient.

Parameters:

• in_length (int) – the number of bits in the input

• out_length (int) – the number of bits in the output

• vmin (int) – the minimum value of the differential uniformity to consider

• vmax (int) – the maximum value of the differential uniformity to consider

Returns:

A dictionary d such that d[i] is the probability that an F_2 S-box mapping in_length bits to out_length has a differential uniformity equal to i.

Return type:

dict

sboxUv2.statistics.anomalies.expected_linearity_distribution_function(in_length, out_length, vmin=8, vmax=100)

The coefficients of the LAT of a random function can be modeled like independent and identically distributed random variables following a specific Poisson distribution [JMC:DaeRij07]. As a consequence, we can estimate the value of the maximum absolute coefficient of the LAT (i.e., the linearity).

Parameters:

• in_length (int) – the number of bits in the input

• out_length (int) – the number of bits in the output

• vmin (int) – the minimum value of the linearity to consider

• vmax (int) – the maximum value of the linearity to consider

Returns:

A dictionary d such that d[i] is the probability that a permutation operating on in_length bits has a linearity uniformity equal to i.

Return type:

dict

sboxUv2.statistics.anomalies.expected_linearity_distribution_permutation(in_length, out_length, vmin=8, vmax=100)

The coefficients of the LAT of a random permutation can be modeled like independent and identically distributed random variables following a specific Poisson distribution [JMC:DaeRij07]. As a consequence, we can estimate the value of the maximum absolute coefficient of the LAT (i.e., the linearity).

Parameters:

• in_length (int) – the number of bits in the input

• out_length (int) – the number of bits in the output

• vmin (int) – the minimum value of the linearity to consider

• vmax (int) – the maximum value of the linearity to consider

Returns:

A dictionary d such that d[i] is the probability that a permutation operating on in_length bits has a linearity uniformity equal to i.

Return type:

dict

sboxUv2.statistics.anomalies.expected_maximum_distribution(in_length, out_length, proba_func, n_coeffs, vmin=2, vmax=100)

Assuming that a table contains 2**in_length-1 non trivial rows of 2**out_length-1 non-trivial columns, returns the probability distribution of the maximum coefficient in the table as dictionary.

Parameters:

• in_length (int) – the number of bits in the input

• out_length (int) – the number of bits in the output

• proba_func (function) – a function taking as input an input length, an output length and a coefficient, and which returns the probability that this coefficient occurs given the other parameters

• n_coeffs (int) – the total number of non-trivial coefficients

• vmin (int) – the minimum value of the differential uniformity to consider

• vmax (int) – the maximum value of the differential uniformity to consider

Returns:

A dictionary d such that d[i] is the probability that the maximum coefficient is equal to i.

Return type:

dict

sboxUv2.statistics.anomalies.get_proba_func(s, table)

sboxUv2.statistics.anomalies.lat_coeff_probability_function(in_length, out_length, c, precision=120)

The non-trivial coefficients of the LAT of a function behave like samples from independent and identically distributed random variables following the same distribution, as explained in [JMC:DaeRij07] (where said distribution is also given). This distribution is not the same as in the case of permutations.

Parameters:

• in_length (int) – the input bit-length

• out_length (int) – the output bit-length

• c (int) – the absolute value of the LAT coefficient value whose probability we want

• precision (int) – a facultative argument corresponding to the level of precision to use for the floating point arithmetic.

Returns:

The probability that a coefficient of the LAT of a function mapping in_length bits to out_length bits has an absolute value equal to c.

Return type:

RealNumber

sboxUv2.statistics.anomalies.lat_coeff_probability_permutation(in_length, out_length, c, precision=120)

The non-trivial coefficients of the LAT of a permutation behave like samples from independent and identically distributed random variables following the same distribution, as explained in [JMC:DaeRij07] (where said distribution is also given). This distribution is not the same as in the case of non-bijective functions.

If in_length != out_length, raises an error: a permutation cannot have a different input and output size.

Parameters:

• in_length (int) – the input bit-length

• out_length (int) – the output bit-length

• c (int) – the absolute value of the LAT coefficient value whose probability we want

• precision (int) – a facultative argument corresponding to the level of precision to use for the floating point arithmetic.

Returns:

The probability that a coefficient of the LAT of a permutation operating on in_length bits has an absolute value equal to c.

Return type:

RealNumber

sboxUv2.statistics.anomalies.probability_of_max_and_occurrences(in_length, out_length, v_max, occurrences, proba_func, precision=120)

Returns the logarithm in base 2 of the probability that $(2^m-1)(2^n-1)$ trials of an experiment yielding output c with probability proba_func(m, n, c) will have a result equal to v_max at most occurrences times and be strictly smaller on all other trials.

sboxUv2.statistics.anomalies.table_anomaly(s, table, spec=None, precision=120)

Computes the positive anomaly (in the sense of [AC:BonPerTia19]) of the S-boxable object s that corresponds to its DDT, LAT or BCT.

Parameters:

• s – the S_boxable object you want the anomaly of.

• table – the name of the table for which the anomaly must be computed. Must be either “DDT”, “LAT” or “BCT”.

Returns:

the positive anomaly associated to the given table for the S-box corresponding to s.

Return type:

RealNumber

sboxUv2.statistics.anomalies.table_negative_anomaly(s, table, spec=None, precision=120)

Computes the negative anomaly (in the sense of [AC:BonPerTia19]) of the S_box s that corresponds to its DDT, LAT or BCT.

Parameters:

• s – the S_boxable object you want the anomaly of.

• table – the name of the table for which the anomaly must be computed. Must be either “DDT”, “LAT” or “BCT”.

Returns:

the negative anomaly associated to the given table for the S-box corresponding to s.

Return type:

RealNumber

sboxUv2.statistics.cython_functions module

sboxUv2.statistics.cython_functions.absolute_walsh_spectrum(s)

The absolute Walsh transform counts the number of occurrences of coefficients with a given absolute value in the Walsh transform for a function (or LAT for a vectorial function).

This function does not store the LAT in memory before counting, and uses openMP multi-threading to speed things further.

Parameters:

s – an S-boxable object

Returns:

a Spectrum instance d such that d[i] is the sum of the number of occurrences of i and -i in the LAT of s.

Return type:

Spectrum

sboxUv2.statistics.cython_functions.bct(s)

The Boomerang Connectivity Table was introduced in [EC:CHPS+18] to better capture what happens at the transition between the forward and the backward trail in a boomerang attack against an SPN.

It is a two dimensional array B such that, for all a and b:

$B(a,b) = #{x, S^{-1}(S(x)+b) + S^{-1}(S(x+a)+b)=a}$

sboxUv2.statistics.cython_functions.boomerang_spectrum(s)

The boomerang spectrum captures the number of occurrences of each coefficient in the BCT of a vectorial Boolean function (as returned by the bct function).

This function does not store the full BCT in memory before counting, and uses openMP multi-threading to speed things further.

Parameters:

s – an S-boxable object

Returns:

a Spectrum instance d such that d[i] is the number of occurrences of i in the BCT of s.

Return type:

Spectrum

sboxUv2.statistics.cython_functions.boomerang_uniformity(s)

sboxUv2.statistics.cython_functions.ddt(s)

The Difference Distribution Table of a function F is a two dimensional array D such that D[a][b] = #{x, F(x+a) = F(x)+b}. The number of rows and columns of the DDT depends on the dimensions of the input and output of the S-box (respectively). Depending on the underlying arithmetic of s, + corresponds either to a XOR (in F_2) or to a modular addition.

Parameters:

s – An S-boxable object.

Returns:

A list of lists corresponding to a 2-dimensional array containing the DDT of s.

Return type:

list

sboxUv2.statistics.cython_functions.differential_spectrum(s)

The differential spectrum of an S-box counts the number of entries in the DDT that are equal to each value.

This function does not store the DDT in memory before counting, and uses openMP multi-threading to speed things further.

Parameters:

s – An S-boxable object.

Returns:

A Spectrum instance d such that d[k] is equal to the number of occurrences of the coefficient k in the DDT of s.

Return type:

Spectrum

sboxUv2.statistics.cython_functions.differential_uniformity(s)

The differential uniformity of a function F is the maximum over all a != 0 and all b of the number of solutions x of the equation F(x+a)=F(x)+b.

Parameters:

s – An S-boxable object.

Returns:

The differential uniformity of the function corresponding to s.

Return type:

int

sboxUv2.statistics.cython_functions.fbct(s)

sboxUv2.statistics.cython_functions.fbct_spectrum(s)

sboxUv2.statistics.cython_functions.invert_lat(l)

The LAT is essentially a Fourier transform, meaning that it can be inverted. That is what this function does.

Parameters:

l (list) – A list of list corresponding to the LAT of a function.

Returns:

An S_box instance whose LAT is l.

sboxUv2.statistics.cython_functions.is_differential_uniformity_smaller_than(s, u)

Tests whether the differential uniformity of a function is below or equal to a given threshold. If the answer is “no”, then its execution can be much smaller than a proper computation of the differential uniformity.

Parameters:

• s – An S-boxable object.

• u (int) – The threshold such differential uniformity <= u.

Returns:

True if and only if the differential uniformity of the function corresponding to s is at most equal to u.

Return type:

bool

sboxUv2.statistics.cython_functions.lat(s)

The Linear Approximation Table of a function F over a vector space of a field of prime characteristic p is a two dimensional array $W_F$ such that

$ W_F(a, b) = sum_x rho_c^{ax + bF(x)} $

where $ax$ and $bF(x)$ denote the scalar products of $a$ and $x$, and $b$ and $F(x)$; and where $rho_c$ is a complex order c root of unity (i.e. $rho_c = -1$ for Boolean functions).

Parameters:

s – an S-boxable object

Returns:

A list of list l such that l[a][b] = $W_{F}(a, b)$.

Return type:

list

sboxUv2.statistics.cython_functions.linear_structures(s)

Args :

s: an S-boxable object over F_2 of output length 1

Returns:

A pair of lists [l_0, l_1] such that, for all a in l_e (with e in [0,1]), f(x+a) + f(x) = e, for all x (where + corresponds to a XOR). 0 does not appear in l_0 as it would always be present.

Return type:

list,list

sboxUv2.statistics.cython_functions.linear_structures_vectorial(s)

Args :

s: an S-boxable object over F_2

Returns :

dict : A dictionnary d, where d[c] is a pair of lists [l_0,l_1] such that, for all a in l_e (with e in [0,1]), c. (s(x+a) + s(x)) = e, for all x (where + corresponds to a XOR), where . is the scalar product. The dictionnary only contains keys where l_0 or l_1 are non-trivial, i.e. where l_0 contains more than just 0 and/or where l_1 is non-empty.

sboxUv2.statistics.cython_functions.linear_structures_vectorial_spectrum(s)

Args :

s: an S-boxable object over F_2

Returns :

Spectrum: a Spectrum instance d such that d[c] is the number of linear structures of the Boolean function c.s , where . is the scalar product. The spectrum only contains keys for which the number of linear structures is non-zero.

sboxUv2.statistics.cython_functions.linearity(s)

The linearity is the maximum module/absolute value to be found among non-trivial coefficients in the Walsh transform/LAT of a function.

Parameters:

s – an S-boxable object

Returns:

In F_2, an integer; in F_p, a real number.

Return type:

number

sboxUv2.statistics.cython_functions.walsh_spectrum(s)

The Walsh spectrum of a function describes the number of time each value appears in its Walsh transform (as returned by walsh_transform). For a vectorial function, it counts the number of occurrences of each coefficient in its LAT (as returned by lat).

This function does not store the LAT in memory before counting, and uses openMP multi-threading to speed things further.

Parameters:

s – an S-boxable object

Returns:

a Spectrum instance d such that d[i] is the number of occurrences of i in the LAT of s.

Return type:

Spectrum

sboxUv2.statistics.cython_functions.walsh_transform(s)

The Walsh transform of a function f over of a field of characteristic $c$ is the set

$W_f(a) = sum_x rho_c^{ax + f(x)}$

where ax is a the scalar product of the vectors a and x, where $rho_c$ is an order $c$ complex root of unity, and where a takes all possible values. Here, they are ordered using their representation as integers.

Parameters:

s – an S-boxable object

Returns:

a list l such that l[a] is equal to $W_f(a)$. Contains integers for vectorial Boolean function, complex numbers otherwise.

Return type:

list

sboxUv2.statistics.cython_functions.xddt(s)

The XDDT of a function F is a three dimensional array D such that D[a][b] = {x, F(x+a) = F(x)+b}. The number of rows and columns of the XDDT depends on the dimensions of the input and output of the S-box (respectively).

Args :

s: an S-boxable object over F_2

Returns :

list: A list of lists of lists corresponding to a 3-dimensional array containing the XDDT of s.

sboxUv2.statistics.cython_functions.yddt(s)

The YDDT of a function F is a three dimensional array D such that D[a][b] = {F(x), F(x+a) = F(x)+b}. The number of rows and columns of the YDDT depends on the dimensions of the input and output of the S-box (respectively).

Args :

s: an S-boxable object over F_2

Returns :

list: A list of lists of lists corresponding to a 3-dimensional array containing the YDDT of s.

sboxUv2.statistics.cython_functions.zddt(s)

The ZDDT of a function F is a three dimensional array D such that D[a][b] = {x|F(x), F(x+a) = F(x)+b}. The number of rows and columns of the ZDDT depends on the dimensions of the input and output of the S-box (respectively).

Args :

s: an S-boxable object over F_2

Returns :

list: A list of lists of lists corresponding to a 3-dimensional array containing the ZDDT of s.