Plans for the cryptanalysis of Rijndael in Maxima/Lisp.
More...
Go to the source code of this file.
Detailed Description
Plans for the cryptanalysis of Rijndael in Maxima/Lisp.
 Todo:
 Connections
 Todo:
 Functions should not cache return values
 Todo:
 Generating defaults constant for small scale

At present, we only have Sbox matrices, affine constants, modulo polynomials and so on defined when the field exponent is 1, 4 or 8, as these are either trivial or given in [Small scale variants of the AES; Cid, Murphy and Robshaw].

We would like to extend this to arbitrary exponents (although we still restrict ourselves to binary bases for simplicity), and therefore we need defaults for the following values for each exponent:

sbox linear transformation matrix:

This bitlevel matrix must be a invertible matrix which is a linear operation over the GF(b^e) field.

There are also other properties involving correlation coefficients and so on (regarding security against linear and differential cryptanalysis) that need to be considered here (see [Design of Rijndael; Daemen and Rijmen]).

sbox affine constant:

It seems this can be arbitrary but shouldn't be completely trivial (0,01 etc).

We need more information on the choice of this.

Field polynomial:

We aren't concerned with efficient circuit implementation, so presumably this can be arbitrary, as long as it defines a genuine GF(b^e) field.

MixColumn matrix:

This byte/wordlevel matrix operation must be invertible (else we don't have a cipher).

[Design of Rijndael; Daemen and Rijmen] also suggest that the matrix should be maximal distance separate. A matrix is MDS iff every square submatrix is nonsingular. See section 9 and specifically 9.6 in [Design of Rijndael; Daemen and Rijmen], as well as [Small scale variants of the AES; Cid, Murphy and Robshaw].

We would also like to be able to calculate all the various measurements considered in the AES literature on these components, so as to compare any that we introduce against such metrics.
 Todo:
 Generating polynomial representations of field operations

Any small scale field operation can be represented as a polynomial of degree at most (b^e)1.

There are at most b^e points and it forms a field, therefore we find this polynomial via linear interpolation.

We need to implement linear interpolation over the field for arbitrary fields.

This todo should be moved to Cryptography/AdvancedEncryptionStandard/plans/Representations/.
 Todo:
 Sbox and multiplication boolean 6xm functions

We wish to translate the AES where the Sbox and multiplications are considered as 8 8x1 boolean functions.

There is also the possibility of generalising this to 8/m boolean 8xm functions, or even combinations of 1 8x4 and 2 6x2 boolean functions etc.

See also "Sbox boolean 6xm functions" in Cryptology/Lisp/Cryptanalysis/DataEncryptionStandard/plans/general.hpp.
 Todo:
 Translating the constraintsystem into SAT, CSP, ...

The SAT translation is available as output_ss_fcl_std in ComputerAlgebra/Cryptology/Lisp/Cryptanalysis/Rijndael/Translations.mac.

Constraint translation:

We must provide a translation of the "constraints" we generate in the AES translation to more concrete constraints.

See 'Notion of "constraint"' in Cryptanalysis/Rijndael/plans/ConstraintTemplateRewriteSystem.hpp.

For the DES constraint translation, see "Translating the constraintsystem into SAT, CSP, ..." in Cryptanalysis/DataEncryptionStandard/plans/general.hpp.

Sbox constraints:

For the full AESSbox, there is one type of Sbox, so we could represent it as a constraint by a list [[v_1,...,v_8],[w_1,...,w_8]].

For smallscale Sboxes we must specify *which* Sbox is being considered.

We represent a smallscale Sbox as a constraint by the list [b,e,p,mat,c,[v_1,...,v_(b^e)],[w_1,...,w_(b^e)]] where the Sbox represented is a finite function from {1,...,b^e} to {1,...,b^e} given by:
Sbox(b,e,p,mat,c)(v) = mod(mat . v + c,p)
where

v is a vector of elements in {1,...,b} of length e;

mat is an e x e matrix of elements in {1,...,b};

c is a constant vector with elements in {1,...,b} of length e;

p is a polynomial over {1,...,b}.

Multiplication constraints:

For the full AESmultiplcations, we could represent them as a constraint by a list [e,[v_1,...,v_8],[w_1,...,w_8]], where e is the element in {0,...,255} to be multiplied by.

For smallscale multiplications further parameters are needed to specify *which* smallscale AES variant and multiplication are being considered.

We represent a smallscale multiplication as a constraint by the list
[i,b,e,p,[v_1,...,v_(b^e)],[w_1,...,w_(b^e)]]
where the constraints represents the multiplication of an element in {1,...,b^e} by i modulo the polynomial p resulting in an element again in {1,...,b^e}.

XOR constraints:

See 'The notion of a "linear constraint"' for the details of the XOR constraint.

An XOR constraint is a list [x,b] where x is a list of literals and b is in {0,1}, such that the constraint is that where l is the length of x.

We must also consider the following constraints:

Sbox linear component.

Field inversion.

Combined Sbox linear component and field multiplications.

MixColumn: MixColumns on a single column.

8 x m boolean function versions of all constraints.

Translating high level constraints into positive boolean constraints:

This might be a good idea, especially for the Sbox and multiplications, given their canonical DNF representations.

We could translate a list of Sbox and multiplication constraints directly to a positive boolean constraints; see ComputerAlgebra/Satisfiability/Lisp/ConstraintProblems/Conditions.mac.

However, this would yield a much larger representation which would repeat the definition of the boxes for each instance of the box (modulo variable renaming), and hide the underlying constraints.

Therefore, we reserve translation of constraints to the level of full clausesets, or "truth tables" until we (possibly) later translate directly to some CSP solver input language.

We need functions, taking the same parameters as ss_fcl:

ss_sboxc: generates the smallscale AES Sbox constraints.

ss_mulc: generates the smallscale AES multiplication constraints.

ss_xor: generates the smallscale AES XOR constraints.

Other constraints based on the linear components, field inversion and so on, which should be added to this list, as they are considered.

Translating AES constraints to Minion:

We should provide a translation for input into the Minion solver.

We could first provide a model of the Minion input language at the Maxima level, which is then only output to file, but such a language isn't likely useful for us outside of input to Minion; we already model the constraints in our own way; it is best to translate as we output to file.

Sbox and multiplication constraints should be translated to "table" constraints where we specify the truth table for each Sbox.

XOR constraints should be translated to "watchsumleq" and "watchsumgeq" constraints.

We need a function "output_ss_minion" which takes the same parameters as ss_fcl and uses ss_sboxc, ss_mulc etc to generate the constraints associated with the AES given the input parameters, and outputs the corresponding Minion input file.

We also need a function "output_ss_minion_6tm" which takes the number of rounds, and the parameter m and generates the constraints associated with the AES where the Sboxes and multiplications are considered as boolean 6 x m functions. See "Sbox and multiplication
boolean 6xm functions".

We should also translate to one of the constraint modelling languages; see "Constraint modelling languages" in Buildsystem/ExternalSources/SpecialBuilds/plans/CSP.hpp.
 Todo:
 Evaluating AES "constraints"
 Todo:
 Rewrite translation functions using ss_field_op_fulldnf_gen_fcl etc

Functions such as ss_sbox_fulldnf_gen_fcl should be rewritten using ss_field_op_fulldnf_gen_fcl and passing in the appropriate operations.
Definition in file general.hpp.