# Re: Some empirical results of random S-boxes

**From:** David Eather (*eather_at_tpg.com.au*)

**Date:** 09/27/04

**Next message:**Patrick J. LoPresti: "Re: new /dev/random"**Previous message:**Catalin Ispasoiu: "SSL protocol"**In reply to:**Mok-Kong Shen: "Re: Some empirical results of random S-boxes"**Next in thread:**Mok-Kong Shen: "Re: Some empirical results of random S-boxes"**Reply:**Mok-Kong Shen: "Re: Some empirical results of random S-boxes"**Reply:**Terry Ritter: "Re: Some empirical results of random S-boxes"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

**Next message:**Patrick J. LoPresti: "Re: new /dev/random"**Previous message:**Catalin Ispasoiu: "SSL protocol"**In reply to:**Mok-Kong Shen: "Re: Some empirical results of random S-boxes"**Next in thread:**Mok-Kong Shen: "Re: Some empirical results of random S-boxes"**Reply:**Mok-Kong Shen: "Re: Some empirical results of random S-boxes"**Reply:**Terry Ritter: "Re: Some empirical results of random S-boxes"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]