OKlibrary  0.2.1.6
5_13.hpp File Reference

Investigations into small-scale AES key discovery for 5 + 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 5 + 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(5,1,16,4):
  • Generating small-scale AES for 5 + 1/3 rounds:
    num_rounds : 5$
    num_rows : 1$
    num_columns : 16$
    exp : 4$
    final_round_b : false$
    box_tran : aes_ts_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_r5_c16_rw1_e4_f0.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG n
     n non_taut_c red_l taut_c orig_l comment_count finished_bool
    2872 16521 46788 0 46788 2873 1
     length count
    1 20
    2 12160
    3 2736
    4 160
    9 1360
    16 85
       
  • In this translation, we have:
    • 5 full rounds (Key Addition, SubBytes, and MixColumns operation).
    • 85 Sboxes:
      • 80 from SubBytes = 16 byte * 5 rounds;
      • 5 from key schedule = 1 row * 1 byte * 5 rounds.
    • 1344 additions:
      • 640 additions of arity 1:
        • 640 from MixColumns = 1 row * 16 columns * 2 directions (forward + inverse) * 4 bits * 5 rounds.
      • 684 additions of arity 2:
        • 320 from key additions = 64 bits * 5 round;
        • 64 from final key addition = 64 bits;
        • 300 from the key schedule = (64 bits - 4 bits) * 5 round.
      • 20 additions of arity 3:
        • 20 from the key schedule = 4 bits * 5 rounds.
    • 20 bits for the constant in the key schedule = 4 bits * 5 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 : 20 = key schedule constant * 1;
    • 2 : 12160 = 80 S-boxes * 128 + 640 additions (arity 1) * 2;
    • 3 : 2736 = 684 additions (arity 2) * 4;
    • 4 : 160 = 20 additions (arity 3) * 8;
    • 9 : 1360 = 85 S-boxes * 16;
    • 16 : 85 = 85 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_r5_c16_rw1_e4_f0.cnf ssaes_pkpair_r5_c16_rw1_e4_f0_s1.cnf > experiment_r5_k1.cnf
       
  • minisat-2.2.0 solves it in 25.4s:
    shell> minisat-2.2.0 experiment_r5_k1.cnf
    <snip>
    restarts              : 404
    conflicts             : 151945         (5982 /sec)
    decisions             : 184854         (0.00 % random) (7278 /sec)
    propagations          : 147381578      (5802424 /sec)
    CPU time              : 25.4 s
       
Todo:
Using the 1-base box translation
  • Translation of aes(5,1,16,4):
  • Generating small-scale AES for 5 + 1/3 rounds:
    num_rounds : 5$
    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_r5_c16_rw1_e4_f0.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG n
     n non_taut_c red_l taut_c orig_l comment_count finished_bool
    1512 6491 19588 0 19588 1513 1
     length count
    1 20
    2 1280
    3 3756
    4 1435
       
  • In this translation, we have:
    • 5 full rounds (Key Addition, SubBytes, and MixColumns operation).
    • 85 S-boxes:
      • 80 from SubBytes = 16 byte * 5 rounds;
      • 5 from key schedule = 1 row * 1 byte * 5 rounds.
    • 1344 additions:
      • 640 additions of arity 1:
        • 640 from MixColumns = 1 row * 16 columns * 2 directions (forward + inverse) * 4 bits * 5 rounds.
      • 684 additions of arity 2:
        • 320 from key additions = 64 bits * 5 round;
        • 64 from final key addition = 64 bits;
        • 300 from the key schedule = (64 bits - 4 bits) * 5 round.
      • 20 additions of arity 3:
        • 20 from the key schedule = 4 bits * 5 rounds.
    • 20 bits for the constant in the key schedule = 4 bits * 5 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 : 20 = key schedule constant * 1;
    • 2 : 1280 = 640 additions (arity 1) * 2;
    • 3 : 3756 = 85 S-boxes * 12 + 684 additions (arity 2) * 4;
    • 4 : 1435 = 85 S-boxes * 15 + 20 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_r5_c16_rw1_e4_f0.cnf ssaes_pkpair_r5_c16_rw1_e4_f0_s1.cnf > experiment_r5_k1.cnf
       
  • minisat-2.2.0 solves it in 239s:
    shell> minisat-2.2.0 experiment_r5_k1.cnf
    <snip>
    restarts              : 5115
    conflicts             : 2877957        (12075 /sec)
    decisions             : 3273542        (0.00 % random) (13735 /sec)
    propagations          : 869271128      (3647189 /sec)
    CPU time              : 238.34 s
       

Definition in file 5_13.hpp.