OKlibrary  0.2.1.6
Translations.hpp File Reference

Listing the translations for the small-scale AES key discovery for AES with a 2x1 plaintext matrix and 8-bit field elements. More...

Go to the source code of this file.


Detailed Description

Listing the translations for the small-scale AES key discovery for AES with a 2x1 plaintext matrix and 8-bit field elements.

Todo:
Standard "box" translations
  • We consider the default decomposition into small boolean functions for aes(r,2,1,8) discussed in "Problem specification" AdvancedEncryptionStandard/plans/KeyDiscovery/016/2_1_8/general.hpp.
  • Splitting aes(r,2,1,8) into boolean functions ("boxes") in the "standard"/"default" way:
    • The AES is decomposed into Subbytes, MixColumns and the Key schedule.
    • The Subbytes is decomposed into S-boxes.
    • The MixColumns operation is decomposed into its field multiplications (02 and 03) and addition operations.
    • The Key schedule is decomposed into S-boxes and additions using new variables to store intermediate results.
    • We treat S-boxes, field multiplications and additions as the "boxes".
    • The "boxes" are then translated using (see below):
      • "The canonical box translation".
      • "The 1-base box translation".
      • 'The "minimum" box translation".
  • The MixColumns operation is translated by translating both the MixColumns operation and its inverse (it is self-inverse).
  • Size of boolean functions:
    • The S-box and field multiplications are considered as a 16x1 boolean functions.
    • Additions of arity k are considered bit-wise as (k+1)-bit to 1-bit boolean functions; translated using their prime implicates.
  • In any standard "box" translation, for r rounds, we have:
    • r full rounds (Key Addition, SubBytes, and MixColumns operation).
    • 4*r Sboxes:
      • 2*r from SubBytes = 2 byte * r rounds;
      • 2*r from key schedule = 2 row * 1 byte * r rounds.
    • 4*r multiplications by 02: 2 rows * 1 multiplication * 1 columns * r rounds * 2 directions (forward + inverse).
    • 4*r multiplications by 03: 2 rows * 1 multiplication * 1 columns * r rounds * 2 directions (forward + inverse).
    • 56*r + 16 additions of arity 2:
      • 16*r from key additions = 16 bits * r round;
      • 16 from final key addition = 16 bits;
      • 8*r from the key schedule = 1 rows * 8 bits * r round.
      • 16*r from forward MixColumns = 2 rows * 1 column * 8 bits * r rounds;
      • 16*r from inverse MixColumns = 2 rows * 1 column * 8 bits * r rounds.
    • 8*r bits for the constant in the key schedule = 8 bits * r rounds.
  • Note that as this variant has only one column, the key schedule applies Sbox(K_i) + C rather than Sbox(K_i) + K_j + C where K_i and K_j are key words from the previous round key.
Todo:
The canonical box translation
  • Using the 'Standard "box" translation' (see above).
  • The Sboxes and multiplications boxes are translated using the canonical translation, which has the following number of clauses of each length:
    maxima> ncl_list_full_dualts(16,256);
    [[2,4096],[17,256],[256,1]]
       
  • This instance has 120 boxes = 40 S-boxes + 80 multiplications.
  • This instance has the following number of clauses of length:
    • 1 : 8*r = key schedule constant * 1;
    • 2 : 49152*r = 12*r boxes * 4096;
    • 3 : 224*r + 64 = 56*r+16 additions (arity 2) * 4;
    • 17 : 3072*r = 120 boxes * 256;
    • 256 : 12*r = 120 boxes * 1.
