OKlibrary  0.2.1.6
FieldOperationsAnalysis.hpp File Reference

Plans for the cryptanalysis of the Rijndael field operations. More...

Go to the source code of this file.


Detailed Description

Plans for the cryptanalysis of the Rijndael field operations.

Todo:
Add XOR translations for field multiplications
  • The AES field multiplications are simply multiplications by an 8x8 bit matrix (this is the same even for the small scale, it simply becomes a 4x4 or e * e bit matrix), and therefore, we could simply translate this function as a series of XOR (+ possibly negating variables) constraints.
  • Such translations might benefit solvers which make use of XOR constraints.
  • This should also be useful when considering rearranging linear components of the AES (see "Rearranging linear components of Sbox and MixColumns" in Cryptology/Lisp/Cryptanalysis/Rijndael/plans/Translations.hpp) .
  • See ss_mixcolumn_boolm_cstr_cstl in Cryptanalysis/Rijndael/ConstraintTemplateSmallScaleRewriteRules.mac for an "XOR" translation of the whole MixColumns.
Todo:
Move experimental todos to investigations
  • The following todos need to be split and moved to Cryptography/AdvancedEncryptionStandard/plans/Representations/:
    • Generate good CNF hitting clause-sets for the AES Field Operations.
    • Extracting prime implicate representations from the hitting-cls-representations .
    • Find the symmetries of the AES Field Operations .
Todo:
Generate good CNF hitting clause-sets for the AES Field Operations
  • Multiplication by 2 in Rijndael's byte field (GF(2^8)).
    statistics_cs(rijnmult2hittingcnf_fcs(intToGF2t8Poly(2),dll_heuristics_max_lit));
    [16, 522, 7244, 16, 3]
       
  • Multiplication by 3 in Rijndael's byte field (GF(2^8)).
    statistics_cs(rijnmult2hittingcnf_fcs(intToGF2t8Poly(3),dll_heuristics_max_lit));
    [16, 842, 11592, 16, 3]
       
  • Multiplication by 9 in Rijndael's byte field (GF(2^8)).
    statistics_cs(rijnmult2hittingcnf_fcs(intToGF2t8Poly(9),dll_heuristics_max_lit));
    [16, 1192, 15742, 16, 4]
       
  • Multiplication by 11 in Rijndael's byte field (GF(2^8)).
    statistics_cs(rijnmult2hittingcnf_fcs(intToGF2t8Poly(11),dll_heuristics_max_lit));
    [16, 1270, 17012, 16, 5]
       
  • Multiplication by 13 in Rijndael's byte field (GF(2^8)).
    statistics_cs(rijnmult2hittingcnf_fcs(intToGF2t8Poly(13),dll_heuristics_max_lit));
    [16, 1230, 16180, 16, 6]
       
  • Multiplication by 14 in Rijndael's byte field (GF(2^8)).
    statistics_cs(rijnmult2hittingcnf_fcs(intToGF2t8Poly(14),dll_heuristics_max_lit));
    [16, 1312, 17406, 16, 4]
       
