S-Boxes and Their Algebraic Representations¶

class sage.crypto.sbox.SBox(*args, **kwargs)¶

Bases: sage.structure.sage_object.SageObject

A substitution box or S-box is one of the basic components of symmetric key cryptography. In general, an S-box takes m input bits and transforms them into n output bits. This is called an mxn S-box and is often implemented as a lookup table. These S-boxes are carefully chosen to resist linear and differential cryptanalysis [He2002].

This module implements an S-box class which allows an algebraic treatment and determine various cryptographic properties.

EXAMPLES:

We consider the S-box of the block cipher PRESENT [BKLPPRSV2007]:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2); S
(12, 5, 6, 11, 9, 0, 10, 13, 3, 14, 15, 8, 4, 7, 1, 2)
sage: S(1)
5

Note that by default bits are interpreted in big endian order. This is not consistent with the rest of Sage, which has a strong bias towards little endian, but is consistent with most cryptographic literature:

sage: S([0,0,0,1])
[0, 1, 0, 1]

sage: S = SBox(12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2, big_endian=False)
sage: S(1)
5
sage: S([0,0,0,1])
[1, 1, 0, 0]

Now we construct an SBox object for the 4-bit small scale AES S-Box (cf. sage.crypto.mq.sr):

sage: sr = mq.SR(1,1,1,4, allow_zero_inversions=True)
sage: S = SBox([sr.sub_byte(e) for e in list(sr.k)])
sage: S
(6, 5, 2, 9, 4, 7, 3, 12, 14, 15, 10, 0, 8, 1, 13, 11)

AUTHORS:

Rusydi H. Makarim (2016-03-31) : added more functions to determine related cryptographic properties
Yann Laigle-Chapuy (2009-07-01): improve linear and difference matrix computation
Martin R. Albrecht (2008-03-12): initial implementation

REFERENCES:

autocorrelation_table()¶

Return the autocorrelation table corresponding to this S-Box.

for an \(m \times n\) S-Box \(S\), its autocorrelation table entry at row \(a \in \GF{2}^m\) and column \(b \in \GF{2}^n\) (considering their integer representation) is defined as:

\[\sum_{x \in \GF{2}^m} (-1)^{b \cdot S(x) \oplus b \cdot S(x \oplus a)}\]

Equivalently, the columns \(b\) of autocorrelation table correspond to the autocorrelation spectrum of component function \(b \cdot S(x)\).

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.autocorrelation_table()
[ 8  8  8  8  8  8  8  8]
[ 8  0  0  0  0  0  0 -8]
[ 8  0 -8  0  0  0  0  0]
[ 8  0  0  0  0 -8  0  0]
[ 8 -8  0  0  0  0  0  0]
[ 8  0  0  0  0  0 -8  0]
[ 8  0  0 -8  0  0  0  0]
[ 8  0  0  0 -8  0  0  0]

boomerang_connectivity_table()¶

Return the boomerang connectivity table (BCT) for this S-Box.

Boomerang connectivity matrix of an invertible \(m \times m\) S-Box \(S\) is an \(2^m \times 2^m\) matrix with entry at row \(\Delta_i \in \GF{2}^m\) and column \(\Delta_o \in \GF{2}^m\) equal to

\[|\{ x \in \GF{2}^m | S^{-1}( S(x) \oplus \Delta_o) \oplus S^{-1}( S(x \oplus \Delta_i) \oplus \Delta_o) = \Delta_i\}|.\]

For more results concerning boomerang connectivity matrix, see [CHPSS18] . The algorithm used here, is the one from Dunkelman, published in a preprint, see [Du2018] .

EXAMPLES:

