general.hpp File Reference

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.

Functions should not cache return values
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 bit-level 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/word-level 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 sub-matrix is non-singular. 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.
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/.
S-box and multiplication boolean 6xm functions
  • We wish to translate the AES where the S-box 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 "S-box boolean 6xm functions" in Cryptology/Lisp/Cryptanalysis/DataEncryptionStandard/plans/general.hpp.
Translating the constraint-system 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 constraint-system into SAT, CSP, ..." in Cryptanalysis/DataEncryptionStandard/plans/general.hpp.
    • S-box constraints:
      • For the full AES-S-box, there is one type of S-box, so we could represent it as a constraint by a list [[v_1,...,v_8],[w_1,...,w_8]].
      • For small-scale S-boxes we must specify *which* S-box is being considered.
      • We represent a small-scale S-box as a constraint by the list [b,e,p,mat,c,[v_1,...,v_(b^e)],[w_1,...,w_(b^e)]] where the S-box represented is a finite function from {1,...,b^e} to {1,...,b^e} given by:
        S-box(b,e,p,mat,c)(v) = mod(mat . v + c,p)
        • 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 AES-multiplcations, 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 small-scale multiplications further parameters are needed to specify *which* small-scale AES variant and multiplication are being considered.
      • We represent a small-scale multiplication as a constraint by the list
        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
        x[1] + ... + x[l] = b
        where l is the length of x.
    • We must also consider the following constraints:
      • S-box linear component.
      • Field inversion.
      • Combined S-box 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 S-box and multiplications, given their canonical DNF representations.
    • We could translate a list of S-box 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 clause-sets, 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 small-scale AES S-box constraints.
      • ss_mulc: generates the small-scale AES multiplication constraints.
      • ss_xor: generates the small-scale 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.
    • S-box and multiplication constraints should be translated to "table" constraints where we specify the truth table for each S-box.
    • 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 S-boxes and multiplications are considered as boolean 6 x m functions. See "S-box 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.
Evaluating AES "constraints"
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.