OKlibrary  0.2.1.6
general.hpp File Reference

On investigations into the Data Encryption Standard. More...

Go to the source code of this file.

## Detailed Description

On investigations into the Data Encryption Standard.

Todo:
Todo:
Analysing the S-boxes
• Most urgent is to use all our instruments to analyse the 8 S-boxes.
• Of course, starting with defining them at Maxima-level.
• Considering them as one 10-bit boolean function, or as 4 6-bit boolean functions. Likely better the first view, but we need to consider all possibilities.
• See "Add 6-to-1 bit Sbox functions" in ComputerAlgebra/Cryptology/Lisp/Cryptanalysis/DataEncryptionStandard/plans/general.hpp.
• Determining the number of prime implicates, data on the subsumption hypergraph, and minimum CNFs, and r_0-,r_1-bases.
• Here also minimum DNF-representations are of interest!
• They can be used to yield pseudo-canonical translations.
• Analysis of the prime clauses:
1. Creating the CNF/DNF files:
```OKplatform> mkdir EXP_DES
OKplatform> cd EXP_DES/
EXP_DES> oklib --maxima

for i : 1 thru 8 do (output_dessbox_fulldnf_stdname(i),output_dessbox_fullcnf_stdname(i));
```
2. Prime-clause statistics:
```EXP_DES> for F in *.cnf; do QuineMcCluskeySubsumptionHypergraphFullStatistics-n16-O3-DNDEBUG \${F}; done

EXP_DES> for F in DES_Sbox_?_fullDNF.cnf_primes_stats; do cat \${F}; done

EXP_DES> for F in DES_Sbox_?_fullCNF.cnf_primes_stats; do cat \${F}; done

n non_taut_c red_l taut_c orig_l comment_count finished_bool
10 1624 9554 0 9554 0 1
length count
5 243
6 1328
7 53

10 1844 10967 0 10967 0 1
5 154
6 1633
7 57

10 1767 10458 0 10458 0 1
5 219
6 1473
7 75

10 1881 11197 0 11197 0 1
5 153
6 1664
7 64

10 1812 10768 0 10768 0 1
5 174
6 1568
7 70

10 1705 10115 0 10115 0 1
5 204
6 1412
7 89

10 1673 9891 0 9891 0 1
5 228
6 1364
7 81

10 2047 12227 0 12227 0 1
5 106
6 1890
7 51
```
3. Subsumption hypergraph statistics:
```> sbox1_df = read.table(paste("DES_Sbox_",1,"_fullCNF.cnf_shg_stats",sep=""), head=TRUE, skip=2)
> summary(sbox1_df)
length          count
Min.   :10.00   Min.   : 0.00
1st Qu.:22.25   1st Qu.: 5.00
Median :34.50   Median :19.00
Mean   :34.50   Mean   :19.20
3rd Qu.:46.75   3rd Qu.:31.75
Max.   :59.00   Max.   :48.00
> summary(sbox2_df)
length          count
Min.   :11.00   Min.   : 0.00
1st Qu.:23.75   1st Qu.: 3.75
Median :36.50   Median :19.50
Mean   :36.50   Mean   :18.46
3rd Qu.:49.25   3rd Qu.:30.00
Max.   :62.00   Max.   :56.00
> summary(sbox3_df)
length         count
Min.   : 7.0   Min.   : 0.00
1st Qu.:20.5   1st Qu.: 3.00
Median :34.0   Median :17.00
Mean   :34.0   Mean   :17.45
3rd Qu.:47.5   3rd Qu.:29.50
Max.   :61.0   Max.   :49.00
> summary(sbox4_df)
length          count
Min.   :12.00   Min.   : 0
1st Qu.:23.75   1st Qu.: 7
Median :35.50   Median :21
Mean   :35.50   Mean   :20
3rd Qu.:47.25   3rd Qu.:32
Max.   :59.00   Max.   :52
> summary(sbox5_df)
length         count
Min.   :11.0   Min.   : 0.00
1st Qu.:23.5   1st Qu.: 5.50
Median :36.0   Median :19.00
Mean   :36.0   Mean   :18.82
3rd Qu.:48.5   3rd Qu.:29.00
Max.   :61.0   Max.   :43.00
> summary(sbox6_df)
length          count
Min.   :11.00   Min.   : 0.00
1st Qu.:23.75   1st Qu.: 3.75
Median :36.50   Median :15.00
Mean   :36.50   Mean   :18.46
3rd Qu.:49.25   3rd Qu.:31.50
Max.   :62.00   Max.   :56.00
> summary(sbox7_df)
length       count
Min.   :11   Min.   : 0.00
1st Qu.:23   1st Qu.: 4.00
Median :35   Median :21.00
Mean   :35   Mean   :19.59
3rd Qu.:47   3rd Qu.:30.00
Max.   :59   Max.   :53.00
> summary(sbox8_df)
length         count
Min.   :12.0   Min.   : 1.00
1st Qu.:24.5   1st Qu.: 5.50
Median :37.0   Median :17.00
Mean   :37.0   Mean   :18.82
3rd Qu.:49.5   3rd Qu.:28.00
Max.   :62.0   Max.   :45.00
```
4. All curves k -> nr (clause-length to number of occurrences) look like nice relatively symmetric curves. They have maximums around 30. Some (1,2,4) look slightly concave and some look slightly convex (3,5,6,7,8).
5. The DNF-output shows that no resolutions are possible, and thus these boolean functions have unique DNF.
6. Quite some differences regarding the prime implicates. S-box number 1 is the easiest, number 8 is the hardest.
7. This is also confirmed by r_1-bases: Box 1 has an r_1-base with 124 clauses, while for box 8 only one with 152 clauses was found.
8. The minimum representations seem to be of a similar size (from 66 to 69 clauses). See "Investigations into specific Sboxes" under "Links".
9. As a model one can study random 6 x 4 boolean functions.
10. DONE Also minimum representations need to be studied.
• DONE These considerations need a dedicated sub-module.
Todo:
Analysing the 6-to-1 bit Sbox functions
• In general we consider each DES Sboxes as one whole 6-to-4 bit boolean function.
• However, the Sbox can be represented as 4 6-to-1 bit boolean functions.
• We should investigate the DNF and CNF representations, prime implicates, and so on, of these 6-to-1 bit representations.
• Prime implicates/implicants:
• The number of prime implicants range from 50 to 68. All except 5 (out of the 32) have less than 64 prime implicants.
• The DNFs are not unique.
• Generating the CNFs and prime implicates:
```maxima> for i : 1 thru 8 do for j : 1 thru 4 do output_dessbox_bit_fullcnf_stdname(i,j);
shell> for i in \$(seq 1 8); do for j in \$(seq 1 4); do QuineMcCluskey-n16-O3-DNDEBUG DES_Sbox_\${i}_\${j}_fullCNF.cnf > \${i}_\${j}_primes; done; done
```
• The number of prime implicates for all DES S-box 6-to-1 bit functions is exactly the same as the number of prime implicants:
```oklib_load_all()\$
prime1_len_l :  create_list(
length(min_2resolution_closure_cs(setify( des_sbox_bit_fulldnf_cl(i,j) ))),
i, 1,8,j,1,4)\$
prime0_len_l :  create_list(
length(min_2resolution_closure_cs( des_sbox_bit_fullcnf_fcs(i,j)[2] )),
i, 1,8,j,1,4);
is(prime1_len_l = prime0_len_l);

[55,60,57,51,66,50,59,53,60,63,57,57,61,68,68,61,63,65,53,60,57,58,63,56,61,56,57,62,67,61,53,61]
true
```
Why is this?
• Minimum representations:
• We can generate the minimum DNF and CNF representations like so:
```maxima> for i : 1 thru 8 do for j : 1 thru 4 do output_dessbox_bit_fulldnf_stdname(i,j)\$
maxima> for i : 1 thru 8 do for j : 1 thru 4 do output_dessbox_bit_fullcnf_stdname(i,j)\$
shell> for i in \$(seq 1 8); do for j in \$(seq 1 4); do \$OKLIB/Satisfiability/Optimisation/minimise_cnf_cryptominisat DES_Sbox_\${i}_\${j}_fullDNF.cnf > \${i}_\${j}_min_dnf; done; done
shell> for i in \$(seq 1 8); do for j in \$(seq 1 4); do \$OKLIB/Satisfiability/Optimisation/minimise_cnf_cryptominisat DES_Sbox_\${i}_\${j}_fullCNF.cnf > \${i}_\${j}_min_cnf; done; done
```
• The minimum DNF representations have between 30 and 46 clauses.
• Every minimum CNF representations for the 6-to-1 bit DES S-box functions have exactly the same number of clauses as their respective minimum DNF representations. Why is this?
• See bf2nm2n1 in ComputerAlgebra/Satisfiability/Lisp/FiniteFunctions/Basics.mac.

Definition in file general.hpp.