sage: from sage.crypto.sboxes import PRESENT
sage: PRESENT.boomerang_connectivity_table()
[16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16]
[16  0  4  4  0 16  4  4  4  4  0  0  4  4  0  0]
[16  0  0  6  0  4  6  0  0  0  2  0  2  2  2  0]
[16  2  0  6  2  4  4  2  0  0  2  2  0  0  0  0]
[16  0  0  0  0  4  2  2  0  6  2  0  6  0  2  0]
[16  2  0  0  2  4  0  0  0  6  2  2  4  2  0  0]
[16  4  2  0  4  0  2  0  2  0  0  4  2  0  4  8]
[16  4  2  0  4  0  2  0  2  0  0  4  2  0  4  8]
[16  4  0  2  4  0  0  2  0  2  0  4  0  2  4  8]
[16  4  2  0  4  0  2  0  2  0  0  4  2  0  4  8]
[16  0  2  2  0  4  0  0  6  0  2  0  0  6  2  0]
[16  2  0  0  2  4  0  0  4  2  2  2  0  6  0  0]
[16  0  6  0  0  4  0  6  2  2  2  0  0  0  2  0]
[16  2  4  2  2  4  0  6  0  0  2  2  0  0  0  0]
[16  0  2  2  0  0  2  2  2  2  0  0  2  2  0  0]
[16  8  0  0  8  0  0  0  0  0  0  8  0  0  8 16]

boomerang_uniformity()¶

Return the boomerang uniformity

The boomerang uniformity is defined as the highest entry in the boomerang connectivity table, ignoring the first row and column.

EXAMPLES:

sage: from sage.crypto.sboxes import AES
sage: AES.boomerang_uniformity()
6

cnf(xi=None, yi=None, format=None)¶

Return a representation of this S-Box in conjunctive normal form.

This function examines the truth tables for each output bit of the S-Box and thus has complexity \(n * 2^m\) for an m x n S-Box.

INPUT:

xi - indices for the input variables (default: 1...m)
yi - indices for the output variables (default: m+1 ... m+n)
format - output format, see below (default: None)

FORMATS:

