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> 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.