OKlibrary  0.2.1.6
general.hpp
Go to the documentation of this file.
00001 // Matthew Gwynne, 21.12.2011 (Swansea)
00002 /* Copyright 2011, 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 Statistics | tail -n 1 | awk " { print \$0 \" ${r} ${s}\"}";
00161   done;
00162 done) > AllStatistics
00163 shell> oklib --R
00164 R> E = read.table("AllStatistics", header=TRUE)
00165 R> aggregate(E, by=list(r=E$r), FUN=mean)
00166  r            t        cfs        dec     rts           r1  stime         cfl
00167  1   0.00289900      18.80      34.65    1.00 1.224150e+03 0.0000      129.30
00168  2   0.00864825     150.95     202.25    1.95 2.054995e+04 0.0000     2323.00
00169  3   0.09938440    3205.55    4061.70   16.55 4.692709e+05 0.0025    63898.15
00170  4   1.97394910   56095.80   66470.75  169.10 8.556475e+06 0.0065  1205026.60
00171  5   3.58265675   83325.50   99447.50  228.20 1.584073e+07 0.0085  1662965.60
00172  6   4.48276720   79253.75   92244.20  215.45 2.260616e+07 0.0100  1585754.65
00173  7  32.95754350  673276.10  780147.80 1372.25 1.296335e+08 0.0100 15616870.40
00174  8  88.57197750 1363225.75 1547851.75 2548.10 3.033040e+08 0.0100 33078622.35
00175  9 236.31324750 2414303.30 2701230.55 4162.85 8.848807e+08 0.0100 59058436.75
00176 10 109.43531050  865097.75  962761.35 1690.90 5.363367e+08 0.0100 23500386.20
00177 11 274.08449150 1634774.60 1774671.55 2806.60 1.400587e+09 0.0100 48309179.50
00178 12 349.99709250 1930769.45 2092893.60 3417.20 1.857727e+09 0.0105 57083817.35
00179 13 368.13081900 1845160.60 1999870.65 3218.90 1.961107e+09 0.0140 53564687.30
00180 14 369.74578100 1768702.95 1919838.65 3168.10 1.963695e+09 0.0185 51190010.85
00181 15 524.95462800 2352615.10 2561227.70 4050.25 2.768973e+09 0.0195 66714646.00
00182 16 458.02631000 1976219.90 2145367.45 3464.30 2.418103e+09 0.0200 55211831.15
00183 17 672.52478500 2686551.65 2926971.10 4597.70 3.527381e+09 0.0200 71261989.50
00184 18 365.57899500 1403151.65 1531964.35 2528.55 1.883815e+09 0.0200 38047782.20
00185 19 377.10726400 1366766.50 1495685.00 2482.60 1.950081e+09 0.0200 36869190.45
00186 20 719.15839000 2342798.75 2550079.70 4080.80 3.590161e+09 0.0200 60994987.80
00187 R> aggregate_statistics(E[c("t","cfs","r1")], by=list("r"))
00188  r       t.mean         t.sd     t.min       t.max   cfs.mean       cfs.sd cfs.min  cfs.max      r1.mean        r1.sd    r1.min      r1.max
00189  1   0.00289900 1.293709e-03  0.000999    0.004999      18.80 2.360999e+01       0       84 1.224150e+03 1.089476e+03       198        3927
00190  2   0.00864825 3.616275e-03  0.003999    0.016997     150.95 1.253565e+02       9      442 2.054995e+04 1.754647e+04      1609       65020
00191  3   0.09938440 8.277337e-02  0.008998    0.284956    3205.55 2.800350e+03      80     9309 4.692709e+05 4.167659e+05     13427     1444607
00192  4   1.97394910 1.496775e+00  0.104984    5.143220   56095.80 4.086345e+04    2909   142429 8.556475e+06 6.385982e+06    490058    21435727
00193  5   3.58265675 2.886426e+00  0.219966   10.037500   83325.50 6.302153e+04    5946   234841 1.584073e+07 1.230094e+07   1143085    43608241
00194  6   4.48276720 6.237955e+00  0.222966   27.984700   79253.75 9.916875e+04    5716   446965 2.260616e+07 2.967857e+07   1141349   131376957
00195  7  32.95754350 2.301329e+01  2.011690   69.493400  673276.10 4.449626e+05   46826  1318893 1.296335e+08 8.960912e+07   8816866   273159976
00196  8  88.57197750 1.075224e+02  8.889650  455.307000 1363225.75 1.587446e+06  135626  6737200 3.033040e+08 3.342192e+08  39028463  1418482701
00197  9 236.31324750 2.586699e+02  4.246350  929.702000 2414303.30 2.418932e+06   38307  7539012 8.848807e+08 9.838747e+08  26266158  3873827416
00198 10 109.43531050 1.169486e+02  1.847720  471.945000  865097.75 1.061478e+06   16099  4391594 5.363367e+08 4.802721e+08  12212167  1687833673
00199 11 274.08449150 3.370047e+02  2.452630  953.102000 1634774.60 1.949354e+06   21063  5532892 1.400587e+09 1.678051e+09  15861059  4966487634
00200 12 349.99709250 3.326717e+02  5.589150  974.785000 1930769.45 1.789485e+06   42397  5486904 1.857727e+09 1.712279e+09  35167582  5002124985
00201 13 368.13081900 5.632656e+02  2.462630 2440.090000 1845160.60 2.644793e+06   18447 11390661 1.961107e+09 2.931591e+09  15852466 12752829538
00202 14 369.74578100 4.024378e+02  3.183520 1216.630000 1768702.95 1.841572e+06   22738  5584888 1.963695e+09 2.086437e+09  19888665  6436460574
00203 15 524.95462800 5.020760e+02  3.556460 1571.380000 2352615.10 2.121471e+06   24803  6581662 2.768973e+09 2.561089e+09  22358567  7975512835
00204 16 458.02631000 4.832726e+02  1.943700 1424.980000 1976219.90 2.010594e+06   13837  6029348 2.418103e+09 2.506961e+09  12390420  7414909692
00205 17 672.52478500 6.478584e+02 24.673200 1889.140000 2686551.65 2.477644e+06  126669  7331165 3.527381e+09 3.340573e+09 145464097  9751285452
00206 18 365.57899500 5.626881e+02 20.710900 1817.420000 1403151.65 2.074508e+06  100681  6793247 1.883815e+09 2.816790e+09 121935860  9163018204
00207 19 377.10726400 3.895595e+02  8.671680 1513.270000 1366766.50 1.337108e+06   42785  5175280 1.950081e+09 1.969615e+09  53495371  7704961316
00208 20 719.15839000 8.707486e+02 43.520400 3511.650000 2342798.75 2.612606e+06  179737 10423224 3.590161e+09 4.095705e+09 248504001 16328426069
00209      \endverbatim
00210      </li>
00211     </ul>
00212    </li>
00213   </ul>
00214 
00215 
00216   \todo The 1-base box translation
00217   <ul>
00218    <li> The Sboxes and multiplications boxes are translated using the
00219    1-base translation, discussed in "The 1-base box translation"
00220    in
00221    plans/KeyDiscovery/016/2_1_8/Translations.hpp
00222    where statistics are also provided. </li>
00223    <li> There are currently active investigations attempting to find the
00224    minimum-size 1-base representations for each of the boxes, discussed in
00225     <ul>
00226      <li> AdvancedEncryptionStandard/plans/Representations/Sbox_8.hpp.
00227      </li>
00228      <li> AdvancedEncryptionStandard/plans/Representations/Mul_2_8.hpp.
00229      </li>
00230      <li> AdvancedEncryptionStandard/plans/Representations/Mul_3_8.hpp.
00231      </li>
00232     </ul>
00233    </li>
00234    <li> Over 20 rounds, with 20 random plaintext-ciphertext-pairs per round:
00235     <ul>
00236      <li> For instructions on generating the 1-bases, see
00237      "The 1-base box translation" in
00238      AdvancedEncryptionStandard/plans/KeyDiscovery/016/2_1_8/Translations.hpp.
00239      </li>
00240      <li> Generating the instances (in Maxima):
00241      \verbatim
00242 oklib_monitor : true$
00243 set_hm(ss_sbox_rbase_cnfs,8,read_fcl_f("AES_Sbox_base.cnf"))$
00244 set_hm(ss_field_rbase_cnfs,[8,2],read_fcl_f("AES_byte_field_mul_2_base.cnf"))$
00245 set_hm(ss_field_rbase_cnfs,[8,3],read_fcl_f("AES_byte_field_mul_3_base.cnf"))$
00246 for rounds : 1 thru 20 do
00247   output_ss_fcl_std(rounds, num_columns : 1, num_rows : 2, exp : 8, final_round_b : false, box_tran : aes_rbase_box, mc_tran : aes_mc_bidirectional)$
00248      \endverbatim
00249      </li>
00250      <li> Generating 20 random assignments for the plaintext and ciphertext,
00251      leaving the key unknown:
00252      \verbatim
00253 maxima> for seed : 1 thru 20 do output_ss_random_pc_pair(seed,rounds,num_columns,num_rows,exp,final_round_b);
00254      \endverbatim
00255      </li>
00256      <li> Running minisat-2.2.0:
00257      \verbatim
00258 shell> col=1; row=2; e=8;
00259 for r in $(seq 1 20); do
00260   for k in $(seq 1 20); do
00261       echo "Key ${k} Round ${r}";
00262       AppendDimacs-O3-DNDEBUG ssaes_r${r}_c${col}_rw${row}_e${e}_f0.cnf ssaes_pcpair_r${r}_c${col}_rw${row}_e${e}_f0_s${k}.cnf > r${r}_k${k}.cnf;
00263       minisat-2.2.0 r${r}_k${k}.cnf > minisat_r${r}_k${k}.result 2>&1;
00264   done;
00265 done
00266 shell> ExtractMinisat header-only | awk ' { print $0 " r k" }' > minisat_results;
00267 for r in $(seq 1 20); do
00268   for k in $(seq 1 20); do
00269     cat minisat_r${r}_k${k}.result | ExtractMinisat data-only | awk " { print \$0 \"  $r  $k\" }";
00270   done;
00271 done >> minisat_results;
00272      \endverbatim
00273      yields:
00274      \verbatim
00275 shell> oklib --R
00276 E = read.table("minisat_results", header=TRUE)
00277 EM = aggregate(E, by=list(r=E$r), FUN=mean)
00278 options(width=1000)
00279 EM
00280  r   rn     rc        t       cfs       dec    rts          r1  ptime  stime       cfl
00281  1  192  18272   0.5285    378.40    407.10   3.55    17333.15 0.0110 0.5115    2898.3
00282  2  336  36480   9.6240  38637.05  41081.25 125.30  3096961.95 0.0205 0.9600  635664.8
00283  3  480  54688  15.2920  37360.50  39724.25 118.35  5821360.20 0.0350 1.4000  569780.4
00284  4  624  72896  24.8370  45409.70  49792.90 138.35  8149119.90 0.0445 1.8700  817007.7
00285  5  768  91104  30.2230  40354.70  44488.95 130.10  9966599.80 0.0570 2.3100  644105.6
00286  6  912 109312  46.9385  56145.40  62684.00 170.25 14110385.50 0.0640 2.7595  888331.9
00287  7 1056 127520  46.7475  53666.90  61842.45 166.15 13175222.50 0.0785 3.1975  853229.2
00288  8 1200 145728 102.3470  84242.95  96100.55 239.45 24387576.30 0.0915 3.6640 1316421.4
00289  9 1344 163936 117.9040  87504.90 101635.25 251.80 27133294.20 0.1015 4.1090 1399346.6
00290 10 1488 182144 143.2785  97662.45 114138.40 273.80 30732365.70 0.1130 4.5550 1627517.4
00291 11 1632 200352 100.5410  82608.05 100458.20 239.20 21793714.35 0.1245 4.9960 1477655.9
00292 12 1776 218560 162.2785 112890.40 135246.05 309.75 33442510.10 0.1345 5.4655 2002968.6
00293 13 1920 236768 219.8780 128707.95 154327.85 350.65 44485694.45 0.1510 5.9085 2238872.5
00294 14 2064 254976 277.6545 149758.45 179119.00 397.55 54358522.10 0.1570 6.3560 2664466.5
00295 15 2208 273184 278.9755 154428.90 186527.30 408.50 54256192.65 0.1710 6.7920 2824605.1
00296 16 2352 291392 244.3250 144208.05 177472.55 386.45 48356482.55 0.1835 7.2620 2758481.2
00297 17 2496 309600 283.3340 163903.60 202336.40 422.85 54694309.85 0.1970 7.7045 3221092.9
00298 18 2640 327808 350.5680 180847.40 222289.35 461.60 66776355.60 0.2075 8.1530 3461162.0
00299 19 2784 346016 350.7520 182180.55 226259.50 453.00 66744064.25 0.2190 8.5940 3528544.8
00300 20 2928 364224 365.6620 194371.05 242715.75 491.40 69723963.15 0.2275 9.0660 3904121.5
00301      \endverbatim
00302      </li>
00303      <li> Consider:
00304      \verbatim
00305 R> plot(E$cfs)
00306 R> plot(E$t)
00307      \endverbatim
00308      The minisat-2.2.0 times and number of conflicts appear to be linear in
00309      the number of rounds! </li>
00310     </ul>
00311    </li>
00312   </ul>
00313 
00314 
00315   \todo The "minimum" box translation
00316   <ul>
00317    <li> The Sboxes and multiplications boxes are translated using the
00318    "minimum" translations, discussed in 'The "minimum" box translation'
00319    in
00320    plans/KeyDiscovery/016/2_1_8/Translations.hpp
00321    where statistics are also provided. </li>
00322    <li> There are currently active investigations attempting to find the
00323    minimum representations for each of the boxes, discussed in
00324     <ul>
00325      <li> AdvancedEncryptionStandard/plans/Representations/Sbox_8.hpp.
00326      </li>
00327      <li> AdvancedEncryptionStandard/plans/Representations/Mul_2_8.hpp.
00328      </li>
00329      <li> AdvancedEncryptionStandard/plans/Representations/Mul_3_8.hpp.
00330      </li>
00331     </ul>
00332    </li>
00333    <li> Over 20 rounds, with 20 random plaintext-ciphertext-pairs per round:
00334     <ul>
00335      <li> For instructions on generating the 1-bases, see
00336      'The "minimum" box translation' in
00337      plans/KeyDiscovery/016/2_1_8/Translations.hpp.
00338      </li>
00339      <li> Generating the instances (in Maxima):
00340      \verbatim
00341 oklib_monitor : true$
00342 for rounds : 1 thru 20 do
00343   output_ss_fcl_std(rounds, num_columns : 1, num_rows : 2, exp : 8, final_round_b : false, box_tran : aes_small_box, mc_tran : aes_mc_bidirectional)$
00344      \endverbatim
00345      </li>
00346      <li> Generating 20 random assignments for the plaintext and ciphertext,
00347      leaving the key unknown:
00348      \verbatim
00349 maxima> for seed : 1 thru 20 do output_ss_random_pc_pair(seed,rounds,num_columns,num_rows,exp,final_round_b);
00350      \endverbatim
00351      </li>
00352      <li> Running minisat-2.2.0:
00353      \verbatim
00354 shell> col=1; row=2; e=8;
00355 for r in $(seq 1 20); do
00356   for k in $(seq 1 20); do
00357       echo "Key ${k} Round ${r}";
00358       AppendDimacs-O3-DNDEBUG ssaes_r${r}_c${col}_rw${row}_e${e}_f0.cnf ssaes_pcpair_r${r}_c${col}_rw${row}_e${e}_f0_s${k}.cnf > r${r}_k${k}.cnf;
00359       minisat-2.2.0 r${r}_k${k}.cnf > minisat_r${r}_k${k}.result 2>&1;
00360   done;
00361 done
00362 shell> ExtractMinisat header-only | awk ' { print $0 " r k" }' > minisat_results;
00363 for r in $(seq 1 7); do
00364   for k in $(seq 1 20); do
00365     cat minisat_r${r}_k${k}.result | ExtractMinisat data-only | awk " { print \$0 \"  $r  $k\" }";
00366   done;
00367 done >> minisat_results;
00368      \endverbatim
00369      yields:
00370      \verbatim
00371 shell> oklib --R
00372 E = read.table("minisat_results", header=TRUE)
00373 EM = aggregate(E, by=list(r=E$r), FUN=mean)
00374 options(width=1000)
00375 EM
00376 r   rn    rc         t sat         cfs          dec       rts         r1    mem ptime  stime          cfl
00377 1  192  1672    0.0000   1      2172.9      2519.45     12.85      30390  19.00 0.000 0.0000      20832.6
00378 2  336  3280    6.5950   1    409431.4    500513.75    890.90   10805115   8.00 0.000 0.0100    5935048.8
00379 3  480  4888   41.2035   1   2037583.0   2750387.90   3644.10   57608122  10.30 0.003 0.0110   31753123.5
00380 4  624  6496  175.4085   1   7296806.1   9758815.50  11511.35  211049076  19.80 0.007 0.0200  121938539.2
00381 5  768  8104 1283.3405   1  34959474.8  45516313.85  47351.05 1298488466  46.30 0.010 0.0200  653104802.5
00382 6  912  9712 2271.9195   1  49611107.0  64456781.95  64882.05 2092377044  62.45 0.010 0.0215  995531156.5
00383 7 1056 11320 8378.2225   1 136949749.2 176287970.80 164861.05 6692014820 116.10 0.010 0.0300 2934315940.0
00384      \endverbatim
00385      </li>
00386      <li> Consider:
00387      \verbatim
00388 R> plot(E$cfs)
00389 R> plot(E$t)
00390      \endverbatim
00391      The minisat-2.2.0 times and number of conflicts grow much more quickly in
00392      the number of rounds than the 1-base and canonical translations. Is this
00393      exponential growth? </li>
00394      <li> We need data for more rounds. </li>
00395     </ul>
00396    </li>
00397   </ul>
00398 
00399 */