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

is balanced since the truth table of f is (01010110) and the function takes the value zero the prescribed four times.

A Boolean function f : n ! GF (2) is aÆne if it can be represented in the form

f (x1; : : : ; xn) = a0 a1x1 anxn;

where ai 2 for i = 0; : : : ; n. The set of all aÆne functions over n is denoted by An. An aÆne function f is called linear if a0 = 0. The sequence of an aÆne (or linear) function is called an aÆne (or linear) sequence. The function f(x1; x2; x3) = x3 x1 1 is aÆne, and the function f (x1; x2; x3) = x3 x1 is linear.

The Hamming weight of a binary vector 2 n, denoted by W ( ), is the number of ones it contains. For example, W (010011) = 3. Given two functions f; g : n ! GF (2), the Hamming distance between them is de ned as

d(f; g) = W (f(x) g(x));

where W (f(x) g(x)) is the weight of the truth table of the function f(x) g(x). Let f(x) = x1x2 and g(x) = x1 x2 be two Boolean functions. Then

d(f; g) = W (f(x) g(x)) = W (x1x2 x1 x2):

As the truth table of the function f g = x1x2 x1 x2 is (0111), the distance d(f; g) = 3.

Let = (a1; : : : ; an) and = (b1; : : : ; bn) be two vectors (or sequences), the scalar product of and , denoted by h ; i, is de ned as the sum of the component-wise multiplications. In particular, when and are from n, h ; i = a1b1 anbn. If and are (1; 1)-sequences, the scalar product h ; i = Pni=1 aibi, and the addition and multiplication is taken over the reals.

142 3 PRIVATE-KEY CRYPTOSYSTEMS

Lemma 2. If = (a0; : : : ; a2n 1) and = (b0; : : : ; b2n 1) are the sequences of functions f1; f2 : n ! GF (2), respectively, then

= (a0b0; a1b1; : : : ; a2n 1b2n 1)

is the sequence of f1(x) f2(x), where x = (x1; x2; : : : ; xn).

An r r matrix with entries from f1; 1g is called a Hadamard matrix if

HHT = rIr;

where HT is the transpose of H and Ir is the r r identity matrix. It is well known that Hadamard matrices exist when n = 1; 2 or n is multiple of 4 [519]. A Sylvester-Hadamard or Walsh-Hadamard matrix is a 2n 2n matrix Hn which is generated according to the following recursive relation:

H0 = 1; Hn = "Hn 1 Hn 1 # ; n = 1;2; : : : :

Hn 1 Hn 1

The way the matrix Hn is constructed from Hn 1 is written shortly as Hn = H1 Hn 1 where in means the Kronecker product. For instance, let

An interesting relation between Walsh-Hadamard matrices and the collection of linear functions is described in the next lemma.

Proof. By induction on n. Let n = 1. Note that H1 = "++ +# where + and

stand for 1 and 1, respectively. The rst row of H1 is `0 = (+ +) which is equal to h0; xi. The corresponding function is the constant function f (x) = 0. The second row of H1 is `1 = (+ ) which is the same as the sequence of h1; xi where x 2 . The corresponding function is f(x) = x.

Suppose the lemma is true for n = 1; 2; : : : ; k 1. Since Hk = H1 Hk 1, each row of Hn can be written as either (`; `) or (`; `) where ` is a row in Hk 1. From the assumption, ` is the sequence of some linear function '(x)

The rst four Walsh-Hadamard matrices are:

de ned as

144 3 PRIVATE-KEY CRYPTOSYSTEMS

DÆ(y1; y2; : : : ; yp) = (y1 i1)(y2 i2) (yp ip)

where ij is the complement of ij for j = 1; 2; : : : ; p. The D-function of Æ is useful in obtaining the function representation for the concatenation of binary sequences. Let fi : q ! GF (2); i = 0; : : : ; 2p 1, be a collection of 2p Boolean functions. Also let i be the sequence of fi(x1; : : : ; xq). Now we create the concatenation of the sequences i; i = 0 : : : ; 2p 1 so

= ( 0; 1; : : : ; 2p 1):

Obviously, the function that corresponds to , is Boolean function f : p+q ! GF (2) and

g(u; x1; : : : ; xn) = (1 u)f1(x) uf2(x):

3.6.2 S-box Design Criteria

