general.hpp File Reference

On investigations into the Advanced Encryption Standard. More...

Go to the source code of this file.

Detailed Description

On investigations into the Advanced Encryption Standard.

DONE (removed directory and integrated milestones with higher level) Merge SAT2011 plans with module one level higher
  • The experiments in the SAT2011 module are not SAT2011 specific.
  • The SAT2011 module should be removed and/or how to present or link to paper/presentation specific experiments reconsidered.
SAT 2012
Notions for AES operation
  • When considering the AES round, we don't consider the ShiftRows operation as a separate operation, as it rewires bits of the AES block, and nothing else. As it is simply a renaming, it isn't represented by any clauses in the translation.
  • To remove the ShiftRows as a separate operation, we can move it into the MixColumns operation.
  • We need the correct notion and name for this operation, and at the same time we should consider the notions of the AES round and key schedule.
  • Possible notions for the combined MixColumns and ShiftRows operation:
    • "linear diffusion operation" is a reasonable name which brings attention to the following relevant facts:
      • The reason for the inclusion of MixColumns and ShiftRows in the AES is for their "diffusion" properties and linearity, and both operations share these properties while the SubBytes is non-linear.
      • In [Algebraic Aspects of the Advanced Encryption Standard;Cid, Murphy and Robshaw], they call these operations, together, the "diffusion layer".
      • The two operations in the core of the AES round (i.e., excluding the key addition) are made up of a non-linear component and a linear component.
Determining a "good" local search algorithm to use on AES instances
  • Question: what is a good algorithm to use, considering the algorithms tested by "run_ubcsat" (see Experimentation/ExperimentSystem/ControllingLocalSearch/Evaluation.R)
  • Presumably local search will not do well on AES instances compared to DPLL/CDCL solvers, as often local search solvers perform poorly on industrial and crafted instances, which the AES translations are likely similar to, considering the large number of new variables involved.
  • What sort of metrics to use to determine a good algorithm once the experiment has been run?
    • Sorting first by the average number of falsified clauses and then by the number of steps seems reasonable, as we wish to minimise the number of falsified clauses as much as possible.
Explain how to replace various AES boxes with identity or random boxes
  • As part of our investigations, we make various parts of the AES sbox the identity, and then introduce the various boxes (Sbox, field multiplications etc), to determine which combinations of boxes "make AES difficult".
  • To do this, we need to be able to generate AES translations which "make sense" (i.e. are permutations, given the key).
  • These translations are possible with the current translation system without writing additional rewrite functions, however instructions and/or additional helper functions are necessary to make sure things easy to experiment with.
Separate key-schedule and block-cipher
  • Using the notions from ComputerAlgebra/Cryptology/Lisp/CryptoSystems/IteratedBlockCipher.mac, we should split off the key schedule.
  • That is, we consider two variations, one where the round-composition ignores the round-keys, and so the key-schedule can just be removed, and one where the message round-function is the identity.
  • However, cryptographically, removing the key schedule makes cracking AES trivial. One just applies the inverted round a number of times and then the key is just the plaintext XORed with the ciphertext.
  • Therefore, we should also consider a key schedule where the round key for every round is the input key.
  • "Compositional iterated block ciphers with iterated key schedule" in the sense of ComputerAlgebra/Cryptology/Lisp/CryptoSystems/IteratedBlockCipher.mac are compositions of two crypto-systems, the pure iteration of block ciphers and the pure addition of round-keys in every round; this likely should also be studied in separation.
  • As discussed in the manual http://gauss.ececs.uc.edu/sbsat_user_manual/, the input can consist of a list of files containing DNFs ir XOR constraints, and so we can easily specify AES and generalisations.
  • The MixColumns constraint can either be represented via the xor of boxes, or by the direct representation via 32 xor-constraints (for standard AES).
  • We need to get the respective file-formats and the translations into our system (while we can't get the solver into our system, since it is not open-source).
  • Most basic is to get the sizes of smurfs for the various boolean functions ("boxes"); see "Smurfs" in ComputerAlgebra/Satisfiability/Lisp/FiniteFunctions/plans/BDDs.hpp for the general theory.
Investigating conditions and their representations
Summary of previous experimental results
  • Before various improvements were made to the AES translation, experiments were run for 1-4 rounds translations of the AES and on the various boxes.
  • A basic summary (even if not reproducible due to the new state of the system), should be made available here.
DONE (corrected kernel bug described in "Rerun time-sensitive experiments" of Experimentation/Investigations/plans/general.hpp) MiniSAT2 based solvers return incorrect times using experiment script
  • minisat2 based solvers (glucose and minisat2) return run times of a fraction of a second using when run using "run_all_solvers_2by2" while they clearly take much much longer when run separately.
  • See "Using the canonical translation" in AdvancedEncryptionStandard/plans/KeyDiscovery/032/4_2_4/1_13.hpp.
  • Just use "time"!
DONE Add milestones
  • We urgently need milestones at this level.
DONE (misplaced scripts moved; todos added for improvement of others) Just an unstructured morass of scripts
DONE (moved to "Improve minimisation scripts" in Satisfiability/Optimisation/plans/general.hpp) Update scripts
  • The following scripts:
    • Satisfiability/Optimisation/minimise_cnf_oksolver.
    • Satisfiability/Optimisation/cardinality_bounded_cnf.
    • Satisfiability/Optimisation/extend_strict_dimacs_with_extended.
    • Satisfiability/Optimisation/all_minimum_cnf.
    need the following changes:
    • Tests (URGENT).
    • Error checking code.
    • Merging with other scripts in other investigations into general tools.
    • Update documentation in comments.
    • Add version numbers. DONE
DONE Replace "merge_cnf.sh" with "AppendDimacs"
  • All instances of the "merge_cnf.sh" script at Investigations/Cryptography/AdvancedEncryptionStandard/merge_cnf.sh should be replaced with "AppendDimacs-O3-DNDEBUG" as "AppendDimacs-O3-DNDEBUG" performs the same operation, is correct and has tests.

Definition in file general.hpp.