Re: Some empirical results of random S-boxes

From: David Eather (eather_at_tpg.com.au)
Date: 09/27/04


Date: Mon, 27 Sep 2004 22:32:24 +1000


The paper you want to read is

http://citeseer.ist.psu.edu/oconnor94distribution.html

My results were not as impressive

Approximating random S-box differentials

The last time random or key dependent s-boxes were raised in this forum they
were described as voodoo and unscientific. That is rather strange
considering its own practitioners often claim that crypto is a "black art".

Perhaps it is because there is so little theory on the differential and
linear properties of these types of random constructions.

To start the ball rolling I have discovered a formula that approximates the
differential** characteristics of randomly chosen n x m S-Boxes where n=m. I
'm also hoping no one else has noted this first, and that if my notation is
poor that at least it is understandable.

==========

Eather's conjecture (I have to call the conjecture something)

The differential characteristics of randomly chosen n x m S-Boxes, where
n=m, is approximated by:

p(i) = sqrt(1/e) / 2 / 4 / 6 . i-4 / i-2 / i

Where p(i) is the probability of a specific entry in the difference table
having the value i, with i being the even numbers 2,4,6 etc and with P(0)
defined as:

p(0) = sqrt(1/e)

==========

Three points to note:

1. This approximation appears to be indifferent to the size of the s-box
(providing n=m) and mostly indifferent to the construction method (random
numbers vs. random permutation). However as with any approximation of
random events the "law of large numbers" comes into play and larger samples
give less variable results.

2. With randomly selected data, odd sizes of s-boxes (7bit or 9 bit for
example) provide no special benefit other than that conferred by size.

3. The conjecture and the results bear out the truism that bigger is
generally better.

======

Method and Results

In simulations, groups of 256 S-boxes of various sizes, constructed from
random permutations or random numbers were tested. The actual differential
characteristics were calculated and then all results combined. The result
closely followed that predicted by the conjecture, with the constraints that
some of the samples were quiet small and the numbers displayed have been
truncated rather than rounded off. The conjecture shows increasing accuracy
with larger sample sizes in line with the "law of large numbers"

DT = the difference table entry
N(a) = the actual numbers of entries with the specified difference
N(c) = the predicted number of entries of the specified difference
Error = percentage error between the test sample and calculated value.

======

Results for s-boxes constructed with random permutations
(I can e-mail PDF format if the graphs are unreadable)

 4 bit s-box 7 bit s-box
------------------------------------------------------------
DT N(a) N(c) Error N(a) N(c) Error
0 41495 39594 -4.80% 2560062 2543818 -0.64%
2 17994 19797 9.11% 1256161 1271909 1.24%
4 4795 4949 3.12% 316958 317977 0.32%
6 864 824 -4.74% 53566 52996 -1.08%
8 120 103 -16.38% 6573 6624 0.78%
10 8 10 22.41% 670 662 -1.14%
12 4 0-365.52% 55 55
0.37%
14 - - - 3 3
23.92%
============================================================

 8 bit s-box
------------------------------------------------------------
DT N(a) N(c) Error
0 10207693 10175740 -0.31%
2 5057827 5087870 0.59%
4 1269110 1271967 0.22%
6 212842 211994 -0.40%
8 26468 26499 0.12%
10 2751 2649 -3.81%
12 244 220 -10.49%
14 24 15 -52.15%
16 1 0 -1.44%
============================================================

9 bit s-box
------------------------------------------------------------
DT N(a) N(c) Error
0 40770411 40703428 -0.16%
2 20286551 20351714 0.32%
4 5084022 5087928 0.08%
6 849048 847988 -0.12%
8 106800 105998 -0.76%
10 10769 10599 -1.60%
12 941 883 -6.53%
14 62 63 1.73%
16 4 3 -1.44%
============================================================

Results for s-boxes constructed with random numbers

 4 bit s-box 7 bit s-box
------------------------------------------------------------
DT N(a) N(c) Error N(a) N(c) Error
0 40608 39594 -2.56% 2551454 2543818 -0.30%
2 19363 19797 2.19% 1269561 1271909 0.18%
4 4643 4949 6.19% 315249 317977 0.86%
6 597 824 27.63% 51062 52996 3.65%
8 65 103 36.96% 6121 6624 7.60%
10 4 10 61.21% 567 662 14.41%
12 - - - 34 55
38.41%
============================================================

 8 bit s-box
------------------------------------------------------------
DT N(a) N(c) Error
0 10192465 10175740 -0.16%
2 5081072 5087870 0.13%
4 1266493 1271967 0.43%
6 208779 211994 1.52%
8 25512 26499 3.73%
10 2447 2649 7.66%
12 182 220 17.58%
14 10 15 36.60%
============================================================

9 bit s-box
------------------------------------------------------------
DT N(a) N(c) Error
0 40737461 40703428 -0.08%
2 20339356 20351714 0.06%
4 5073977 5087928 0.27%
6 841803 847988 0.73%
8 104868 105998 1.07%
12 855 883 3.21%
14 63 63 0.15%
16 3 3 23.92%
============================================================

** the linear case is simple and can be seen as a whole sequence of
Bernoulli trials. The probabilities of a particular bias can be calculated
by dividing the area of the appropriate Bernoulli curve between -b and b by
the area of the entire curve.

Somewhere I am supposed to quip, "assuredly I have a wonderful proof of my
theorem but this e-mail is not long enough to hold it."

David Eather