S-Boxes and Their Algebraic Representations

class sage.crypto.mq.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 [Heys02].

This module implements an S-box class which allows an algebraic treatment.

EXAMPLE:

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

sage: S = mq.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 = mq.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 = mq.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)

REFERENCES:

[Heys02]

(1, 2, 3) H. Heys A Tutorial on Linear and Differential Cryptanalysis ; 2002’ available at http://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf

[PRESENT07]

A. Bogdanov, L. Knudsen, G. Leander, C. Paar, A. Poschmann, M. Robshaw, Y. Seurin, C. Vikkelsoe PRESENT: An Ultra-Lightweight Block Cipher; in Proceedings of CHES 2007; LNCS 7427; pp. 450-466; Springer Verlag 2007; available at http://www.crypto.rub.de/imperia/md/content/texte/publications/conferences/present_ches2007.pdf

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 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.

EXAMPLE:

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

sage: S = mq.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 = mq.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)]

TESTS:

sage: S = mq.SBox(1,2,0,3, big_endian=False) sage: S.cnf([1000,1001,1002], [2000,2001,2002]) Traceback (most recent call last): ... TypeError: first arg required to have length 2, got 3 instead.

difference_distribution_matrix()

Return difference distribution matrix 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 [Heys02] for an introduction to differential cryptanalysis.

EXAMPLE:

sage: S = mq.SBox(7,6,0,4,2,5,1,3)
sage: S.difference_distribution_matrix()
[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]

from_bits(x, n=None)

Return integer for bitstring x of length n.

INPUT:

• x - a bitstring
• n - bit length (optional)

EXAMPLE:

sage: S = mq.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

interpolation_polynomial(k=None)

Return a univariate polynomial over an extension field representing this S-box.

If m is the input length of this S-box then the extension field is of degree m.

If the output length does not match the input length then a TypeError is raised.

INPUT:

• k - an instance of (default: None)

EXAMPLE:

sage: S = mq.SBox(7,6,0,4,2,5,1,3)
sage: f = S.interpolation_polynomial()
sage: f
x^6 + a*x^5 + (a + 1)*x^4 + (a^2 + a + 1)*x^3
  + (a^2 + 1)*x^2 + (a + 1)*x + a^2 + a + 1

sage: a = f.base_ring().gen()

sage: f(0), S(0)
(a^2 + a + 1, 7)

sage: f(a^2 + 1), S(5)
(a^2 + 1, 5)

is_permutation()

Return True if this S-Box is a permutation.

EXAMPLE:

sage: S = mq.SBox(7,6,0,4,2,5,1,3)
sage: S.is_permutation()
True

sage: S = mq.SBox(3,2,0,0,2,1,1,3)
sage: S.is_permutation()
False

linear_approximation_matrix()

Return linear approximation matrix A for this S-box.

Let i_b be the b-th bit of i and o_b the b-th bit of o. Then v = A[i,o] encodes the bias of the equation sum( i_b * x_i ) = sum( o_b * y_i ) if x_i and y_i represent the input and output variables of the S-box.

See [Heys02] for an introduction to linear cryptanalysis.

EXAMPLE:

sage: S = mq.SBox(7,6,0,4,2,5,1,3)
sage: S.linear_approximation_matrix()
[ 4  0  0  0  0  0  0  0]
[ 0  0  0  0  2  2  2 -2]
[ 0  0 -2 -2 -2  2  0  0]
[ 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 -2 -2  0  0 -2  2  0]
[ 0 -2  2  0 -2  0  0 -2]

According to this matrix the first bit of the input is equal to the third bit of the output 6 out of 8 times:

sage: for i in srange(8): print S.to_bits(i)[0] == S.to_bits(S(i))[2]
False
True
True
True
False
True
True
True

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.

EXAMPLE:

sage: S = mq.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.

EXAMPLE:

sage: S = mq.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 .

EXAMPLE:

sage: S = mq.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.

EXAMPLE:

sage: S = mq.SBox(7,6,0,4,2,5,1,3)
sage: S.maximal_linear_bias_relative()
0.25

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 [BC03]). 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: S = mq.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]

REFERENCES:

[BC03]

A. Biryukov and C. D. Canniere Block Ciphers and Systems of Quadratic Equations; in Proceedings of Fast Software Encryption 2003; LNCS 2887; pp. 274-289, Springer-Verlag 2003.

ring()

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

EXAMPLE:

sage: S = mq.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)

EXAMPLE:

sage: S = mq.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)

EXAMPLE:

sage: S = mq.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]