View source for 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