A tutorial on linear and differential cryptanalysis

Cryptologia, Jul 2002 by Heys, Howard M

For our cipher, we shall use the same nonlinear mapping for all S-boxes. (In DES all the S-boxes in a round are different, while all rounds use the same set of S-boxes.) The attacks of linear and differential cryptanalysis apply equally whether there is one mapping or all S-boxes are different mappings. The mapping chosen for our cipher, given in Table 1, is chosen from the S-boxes of DES. (It is the first row of the first S-box.) In the table, the most significant bit of the hexadecimal notation represents the leftmost bit of the S-box in Figure 1.

2.2 Permutation

The permutation portion of a round is simply the tranposition of the bits or the permutation of the bit positions. The permutation of Figure 1 is given in Table 2 (where the numbers represent bit positions in the block, with 1 being the leftmost bit and 16 being the rightmost bit) and can be simply described as: output i of S-box j is connected to input j of S-box i. Note that there would be no purpose for a permutation in the last round and, hence, our cipher does not have one.

2.3 Key Mixing

To achieve the key mixing, we use a simple bit-wise exclusive-OR between the key bits associated with a round (referred to as a subkey) and the data block input to a round. As well, a subkey is applied following the last round, ensuring that the last layer of substitution cannot be easily ignored by a cryptanalyst that simply works backward through the last round's substitution. Normally, in a cipher, the subkey for a round is derived from the cipher's master key through a process known as the key schedule. In our cipher, we shall assume that all bits of the subkeys are independently generated and unrelated.

2.4 Decryption

In order to decrypt, data is essentially passed backwards through the network. Hence, decryption is also of the form of an SPN as illustrated in Figure 1. However, the mappings used in the S-boxes of the decryption network are the inverse of the mappings in the encryption network (i.e., input becomes output, output becomes input). This implies that, in order for an SPN to allow for decryption, all S-boxes must be bijective, that is, a one-to-one mapping with the same number of input and output bits. As well, in order for the network to properly decrypt, the subkeys are applied in reverse order and the bits of the subkeys must be moved around according to the permutation, if the SPN is to look similar to Figure 1. Note also that the lack of the permutation in the last round ensures that the decryption network can be the same structure as the encryption network. (If there was a permutation after the last substitution layer in the encryption, the decryption would require a permutation before the first layer of substitution.)

3 LINEAR CRYPTANALYSIS

In this section, we outline the approach to attacking a cipher using linear cryptanalysis based on the example cipher of our basic SPN.

3.1 Overview of Basic Attack

Equation (1) could be equivalently reformulated to have the right side being the sum of a number of subkey bits. However, in (1) as written with the right side of "0", the equation implicitly has subkey bits involved: these bits are fixed but unknown (as they are determined by the key under attack) and implicity absorbed into the "0" on the right side of equation (1) and the probability PL that the linear expression holds. If the sum of the involved subkey bits is "0", the bias of (1) will have the same sign ( or -) as the bias of the expression involving the subkey sum and, if the sum of the involved subkey bits is "1", the bias of (1) will have the opposite sign.