Investigations into the 4bit AES Sbox.
More...
Go to the source code of this file.
Detailed Description
Investigations into the 4bit AES Sbox.
 Bug:
 Update

The generated 1base for the 4bit Sbox also needs to be added.

DONE (see "Basic Data") Commit b47ed2bac74daaf648852bba0c61f26b3e7f7c8f added some representation  where does this come from, and where it is represented here?
 Todo:
 Basic data

Generating the full CNF representation:

The CNFfile "AES_Sbox_full.cnf" is created by the Maximafunction output_ss_sbox_fullcnf_stdname(2,4,ss_polynomial_2_4) in ComputerAlgebra/Cryptology/Lisp/Cryptanalysis/Rijndael/SboxAnalysis.mac, which is a full clauseset with 8 variables and 2^8  2^4 = 240 clauses:
> cat AES_sbox_2_4_full.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG
n non_taut_c red_l taut_c orig_l comment_count finished_bool
8 240 1920 0 1920 1 1
length count
8 240

The underlying clauseset is ss_sbox_fullcnf_fcs(2,4,ss_polynomial_2_4).

This clauseset is also computed by bf2relation_fullcnf_fcs(lambda([V],ss_sbox_bf(V,2,4)),4).

Prime implicates:

There are 147 prime implicates, with 581 literals in total, and with clauselengthdistribution as follows:
> QuineMcCluskeyn16O3DNDEBUG AES_sbox_2_4_full.cnf > AES_sbox_2_4_full.cnf_primes
> cat AES_sbox_2_4_full.cnf_primes  ExtendedDimacsFullStatisticsO3DNDEBUG
n non_taut_c red_l taut_c orig_l comment_count finished_bool
8 147 581 0 581 1 1
length count
3 22
4 110
5 15

Minimum representations:

A minimum representation can be computed by:
maxima> oklib_load_all()$
maxima> output_ss_sbox_fullcnf_stdname(2,4,ss_polynomial_2_4);
shell> OKP=~/Work/OKlibrary/OKplatform/ ${OKP}/OKsystem/OKlib/Satisfiability/Optimisation/minimise_cnf_cryptominisat AES_sbox_2_4_full.cnf  tee Sbox_4_min.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n
n non_taut_c red_l taut_c orig_l comment_count finished_bool
8 22 82 0 82 1 1
length count
3 8
4 12
5 2

The hardness of this representation is 2:
shell> Sbox_4_min : read_fcl_f("Sbox_4_min.cnf")$
shell> hardness_cs(setify(Sbox_4_min[2]));
2

See "Hardness of boolean function representations" in Experimentation/Investigations/BooleanFunctions/plans/general.hpp for discussion on the notions of hardness and methods for computing it.
 Todo:
 Overview

The minimum size of a CNF representation for the AES 4bit Sbox is 22; see "Basic data".

Here we should have an overview of the current state of this investigation and open problems.

DONE (now we do; see "Basic data") We do *not* currently know the minimum CNF size for the 4bit Sbox.
 Todo:
 Combining Sbox with field addition

The AES key schedule includes various field additions which applying associativity and commutativity rules can be combined with the Sbox of the round *after* the key schedule.

In particular, the round key is output by the key schedule, and then added (XORed) to the result of the previous round, and given as input to the next round.

Within the key schedule, each word is the result of the addition of one key word, with the result of the Sbox operation and addition of certain other key words from the previous round key.

As each round key results from the addition of a key word from the previous round, one should investigate combining this key word addition with the the Sbox for the next round.

For this case (4bit boxes), this would yield a 12bit relation, 8bits input (round input and key) and 4bits output.

Such a function should be fully analysed.

Prime implicates:
maxima> FF : bf2relation_fullcnf_fcs(lambda([V],ss_sbox_w_add_bf(V,2,4)),8)$
maxima> output_fcs("SboxPlusKey4.cnf", FF, "SboxPlusKey4.cnf")$
> cat SboxPlusKey4.cnf_primes  ExtendedDimacsFullStatisticsO3DNDEBUG
n non_taut_c red_l taut_c orig_l comment_count finished_bool
12 634 4020 0 4020 1 1
length count
4 20
5 100
6 262
7 180
8 40
9 32

See ss_sbox_w_add_bf in ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael/SmallScaleAdvancedEncryptionStandard.mac.
 Todo:
 Generating all minimum representations via hypergraph transversals

Generate full CNFs:
maxima> output_ss_sbox_fullcnf_stdname(2,4,ss_polynomial_2_4);

Computing minimum representations for the 4bit Sbox:
shell> ${OKPLATFORM}/OKsystem/OKlib/Satisfiability/Optimisation/all_minimum_cnf AES_sbox_2_4_full.cnf
...

The computation is still running after 5 days. XXX
Definition in file Sbox_4.hpp.