# How do the Serpent S-boxes work?

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.

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 = 1$$. Which S-box is used is determined by the round. The Serpent authors decided to use 8 different S-boxes instead of 32 different ones because the security benefit did not appear to be worth the added ROM footprint.

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. • Thanks for the initial, clear and detailed answer. However, it is still not clear to me how a single word is passed through a s-box. A S-box is 4 bits, a word is 32. The word is split into nibbles, and so are every nibbles passed through the same s-box of the round ? – user96649 Mar 26 '19 at 5:46
• @user96649 Each word is split into chunks of one bit, and since there are four words, that makes four bits. The first bit of each of the four words makes up the input to one 4-bit S-box. The second bit of each of the four words makes up the input to the second 4-bit S-box, etc. for a total of 32 S-boxes. So you need more than just one word. You need all four 32-bit words taken from the 128-bit block to feed the S-boxes. – forest Mar 26 '19 at 5:47
• @user96649 So if we have four words starting with "011001...", "100111...", "110101...", and "001110...", then we take the first bit of each of those words (which are "0", "1", "1", and "0") and put them together into a nibble. That nibble is fed to the first S-box, so it takes "0110". The second S-box is fed the second bit of each word, so it takes "1010". The third is fed "1001", the forth is fed "0111", etc. This goes on 32 times. – forest Mar 26 '19 at 5:52
• Okay, now I understand. Thanks a lot ! – user96649 Mar 26 '19 at 6:05
• Good answer (I like derangements) , but is $S_4$ okay? – Paul Uszak May 10 '19 at 14:20