How do the Serpent S-boxes work?

Question

Warning: The link in the answer explain the S-Box well, but there is an error in the pseudocode.

$K_i = K_{i-8} \oplus K_{i-5} \oplus K_{i-3} \oplus K_{i-1} \oplus 0x9e3779b9 \oplus i$;

Instead, it should be : $K_i = K_{i-8} \oplus K_{i-5} \oplus K_{i-3} \oplus K_{i-1} \oplus 0x9e3779b9 \oplus (i-8)$;

The loop start from 8, but in the paper, i is worth 0 as the beginning of the loop.

---

For DES, you take the 4 inner bits as the column to choose from the S-Box, and the two outer bits to choose the row.

However, for Serpent it doesn't make sense to me as the prekeys that are used to choose the row and columns are 32 bit words, and the 8 S-boxes are one dimensional arrays.

Now the paper tells us that the S-boxes are 4 bit permutations, but what does it mean? Would it mean that the two outer bits are used to choose one of the 8 S-box, and the 4 inner (ignoring thus 2 bits in the process) would be used for the columns? However, the paper directly specifies which S-box to use, like so:

${k_0 , k_1 , k_2 , k_3 } := S_3 (w_0 , w_1 , w_2 , w_3)$

I've searched online, but serpent doesn't seem to be as documented as Rijndael or DES.

Answer 1

Serpent uses 8 different 4-bit S-boxes (i.e. each S-box contains 16 elements) a total of 32 times. There are no "rows" or "columns" as it is a one-dimensional array containing a derangement of 16 elements. For each S-box, a 4-bit integer from 0 to 15 is mapped to another 4-bit integer from 0 to 15. When implementing the S-box as an array, the input is used as the index and the contents of the array are what make up the S-box itself. The output is simply the element at the index given by the input.

The 8 different Serpent S-boxes (ignoring the inverse S-boxes) are described by the following table: \begin{equation} \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \text{Input}&\operatorname{S_0}&\operatorname{S_1}&\operatorname{S_2}&\operatorname{S_3}&\operatorname{S_4}&\operatorname{S_5}&\operatorname{S_6}&\operatorname{S_7}\\ \hline 0&3&15&8&0&1&15&7&1\\ 1&8&12&6&15&15&5&2&13\\ 2&15&2&7&11&8&2&12&15\\ 3&1&7&9&8&3&11&5&0\\ 4&10&9&3&12&12&4&8&14\\ 5&6&0&12&9&0&10&4&8\\ 6&5&5&10&6&11&9&6&2\\ 7&11&10&15&3&6&12&11&11\\ 8&14&1&13&13&2&0&14&7\\ 9&13&11&1&1&5&3&9&4\\ 10&4&14&14&2&4&14&1&12\\ 11&2&8&4&4&10&8&15&10\\ 12&7&6&0&10&9&13&13&9\\ 13&0&13&11&7&14&6&3&3\\ 14&9&3&5&5&7&7&10&5\\ 15&12&4&2&14&13&1&0&6\\ \hline \end{array} \end{equation}

This means that the integer $9$ (binary $1001$) fed through the 3rd S-box ($\operatorname{S_2}$) would be the element at index 9, which happens to be the integer $1$ (binary $0001$). In other words, $\operatorname{S}_2[9] = 1$. The S-box that is used in any given round is determined by the round number. Round $r$ uses $\operatorname{S}_{r\bmod 8}$. The Serpent authors decided to use 8 different S-boxes instead of 32 because the security benefit did not appear to be worth the added ROM footprint, and fewer than 8 would be insecure for such a small S-box.

Each of the 4-bit S-boxes operate on 4-bit chunks of input, returning 4-bit chunks of output. Each round's substitution step involves 32 parallel applications of the same S-box. This substitution is done 32 times (one time for each round). This is realized by splitting the 128-bit block into four 32-bit words. The first bit of each word is used as input for the first S-box. The second bit of each word is used as input for the second S-box. This continues 32 times. Since there are always four words, each S-box only takes 4-bit inputs. The following is taken from a blog post on an implementation of Serpent which explains how a 4-bit S-box is capable of operating on four 32-bit words (i.e. the 128-bit round state):

The diagram below shows how the s-boxes are implemented in bitslice mode. The 128 bit input block is divided up into 4 x 32 bit words: |w0|w1|w2|w3|. These are then arranged as shown in the diagram. The substitution is then applied by taking 32 slices of 4 bits each and putting then through 32 copies of the s-box in parallel. Bit 0 is the lsb in the 4 bit value.