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

For example, an 8-bit P-box might be specified as
P = [3 5 1 0 4 7 6 2]
This stands for P[0] = 3, P[1] = 5, P[2] = 1, ... , P[6] = 6, P[7] = 2. The
operation means to take bit 0 of the input and copy it to bit 3 of the output. Also take bit 1 of the input, and copy
it to bit 5 of the output, and so forth. (Note that not all bits necessarily map to other bits — e.g., in this P-box,
bits 4 and 6 map to themselves.) The example in Figure 4-3 illustrates this concept graphically.
Figure 4-3 A simple graphical representation of an 8-bit P-box. Note that bits 4 and 6 are passed straight
through.
For the preceding P-box, assume that the bits are numbered in increasing order of significance (0 being the
least significant bit, 7 the most). Then, for example, the input of 00 will correspond to 00 . In hexadecimal (us-
ing big-endian notation), the input 01 would correspond to 20 , and 33 would correspond to B8 .
A few things to note about P-boxes: They aren't as random as S-boxes — there is a one-to-one correspond-
ence of bits from the input to the output. P-boxes also take a lot less space to specify than S-boxes: The 8-bit
P-box could be written out in very little space. A 16-bit P-box could be written as a list of 16 numbers, but it
would require a list of 65,536 numbers to fully specify a 16-bit S-box.
However, technically speaking, P-boxes are S-boxes, just with a more compact form. This is because they
are simply a mapping of input values to output values and can be represented as a simple lookup table, such as
an S-box. The P-box representation is merely a shortcut, albeit a very handy one.
If we look at any of the previously mentioned structures, though, we can see that they should not be used
alone. A trivial cipher can be obtained by just using an S-box on an input, or a P-box, or even XORing each
input byte with a fixed number. None of these techniques provides adequate security, though: The first two al-
low anyone with knowledge of the S-box or P-box to immediately decrypt a message, and with a simple XOR,
anyone who knows the particular value of one byte in both plaintext and ciphertext could immediately derive
the key.
For these reasons, I will use the above concept of a product cipher to combine each of these concepts —
bitwise operations, S-boxes, and P-boxes — to create a very complicated structure. We won't limit ourselves
to just these particular operations and boxes, but the ones explained so far represent the core of what is used in
most modern cryptographic algorithms.
4.3.3 Shift Registers
Another tool used in the construction of ciphers is a shift register. Look at Figure 4-4 , one of two shift registers
in Skipjack (called Rule A and Rule B), for an example of how a shift register operates.