Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

*The S-Box Substitution*

After the compressed key is XORed with the expanded block, the 48-bit result moves to a substitution operation. The substitutions are performed by eight **substitution boxes,** or **S-boxes**. Each S-box has a 6-bit input and a 4-bit output, and there are eight different S-boxes. (The total memory requirement for the eight DES S-boxes is 256 bytes.) The 48 bits are divided into eight 6-bit sub-blocks. Each separate block is operated on by a separate S-box: The first block is operated on by S-box 1, the second block is operated on by S-box 2, and so on. See Figure 12.4.

Each S-box is a table of 4 rows and 16 columns. Each entry in the box is a 4-bit number. The 6 input bits of the S-box specify under which row and column number to look for the output. Table 12.6 shows all eight S-boxes.

The input bits specify an entry in the S-box in a very particular manner. Consider an S-box input of 6 bits, labeled *b*_{1} *b*_{2} *b*_{3} *b*_{4} *b*_{5} and *b*_{6}. Bits *b*_{1} and *b*_{6} are combined to form a 2-bit number, from 0 to 3, which corresponds to a row in the table. The middle 4 bits, *b*_{2} through *b*_{5} are combined to form a 4-bit number, from 0 to 15, which corresponds to a column in the table.

For example, assume that the input to the sixth S-box (i.e., bits 31 through 36 of the XOR function) is 110011. The first and last bits combine to form 11, which corresponds to row 3 of the sixth S-box. The middle 4 bits combine to form 1001, which corresponds to the column 9 of the same S-box. The entry under row 3, column 9 of S-box 6 is 14. (Remember to count rows and columns from 0 and not from 1.) The value 1110 is substituted for 110011.

*
Figure 12.3 Expansion permutation.*

Table 12.5 Expansion Permutation | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

32, | 1, | 2, | 3, | 4, | 5, | 4, | 5, | 6, | 7, | 8, | 9, |

8, | 9, | 10, | 11, | 12, | 13, | 12, | 13, | 14, | 15, | 16, | 17, |

16, | 17, | 18, | 19, | 20, | 21, | 20, | 21, | 22, | 23, | 24, | 25, |

24, | 25, | 26, | 27, | 28, | 29, | 28, | 29, | 30, | 31, | 32, | 1 |

It is, of course, far easier to implement the S-boxes in software as 64-entry arrays. It takes some rearranging of the entries to do this, but that’s not hard. (Don’t just change the indexing without rearranging the entries. The S-boxes are designed very carefully.) However, this way of describing the S-boxes helps visualize how they work. Each S-box can be viewed as a substitution function on a 4-bit entry: *b*_{2} through *b*_{5} go in, and a 4-bit result comes out. Bits *b*_{1} and *b*_{6} come from neighboring blocks; they select one out of four substitution functions available in the particular S-box.

The S-box substitution is the critical step in DES. The algorithm’s other operations are linear and easy to analyze. The S-boxes are nonlinear and, more than anything else, give DES its security.

The result of this substitution phase is eight 4-bit blocks which are recombined into a single 32-bit block. This block moves to the next step: the P-box permutation.

*The P-Box Permutation*

The 32-bit output of the S-box substitution is permuted according to a **P-box**. This permutation maps each input bit to an output position; no bits are used twice and no bits are ignored. This is called a **straight permutation** or just a permutation. Table 12.7 shows the position to which each bit moves. For example, bit 21 moves to bit 4, while bit 4 moves to bit 31.

*
Figure 12.4 S-box substitution.*

Table 12.6 S-Boxes | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

S-box 1:
| |||||||||||||||

14, | 4, | 13, | 1, | 2, | 15, | 11, | 8, | 3, | 10, | 6, | 12, | 5, | 9, | 0, | 7, |

0, | 15, | 7, | 4, | 14, | 2, | 13, | 1, | 10, | 6, | 12, | 11, | 9, | 5, | 3, | 8, |

4, | 1, | 14, | 8, | 13, | 6, | 2, | 11, | 15, | 12, | 9, | 7, | 3, | 10, | 5, | 0, |

15, | 12, | 8, | 2, | 4, | 9, | 1, | 7, | 5, | 11, | 3, | 14, | 10, | 0, | 6, | 13, |

S-box 2:
| |||||||||||||||

15, | 1, | 8, | 14, | 6, | 11, | 3, | 4, | 9, | 7, | 2, | 13, | 12, | 0, | 5, | 10, |

3, | 13, | 4, | 7, | 15, | 2, | 8, | 14, | 12, | 0, | 1, | 10, | 6, | 9, | 11, | 5, |

