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

Figure 4-4 Skipjack's Rule A shift register.
Typically, a shift register works by taking the input and splitting it into several portions; thus, in this case,
w = w 1 || w 2 || w 3 || w 4 is our input. Then, the circuit is iterated several times. In this diagram, G represents a
permutation operation. Thus, after one round through the algorithm, w 2 will get the permutation of w 1 ; w 3 will
be the XOR of the old w 2 , the counter, and the old w 1 ; and w 4 will get the old value of w 3 ; while w 1 gets the old
value of w 4 . This iteration is repeated many times (in Skipjack, it iterates eight times in two different locations).
Shift registers are meant to mimic the way many circuits and machines were designed to work, by churning
the data in steps. These are also designed with parallelism in mind: While one piece of circuitry is performing
one part of the computation, another can be computing with a different part of the data, to be used in following
steps.
4.4 Substiuition-Permutation Network
The first natural extension of the above simple techniques is to merely start combining them. A substitu-
tion-permutation network (SPN) is just that: It chains the output of one or more S-boxes with one or more
P-boxes, or vice versa. The concept is similar to chaining together simple substitution ciphers of text and trans-
position ciphers: We have one layer substituting values for other values, thereby adding a lot of confusion (in
that it is a bit harder to see where the output comes from). We then have another layer mixing the output bits
from one or more S-boxes and jumbling them together, contributing primarily to diffusion (in that input bits
influence a lot of output bits).
However, up until this point, we are still going to have trouble with the output being trivially related to the
input: Simply knowing the combinations of S-boxes and P-boxes can let us derive one from the other. We need
a way of adding a key into the system so that only parties privy to the key will be able to encrypt and decrypt
messages.
The most common mechanism for adding keys to the above system is to compute some function of the key
to give a set of bits, referred to as the keyschedule. These bits from the key schedule are then usually integrated
into the cipher somehow, normally by XORing them together with intermediate bits in the cipher (such as the
input of some S-boxes).
The most common way of forming an SPN is to have many (usually different) S-boxes and P-boxes, with
their inputs and outputs chained together. For example, see Figure 4-5 . When we chain them together like this,
we may XOR in the key schedule bits several times. We call these key schedule bits and not just the key bits
because, as I said above, these bits are merely derived from the key. Some may be identical to the key, but, for
example, we may use different subsets of the key bits at different parts of the network (maybe shifted, or inver-
ted at different parts).