None - return a list of tuples of integers where each tuple represents a clause, the absolute value of an integer represents a variable and the sign of an integer indicates inversion.
symbolic - a string that can be parsed by the SymbolicLogic package.
dimacs - a string in DIMACS format which is the gold standard for SAT-solver input (cf. http://www.satlib.org/).
dimacs_headless - a string in DIMACS format, but without the header. This is useful for concatenation of outputs.

EXAMPLES:

We give a very small example to explain the output format:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(1,2,0,3); S
(1, 2, 0, 3)
sage: cnf = S.cnf(); cnf
[(1, 2, -3),  (1, 2, 4),
 (1, -2, 3),  (1, -2, -4),
 (-1, 2, -3), (-1, 2, -4),
 (-1, -2, 3), (-1, -2, 4)]

This output completely describes the S-Box. For instance, we can check that S([0,1]) -> [1,0] satisfies every clause if the first input bit corresponds to the index 1 and the last output bit corresponds to the index 3 in the output.

We can convert this representation to the DIMACS format:

sage: print(S.cnf(format='dimacs'))
p cnf 4 8
1 2 -3 0
1 2 4 0
1 -2 3 0
1 -2 -4 0
-1 2 -3 0
-1 2 -4 0
-1 -2 3 0
-1 -2 4 0

For concatenation we can strip the header:

sage: print(S.cnf(format='dimacs_headless'))
1 2 -3 0
1 2 4 0
1 -2 3 0
1 -2 -4 0
-1 2 -3 0
-1 2 -4 0
-1 -2 3 0
-1 -2 4 0

This might be helpful in combination with the xi and yi parameter to assign indices manually:

sage: print(S.cnf(xi=[10,20],yi=[30,40], format='dimacs_headless'))
10 20 -30 0
10 20 40 0
10 -20 30 0
10 -20 -40 0
-10 20 -30 0
-10 20 -40 0
-10 -20 30 0
-10 -20 40 0

We can also return a string which is parse-able by the SymbolicLogic package:

sage: log = SymbolicLogic()
sage: s = log.statement(S.cnf(format='symbolic'))
sage: log.truthtable(s)[1:]
[['False', 'False', 'False', 'False', 'False'],
 ['False', 'False', 'False', 'True', 'False'],
 ['False', 'False', 'True', 'False', 'False'],
 ['False', 'False', 'True', 'True', 'True'],
 ['False', 'True', 'False', 'False', 'True'],
 ['False', 'True', 'False', 'True', 'True'],
 ['False', 'True', 'True', 'False', 'True'],
 ['False', 'True', 'True', 'True', 'True'],
 ['True', 'False', 'False', 'False', 'True'],
 ['True', 'False', 'False', 'True', 'True'],
 ['True', 'False', 'True', 'False', 'True'],
 ['True', 'False', 'True', 'True', 'True'],
 ['True', 'True', 'False', 'False', 'True'],
 ['True', 'True', 'False', 'True', 'True'],
 ['True', 'True', 'True', 'False', 'True'],
 ['True', 'True', 'True', 'True', 'True']]

This function respects endianness of the S-Box:

sage: S = SBox(1,2,0,3, big_endian=False); S
(1, 2, 0, 3)
sage: cnf = S.cnf(); cnf
[(1, 2, -4), (1, 2, 3),
 (-1, 2, 4), (-1, 2, -3),
 (1, -2, -4), (1, -2, -3),
 (-1, -2, 4), (-1, -2, 3)]

S-Boxes with m!=n also work:

sage: o = list(range(8)) + list(range(8)) sage: shuffle(o) sage: S = SBox(o) sage: S.is_permutation() False

sage: len(S.cnf()) == 3*2^4 True

component_function(b)¶

Return a Boolean function corresponding to the component function \(b \cdot S(x)\).

If \(S\) is an \(m \times n\) S-Box, then \(b \in \GF{2}^n\) and \(\cdot\) denotes dot product of two vectors.

INPUT:

b – either an integer or a list/tuple/vector of \(\GF{2}\) elements of length self.output_size()

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([7,6,0,4,2,5,1,3])
sage: f3 = S.component_function(3)
sage: f3.algebraic_normal_form()
x0*x1 + x0*x2 + x0 + x2

sage: f5 = S.component_function([1, 0, 1])
sage: f5.algebraic_normal_form()
x0*x2 + x0 + x1*x2

derivative(u)¶

Return the derivative in direction of u

INPUT:

u – either an integer or a tuple/list of \(\GF{2}\) elements of length equal to m

The derivative of \(F\) in direction of \(u\) is defined as \(x \mapsto F(x) + F(x + u)\).

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: s = SBox(0,1,2,3)
sage: s.derivative(1)
(1, 1, 1, 1)
sage: u = [1,0]
sage: s.derivative(u)
(1, 1, 1, 1)
sage: v = vector(GF(2), [1,0])
sage: s.derivative(v)
(1, 1, 1, 1)
sage: s.derivative(4)
Traceback (most recent call last):
...
IndexError: list index out of range
sage: from sage.crypto.sboxes import PRESENT
sage: PRESENT.derivative(1).max_degree() < PRESENT.max_degree()
True

difference_distribution_table()¶

Return difference distribution table (DDT) A for this S-box.

The rows of A encode the differences Delta I of the input and the columns encode the difference Delta O for the output. The bits are ordered according to the endianess of this S-box. The value at A[Delta I,Delta O] encodes how often Delta O is the actual output difference given Delta I as input difference.

See [He2002] for an introduction to differential cryptanalysis.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.difference_distribution_table()
[8 0 0 0 0 0 0 0]
[0 2 2 0 2 0 0 2]
[0 0 2 2 0 0 2 2]
[0 2 0 2 2 0 2 0]
[0 2 0 2 0 2 0 2]
[0 0 2 2 2 2 0 0]
[0 2 2 0 0 2 2 0]
[0 0 0 0 2 2 2 2]

differential_branch_number()¶

Return differential branch number of this S-Box.

The differential branch number of an S-Box \(S\) is defined as

\[\min_{v, w \neq v} \{ \mathrm{wt}(v \oplus w) + \mathrm{wt}(S(v) \oplus S(w)) \}\]

where \(\mathrm{wt}(x)\) denotes the Hamming weight of vector \(x\).

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2])
sage: S.differential_branch_number()
3