0, | 14, | 7, | 11, | 10, | 4, | 13, | 1, | 5, | 8, | 12, | 6, | 9, | 3, | 2, | 15, |

13, | 8, | 10, | 1, | 3, | 15, | 4, | 2, | 11, | 6, | 7, | 12, | 0, | 5, | 14, | 9, |

S-box 3:
| |||||||||||||||

10, | 0, | 9, | 14, | 6, | 3, | 15, | 5, | 1, | 13, | 12, | 7, | 11, | 4, | 2, | 8, |

13, | 7, | 0, | 9, | 3, | 4, | 6, | 10, | 2, | 8, | 5, | 14, | 12, | 11, | 15, | 1, |

13, | 6, | 4, | 9, | 8, | 15, | 3, | 0, | 11, | 1, | 2, | 12, | 5, | 10, | 14, | 7, |

1, | 10, | 13, | 0, | 6, | 9, | 8, | 7, | 4, | 15, | 14, | 3, | 11, | 5, | 2, | 12, |

S-box 4:
| |||||||||||||||

7, | 13, | 14, | 3, | 0, | 6, | 9, | 10, | 1, | 2, | 8, | 5, | 11, | 12, | 4, | 15, |

13, | 8, | 11, | 5, | 6, | 15, | 0, | 3, | 4, | 7, | 2, | 12, | 1, | 10, | 14, | 9, |

10, | 6, | 9, | 0, | 12, | 11, | 7, | 13, | 15, | 1, | 3, | 14, | 5, | 2, | 8, | 4, |

3, | 15, | 0, | 6, | 10, | 1, | 13, | 8, | 9, | 4, | 5, | 11, | 12, | 7, | 2, | 14, |

S-box 5:
| |||||||||||||||

2, | 12, | 4, | 1, | 7, | 10, | 11, | 6, | 8, | 5, | 3, | 15, | 13, | 0, | 14, | 9, |

14, | 11, | 2, | 12, | 4, | 7, | 13, | 1, | 5, | 0, | 15, | 10, | 3, | 9, | 8, | 6, |

4, | 2, | 1, | 11, | 10, | 13, | 7, | 8, | 15, | 9, | 12, | 5, | 6, | 3, | 0, | 14, |

11, | 8, | 12, | 7, | 1, | 14, | 2, | 13, | 6, | 15, | 0, | 9, | 10, | 4, | 5, | 3, |

S-box 6:
| |||||||||||||||

12, | 1, | 10, | 15, | 9, | 2, | 6, | 8, | 0, | 13, | 3, | 4, | 14, | 7, | 5, | 11, |

10, | 15, | 4, | 2, | 7, | 12, | 9, | 5, | 6, | 1, | 13, | 14, | 0, | 11, | 3, | 8, |

9, | 14, | 15, | 5, | 2, | 8, | 12, | 3, | 7, | 0, | 4, | 10, | 1, | 13, | 11, | 6, |

4, | 3, | 2, | 12, | 9, | 5, | 15, | 10, | 11, | 14, | 1, | 7, | 6, | 0, | 8, | 13, |

S-box 7:
| |||||||||||||||

4, | 11, | 2, | 14, | 15, | 0, | 8, | 13, | 3, | 12, | 9, | 7, | 5, | 10, | 6, | 1, |

13, | 0, | 11, | 7, | 4, | 9, | 1, | 10, | 14, | 3, | 5, | 12, | 2, | 15, | 8, | 6, |

1, | 4, | 11, | 13, | 12, | 3, | 7, | 14, | 10, | 15, | 6, | 8, | 0, | 5, | 9, | 2, |

6, | 11, | 13, | 8, | 1, | 4, | 10, | 7, | 9, | 5, | 0, | 15, | 14, | 2, | 3, | 12, |

S-box 8:
| |||||||||||||||

13, | 2, | 8, | 4, | 6, | 15, | 11, | 1, | 10, | 9, | 3, | 14, | 5, | 0, | 12, | 7, |

1, | 15, | 13, | 8, | 10, | 3, | 7, | 4, | 12, | 5, | 6, | 11, | 0, | 14, | 9, | 2, |

7, | 11, | 4, | 1, | 9, | 12, | 14, | 2, | 0, | 6, | 10, | 13, | 15, | 3, | 5, | 8, |

2, | 1, | 14, | 7, | 4, | 10, | 8, | 13, | 15, | 12, | 9, | 0, | 3, | 5, | 6, | 11 |

Previous | Table of Contents | Next |