OKlibrary  0.2.1.6
20_13.hpp File Reference

Investigations into small-scale AES key discovery with 1 row, 1 column and 8-bit field elements for 20 + 1/3 round AES. More...

Go to the source code of this file.


Detailed Description

Investigations into small-scale AES key discovery with 1 row, 1 column and 8-bit field elements for 20 + 1/3 round AES.

Todo:
Problem specification
Todo:
Using the canonical box translation
  • Translation of aes(20,1,1,8):
  • Translation of aes(20,1,1,8):
  • Generating simplest small-scale 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 | ExtendedDimacsFullStatistics-O3-DNDEBUG 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 S-box:
    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 S-boxes * 4096 + 320 "additions" (arity 1) * 2;
    • 3 : 1312 = 328 additions (arity 2) * 4;
    • 17 : 10240 = 40 S-boxes * 256;
    • 256 : 40 = 40 S-boxes * 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.