Todo:
The 1-base box translation
  • There are currently active investigations attempting to find the minimum-size 1-base representations for each of the boxes, discussed in
  • Generating the smallest (so far) 1-base for the S-box (as of 05/08/2011) from AdvancedEncryptionStandard/plans/Representations/Sbox_8.hpp:
    maxima> output_rijnsbox_fullcnf_stdname();
    shell> QuineMcCluskey-n16-O3-DNDEBUG AES_Sbox_full.cnf > AES_Sbox_pi.cnf
    shell> RandomShuffleDimacs-O3-DNDEBUG 103 < AES_Sbox_pi.cnf | SortByClauseLength-O3-DNDEBUG > AES_Sbox_sortedpi.cnf
    shell> RUcpGen-O3-DNDEBUG AES_Sbox_sortedpi.cnf > AES_Sbox_gen.cnf
    shell> RandomShuffleDimacs-O3-DNDEBUG 1 < AES_Sbox_gen.cnf | SortByClauseLengthDescending-O3-DNDEBUG | RUcpBase-O3-DNDEBUG > AES_Sbox_base.cnf
    shell> cat AES_Sbox_base.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG n
         pn      pc      n    nmi       c        l     n0   n0mi      c0       l0  cmts
         16    4398     16     16    4398    30108     NA     NA    4398    30108     0
     length   count
          5       1
          6    1187
          7    2703
          8     503
          9       4
       
  • Generating the smallest (so far) 1-base for the multiplication by 02 and 03 the (as of 05/08/2011) from Cryptography/AdvancedEncryptionStandard/plans/Representations/Mul_2_8.hpp and Cryptography/AdvancedEncryptionStandard/plans/Representations/Mul_3_8.hpp:
    maxima> output_rijn_mult_fullcnf_stdname(2);
    shell> QuineMcCluskey-n16-O3-DNDEBUG AES_byte_field_mul_full_2.cnf > AES_byte_field_mul_2_pi.cnf
    shell> RandomShuffleDimacs-O3-DNDEBUG 1 < AES_byte_field_mul_2_pi.cnf | SortByClauseLength-O3-DNDEBUG > AES_byte_field_mul_2_sortedpi.cnf
    shell> RUcpGen-O3-DNDEBUG AES_byte_field_mul_2_sortedpi.cnf > AES_byte_field_mul_2_gen.cnf
    shell> RandomShuffleDimacs-O3-DNDEBUG 1 < AES_byte_field_mul_2_gen.cnf | SortByClauseLengthDescending-O3-DNDEBUG | RUcpBase-O3-DNDEBUG > AES_byte_field_mul_2_base.cnf
    shell> cat AES_byte_field_mul_2_base.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG n
         pn      pc      n    nmi       c        l     n0   n0mi      c0       l0  cmts
         16      22     16     16      22       56     NA     NA      22       56     0
     length   count
          2      10
          3      12
    maxima> output_rijn_mult_fullcnf_stdname(3);
    shell> QuineMcCluskey-n16-O3-DNDEBUG AES_byte_field_mul_full_3.cnf > AES_byte_field_mul_3_pi.cnf
    shell> RandomShuffleDimacs-O3-DNDEBUG 1 < AES_byte_field_mul_3_pi.cnf | SortByClauseLength-O3-DNDEBUG > AES_byte_field_mul_3_sortedpi.cnf
    shell> RUcpGen-O3-DNDEBUG AES_byte_field_mul_3_sortedpi.cnf > AES_byte_field_mul_3_gen.cnf
    shell> RandomShuffleDimacs-O3-DNDEBUG 1 < AES_byte_field_mul_3_gen.cnf | SortByClauseLengthDescending-O3-DNDEBUG | RUcpBase-O3-DNDEBUG > AES_byte_field_mul_3_base.cnf
    shell> cat AES_byte_field_mul_3_base.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG n
         pn      pc      n    nmi       c        l     n0   n0mi      c0       l0  cmts
         16      80     16     16      80      328     NA     NA      80      328     0
     length   count
          3      24
          4      24
          5      32
       
  • The Sboxes and multiplications use 1-base translations, which have the following number of clauses of each length:
    maxima> ncl_list_fcs(ev_hm(ss_sbox_rbase_cnfs,8));
    [[5,1],[6,1187],[7,2703],[8,503],[9,4]]
    maxima> ncl_list_fcs(ev_hm(ss_field_rbase_cnfs,[8,2]))
    [[2,10],[3,12]]
    maxima> ncl_list_fcs(ev_hm(ss_field_rbase_cnfs,[8,3]))
    [[3,24],[4,24],[5,32]]
       
  • This instance has the following number of clauses of length:
    • 1 : 8*r = key schedule constant * 1;
    • 2 : 4*r = 4*r multiplications by 02 * 10;
    • 3 : 368*r + 64 = 4*r multiplications by 02 * 12 + 4*r multiplications by 03 * 24 + 56*r+16 additions (arity 2) * 4;
    • 4 : 96*r = 4*r multiplications by 03 * 24;
    • 5 : 132 = 4*r S-boxes * 1 + 4 multiplications by 03 * 32;
    • 6 : 4748*r = 4*r S-boxes * 1187;
    • 7 : 10812*r = 4*r S-boxes * 2703;
    • 8 : 2012*r = 4*r S-boxes * 503;
    • 9 : 16*r = 4*r S-boxes * 4.