fixed_points()¶

Return a list of all fixed points of this S-Box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([0,1,3,6,7,4,5,2])
sage: S.fixed_points()
[0, 1]

from_bits(x, n=None)¶

Return integer for bitstring x of length n.

INPUT:

x - a bitstring
n - bit length (optional)

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.from_bits( [1,1,0])
6

sage: S( S.from_bits( [1,1,0] ) )
1
sage: S.from_bits( S( [1,1,0] ) )
1

has_linear_structure()¶

Return True if there exists a nonzero component function of this S-Box that has a linear structure.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([0,1,3,6,7,4,5,2])
sage: S.linear_structures()
[(1, 1, 1), (2, 2, 1), (3, 3, 1), (4, 4, 1), (5, 5, 1), (6, 6, 1), (7, 7, 1)]

linearity()¶

Return the linearity of this S-Box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = mq.SR(1, 4, 4, 8).sbox()
sage: S.linearity()
32

max_degree()¶

Return the maximal algebraic degree of all its component functions.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2])
sage: S.max_degree()
3

maximal_difference_probability()¶

Return the difference probability of the difference with the highest probability in the range between 0.0 and 1.0 indicating 0% or 100% respectively.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.maximal_difference_probability()
0.25

maximal_difference_probability_absolute()¶

Return the difference probability of the difference with the highest probability in absolute terms, i.e. how often it occurs in total.

Equivalently, this is equal to the differential uniformity of this S-Box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.maximal_difference_probability_absolute()
2

Note

This code is mainly called internally.

maximal_linear_bias_absolute()¶

Return maximal linear bias, i.e. how often the linear approximation with the highest bias is true or false minus \(2^{n-1}\).

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.maximal_linear_bias_absolute()
2

maximal_linear_bias_relative()¶

Return maximal bias of all linear approximations of this S-box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.maximal_linear_bias_relative()
0.25

min_degree()¶

Return the minimal algebraic degree of all its component functions.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2])
sage: S.min_degree()
2

nonlinearity()¶

Return the nonlinearity of this S-Box.

The nonlinearity of an S-Box is defined as the minimum nonlinearity of all its component functions.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = mq.SR(1,4,4,8).sbox()
sage: S.nonlinearity()
112

output_size()¶

Return the output size of this S-Box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([0, 3, 2, 1, 1, 3, 2, 0])
sage: S.output_size()
2

polynomials(X=None, Y=None, degree=2, groebner=False)¶

Return a list of polynomials satisfying this S-box.

First, a simple linear fitting is performed for the given degree (cf. for example [BC2003]). If groebner=True a Groebner basis is also computed for the result of that process.

INPUT:

X - input variables
Y - output variables
degree - integer > 0 (default: 2)
groebner - calculate a reduced Groebner basis of the spanning polynomials to obtain more polynomials (default: False)

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: P = S.ring()

By default, this method returns an indirect representation:

sage: S.polynomials()
[x0*x2 + x1 + y1 + 1,
 x0*x1 + x1 + x2 + y0 + y1 + y2 + 1,
 x0*y1 + x0 + x2 + y0 + y2,
 x0*y0 + x0*y2 + x1 + x2 + y0 + y1 + y2 + 1,
 x1*x2 + x0 + x1 + x2 + y2 + 1,
 x0*y0 + x1*y0 + x0 + x2 + y1 + y2,
 x0*y0 + x1*y1 + x1 + y1 + 1,
 x1*y2 + x1 + x2 + y0 + y1 + y2 + 1,
 x0*y0 + x2*y0 + x1 + x2 + y1 + 1,
 x2*y1 + x0 + y1 + y2,
 x2*y2 + x1 + y1 + 1,
 y0*y1 + x0 + x2 + y0 + y1 + y2,
 y0*y2 + x1 + x2 + y0 + y1 + 1,
 y1*y2 + x2 + y0]

