Sebery J.Cryptography.An introduction to computer security.1989

3.4 Di erential Cryptanalysis

131

3.4.5 Analysis of Other Feistel-Type Cryptosystems

Similar analysis can be conducted for versions of DES with more rounds. Table 3.14 summarizes the results (for more details consult [36]). It is no surprise that the eÆciency of the attack drops exponentially with the number of rounds. This is due to the fact that longer characteristics have smaller probabilities associated with them.

Murphy [363] has shown that the FEAL-4 algorithm is vulnerable to the di erential analysis with 20 chosen plaintexts only. Biham and Shamir [34] demonstrated that FEAL-N with N smaller than 32 is subject to the di erential cryptanalysis whose eÆciency is higher than the exhaustive search of the key space.

The main features of the di erential analysis are summarized below.

{The di erential analysis can be applied to Feistel cryptosystems with t rounds where it is possible to see inputs to the round function and deduce or guess (with high probability) the corresponding output di erences.

{Characteristics are useful in guessing the correct output di erences of the

round function. It is enough to have (t 3)-round characteristic to nd out output di erences in the t-round Feistel cryptosystem.

{As the di erential analysis enables to nd keys applied in the last round function, it by-passes the key schedule. It works under the assumption that round keys are statistically independent.

{Once the key in the last round is found, the last round can be stripped o by applying the extra round which is the inverse of the last round. The analysis can be now applied to system with t 1 rounds (peeling o technique).

To make a Feistel cryptosystem immune against the di erential analysis, the following points need to be addressed:

{The XOR pro le must not have entries with large numbers.

{The best (t 3)-round characteristics should work with the probability smaller than the probability of guessing the right key (t is the number of rounds in the cryptosystem).

{The S-boxes should depend upon the secret key in a nonlinear way. This will cause that XOR pro le of S-boxes become more complex. One way of implementation of this idea would be an on-the- y selection of S-boxes depending on the round key.

132 3 PRIVATE-KEY CRYPTOSYSTEMS

3.5 Linear Cryptanalysis

At Eurocrypt '93 Matsui presented a new class of general attacks which exploits a low nonlinearity of S-boxes. The attack referred to as the linear cryptanalysis is a known-plaintext attack. The linear cryptanalysis can also work as a ciphertext-only attack. The principles of the linear cryptanalysis are explained in [322]. The linear cryptanalysis of DES is described in [321].

3.5.1 Linear Approximation

A Boolean function h : n ! in n variables s1; : : : ; sn, is linear if it can be represented as h(s) = a1s1 : : : ansn for some ai 2 = f0; 1g; i = 1; : : : ; n. The set of all linear Boolean functions in n variables is denoted by

Ln = fh : n ! j h = a1s1 : : : ansng:

A Boolean function f : n ! is called aÆne if either f(s) = h(s) or f(s) = his(s) 1, for some h(s) 2 Ln. The set of all aÆne Boolean functions in n variables

An = Ln [ fh 1 j h 2 Lng = Ln [ Ln;

i.e. An consists of all linear functions and their negations. A Boolean function f : n ! is uniquely represented by the corresponding truth table. Assume that the argument i 2 n runs through all its possible values 0; 1; : : : ; 2n 1 so 0 = (00 : : : 0), 1 = (00 : : : 1), and so forth until 2n 1 = (11 : : : 1). The truth table of f is equivalent to the following vector

f = (f( 0); f ( 1); : : : ; f ( 2n 1))

where f( i) speci es the value of the function for the argument expressed by the vector i (i = 0; : : : ; 2n 1). The Hamming distance d(f; g) between two Boolean functions f; g : n ! is the number of 1s in the vector

(f( 0) g( 0); f ( 1) g( 1); : : : ; f ( 2n 1) g( 2n 1)): or conversely, the number of disagreements between f and g.

De nition 4. The nonlinearity N(f ) of a Boolean function f : n ! is

N(f) = min d(h; f );

h2An

i.e., it is the minimal distance between the function f and its best linear approximation.

3.5 Linear Cryptanalysis

133

The cryptographic strength of modern encryption algorithms mainly rests on an appropriately chosen cryptographic structure of the cipher round. Those structures can always be seen as a collection of Boolean functions or S-boxes

tying input and output bits of the round. More precisely, an (n m) S-box S : n ! m is a collection of m functions fi : n ! ; i = 1; : : : ; m, in n Boolean variables s = (s1; : : : ; sn) for which

S(s) = (f1(s); : : : ; fm(s)):

The notion of nonlinearity can be extended as in the following de nition.

De nition 5. The nonlinearity of a (n m) S-box S = (f1; : : : ; fm) is

N(S) =

min

N(w1f1

: : :

wmfm

v):

(3.7)

w=(w1;:::;wm)2 m;v2

For instance, consider f : 2 !

where f (s) = s1s2. The truth table and

all linear functions from

L2 = f0; s1

; s2; s1

s2g are presented in Table 3.15. So

distances are d(f; 0) = d(f; s1) = d(f; s2) = 1 and d(f; s1 s2) = 3.

Knowing the distance d(f; h) = df;h

where h 2 Ln, it is easy to obtain

d(f; h 1) =

2n df;h. So to determine the

nonlinearity of a function f :

n ! , it is enough to nd all distances between the function and

the set of

linear functions. The distances for the aÆne functions from the set

Ln can be

computed from the distances of linear functions.

In the DES algorithm, there are eight S-boxes Si : 6 ! 4 for i = 1; : : : ; 8.

Each S-box can be treated as a collection of four Boolean functions. For a given S-box, we can create a table of distances as follows. Rows of the table are indexed by a linear function ` 2 L6. There are 26 = 64 possible linear functions. The index of the row is a hexadecimal number which represents the linear function. So the index 31x = 11 0001 corresponds to the linear function `(s) = s6 s5 s1 where s = (s6; s5; s4; s3; s2; s1). The columns of the table are indexed by linear combinations of S-box outputs. So if the S-box function S = (f4; f3; f2; f1), the linear combination f = (a4f4 a3f3 a2f2 a1f1) where a4a3a2a1 is the column index in the hexadecimal notation. For instance, the index 9x = 1001 corresponds to the linear combination of outputs f4 f1. There are 15 nonzero columns. The entry (`; f) gives the Hamming distance d(`; f). This table is called the linear pro le of an S-box.

The linear pro le of S5 is given in Table 3.16. All entries are even numbers, which results from the fact that all outputs in all S-boxes have equal number

134 3 PRIVATE-KEY CRYPTOSYSTEMS

of 0s and 1s (the output functions are balanced). The nonlinearity of a linear combination of outputs can be found by looking for the smallest and the biggest

entry in the corresponding column f. Let the two entries be dmin = df;r1 dmax = df;r2. The nonlinearity of the function f is the smaller integer from (dmin; 26 dmax). The best linear approximation of the column function is either the linear function `r1 if dmin < 26 dmax or the negation of the linear function `r2, i.e. the aÆne function `r2 1 where `r1 and `r2 are linear functions that correspond to the row r1 and r2, respectively.

The best linear approximation of a function f : n ! is the aÆne function ` 2 An that is closest (in the sense of Hamming distance) to the function f and the distance d(`; f) is the nonlinearity of the function. For instance, the function f8x has the best linear approximation

`f8x = s6 s5 s3 s2 s1

(the row 37x) and nonlinearity N(f8x ) = 20. The function f4x is best approximated by

`f4x = s6 s5 s4 s3 s2 s1 1

(the row 3Fx). The nonlinearity of f4x is 64 46 = 18.

The global characterization of S-box can be done by the selection of the pair:

the smallest dgmin and biggest entry dgmax. The nonlinearity of the S-box is the minimum of dgmin and 2n dgmax. For S5 the nonlinearity of the S-box is 12 (the entry for the row 10x and the column Fx) { so fFx can be approximated by s5.

This is the best available approximation in S5 and as a matter of fact, in all S-boxes.

Let a function f : n ! and its linear approximation ` : n ! be given. How well does ` approximate f? The distance d(`; f) gives the number of input values for which the functions di er. So if we randomly select an input, we have the probability

2n 2dn(`; f)

that the outputs of ` and f will be the same. The worst case is when the best

linear approximation ` di ers for about half of the possible input values, i.e. d(`; f) 2n 1. The probability that `(s) 6= f(s) or `(s) = f(s) is 0:5 for a random s 2 n.

3.5 Linear Cryptanalysis

135

R

k

X15

E

S-boxes

P

S (7,18,24,29)

Fig. 3.33. Linear approximation in a single round of DES

3.5.2 Analysis of 3-Round DES

Now we use the linear approximation from the previous section to devise an eÆcient attack on 3-round DES. The attack uses the best linear approximation of S5. This approximation is

s1 s2 s3 s4 = s5

where si are outputs and s5 is an input of S5. This equation translates to (Figure 3.33)

def

R(15) k(22) = S(7) S(18) S(24) S(29) = S(7;18;24;29)

in a single round of DES.

For 3-round DES (Figure 3.34), we can establish the following equations:

R2(7;18;24;29) L1(7;18;24;29)	= k1(22)	R1(15)		(3.8)
R2(7;18;24;29) L3(7;18;24;29)	= k3(22)	R3(15)		(3.9)
If we merge Equations (3.8) and (3.9), we obtain
L1(7;18;24;29) L3(7;18;24;29) R1(15)		R3(15)	= k1(22) k3(22)	(3.10)

What is the probability that Equation (3.10) is true? Equation (3.10) is true in the two cases: rst, if Equations (3.8) and (3.9) are true, or second, if the equations are simultaneously false. Therefore the probability is (5264 )2 + (1264 )2 0:7

Note that Equation (3.10) ties bits of plaintext and ciphertext with bits of the secret key. The secret key is xed so the right-hand side of the equation is constant (either 0 or 1). The left-hand side relates to speci c subset of bits of

136 3 PRIVATE-KEY CRYPTOSYSTEMS

PLAINTEXT
L1	(22)	k1
(7,18,24,29)	(15)
		( 1224
f	R1		)
		k2
f	R2
		k3
(7,18,24,29)	R3	( 1224	)
f

L3

CIPHERTEXT

Fig. 3.34. Three-round linear characteristic

a single plaintext/ciphertext observation and equals to the constant with the probability 0.7. This means that having a large enough collection of observations of plaintext/ciphertext pairs, the frequency distribution of the results is biased and the higher occurrence indicates the correct value of the constant k1(22) k3(22). The attack could proceed by choosing other good approximations and assemble linear equations for other key bits. If we had enough linearly independent equations, we could nd the key.

3.5.3 Linear Characteristics

Take a look at Figure 3.35, which shows 5-round DES. In the rst and fth round the 15th bit coming out of the round function is approximated using the following equation

S(15) = k(27) k(28) k(30) k(31) R(27) R(28) R(30) R(31)	def
	=
k(27;28;30;31) R(27;28;30;31)	(3.11)

This bit comes from S1 and its nonlinearity is 22. The following two equations are derived for the 1st and 5th round

R2(15) = L1(15) S1(15) = L1(15) k1(27;28;30;31) R1(27;28;30;31)

R4(15) = L5(15) S5(15) = L5(15) k5(27;28;30;31) R5(27;28;30;31):

The 2nd and 4th rounds use the same approximation as in the previously discussed 3-round DES so we have

3.5 Linear Cryptanalysis

137

PLAINTEXT
L1		R1	k1
S1(15)	f	(42,43,45,46)
	(27,28,30,31)
		(22)	k2
S2(7,18,24,29)
	(15)
	f	R2
			k3

f	R3

(22)k4

	S4(7,18,24,29)	(15)
	f
		R4

	k5
S5(15)	(27,28,30,31)
f	R5
L5

CIPHERTEXT

Fig. 3.35. Five-round linear characteristic

R3(7;18;24;29) = R1(7;18;24;29) S2(7;18;24;29) = R1(7;18;24;29) k2(22) R2(15)

R3(7;18;24;29) = R5(7;18;24;29) S4(7;18;24;29) = R5(7;18;24;29) k4(22) R4(15):

After merging these two, we get

R1(7;18;24;29) R5(7;18;24;29) = k2(22) R2(22) k4(22) R4(22):

Now we substitute R2(22) and R4(22) by their linear approximations and we have the nal linear characteristic

L1(15) L5(15) R1(7;18;24;27;28;29;30;31) R5(7;18;24;27;28;29;30;31) =
k1(27;28;30;31) k2(22) k4(22) k5(27;28;30;31):	(3.12)

The characteristic uses four linear approximations. Each approximation has the associated probability which expresses the accuracy of the approximation. How can we compute the probability that Equation (3.12) holds? The answer is given in the following theorem.

138 3 PRIVATE-KEY CRYPTOSYSTEMS

Theorem 12. (Matsui [322]) Given n independent random variables X1; : : : ; Xn

	such that P (Xi = 0) = pi and P (Xi = 1) = 1				pi for i = 1; : : : ; n. Then the
	probability that X1 : : : Xn = 0 is
	1	n
		Y
	2 + 2n 1		(pi	0:5):	(3.13)
		i=1

Note that to produce the characteristic from Equation (3.12), we have used four approximations whose probabilities are: 4264 ; 5264 ; 5264 ; 4264 . The probability that Equation (3.12) holds, is 0:519. It means that after 2800 pairs of plaintext/ciphertext the right value of k1(27;28;30;31) k2(22) k4(22) k5(27;28;30;31) can be found.

Linear characteristics are linear approximations of some of the key bits by a combination of plaintext/ciphertext bits. The eÆciency of a characteristic is measured by the probability that the characteristic is true (or all approximations in the characteristic hold). It can be computed from probabilities of S-box approximations by applying Theorem 12.

Matsui also introduced a nice improvement which speeds up the analysis. The improvement can be used in the rst and last round when we can see the inputs to the round functions. Instead of approximation, we try to guess the right bits of a part of the round key (only these bits of the key which in uence the characteristic). Assume that the characteristic depends on v bits of the key (in the rst or last round). We can evaluate the characteristic for all possible patterns of v bits simultaneously. Due to the probabilistic nature of characteristics, it is expected that the correct value of v bits will cause a noticeable bias in counting, which must be proportional to the probability of the characteristic. This allows to retrieve v bits of the key.

The analysis of 16-round DES can be done by using two linear characteristics. The second characteristic is obtained from the rst one by swapping plaintext bits with ciphertext bits in the equation. The characteristics approximate all rounds except the rst and last ones. For the rst and last rounds, we guess parts of the round keys. This produces 12 bits of the key plus 1 bit from the characteristic. As the attack uses 2 characteristics, we can determine 26 bits of the key. The remaining 30 bits are found by the exhaustive search. To break DES, it takes 243 steps and the success rate is 85% if 243 pairs (plaintext, ciphertext) are known.

3.6 S-box Theory

139

The FEAL cipher was the rst algorithm Matsui and Yamagishi [324] attacked using the linear cryptanalysis. The attack was much easier to launch due to the structure of the S-boxes. Matsui and Yamagishi [324] noted that the S-boxes have low nonlinearity and in particular, the least signi cant bit is linear. Consequently, they demonstrated that FEAL-4 is breakable with 5 observations and FEAL-8 with 215 observations.

How can cryptographic systems be prevented against the linear cryptanalysis? The answer seems to be easy: use highly nonlinear S-boxes. For a highly nonlinear S-box, each linear approximation of the S-box function works with low probability. However, it is also possible to increase the immunity of the system against the linear analysis by permuting S-boxes [323]. This is due to the fact that for a carefully chosen order of S-boxes in the round function, concatenation of linear approximations fails to create a good linear characteristic.

3.6 S-box Theory

Shannon's concept of product ciphers uses two basic transformations: confusion and di usion. All modern cryptographic algorithms use in some or another way a collection of S-boxes that provide confusion and P-boxes which spread out the output bits to di erent S-boxes of the next round. P-boxes have usually a xed permutation of input and output bits. The strength of product ciphers mainly comes from the \properly" designed S-boxes. The de nition of cryptographically strong S-boxes is to some extend arbitrary. It is well known that weaknesses of S-boxes may be compensated by the increased number of rounds. This is precisely the case with the FEAL algorithm, which becomes immune against the linear cryptanalysis when the number of rounds is bigger than 32. Note that if a cryptographic algorithm is to be both cryptographically strong and fast, then a careful design of all its components is of utmost importance.

Each general cryptographic attack that is better than the exhaustive search, explores some weakness in S-boxes. In response, a new S-box criterion is introduced. If the criterion is incorporated into S-boxes, it makes the cryptographic algorithm immune against the attack. For instance, the di erential attack brought to our attention the need for good XOR pro les in S-box design.

140 3 PRIVATE-KEY CRYPTOSYSTEMS

3.6.1 Boolean Functions

Recall that = f0; 1g. The simplest eld which can be de ned over is GF (2) = h ; ; i with the addition and multiplication . GF (2) is called the binary eld. Clearly, addition is 0 0 = 1 1 = 0 and 0 1 = 1 0 = 1.

Multiplication is de ned as 0 0 = 1 0 = 0 1 = 0 and 1 1 = 1. Consider a Boolean function f : n ! GF (2) that assigns a binary element

f(x) 2 to a vector x = (x1; : : : ; xn) 2 n. For simplicity, we will denote elements (vectors) of n by their decimal representations used as the subscript so

0 = (00 : : : 00)

1 = (00 : : : 01)

.

.

.

2n 1 = (11 : : : 11):

Let f : n ! GF (2) be a Boolean function. The binary sequence (f( 0); f ( 1); : : : ; f( 2n 1))

is called the truth table of the function f . The sequence with components from f1; 1g de ned by

(( 1)f( 0); ( 1)f( 1); : : : ; ( 1)f( 2n 1))

is called the sequence of the function f. A 2n 2n matrix F with entries fi;j = ( 1)f( i j) is called the matrix of the function f.

Consider an example. Let f(x) = x1x2x3 x1x3 x2 x3 1 be a function on 3. It is easy to check that

f(000) = 1; f(001) = 0; f (010) = 0; f(011) = 1; f(100) = 1; f(101) = 1; f (110) = 0; f(111) = 1:

So the truth table of f is (10011101) and the sequence of f is ( 1; 1; 1; 1;1; 1; 1; 1) or ( + + + ) where + and stand for +1 and 1, respectively. The matrix of f is