[312] in cryptography@c2.net mail archive
Re: standardizing key schedules
daemon@ATHENA.MIT.EDU (Hal Finney)
Wed Feb 26 13:06:39 1997
Date: Wed, 26 Feb 1997 09:03:31 -0800
From: Hal Finney <hal@rain.org>
To: cryptography@c2.net, reinhold@world.std.com
From: "Arnold G. Reinhold" <reinhold@world.std.com>
> Since I started this, I should point out that with 256 byte random keys the
> resulting permutations are uniformly random as well. Each swap depends on a
> sum mod 256 one of whose terms is a random 8 bit quantity (a key byte) that
> differs for each swap. Since each of the S array values is swapped at least
> once, one can know nothing about their final values without the key.
If I understand what you're saying, this can't be true, since 256^256
is not a multiple of 256!. So some permutations must be more likely
than others with 256 byte random keys. However I think the bias would
be vanishingly small.
Consider a simplified case, with 3 terms. The chart below shows a
hierarchy, first showing the three possibilities after the first word is
swapped randomly with each of the three choices, then at the second
level it shows the nine possible results after the second swap, and at
the third level it shows the 27 possible results after three swaps.
123 after 1 swap
213 after 2 swaps
312 after 3 swaps
231 ''
213 ''
123 after 2 swaps
321 after 3 swaps
132 ''
123 ''
132 after 2 swaps
231
123 ''
132 ''
213 after 1 swap
123 after 2 swaps
321 after 3 swaps
132 ''
123 ''
213 after 2 swaps
312 after 3 swaps
231 ''
213 ''
231 after 2 swaps
132 after 3 swaps
213 ''
231 ''
321 after 1 swap
231 after 2 swaps
132 after 3 swaps
213 ''
231 ''
321 after 2 swaps
123 after 3 swaps
312 ''
321 ''
312 after 2 swaps
213 after 3 swaps
321 ''
312 ''
For a final count of:
Perm Count
-------------
123 4
132 5
213 5
231 5
312 4
321 4
---------
Total 27
Some of the permutations are slightly more likely than others.
Hal
