Which reordering should I use for an 8-bit S-box?

Question

I'm designing a cipher which has key-dependent S-boxes. The procedure is like this:

1. Transform the key (a string of bytes) into 96 16-bit words (the high bits are ignored, but make a difference when these 96 numbers are reshuffled to make the other two S-boxes).
2. Start with the identity permutation [0..255].
3. Take it 8 bytes at a time, and permute it using one of the 96 numbers. This can produce 32768 of the 40320 permutations, and cannot leave the 8 bytes unaltered. Do this 32 times.
4. Redeal the bytes so that the 8 bytes in one group all end up in different groups.
5. Repeat steps 3 and 4 twice more, thus using up all the 96 numbers.

I've thought of two ways to do step 4:

1. Multiply the index by 10 mod 257, with 0 skipped. So if you start with 00 01 02 03 ..., you get b3 66 19 cd 80 33 e7 9a 4d 00 b4 69 1a ce 81 34 e8 9b 4e 01 ....
2. Multiply the index by 8 in F256. The polynomial I use is 100011101. Starting again with 00 01 02 03 ..., you get 00 ad 47 ea 8e 23 c9 64 01 ac 46 eb 8f 22 c8 65 ....

Which of these is better? Possible reasons to prefer one or the other are:

• Method 1 may produce more birthday collisions. In method 2, given a byte's initial and final positions, there are always exactly 2 ways it could get there. In method 1, there could be 1, 2, or 3.
• Method 2 may be more likely to produce a linear permutation. I might should start with a nonlinear permutation instead of [0..255].

It's hard for me to reason about these probabilities when the number of redealings (32768^96) is more than a googol to the fourth, and the number of permutations (256!) is more than a googol to the fifth.

The code is at https://github.com/phma/wring-twistree in the file src/Cryptography/WringTwistree/Permute.hs.

Answer 1

There's a much simpler way to make key dependent S boxes.

Simply seed a long random number generator (e.g. Xoroshiro128+ ). Then shuffle the identity permutation with Fisher-Yates. You should expect one fixed point in every permutation $P$ you make. Alternatively, there is a brute force method. Sample the RNG and add to the permutation if not already present.

In both cases you can check for fixed points and repeat Fisher-Yates or reject samples from the RNG. That will create a derangement. In checking you can also assert $P[i] \oplus i > n$ for a 'stronger' derangement, where $n$ is the bit difference. Try $n = 2$. I've never managed to make an 8 bit derangement with $n = 3$.

---

Note 1. $96 \times 16 = 1536$ bits. That's quite a key size; paranoid much :-) Is it because that value approaches $\log_2(256!)$ ?

Note 2. Usual stuff about home brew ciphers.