Block Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 77

Of course, in the above S-box, I never specified which representation of bits this represents: most significant
or least significant. A word of caution: Some ciphers do actually use least significant bit order (such as DES),
even though this is fairly uncommon in most other digital computing. This can be very confusing if you are
used to looking at ciphers in most significant bit order, and vice versa.
Asspecified above, S-boxesmay have different sizes forinputs andoutputs. Forexample, anS-boxmay take
a 6-bit input, but only produce a 4-bit output. In this case, many of the outputs will be repeated. For the exact
opposite case, with, say, a 4-bit input and 6-bit output, there will be several outputs that are not generated.
Sometimes S-boxes are derived from simpler moves. For example, we could have a 4-bit S-box that merely
performs, for a 4-bit input x , the operation 4 - x mod 16, and gives the result. The S-box spelled out would be
[4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5]
S-boxes have some advantages, as we can see. They can be very random, with little correspondence between
any input bits and output bits, and have few discernible patterns.
One primary disadvantage is size: They simply take a lot of space to describe. The 8-bit S-box for Rijndael,
shown in Figure 4-2 , takes a lot of space and requires implementing code to store the table in memory (although
it can also be represented as a mathematical function, but this would require more computation at run time).
Figure 4-2 Full listing of the Rijndael's 8-bit S-box.
Another tool, the permutation box (or simply, P-box), is similar to an S-box but has a slightly different
trade-off: A P-box is usually smaller in size and operates on more bits.
4.3.2 P-Box
A P-box provides similar functionality to transpositions in classical cryptography. The purpose of the permuta-
tion box is to permute the bits: shuffle them around but without changing them.
P-boxes operate by mapping each input value to a different output value by a lookup table — each bit
is moved to a fixed position in the output. Most P-boxes simply permute the bits: one input to one output.
However, in some ciphers (such as DES), there are expansive and selective permutations as well, where the
number of output bits is greater (some bits are copied) or smaller (some bits are discarded), respectively.
P-boxes are normally specified in a similar notation to S-boxes, only instead of representing outputs for a
particular input, they specify where a particular bit is mapped to. Assume that we number the bits from 0 to 2 b
- 1, where b is the size of the P-box input, in bits. The output bits will also be numbered from 0 to 2 c - 1, where
c is the size of the P-box output, in bits.