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 inton
output bits. This is called anmxn
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 theSymbolicLogic
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 index1
and the last output bit corresponds to the index3
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
andyi
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)]
S-Boxes with m!=n also work:
sage: o = range(8) + range(8) sage: shuffle(o) sage: S = mq.SBox(o) sage: S.is_permutation() False
sage: len(S.cnf()) == 3*2^4 True
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 differencesDelta I
of the input and the columns encode the differenceDelta O
for the output. The bits are ordered according to the endianess of this S-box. The value atA[Delta I,Delta O]
encodes how oftenDelta O
is the actual output difference givenDelta 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 lengthn
.INPUT:
x
- a bitstringn
- 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 degreem
.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 theb
-th bit ofi
ando_b
theb
-th bit ofo
. Thenv = A[i,o]
encodes the bias of the equationsum( i_b * x_i ) = sum( o_b * y_i )
ifx_i
andy_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]). Ifgroebner=True
a Groebner basis is also computed for the result of that process.INPUT:
X
- input variablesY
- output variablesdegree
- 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 integerx
. The returned bitstring is guaranteed to have lengthn
.INPUT:
x
- an integern
- 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]
-