Todo:
The "minimum" box translation:
  • There are currently active investigations attempting to find the minimum representations for each of the boxes, discussed in
  • The smallest "minimum" representations for the S-box (as of 05/09/2011) and multiplications by 02 and 03 from AdvancedEncryptionStandard/plans/Representations/Sbox_8.hpp, AdvancedEncryptionStandard/plans/Representations/Mul_2_8.hpp and AdvancedEncryptionStandard/plans/Representations/Mul_3_8.hpp :
    /* Multiplication by 02: */
    maxima> FieldMul2CNF : [{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16},{{-9,2},{-2,9},{-10,3},{-3,10},{-11,4},{-4,11},{-12,-5,-1},{-12,1,5},{-5,1,12},{-1,5,12},{-13,-6,-1},{-1,6,13},{-14,7},{-7,14},{-15,1,8},{-8,1,15},{-16,-15,-8},{-16,8,15},{-13,6,16},{-6,13,16}}]$
    set_hm(ss_field_cnfs,[8,2], FieldMul2CNF));
    /* Multiplication by 03: */
    maxima> FieldMul3CNF :
     [[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],
      [{-9,-2,-1},{-2,1,9},{-10,2,3},{-10,-9,-3,1},{-10,-3,-1,9},{-3,2,10},{-9,1,3,10},{-1,3,9,10},{-11,-4,-3},{-11,3,4},{-4,3,11},{-3,4,11},{-12,-5,-4,1},{-12,-4,-1,5},{-5,1,4,12},{-1,4,5,12},{-13,-5,-1,6},{-13,1,5,6},{-13,-12,-6,4},{-13,-6,-4,12},{-6,-5,-1,13},{-6,1,5,13},
       {-12,4,6,13},{-4,6,12,13},{-14,-7,-6},{-14,6,7},{-7,6,14},{-6,7,14},{-16,-8,-1},{-16,1,8},{-16,-15,-7},{-16,7,15},{-8,1,16},{-1,8,16},{-15,7,16},{-7,15,16}]]$
    set_hm(ss_field_cnfs,[8,2], FieldMul3CNF));
    /* Sbox: */
    maxima> output_rijnsbox_fullcnf_stdname();
    shell> QuineMcCluskeySubsumptionHypergraph-n16-O3-DNDEBUG AES_Sbox_full.cnf > AES_Sbox_shg.cnf
    shell> cat AES_Sbox_shg.cnf | MinOnes2WeightedMaxSAT-O3-DNDEBUG > AES_Sbox_shg.wcnf
    shell> ubcsat-okl  -alg gsat -w -runs 100 -cutoff 40000000 -wtarget 294 -solve 1 -seed 3213901809 -i AES_Sbox_shg.wcnf -r model AES_Sbox_s294.ass;
    shell> cat  AES_Sbox_full.cnf_primes | FilterDimacs AES_Sbox_s294.ass > AES_Sbox_s294.cnf
    maxima> SboxMinCNF : read_fcl_f("AES_Sbox_s294.cnf");
    maxima> set_hm(ss_sbox_cnfs,8, SboxMinCNF));
       
  • The Sboxes and multiplications use the "minimum" translations, which have the following number of clauses of each length:
    maxima> ncl_list_fcs(ev_hm(ss_sbox_cnfs,8));
    [[6,143],[7,127],[8,24]]
    maxima> ncl_list_fcs(ev_hm(ss_field_cnfs,[8,2]))
    [[2,8],[3,12]]
    maxima> ncl_list_fcs(ev_hm(ss_field_cnfs,[8,3]))
    [[3,20],[4,16]]
       
  • This instance has the following number of clauses of length:
    • 1 : 8*r = key schedule constant * 1;
    • 2 : 32*r = 4*r multiplications by 02 * 8;
    • 3 : 352*r + 64 = 4*r multiplications by 02 * 12 + 4*r multiplications by 03 * 20 + 56*r+16 additions (arity 2) * 4;
    • 4 : 64*r = 4*r multiplications by 04 * 16;
    • 6 : 572*r = 4*r S-boxes * 143;
    • 7 : 508*r = 4*r S-boxes * 127;
    • 8 : 96*r = 4*r S-boxes * 24.

Definition in file Translations.hpp.