The design of cryptographic algorithms is still in its infancy stage despite an impressive progress. The S-box theory emerged as an attempt to formalize defences that can be incorporated into S-boxes to strengthen the algorithm against cryptographic attacks. Any new attack typically results in a new design criterion that indicates what properties an S-box must have to resist the attack. There is a set of design criteria which are believed to be essential in the design of cryptographic algorithms. If S-boxes do not satisfy one of the criteria, the cryptographic design based on the S-boxes may be cryptographically weak (or easy to attack) or alternatively, the design may need extra rounds to compensate the weakness (resulting in an ineÆcient design). The collection of essential S- box design criteria includes

{completeness,

{balance,

{nonlinearity,

{propagation criterion, and

{ good XOR pro le.

The completeness criterion was introduced by Kam and Davida [266]. The criterion is applicable to the whole cryptographic design (or S-P network) rather than a single S-box. Given S-boxes with a xed structure, it is necessary to design a suitable permutation box (P-box) and compute how many rounds are necessary to build up the cross dependencies so any binary output is a complex function of every binary input. The lack of these dependencies enables an opponent to use the \divide and conquer" strategy to analyze the design.

A Boolean function f : n ! GF (2) is said to be balanced if its truth table has 2n 1 zeroes (or ones). For instance, f = x1x2 x3, a Boolean function on3, is balanced since the truth table of f is (01010110) and the function takes the value zero 23 1 = 4 times. The lack of balance in an S-box causes that each time the S-box is used, it produces outputs with a bias. So some output strings are more probable than other. Even worse, as any cryptographic design uses many rounds with the same S-box, the bias tends to accumulate making the bias larger when the number of rounds grow. This opens up the design to all sort of attacks which explore a nonuniform output string probability distribution.

Given a balanced function f : n ! GF (2). What are possible input transformations such that the resulting function preserves the balance.

Lemma 4. Let

g(x) = f (xB )

where B is any n n nonsingular matrix and 2 n is a vector. Then g is balanced if and only if f is balanced.

Proof. Note that if B is nonsingular, then for x running through all input values from the set f 0; : : : ; 2n 1g, y = xB also takes on the same collection of values. Hence if f (x) is balanced so is g(x) = f (xB ) as the output values of g are permuted values of the function f. tu

Let g(x) = f(xB ) where = (1; 1; 1) and

21 1 03 B = 61 0 17:

40 1 05

Thus g(x1; x2; x3) = f(x1 x2 1; x1 x3 1; x2 1). Clearly, g is also balanced since g(x0) = 0 if and only if f(x0B ) = 0.

146 3 PRIVATE-KEY CRYPTOSYSTEMS

Lemma 5. Let f : n ! GF (2) and g : m ! GF (2) be Boolean functions. Then the function h : n+m ! GF (2) de ned as h(x; y) = f (x) g(y) is balanced if f is balanced.

Proof. Observe that g( ) is constant for given and the truth table of f(x) is zero (one) half the time. Consequently, the truth table of f(x) g(y) is zero (one) half the time. tu

The nonlinearity of a Boolean function can be de ned as the distance between the function and the set of all aÆne functions [406]. More precisely, the nonlinearity of a Boolean function f : n ! GF (2) is

Nf = min d(f; g)

g2An

So that d(f; `1) = d(f; `2) = 1, d(f; `3) = 3. For the missing aÆne functions the distances are either 1 or 3, so the nonlinearity of f is 1.

Lemma 6. Let f; g : ! GF (2) then

d(f; g) = 2n 1 12h ; i

where ; are the sequences of f and g, respectively.

Proof. Denote = (a0; a1; : : : ; a2n 1) and = (b0; b1; : : : ; b2n 1). Let (+) denote the number of positions for which two sequences are the same (aj = bj).

The integer ( ) gives the number of positions where the two sequences di er or

aj 6= bj. Hence, h ; i = (+) ( ) = 2n 2 ( ) and ( ) = 2n 1 12 h ; i. Obviously, ( ) = d(f; g). tu

The next lemma can be easily veri ed using the de nition of nonlinearity.

The notion of nonlinearity can be generalized for a collection of Boolean functions. Let the function f : n ! m. The nonlinearity of the function (Nyberg [378]) is

Nf = min Nf

2 m; 6=0

where f = h ; fi= 1f1 mfm is a linear combination of component functions f = (f1; : : : ; fm) de ned by the vector = ( 1; : : : ; m).

Strict Avalanche Criterion or SAC was introduced by Webster and Tavares [522]. Informally, an S-box satis es SAC if a single bit change on the input results in changes on a half of output bits. Note that if the S-box is used to construct an S-P network, then a single change on the input of the network causes an avalanche of changes. More formally, a function f : n ! GF (2) satis es the SAC if

f (x) f(x )

is balanced for all whose weight is 1, i.e. W ( ) = 1. In other words, the SAC characterizes the output when there is a single bit change on the input. Higher order SAC is generalization of the SAC property where the number of input changes is bigger than one. Both the SAC and higher order SAC are collectively called propagation criteria [2, 415].

We say that f satis es the propagation criterion with respect to the vector

if f(x) f(x ) is a balanced function, where x; 2 n and is a nonzero vector. A function which holds the propagation criterion with respect to all 2 n whose weight is 1 W ( ) k, is said to satisfy the propagation criterion of degree k.

Consider the function f = x1x2 x3 over 3 . Let = (1; 1; 0). It is easy to check that

f (x) f(x ) = (x1x2 x3) ((x1 1)(x2 1) x3) = x1 x2 1

is balanced. So f satis es the propagation criterion with respect to the vector= (1;1; 0). Take the following function over 5

f (x1; x2; x3; x4; x5) = x1 x1x5 x2x4 x2x5 x2x4x5 x3x4x5:

Let the vector = (0; 0; 1; 0;0) then the function

f (x) f(x ) = x3x4x5 (x3 1)x4x5 = x4x5

is not balanced. In fact, f does not satisfy the propagation criterion with respect to any vector in the subset

< = f(0; 0; 0; 0; 0); (0; 0; 0;0; 1); (0; 0; 0; 1; 0); (0; 0;1; 0; 0); (0; 0; 1; 1; 1)g:

The next theorem shows how a nonsingular linear transformation can be used to obtain a function which satis es the SAC.

Theorem 13. Let f : n ! GF (2) be a Boolean function and A be an n n nonsingular matrix with entries from GF (2). If f (x) f(x ) is balanced for each row of A, then the function (x) = f (xA) satis es the SAC.

For instance, consider the function f = x1x2 x3 which does not satisfy SAC as

f (x) f(x e3) = x1x2 x3 x1x2 (x3 1) = 1

is not balanced, for the vector e3 = (001). On the other hand,

f (x) f(x e1) = x2;

f (x) f(x e2) = x1; and

f(x) f(x ) = x1 x2 1

are balanced for the vectors e1 = (100), e2 = (010), = (111), respectively. Consider the matrix built from these vectors so

From Theorem 13 we conclude that g(x) = f (xA) satis es the SAC.

Theorem 13 can be generalized and used to design a collection of functions each of which satisfying the SAC.

Theorem 14. Let f1; : : : ; fm be functions over n and the set of vectors overn be

< = f jfj(x) fj (x ) is not balanced for j, 1 j mg:

If j<j < 2n 1 then there exists a nonsingular n n matrix with entries from GF (2) such that each j(x) = fj(xA) satis es the SAC.

failure happens when the function f(x) f(x ) is constant. Being more precise, let f be a function over n. A vector, , is called a linear structure of f if f(x) f (x ) is constant. Every function has at least one linear structure { the zero vector. For instance, consider the function f = x1x2 x3 over 3. The vector = (0; 0; 1) is a linear structure of f as

f (x) f(x ) = (x1x2 x3) (x1x2 x3 1) = 1:

Needless to say, nonzero linear structures should be avoided in S-boxes as they force the corresponding di erences of functions to be constant.

The XOR pro le was introduced in Section 3.4.1. The criterion is not very restrictive as the designer of S-boxes needs to take care that XOR pro le does not contain entries with \large" numbers. In addition, the XOR pro le must be considered in the context of the best round characteristics. It is possible to trade o the largest entries of XOR pro le with the number of rounds.

In some circumstances, we may request from a collection of Boolean func-

choice of underlying logical operations. Two canonical forms (disjunctive and conjunctive) lead to expressions that are not unique and then one can try tond the shortest expression (the minimization procedure). On the other hand, the algebraic normal form is unique. The function f : n ! GF (2) is written in the algebraic normal form if