User:David MacQuigg/Sandbox/S-box (cryptography)
An S-box (Substitution box) is is a common component in cryptographic systems. It is fast, versatile, and easily implemented in both hardware and software. An "m by n" S-box can take any bit pattern on its m inputs, and transform it to any desired bit pattern on its n outputs. Thus, the function implemented by this S-box can have M = 2**m possible inputs, and N = 2**n possible outputs. Since there can be only one output for any given input, the total number of functions possible is N**M (10**616 for an 8 by 8 S-box).
In hardware, an S-box can be implemented very compactly as PLA (Programmable Logic Array). In software, an S-box is just an array of integers:
S4x4 = [14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7] # 4 by 4 S-box
The integers in this example are just a permutation of all possible 4-bit outputs {0, 1, 2, ... 15}. Restricting the function to just permutations like this reduces the number of possible functions (10**507 for an 8 by 8 S-box), but provides some statistical properties desirable in many crypto systems.
Statistical properties of an S-box
For maximum resistance to cryptographic attacks, S-boxes should be as "random" as possible. What does that mean? Well, one example of a departure from randomness would be a predominance of 1's over 0's (or vice versa) in any output bit of the S-box. An ideal random stream of bits would have an equal number of 1's and 0's. We can quantify this departure from ideality as a "bias" from an ideal probability of 1/2. If output bit 3, for example, has 12 1's (and 4 0's) for every 16 output samples, we would say the bias of this bit is +1/4. If that were 4 1's and 12 0's, the bias would be -1/4. Permutation boxes like the above have the property that all output bits have zero bias (assuming a large number of truly random inputs).
Random S-box - show histogram - epsilon
Correlations between inputs and outputs - What if we look at one or more inputs correlated with one or more outputs? (2**m - 1) * (2**n - 1) possible correlations. Impossible to design a box that has no correlations at all. A good design has no "strong" correlations or correlations involving very few bits.
Using correlations in an attack
Propagation of bias Wide trail strategy