We can get a direct representation by computing a lexicographical Groebner basis with respect to the right variable ordering, i.e. a variable ordering where the output bits are greater than the input bits:

sage: P.<y0,y1,y2,x0,x1,x2> = PolynomialRing(GF(2),6,order='lex')
sage: S.polynomials([x0,x1,x2],[y0,y1,y2], groebner=True)
[y0 + x0*x1 + x0*x2 + x0 + x1*x2 + x1 + 1,
 y1 + x0*x2 + x1 + 1,
 y2 + x0 + x1*x2 + x1 + x2 + 1]

ring()¶

Create, return and cache a polynomial ring for S-box polynomials.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.ring()
Multivariate Polynomial Ring in x0, x1, x2, y0, y1, y2 over Finite Field of size 2

solutions(X=None, Y=None)¶

Return a dictionary of solutions to this S-box.

INPUT:

X - input variables (default: None)
Y - output variables (default: None)

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([7,6,0,4,2,5,1,3])
sage: F = S.polynomials()
sage: s = S.solutions()
sage: any(f.subs(_s) for f in F for _s in s)
False

to_bits(x, n=None)¶

Return bitstring of length n for integer x. The returned bitstring is guaranteed to have length n.

INPUT:

x - an integer
n - bit length (optional)

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.to_bits(6)
[1, 1, 0]

sage: S.to_bits( S(6) )
[0, 0, 1]

sage: S( S.to_bits( 6 ) )
[0, 0, 1]

sage.crypto.sbox.feistel_construction(*args)¶

Return an S-Box constructed by Feistel structure using smaller S-Boxes in args. The number of round in the construction is equal to the number of S-Boxes provided as input. For more results concerning the differential uniformity and the nonlinearity of S-Boxes constructed by Feistel structures see [CDL2015] .

INPUT:

args - a finite iterable SBox objects

EXAMPLES:

Suppose we construct an \(8 \times 8\) S-Box with 3-round Feistel construction from the S-Box of PRESENT:

sage: from sage.crypto.sbox import SBox
sage: s = SBox(12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2)
sage: from sage.crypto.sbox import feistel_construction
sage: S = feistel_construction(s, s, s)

The properties of the constructed S-Box can be easily examined:

sage: S.nonlinearity()
96
sage: S.differential_branch_number()
2
sage: S.linear_branch_number()
2

sage.crypto.sbox.misty_construction(*args)¶

Return an S-Box constructed by MISTY structure using smaller S-Boxes in args. The number of round in the construction is equal to the number of S-Boxes provided as input. For further result related to the nonlinearity and differential uniformity of the constructed S-Box one may consult [CDL2015].

INPUT:

args - a finite iterable SBox objects

EXAMPLES:

We construct an \(8 \times 8\) S-Box using 3-round MISTY structure with the following \(4 \times 4\) S-Boxes \(S1, S2, S3\) (see Example 2 in [CDL2015]):

sage: from sage.crypto.sbox import SBox
sage: S1 = SBox([0x4,0x0,0x1,0xF,0x2,0xB,0x6,0x7,0x3,0x9,0xA,0x5,0xC,0xD,0xE,0x8])
sage: S2 = SBox([0x0,0x0,0x0,0x1,0x0,0xA,0x8,0x3,0x0,0x8,0x2,0xB,0x4,0x6,0xE,0xD])
sage: S3 = SBox([0x0,0x7,0xB,0xD,0x4,0x1,0xB,0xF,0x1,0x2,0xC,0xE,0xD,0xC,0x5,0x5])
sage: from sage.crypto.sbox import misty_construction
sage: S = misty_construction(S1, S2, S3)
sage: S.differential_uniformity()
8
sage: S.linearity()
64

S-Boxes and Their Algebraic Representations¶

Previous topic

Next topic

This Page