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 4-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 4-bit field elements.

Todo:
Standard "box" translations
  • We consider the default decomposition into small boolean functions for aes(r,2,1,4) discussed in "Problem specification" AdvancedEncryptionStandard/plans/KeyDiscovery/016/2_1_8/general.hpp.
  • Splitting aes(r,2,1,4) 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 8x1 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).
    • 32*r + 8 additions of arity 2:
      • 8*r from key additions = 8 bits * r round;
      • 8 from final key addition = 8 bits;
      • 4*r from the key schedule = 1 rows * 4 bits * r round.
      • 8*r from forward MixColumns = 2 rows * 1 column * 4 bits * r rounds;
      • 8*r from inverse MixColumns = 2 rows * 1 column * 4 bits * r rounds.
    • 4*r bits for the constant in the key schedule = 4 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(8,16);
    [[2,128],[9,16],[16,1]]
       
  • This instance has 6 * r boxes = 2*r S-boxes + 4*r multiplications.
  • This instance has the following number of clauses of length:
    • 1 : 8*r = key schedule constant * 1;
    • 2 : 1536*r = 12*r boxes * 128;
    • 3 : 128*r + 32 = 32*r+8 additions (arity 2) * 4;
    • 9 : 96*r = 6*r boxes * 16;
    • 16 : 12*r = 6*r boxes * 1.
Todo:
The 1-base box translation
  • 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,4));
    [[3,12],[4,15]]
    maxima> ncl_list_fcs(ev_hm(ss_field_rbase_cnfs,[4,2]));
    [[2,6],[3,4]]
    maxima> ncl_list_fcs(ev_hm(ss_field_rbase_cnfs,[4,3]));
    [[3,16],[4,8]]
       
  • 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.