Todo:
Prime implicate representations from hitting-cls-representations
  • As explained in "Hitting clause-sets" in Satisfiability/Lisp/Primality/plans/PrimeImplicatesImplicants.hpp, given a hitting clause-set representation, from it we can obtain a shorter representation by prime implicates. This is a better representation.
  • This is achieved by "replace_by_prime_implicates_hitting".
  • Multiplication by 2
    h_aes : rijnmult2hittingcnf_fcs(intToGF2t8Poly(2),dll_heuristics_max_lit)$
    p_aes : replace_by_prime_implicates_hitting(h_aes)$
    statistics_cs(p_aes);
    [16, 27, 71, 3, 2]
    ncl_list_cs(p_aes);
    [[2, 10], [3, 17]]
    irredundant_bydef(cs_to_fcs(p_aes), dll_simplest_trivial1);
    false
    ip_aes : first_irr_fcs(cs_to_fcs(p_aes), dll_simplest_trivial2)$
    statistics_cs(ip_aes[2]);
    [16, 21, 54, 3, 2]
    ncl_list_fcs(ip_aes);
    [[2, 9], [3, 12]]
    rijnmult_cnfp(intToGF2t8Poly(2),ip_aes);
    true
       
  • Multiplication by 3
    h_aes : rijnmult2hittingcnf_fcs(intToGF2t8Poly(3),dll_heuristics_max_lit)$
    p_aes : replace_by_prime_implicates_hitting(h_aes)$
    statistics_cs(p_aes);
    [16, 171, 888, 9, 3]
    ncl_list_cs(p_aes);
    [[3, 23], [4, 34], [5, 51], [6, 34], [7, 14], [8, 9], [9, 6]]
    irredundant_bydef(cs_to_fcs(p_aes), dll_simplest_trivial1);
    false
    ip_aes : first_irr_fcs(cs_to_fcs(p_aes), dll_simplest_trivial2)$
    statistics_cs(ip_aes[2]);
    [16, 61, 271, 9, 3]
    ncl_list_fcs(ip_aes);
    [[3, 19], [4, 19], [5, 11], [6, 6], [7, 2], [8, 3], [9, 1]]
    rijnmult_cnfp(intToGF2t8Poly(3),ip_aes);
    true
       
  • Multiplication by 9
    h_aes : rijnmult2hittingcnf_fcs(intToGF2t8Poly(9),dll_heuristics_max_lit)$
    p_aes : replace_by_prime_implicates_hitting(h_aes)$
    statistics_cs(p_aes);
    [16, 367, 2110, 9, 3]
    ncl_list_cs(p_aes);
    [[3, 16], [4, 49], [5, 94], [6, 97], [7, 77], [8, 31], [9, 3]]
    irredundant_bydef(cs_to_fcs(p_aes), dll_simplest_trivial1);
    false
    ip_aes : first_irr_fcs(cs_to_fcs(p_aes), dll_simplest_trivial2)$
    statistics_cs(ip_aes[2]);
    [16, 86, 402, 8, 3]
    ncl_list_fcs(ip_aes);
    [[3, 12], [4, 32], [5, 24], [6, 10], [7, 6], [8, 2]]
    rijnmult_cnfp(intToGF2t8Poly(3),ip_aes);
    true
       
  • Multiplication by 3
    h_aes : rijnmult2hittingcnf_fcs(intToGF2t8Poly(3),dll_heuristics_max_lit)$
    p_aes : replace_by_prime_implicates_hitting(h_aes)$
    statistics_cs(p_aes);
    [16, 171, 888, 9, 3]
    ncl_list_cs(p_aes);
    [[3, 23], [4, 34], [5, 51], [6, 34], [7, 14], [8, 9], [9, 6]]
    irredundant_bydef(cs_to_fcs(p_aes), dll_simplest_trivial1);
    false
    ip_aes : first_irr_fcs(cs_to_fcs(p_aes), dll_simplest_trivial2)$
    statistics_cs(ip_aes[2]);
    [16, 61, 271, 9, 3]
    ncl_list_fcs(ip_aes);
    [[3, 19], [4, 19], [5, 11], [6, 6], [7, 2], [8, 3], [9, 1]]
    rijnmult_cnfp(intToGF2t8Poly(3),ip_aes);
    true
       
  • Multiplication by 9
    h_aes : rijnmult2hittingcnf_fcs(intToGF2t8Poly(9),dll_heuristics_max_lit)$
    p_aes : replace_by_prime_implicates_hitting(h_aes)$
    statistics_cs(p_aes);
    [16, 367, 2110, 9, 3]
    ncl_list_cs(p_aes);
    [[3, 16], [4, 49], [5, 94], [6, 97], [7, 77], [8, 31], [9, 3]]
    irredundant_bydef(cs_to_fcs(p_aes), dll_simplest_trivial1);
    false
    ip_aes : first_irr_fcs(cs_to_fcs(p_aes), dll_simplest_trivial2)$
    statistics_cs(ip_aes[2]);
    [16, 86, 402, 8, 3]
    ncl_list_fcs(ip_aes);
    [[3, 12], [4, 32], [5, 24], [6, 10], [7, 6], [8, 2]]
    rijnmult_cnfp(intToGF2t8Poly(3),ip_aes);
    true
       
  • Multiplication by 11
    h_aes : rijnmult2hittingcnf_fcs(intToGF2t8Poly(11),dll_heuristics_max_lit)$
    p_aes : replace_by_prime_implicates_hitting(h_aes)$
    statistics_cs(p_aes);
    [16, 492, 2896, 9, 4]
    ncl_list_cs(p_aes);
    [[4, 40], [5, 157], [6, 155], [7, 103], [8, 33], [9, 4]]
    irredundant_bydef(cs_to_fcs(p_aes), dll_simplest_trivial1);
    false
    ip_aes : first_irr_fcs(cs_to_fcs(p_aes), dll_simplest_trivial2)$
    statistics_cs(ip_aes[2]);
    [16, 148, 767, 7, 4]
    ncl_list_fcs(ip_aes);
    [[4, 28], [5, 75], [6, 35], [7, 10]]
    rijnmult_cnfp(intToGF2t8Poly(11),ip_aes);
    true
       
  • Multiplication by 13
    h_aes : rijnmult2hittingcnf_fcs(intToGF2t8Poly(13),dll_heuristics_max_lit)$
    p_aes : replace_by_prime_implicates_hitting(h_aes)$
    statistics_cs(p_aes);
    [16, 489, 2885, 9, 4]
    ncl_list_cs(p_aes);
    [[4, 57], [5, 118], [6, 171], [7, 106], [8, 34], [9, 3]]
    irredundant_bydef(cs_to_fcs(p_aes), dll_simplest_trivial1);
    false
    ip_aes : first_irr_fcs(cs_to_fcs(p_aes), dll_simplest_trivial2)$
    statistics_cs(ip_aes[2]);
    [16, 139, 727, 9, 4]
    ncl_list_fcs(ip_aes);
    [[4, 30], [5, 63], [6, 32], [7, 13], [9, 1]]
    rijnmult_cnfp(intToGF2t8Poly(3),ip_aes);
    true
       
  • Multiplication by 14
    h_aes : rijnmult2hittingcnf_fcs(intToGF2t8Poly(14),dll_heuristics_max_lit)$
    p_aes : replace_by_prime_implicates_hitting(h_aes)$
    statistics_cs(p_aes);
    [16, 456, 2689, 9, 3]
    ncl_list_cs(p_aes);
    [[3, 4], [4, 47], [5, 118], [6, 153], [7, 96], [8, 33], [9, 5]]
    irredundant_bydef(cs_to_fcs(p_aes), dll_simplest_trivial1);
    false
    ip_aes : first_irr_fcs(cs_to_fcs(p_aes), dll_simplest_trivial2)$
    statistics_cs(ip_aes[2]);
    [16, 119, 612, 8, 3]
    ncl_list_fcs(ip_aes);
    [[3, 3], [4, 33], [5, 42], [6, 28], [7, 11], [8, 2]]
    rijnmult_cnfp(intToGF2t8Poly(3),ip_aes);
    true
       
Todo:
Find the symmetries of the AES Field Operations
Todo:
Determine *all* prime implicates (for the purpose of analysis)

Definition in file FieldOperationsAnalysis.hpp.