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.
 Todo:
 Connections
 Todo:
 Links
 Todo:
 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.
 Todo:
 SAT 2012
 Todo:
 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 nonlinear.

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 nonlinear component and a linear component.
 Todo:
 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.
 Todo:
 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.
 Todo:
 Separate keyschedule and blockcipher

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 roundcomposition ignores the roundkeys, and so the keyschedule can just be removed, and one where the message roundfunction 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 cryptosystems, the pure iteration of block ciphers and the pure addition of roundkeys in every round; this likely should also be studied in separation.
 Todo:
 Using SBSAT

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 xorconstraints (for standard AES).

We need to get the respective fileformats and the translations into our system (while we can't get the solver into our system, since it is not opensource).

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.
 Todo:
 Investigating conditions and their representations
 Todo:
 Summary of previous experimental results

Before various improvements were made to the AES translation, experiments were run for 14 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.
 Bug:
 DONE (corrected kernel bug described in "Rerun timesensitive experiments" of Experimentation/Investigations/plans/general.hpp) MiniSAT2 based solvers return incorrect times using experiment script
 Todo:
 DONE Add milestones

We urgently need milestones at this level.
 Todo:
 DONE (misplaced scripts moved; todos added for improvement of others) Just an unstructured morass of scripts
 Todo:
 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
 Todo:
 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 "AppendDimacsO3DNDEBUG" as "AppendDimacsO3DNDEBUG" performs the same operation, is correct and has tests.
Definition in file general.hpp.