Investigations into smallscale AES key discovery with 1 row, 1 column and 8bit field elements for 20 + 1/3 round AES.
More...
Go to the source code of this file.
Detailed Description
Investigations into smallscale AES key discovery with 1 row, 1 column and 8bit field elements for 20 + 1/3 round AES.
 Todo:
 Problem specification

We investigate the 20 + 1/3 round smallscale AES with 1 row, 1 column, using the 8bit field size.

We denote this AES instance by aes(20,1,1,8).

aes(20,1,1,8) takes a 8bit plaintext and 8bit key and outputs a 8bit ciphertext.

For the full specification of this AES instance, see "Problem specification" in Cryptography/AdvancedEncryptionStandard/plans/KeyDiscovery/008/1_1_8/general.hpp.

The decompositions and translations are listed in "Investigating
dimensions" in Cryptography/AdvancedEncryptionStandard/plans/Experimentation.hpp.

Note that we consider the canonical CNF translation, as this is an example of the "hardest" representation without new variables. See "Hardness of boolean function representations" in Experimentation/Investigations/BooleanFunctions/plans/general.hpp.
 Todo:
 Using the canonical box translation

Translation of aes(20,1,1,8):

Translation of aes(20,1,1,8):

Generating simplest smallscale AES for 20+1/3 rounds:
shell> ${OKlib}/Experimentation/Investigations/Cryptography/AdvancedEncryptionStandard/generate_aes_experiment 20 1 1 1 8 false aes_ts_box aes_mc_bidirectional
shell> cat ssaes_r20_c1_rw1_e8_f0.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n
n non_taut_c red_l taut_c orig_l comment_count finished_bool
11224 176232 517376 0 517376 11225 1
length count
1 160
2 164480
3 1312
17 10240
256 40

In this translation, we have:

20 full rounds (Key Addition and SubBytes).

40 Sboxes:

20 from SubBytes = 1 byte * 20 round;

20 from key schedule = 1 row * 1 byte * 20 round.

648 additions:

320 additions of arity 1:

160 from forward MixColumns = 8 bits * 20 rounds;

160 from inverse MixColumns = 8 bits * 20 rounds.

328 additions of arity 2:

160 from key additions = 8 bits * 20 rounds;

8 from final key addition = 8 bits;

160 from the key schedule = 8 bits * 20 rounds.

8 bits for the constant in the key schedule.

The number of clauses of each length in the canonical translation of the Sbox:
maxima> ncl_list_full_dualts(8,16);
[[2,4096],[17,256],[256,1]]

This instance has the following number of clauses of length:

1 : 160 = key schedule constant * 1;

2 : 164480 = 40 Sboxes * 4096 + 320 "additions" (arity 1) * 2;

3 : 1312 = 328 additions (arity 2) * 4;

17 : 10240 = 40 Sboxes * 256;

256 : 40 = 40 Sboxes * 1.

Then we run experiments for AES instances with one round, up to those with twenty rounds, and inspect the results for round 20.
shell> ${OKlib}/Experimentation/Investigations/Cryptography/AdvancedEncryptionStandard/run_aes_experiment 20 1 1 1 8 false aes_ts_box aes_mc_bidirectional

precosat236 solves this problem with no decisions in a fraction of a second:
shell> cat experiment_r20_k1.cnf_precosat236
<snip>
c 0 conflicts, 0 decisions, 0 random
c 0 iterations, 0 restarts, 0 skipped
c prps: 2928753 propagations, 5.87 megaprops
c 0.5 seconds, 15 MB max, 6 MB recycled
Definition in file 20_13.hpp.