OKlibrary  0.2.1.6
4_13.hpp File Reference

Investigations into small-scale AES key discovery for 4 + 1/3 round AES with a 1x16 plaintext matrix and 4-bit field elements. More...

Go to the source code of this file.


Detailed Description

Investigations into small-scale AES key discovery for 4 + 1/3 round AES with a 1x16 plaintext matrix and 4-bit field elements.

Todo:
Problem specification
Todo:
Using the canonical box translation
  • Translation of aes(4,1,16,4):
  • Generating small-scale AES for 4 + 1/3 rounds:
    num_rounds : 4$
    num_rows : 1$
    num_columns : 16$
    exp : 4$
    final_round_b : false$
    box_tran : aes_ts_box$
    seed : 1$
    mc_tran : aes_mc_bidirectional$
    oklib_monitor : true$
    output_ss_fcl_std(num_rounds, num_columns, num_rows, exp, final_round_b, box_tran, mc_tran)$
    
    shell> cat ssaes_r4_c16_rw1_e4_f0.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG n
     n non_taut_c red_l taut_c orig_l comment_count finished_bool
    2336 13268 37584 0 37584 2337 1
     length count
    1 16
    2 9728
    3 2240
    4 128
    9 1088
    16 68
       
  • In this translation, we have:
    • 4 full rounds (Key Addition, SubBytes, and MixColumns operation).
    • 68 S-boxes:
      • 64 from SubBytes = 16 byte * 4 rounds;
      • 4 from key schedule = 1 row * 1 byte * 4 rounds.
    • 1088 additions:
      • 512 additions of arity 1:
        • 512 from MixColumns = 1 row * 16 columns * 2 directions (forward + inverse) * 4 bits * 4 rounds.
      • 560 additions of arity 2:
        • 256 from key additions = 64 bits * 4 round;
        • 64 from final key addition = 64 bits;
        • 240 from the key schedule = (64 bits - 4 bits) * 4 round.
      • 16 additions of arity 3:
        • 16 from the key schedule = 4 bits * 4 rounds.
    • 16 bits for the constant in the key schedule = 4 bits * 4 rounds.
  • The number of clauses of each length in the translation, computed by:
    maxima> ncl_list_full_dualts(8,16);
    [[2,128],[9,16],[16,1]]
       
  • This instance has the following number of clauses of length:
    • 1 : 16 = key schedule constant * 1;
    • 2 : 9728 = 68 S-boxes * 128;
    • 3 : 2240 = 560 additions (arity 2) * 4;
    • 4 : 128 = 16 additions (arity 3) * 8;
    • 9 : 1088 = 68 S-boxes * 16;
    • 16 : 68 = 68 S-boxes * 1.
  • Then we can generate a random assignment with the plaintext and ciphertext, leaving the key unknown:
    maxima> output_ss_random_pc_pair(seed,num_rounds,num_columns,num_rows,exp,final_round_b);
       
    and the merging the assignment with the translation:
    shell> AppendDimacs-O3-DNDEBUG ssaes_r4_c16_rw1_e4_f0.cnf ssaes_pkpair_r4_c16_rw1_e4_f0_s1.cnf > experiment_r4_k1.cnf
       
  • march_pl solves it in 6s:
    shell> march_pl experiment_r4_k.1.cnf
    <snip>
    c main():: nodeCount: 2509
    c main():: dead ends in main: 2
    c main():: lookAheadCount: 539606
    c main():: unitResolveCount: 48512
    c main():: time=6.010000
    <snip>
       
  • minisat-2.2.0 solves it in 19s:
    shell> minisat-2.2.0 experiment_r4_k1.cnf
    <snip>
    restarts              : 354
    conflicts             : 130444         (6942 /sec)
    decisions             : 159038         (0.00 % random) (8464 /sec)
    propagations          : 94165695       (5011479 /sec)
    CPU time              : 18.79 s
       
Todo:
Using the 1-base box translation
  • Translation of aes(4,1,16,4):
  • Generating small-scale AES for 4 + 1/3 rounds:
    num_rounds : 4$
    num_rows : 1$
    num_columns : 16$
    exp : 4$
    final_round_b : false$
    box_tran : aes_rbase_box$
    seed : 1$
    mc_tran : aes_mc_bidirectional$
    output_ss_fcl_std(num_rounds, num_columns, num_rows, exp, final_round_b, box_tran, mc_tran)$
    
    shell> cat ssaes_r4_c16_rw1_e4_f0.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG n
     n non_taut_c red_l taut_c orig_l comment_count finished_bool
    1248 5244 15824 0 15824 1249 1
     length count
    1 16
    2 1024
    3 3056
    4 1148
       
  • In this translation, we have:
    • 4 full rounds (Key Addition, SubBytes, and MixColumns operation).
    • 68 S-boxes:
      • 64 from SubBytes = 16 byte * 4 rounds;
      • 4 from key schedule = 1 row * 1 byte * 4 rounds.
    • 1088 additions:
      • 512 additions of arity 1:
        • 256 from MixColumns = 1 row * 16 columns * 2 directions (forward + inverse) * 4 bits * 4 rounds.
      • 560 additions of arity 2:
        • 256 from key additions = 64 bits * 4 round;
        • 64 from final key addition = 64 bits;
        • 240 from the key schedule = (64 bits - 4 bits) * 4 round.
      • 16 additions of arity 3:
        • 16 from the key schedule = 4 bits * 4 rounds.
    • 16 bits for the constant in the key schedule = 4 bits * 4 rounds.
  • The number of clauses of each length in the translation, computed by:
    maxima> ncl_list_fcs(ev_hm(ss_sbox_rbase_cnfs,4));
    [[3,12],[4,15]]
       
  • This instance has the following number of clauses of length:
    • 1 : 16 = key schedule constant * 1;
    • 2 : 1024 = 512 additions (arity 1) * 2;
    • 3 : 3056 = 68 S-boxes * 12 + 560 additions (arity 2) * 4;
    • 4 : 1148 = 68 S-boxes * 15 + 16 additions (arity 3) * 8;
  • Then we can generate a random assignment with the plaintext and ciphertext, leaving the key unknown:
    maxima> output_ss_random_pc_pair(seed,num_rounds,num_columns,num_rows,exp,final_round_b);
       
    and the merging the assignment with the translation:
    shell> AppendDimacs-O3-DNDEBUG ssaes_r4_c16_rw1_e4_f0.cnf ssaes_pkpair_r4_c16_rw1_e4_f0_s1.cnf > experiment_r4_k1.cnf
       
  • minisat-2.2.0 solves it in 8s:
    shell> minisat-2.2.0 experiment_r4_k1.cnf
    <snip>
    restarts              : 325
    conflicts             : 122695         (15356 /sec)
    decisions             : 137095         (0.00 % random) (17158 /sec)
    propagations          : 42281428       (5291793 /sec)
    CPU time              : 7.99 s
       

Definition in file 4_13.hpp.