Question

Suppose a block cipher uses m-to-m bits S-boxes. How many bits are required to store the look-up table of k different such m-to-m bits S-boxes? Give a formula in terms of k and m. Hint: A look-up table for one DES S-box requires 256 bits of storage.

Answer 1

S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution

In general, an S-box takes some number of input bits, m, and transforms them into some number of output bits, n, where n is not necessarily equal to m. An m×n S-box can be implemented as a lookup table with 2^m words of n bits each. Fixed tables are normally used, as in the Data Encryption Standard (DES), but in some ciphers the tables.

if the S-box input is 8-bit, then there are 2⁸ = 256 possible input values

Most Cipher block implementation DES uses 8 s-boxses which each taken 6 bit input and 4-bit output

Storage (in bytes) = Number of S-boxes x 2Number of input bits x (Number of output bits / 8)

.: DES = 8 x 2⁶ x (4 / 8) = 256 bytes

One good example of a fixed table is the S-box from DES (S₅), mapping 6-bit input into a 4-bit output:

S5	Middle 4 bits of input
0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
Outer bits	00	0010	1100	0100	0001	0111	1010	1011	0110	1000	0101	0011	1111	1101	0000	1110	1001
01	1110	1011	0010	1100	0100	0111	1101	0001	0101	0000	1111	1010	0011	1001	1000	0110
10	0100	0010	0001	1011	1010	1101	0111	1000	1111	1001	1100	0101	0110	0011	0000	1110
11	1011	1000	1100	0111	0001	1110	0010	1101	0110	1111	0000	1001	1010	0100	0101	0011

Given a 6-bit input, the 4-bit output is found by selecting the row using the outer two bits (the first and last bits), and the column using the inner four bits. For example, an input "011011" has outer bits "01" and inner bits "1101"; the corresponding output would be "1001".

The DES (data encryption standard) designated by IBM use block cipher One simplest way to bulid a secret key alogrithm is to break the input into manageble- size chunks (8- bits) ,do the substitition (S-box) on the small chunks

and then take the output of all substitution and run them through a permuter that is big as the input which shuffle the bit around then process is repeated

DES operates on the 64-bit blocks using key sizes of 56- bits. The keys are actually stored as being 64 bits long, but every 8th bit in the key is not used

56-bit key used to to generate sixsteen 48-bit per round keys by taking different 48-bit subset of 56-bits for each key

each stage takes two 32-bit inputs and produces two -32 bit output .

The left output simply copy of the right output the right iutput is simply bitwise XOR of the left input the function of the right input and the key for the stage k.