How to create „good” s-boxes? 1st International Conference for Young Researchers in Computer Science, Control, Electrical Engineering and Telecommunications ICYR 2006, Zielona Góra, Poland 18-20 September 2006 Przemysław Rodwald and Piotr Mroczkowski Military Communication Institute {p.rodwald,p.mroczkowski}@wil.waw.pl S-box (substitution box) is a basic element of many block ciphers and few interesting hash functions (Tiger, Whirlpool). This paper presents design criteria based on information theory, properties of good, cryptographically strong S-boxes and two methods of generation. First base on set of bent functions and second base on inversion mapping. 1. INTRODUCTION Cryptographic substitution, since they have been introduced by Shannon [13], became one of the most frequently used transformation in current symmetric ciphers. The cryptographic strength, resistance to cryptanalysis, comes from carefully designed S-boxes. An n×m S-box is a mapping S : {0,1}n → {0,1}m . Most contemporary use ciphers use static S-boxes, which were generated in advance. But exist group of ciphers (Blowfish or Twofish) which use dynamic generating S-boxes. Last years many criteria, which good S-boxes should fulfill, were presented. They are for example Balancedness, nonlinearity, XOR profile, Strict Avalanche Criterion, Bit Independent Criterion. The problem is that some of them contradict, for example is impossible to reach both: balancedness and highest nonlinearity. Therefore some tradeoffs have to be made. This article is organized as follows. In part 1 we proposed static and dynamic properties of S-boxes and also design criteria based on information theory. Some basic definitions and properties of ideal S-boxes were described in part 2. Last section includes algorithms for generating cryptographically good S-boxes. 2. STATIC AND DYNAMIC PROPERTIES Dawson and Tavares [3] taking into account previous works of for example Forre [5], extended set of desirable properties of S-boxes using information theory and use this properties to propose a design criteria for S-boxes. S-boxes can be seen in two distinct ways: static and dynamic. The static view describes substitution box when an input vector is not changing. The contrary view, dynamic, presents box when an input is changing (∆x) and we explore the change on the output (∆y). x1 x2 … S-box xn y1 ∆x1 y2 ∆x2 … … ym Rys.1. S-box – static view ∆xn ∆y1 internal state x1 x2 … xn ∆y2 … ∆ym Rys.2. S-box – dynamic view 1 To define static and dynamic properties we use entropy. For a random variable z with possible values z1, z2, …, zn entropy H(z) we define as follows: H ( z) = n i =1 ( P ( zi ) log 2 P( zi ) −1 ) and mutual information beetwen two random variables x i y is I(x;y)=H(x)-H(x|y). Dawson and Tavares [3] proposed six properties for ideal S-boxes, devided them for static and dynamic. Base on these properties they defined static and dynamic design criteria (inputoutput independence, output-input independence, output-output independence, dynamic inputoutput independence, dynamic output-input independence, dynamic output-output independence). Sivabalan, Tavares and Peppard [14] suggested that Forre’s criteria apply to the static model only and proposed their own, extended criteria. Previously design criteria was developed at a “single” bit level, but they extended this approach to a “multiple” bit level, where information leakage between one or more output bits and the input bits or between one or more output bits and the rest of the output bits are taking into account. These criteria are defined as follows: Static Input-Output Information Leakage – SL[I,O] Partial information about the input bits should not reduce the uncertainty in the unknown output bits: SL[ I , O ] = I (Yt , X k ) = H (Yt ) − H (Yt | X k) , where X k = {x j1 , x j2 ,..., x jk } is a subset of the input bits for: 1 ≤ k ≤ n − 1, 1 ≤ j1 ,..., j k ≤ n , and Yt = { yl1 ,..., ylt } is a subset of the input bits where 1 ≤ t ≤ n − 1, 1 ≤ l1 ,..., l t ≤ n . Dynamic Input-Output Information Leakage – DL[I,O] Information about any changes in the input bits should not reduce the uncertainty in the changes in the output bits: DL[ I , O] = I (∆Yt , ∆X k ) = H (∆Yt ) − H (∆Yt | ∆X k) , where ∆X k = {∆x j1 , ∆x j2 ,..., ∆x jk } is a set of changes in the input bits for: 1 ≤ k ≤ n − 1, 1 ≤ j1 ,..., j k ≤ n , and ∆Yt = { ∆yl1 , ∆yl2 ,..., ∆ylt } is a set of changes in the output bits where 1 ≤ t ≤ n − 1, 1 ≤ l1 ,..., l t ≤ n Dynamic Output-Output Information Leakage – DL[O,O] Partial information about any changes in the output bits should not reduce the uncertainty in the changes of another output bits: DL[ I , O] = I ( ∆Yt , ∆Yk ) = H ( ∆Yt ) − H ( ∆Yt | ∆Y k ) , where ∆Yk = { ∆y j1 ,∆y j 2 ,...,∆y jk } is a subset of changes in the output bits for 1 ≤ k ≤ n − 1, 1 ≤ j1 ,..., j k ≤ n , and ∆Yt = { ∆yl1 , ∆yl2 ,..., ∆ylt } is another subset of changes in the output bits where 1 ≤ t ≤ n − 1, 1 ≤ l1 ,..., l t ≤ n . To compare S-boxes we produce the averaged matrices, where average means that for any k and t, the leakage is averaged over all choices of Yt and Xk, or ∆Yt and ∆Xk, or ∆Yt and ∆Yk. 2 3. S-BOX DESIRABLE PROPERTIES In private-key cryptosystems which are based on substitution-permutation networks, the strength depends directly on the quality of the substitution boxes, called S-boxes, used by the algorithm. They should satisfy designing criteria in order that to secure the cryptosystem against possible cryptographical attack, especially against linear [8] and differential cryptanalysis. The design of good S-boxes is therefore an important part of designing cryptosystems. An n × m S-box S is mapping S : {0,1}n → {0,1}m , which converts an input vector x = [ xn−1 , xn−2 ,..., x1 , x0 ] to an output vector y = [ ym−1 , ym−2 ,..., y1 , y0 ] : y = S ( x ) . S can be represented as 2n m-bit numbers, denoted r0 ,..., r2 n −1 , in which case S ( x) = [cm −1 ( x), cm − 2 ( x),..., c0 ( x)] where the ci are fixed Boolean functions ci : {0,1}n → {0,1} , for i=0,…m-1; these are the columns of the S-box. Finally, S an be represented by a 2 n × m binary matrix M with the i, j entry being bit j of row i. For further analysis of the S-boxes property we define same notation: binary vector w by n elements – a vector whose coordinates are bits from a set {0,1} w = [ wn−1 , wn−2 ,..., w1 , w0 ] , where wn−1 , wn−2 ,..., w1 , w0 ∈{0,1} ; Hamming weight of a binary vector w, denoted hw(w), is the number of ones it contains: hw( w ) = n −1 i =0 wi ; Hamming distance between two binary vectors w and z, denoted hd(w, z), is defined as the number of bit positions, which differ form each other: hd ( w, z ) = hw( w ⊕ z ) = n −1 i =0 ( wi ⊕ zi ) ; linear combination of m boolean functions f i : {0,1}n → {0,1} , i=m-1,…1,0, is the function f a : { 0 ,1 }n → { 0 ,1 } , which f a ( x) = am −1 f m −1 ( x) ⊕ ... ⊕ a1 f1 ( x) ⊕ a0 f 0 ( x) , we where may x ∈ { 0,1 }n denote and a = [am−1 ,..., a1 , ao ] ∈{0,1}n ; dynamic distance of order j of a function f : { 0 ,1 }n → { 0 ,1 } we define as follows: n DD j ( f ) = maxn d∈{0 ,1} 1≤ hw( d )≤ j 3.1 1 n−1 2 −1 2 − f ( x) ⊕ f ( x ⊕ d ) . 2 n =0 COMPLETENESS A Boolean function f : { 0 ,1 }n → { 0,1 } is complete if its output depends on all input bits, that is, its algebraic normal form includes all components of the input vector x = [ xn−1 , xn−2 ,..., x1 , x0 ] . S-box S : {0,1}n → {0,1}m is complete [6], if for all vectors a = [ an−1 ,..., a1 , ao ] ∈ { 0 ,1 }n which Hamming weight is equal 1, hw( a ) = 1 , there exists vector w = [ wn−1 , wn−2 ,..., w1 , w0 ] ∈ {0,1}n such that S ( w ) and S ( w ⊕ a ) are different at least on j bit for all j ∈ { n − 1,...1,0 } . 3 3.2 BALANCEDNESS A Boolean function f : { 0 ,1 }n → { 0,1 } is said to be balanced if its truth table has 2n-1 zeros (or ones): f ( w ) = 2n−1 . w∈{0,1}n S-box S : {0,1}n → {0,1}m is balanced, if and only when all columns are balanced: ∀ ∀ n f j ( x) ⊕ f j ( x ⊕ α ) = 2n−1 . 0≤ j ≤m−1 α∈{0 ,1} w (α )=1 3.3 x∈Σ n NONLINEARITY The nonlinearity is one of the most important property of boolean functions, which take advantage in cryptography and specify distance to weak cryptographically affine functions. The nonlinearity of Boolean functions f : { 0 ,1 }n → { 0,1 } is defined as the least Haming distance between the function and the set of all affine functions [9]: nl ( f ) = min hd ( f , l ) ; l∈ An where An – a set of all affine functions over {0,1}n . With respect to linear structures, a function f has optimum nonlinearity if for every nonzero vector a = [ an−1 ,..., a1 , ao ] ∈ { 0 ,1 }n the values f ( x ) and f ( x + a) are equal for exactly half arguments x ∈ {0,1}n . If a function f satisfies this property we will call it perfect nonlinear with respect to linear structures, or briefly perfect nonlinear. It turns out that perfect nonlinear functions correspond to certain functions known in combinatorial theory Rothaus [12] has investigated a class of functions, which he called bent functions. Bent functions are not exactly balanced. The above shows that in general perfect nonlinearity may not be compatible with other cryptographic with other cryptographic design criteria, e.g. balance or highest nonlinear order. This fact necessitates doing compromise between nonlinearity and balance. Nonlinearity of S-box S : {0,1}n → {0,1}m is defined as the least value of nonlinearity of all nonzero linear combinations of m boolean functions f i : {0,1}n → {0,1} , i=m-1,…1,0: N ( S ) = minm N (l α ) α ∈{0,1} α ≠0 where : lα= α, f = α1f1 ⊕ …⊕ αmfm is linear combinations of m boolean functions. 3.4 XOR PROFILE The differential cryptanalysis was introduced by Biham and Shamir [2]. The attack is based on using the imbalances in the “pair XOR distribution table”, for an S-box, to predict the output XOR from the input XOR. XOR distribution table consists of : 2n rows, which are responsible for input differences and 2m columns, which are responsible for output differences. The XOR table entry of an S-box S corresponding to (α , β ) is XOR(α , β ) =#{x ∈{0,1}n : S ( x) ⊕ S ( x + α ) = β } , where: # denotes the cardinality of the set, α ∈ {0,1}n \ {0}, β ∈ {0,1}m . 4 The properties of XOR profiles can be summarized as follows: all entries in the XOR table are zeros or positive even integers; the row for α = 0 has only one nonzero entry equal to 2n ; the sum of entries in each row is equal to 2n; an input difference α may cause an output difference β with probability p = δ 2n where δ is the entry of (α , β ) in the XOR table; if an entry (α , β ) in XOR table is zero, then the input difference α cannot cause the difference β on the output. 3.5 STRICTE AVALANCHE CRITERION The Stricte Avalanche Criterion (SAC) was introduced by Webster and Tavares [15]. If a function is to satisfy the strict avalanche criterion, then each of its output bits should change with a probability of one half whenever a single input bit is complemented. The cryptographic significance of the SAC is highlighted by considering the situation where a cryptographer needs some “complex” mapping f of n bits onto one bit. A Boolean function f : { 0 ,1 }n → { 0,1 } satisfies the SAC if DD1 ( f ) = 0 , that is, if the function f ( x ⊕ d ) is balanced for every vectors x ∈ { 0,1 }n and for every vectors d ∈ { 0,1 }n , which Hamming weight is equal 1: hw(d ) = 1 . Similarly, is defined the Higher Order Stricte Avalanche Criterion (HOSAC). A Boolean function f : { 0 ,1 }n → { 0,1 } satisfies the HOSAC of order j if DD j ( f ) = 0 , that is, if the function f ( x ⊕ d ) is balanced for every vectors x ∈ { 0,1 }n and for every vectors d ∈ { 0,1 }n , which Hamming weight is equal j: hw(d ) = j . At the end we define the Maximum Order Stricte Avalanche Criterion (MOSAC). A Boolean function f : { 0 ,1 }n → { 0,1 } satisfies the MOSAC if DDn ( f ) = 0 , that is, if the function f ( x ⊕ d ) is balanced for every vectors x ∈ { 0,1 }n and for every vectors d ∈ { 0,1 }n , which Hamming weight is equal n: hw(d ) = n . An S-box S satisfies SAC, HOSAC and MOSAC if and only when every of its columns satisfy SAC, HOSAC and MOSAC. 3.6 BIT INDEPENDENCE CRITERION Bit Independence Criterion (BIC) was introduced by Webster and Tavares [15]. The Boolean function f satisfy BIC if for every input bit i ∈ {0,1,..., n − 1} and for every output pair of bits p, q ∈ {0,1,..., m − 1}, p ≠ q , the change of bit i on the input causes on the output independent changes of bits p i q. In order to define BIC it was introduced Distance to Higher Order BIC (DHOBIC) . For an S-box S DHOBIC is defined by: DHOBICi , j ( S ) = maxm DD j ( Mc ) , c∈{ 0 ,1 } 1≤hw( c )≤i where M is the binary matrix corresponding to S and the matrix multiplication is done using modulo 2 addition. S-box S satisfies BIC if DHOBIC 2,1 ( S ) = 0 and satisfies High Order BIC (HOBICi,j) if DHOBICi , j ( S ) = 0 . Distances to BIC and HOBIC are given by 5 DHOBIC 2,1 ( S ) = 0 and DHOBICi , j ( S ) = 0 respectively. Maximum order to BIC (MOBIC) and the distance to MOBIC (DMOBIC) correspond to HOBIC and DHOBIC with i=m, j=n. 3.7 CONCLUSION Perfect S-box should fulfill following properties [9,16]: C.1. all linear combinations of columns of S-box should be bent functions C.2. all elements in the xor table should have value 2 for ∆x 0 C.3. S-box should satisfies MOSAC C.4. S-box should satisfies MOBIC C.5. Hamming weight of each column should be equal to 2n-1 C.6. set of weights of rows and all pairs of rows should has value n/2 Property C.1 helps to protect against linear cryptanalysis, C.2 against differential cryptanalysis [2]. Criteria C.1, C.5, C.6 will aid to ensure a good static characteristic and criteria C.2, C.3, C.4, C6 help to ensure good dynamic characteristic. The problem is that not all of them can be achieved simultaneously, because some of them are contradict. To create good S-boxes some of tradeoffs have to be made. We decided to put some border values (the higher or lower possible value) of few criteria. Nyberg [10] shows that it is impossible to achieve perfect nonlinear S-box for n<2m. We replace criterion C.1 by a weaker one: C.1.* all linear combinations of columns should have the highest possible nonlinearity. Criterion C.2 is rather easy to achieved for large S-boxes (where n«m). Property C.3 is guaranteed if we use bent functions. Criterion C.4 must be weakening, because can not be achieved for n<2m [10]: C.4.* S-box should have the lowest possible value DHOBICn,1. All bent functions have Hamming weight equal to 2 n−1 − 2( n / 2 )−1 or 2 n−1 + 2( n / 2 )−1 , however perfect Hamming weight is 2n −1 . To reach this property we can balance bent function. To obtain property C.6 we can modify columns by adding affine functions to columns, because joining bent function with affine function gives as result bent function. 6 4. 4.1 METHODS OF S-BOX CONSTRUCTION METHOD BASE ON BENT FUNCTIONS The simplest way to construct S-boxes is to generate set of bent functions, use them as columns in S-box and in the end to check all desirable criteria of full S-box. The way is simple but very inefficient. The probability that such build S-box is cryptographically good is very low. Much better approach is to do this step by step. It means to add one bent function to the S-box and to check all criteria. If this incomplete S-box fulfill all criteria we can add next bent function, if not we replace this function with another one and so on. An algorithm for generating n×m S-box looks as follows: 1. set variable nr_col=1 2. specify the lowest acceptable value of nonlinearity of combinations of bent functions – NCBFmin 3. specify the higher acceptable value of MOBICn,1 – MOBICmax 4. generate n-inputs bent function – gnr_col 5. balance this bent function gnr_col 6. check following criteria for all linear combination of functions g1,g2,..,gnr_col: a. if nonlinearity is greater than or equal to NCBFmin b. if dynamic distance DD1 is at most MOBICmax 7. if above criteria are fulfilled then load a bent function gnr_col into column of S-box and increase variable nr_col=nr_col+1 else go back to step 2 8. if nr_col < m go back to step 2 4.2 METHOD BASE ON INVERSION MAPPING In 1993 Nyberg shows strong cryptographically mappings which are characterized by high nonlinearity [11] and the may take advantage of constructing S-boxes. One of then is inversion mapping in the GF(22) field. The inversion mapping F : {0,1}n → {0,1}n is defined in the following way: F (a) = −1 a , gdy a ≠ (0, ,0) gdy a = (0, ,0) 0, , −1 where: a - a inverse vector to vector a . Every binary vector a = ( an−1 ,..., a1 , ao ) ∈ { 0 ,1 }n can be considered as a polynomial with coefficients in GF(2): a( x ) = an−1 x n−1 + an−2 x n−2 + ... + a1 x + a0 . In order to define the multiplication or inversion, we need to select a reduction polynomial m( x ) = mn x n + mn−1 x n−1 + ... + m1 x + m0 . The inversion polynomial is defined as: a( x ) ⋅ a −1( x ) ≡ 1 mod m( x ) . −1 −1 n −1 −1 n−2 −1 −1 The coefficients of the inversion polynomial a ( x) = a n−1 x + a n−2 x + ... + a 1 x + a 0 −1 creates vector a = [a −1 n −1 , a −1 n −2 ,..., a −11 , a −10 ] , which is an inversion vector. The constructions of S-box S : {0,1}n → {0,1}m , using an inversion mapping, consists in calculating the inverse vector of every input vector x = [ xn−1 ,..., x1 , xo ] . 7 5. LITERATURE 1. C. Adams, S. Tavares , Good S-boxes are Easy to Find, Advances in Cryptology CRYPTO 1989, LNCS 435, Springer-Verlag, 1989 2. E. Biham, A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Advances in Cryptology – CRYPTO 1990, Springer-Verlag, 1990 3. M. Dawson, S. Tavares, An Expanded Set of S-box Design Criteria Based on Information Theory and its Relation to Differential-like Attacks, Advances in Cryptology – EUROCRYPT 1991, LNCS 547, Springer-Verlag, 1991 4. J. Detombe, S. Tavares, Constructing large cryptographically strong S-boxes, Advances in Cryptology – AUSCRYPT 1992, LNCS 718, Springer-Verlag, 1993 5. R. Forre, Methods and instrument for designing S-boxes, Journal of Cryptology, vol.2, no.3, 1990 6. J. Kam, G. Davida, Structured Design of Substitution-Permutation Encryption Networks, IEEE Transactions on Computers, Vol 28, No. 10, 747, 1979 7. M. Matsui, Linear cryptanalysis method for DES, Advances in Cryptology – EUROCRYPT 1993, Springer-Verlag, 1993 8. W. Meier, O. Staffelbach, Nonlinearity criteria for cryptographic function, Advances in Cryptology – EUROCRYPT 1989, LNCS 434, Springer-Verlag, 1989 9. S. Mister, C. Adams, Practical S-box design, Workshop on Selected Areas in Cryptography, SAC 1996, Workshop Record, 1996 10. K. Nyberg, Perfect nonlinear S-boxes, Advances in Cryptology – EUROCRYPT 1991, LNCS 547, Springer-Verlag, 1991 11. K. Nyberg, Differentially uniform mappings for cryptography, Advances in Cryptology EUROCRYPT 1993, Springer-Verlag, 1993 12. O. S. Rothaus, On bent functions, Journal of Combinatorial Theory 13. C. Shannon, Communication theory of secrecy systems, Bell Systems Technical Journal, vol. 28, 1949 14. M. Sivabalan, S. Tavares, L. Peppard, On the design of SP networks from an information theoretic point of view, Advances in Cryptology – CRYPTO 1992, LNCS 740, SpringerVerlag, 1993 15. A. Webster, S. Tavares, On the Design of S-boxes, Advances in Cryptology – CRYPT0 1985, LNCS 218, Springer-Verlag, 1985 16. R. Wicik, Wykorzystanie szyfrów blokowych opartych o sieci podstawieniowoprzestawieniowe o du ych S-boksach w specjalnych sieciach telekomunikacyjnych, Doctoral dissertation, Military University of Technology, Warsaw, 1999 8

© Copyright 2018