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

3.3 Modern Private-Key Cryptographic Algorithms

111

a0,0

a0,1

a0,2

a0,3

a0,4

a0,5

S-box

b0,0

b0,1

b0,2

b0,3

b0,4

b0,5

a1,0

a1,1

a1,2

ai,j

a1,4

a1,5

b1,0

b1,1

b1,2

bi,j

b1,4

b1,5

a2,0

a2,1

a2,2

a2,3

a2,4

a2,5

b2,0

b2,1

b2,2

b2,3

b2,4

b2,5

a3,0

a3,1

a3,2

a3,3

a3,4

a3,5

b3,0

b3,1

b3,2

b3,3

b3,4

b3,5

Fig. 3.19. ByteSub transformation

{ShiftRow { the bytes of the input are arranged into four rows and every row is rotated a xed number of positions.

{MixColumn { the bytes of the input are arranged into four rows and every

column is transformed using polynomial multiplication over GF (28). { AddRoundKey { the input block is XOR-ed with the round key.

The ByteSub transformation (Figure 3.19) takes and input A = (a0;0; : : : ;

a0;Nb 1; : : : ; a3;0; : : : ; a3;Nb 1) and outputs B = (b0;0; : : : ; b0;Nb 1; : : : ; b3;0; : : : ; b3;Nb 1) such that bi;j = S(ai;j) for i = 0; 1;2; 3 and j = 0; : : : ; Nb 1. S(x) is the S-box (permutation) described as follows:

2	10001111	3	2	1	3
	11000111			1
	11100011			0
S(x) =	11110001	x 1 +		0	;
	11111000			0
	01111100			1
6	00111110	7	6	1	7
	00011111			0
4		5	4		5

where x 1 2 GF (28) is the multiplicative inverse of x if x 6= 0 or zero if x = 0 (Figure 3.20). Note that the aÆne transformation L(x) = S(x 1). The S-box outputs an element from GF (28). Note that for decryption S 1(x) must be used. In this case, the inverse aÆne transformation is used followed by nding the multiplicative inverse in GF (28).

The ShiftRow transformation (Figure 3.21) takes the input

112 3 PRIVATE-KEY CRYPTOSYSTEMS

a0 = (a0;0; : : : ; a0;Nb 1); a1 = (a1;0; : : : ; a1;Nb 1);

a2 = (a2;0; : : : ; a2;Nb 1); and a3 = (a3;0; : : : ; a3;Nb 1)

and returns a0 >>> C0; a1 >>> C1; a2 >>> C2; a3 >>> C3 where a >>> C is the rotation of the sequence a of bytes to the right by C bytes. The values of Ci are given below:

2	if Nb = 4;6	3	if Nb = 4; 6
C0 = 0; C1 = 1; C2 = ( 3	otherwise	and C3 = ( 4	otherwise

In decryption mode, ShiftRow rotates the corresponding sequence of bytes the same number of positions but to the left.

The MixColumn transformation (Figure 3.22) takes the input

a0 = (a0;0; : : : ; a0;Nb 1); a1 = (a1;0; : : : ; a1;Nb 1); a2 = (a2;0; : : : ; a2;Nb 1); a3 = (a3;0; : : : ; a3;Nb 1);

and creates Nb polynomials Aj(x) = a3;jx3+a2;jx2+a1;jx+a0;j; j = 0; : : : ; Nb 1,

multiplies Aj(x) by the polynomial		C(x)	= c3x3 + c2x2 + c1x + c0 where
c3 =0x03, c2 =0x01, c1 =0x01,	and c0		=0x02 (all polynomials are	over
GF (28)). MixColumn returns Bj	=	b3;jx3 + b2;jx2 + b1;jx + b0;j such		that

Bj(x) = Aj (x) C(x) where

	S-box
x	x-1	L	y

Inverse S-box

y	-1	z	z -1	x
	L

Fig. 3.20. S-box in Rijndael

3.3 Modern Private-Key Cryptographic Algorithms

113

m	n	o	p . . .		no shift	m	n	o	p . . .
j	k	l	. . .			rotation by C1					j
d	e	f	. . .			rotation by C2				d	e
w	x	y	z	. . .	rotation by C3				w	x	y

Fig. 3.21. ShiftRow transformation

b0 = (b0;0; : : : ; b0;Nb 1); b1 = (b1;0; : : : ; b1;Nb 1); b2 = (b2;0; : : : ; b2;Nb 1); b3 = (b3;0; : : : ; b3;Nb 1):

In the decryption mode, MixColumn multiplies the respective columns by the inverse D(x) = C(x) 1 or D(x) C(x) = 1 2 GF (28).

The key schedule procedure KeyExpansion produces key material W =

(W0; : : : ; WNb(Nr+1) 1) from the primary key K = (K0; : : : ; KNk 1) where Wi; Ki are 32-bit words. It applies two functions:

{SubByte(a; b; c; d) that accepts four bytes and returns (S(a); S(b); S(c); S(d)),

{RotByte(a; b; c; d) = (b; c; d; a) that rotates bytes.

KeyExpansion has two versions: one for Nk 6 and the other for Nk > 6. Therst version (for Nk 6) takes two phases:

{Initialization where Wi = Ki for i = 0; : : : ; NK 1.

{Expansion phase which takes the last computed word and extends it for the next one. The steps are as follows:

a0,0

a0,1

a 0,j

a0,3

a0,4

a0,5

c(x)

b0,0

b0,1

b0,j

b0,3

b0,4

b0,5

a 1,j

b1,j

a1,0

a1,1

a1,3

a1,4

a1,5

b1,0

b1,1

b0,3

b1,4

b1,5

a2,0

a2,1

a 2,j

a2,3

a2,4

a2,5

b2,0

b2,1

b2,j

b2,3

b2,4

b2,5

a3,0

a3,1

a 3,j

a3,3

a3,4

a3,5

b3,0

b3,1

b3,j

b3,3

b3,4

b3,5

Fig. 3.22. MixColumn transformation

114 3 PRIVATE-KEY CRYPTOSYSTEMS

tmp = Wi 1;

if i (mod Nk) = 0; then tmp=SubByte( RotByte(tmp)) Rconbi=Nkc; Wi = Wi Nk tmp;

where the constants Rconi = (RCi;0; 0; 0) and RCi = RCi 1 = xi 1 where x is an element of GF (28).

The second version (for Nk > 6) takes two phases:

{Initialization where Wi = Ki for i = 0; : : : ; NK 1.

{Expansion phase which takes the last computed word and extends it for the next one. The steps are as follows:

tmp = Wi 1;

if i (mod N) = 0; then tmp=SubByte( RotByte(tmp)) Rconbi=Nkc else if i (mod Nk) = 4 then tmp=SubByte(tmp);

Wi = Wi Nk tmp:

Encryption process is illustrated in Figure 3.23. Clearly, decryption employs inverse transformation in the reverse order.

The Rijndael algorithms is the new Advanced Encryption Standard and it is going to be scrutinized in similar way as the DES algorithm was before. It remains to be seen whether the balance between security and eÆciency is right and whether Rijndael survives the test of time. The algorithm is immune against linear and di erential attacks (Section 3.4). The best known attacks reported in [178] are based on the Square attack. For instance 6-round Rijndael is breakable in time proportional to 244 with 232 chosen plaintext. The attack

for seven rounds takes 2120 steps and 2128 2119 chosen plaintext. The attack on the 256-bit Rijndael with eight rounds consumes 2204 steps and 2128 2119

chosen plaintext.

The Rijadael algorithm has a nice algebraic structure. The relation between input and output can be expressed as a system of polynomials over GF (28) or a single polynomial over a proper Galois eld. It is also interesting to note that the structure can be equivalently represented as a system of quadratic equations over GF (2). The algebraic representation of Rijndael provides a mathematical model in which attacks can be converted into their equivalent problems of solving a system of equations.

3.3 Modern Private-Key Cryptographic Algorithms

115

Message

AddRoundKey

	ByteSub
	ShiftRow		1st Round
	MixColumn
	AddRoundKey
			Further
			N k-2 Rounds
	ByteSub
			Last Round
	ShiftRow
	AddRoundKey
	CipherText
Fig. 3.23. Rijndael encryption

3.3.5 Serpent

The Serpent cipher was an AES submission from an international team (England, Israel and Norway). The description of the cipher can be found at the AES Web site http://www.nist.gov/aes. A very rst version of the algorithm called Serpent-0 was presented at the Fast Software Encryption Workshop in 1998 [32].

Serpent handles 128-bit messages and cryptograms using a cryptographic key which can be either 128or 192or 256-bit long. It implements a Shannon S-P network. The basic cryptographic operations are:

{S-boxes { there are 8 di erent S-boxes S0; : : : ; S7. Each S-box is a permutation mapping 4-bit input into 4-bit output. The ith round applies 32 copies of the same S-box Si mod 8; i = 0; : : : ; 7.

{Linear transformation L { it takes four 32-bit words X0; X1; X2; X3 and performs the following operations:

116 3 PRIVATE-KEY CRYPTOSYSTEMS

X0 = X0 13;

X2 = X2 3;

X1 = X1 X0 X2;

X3 = X3 X2 (X0 3);

X1 = X1 1;

X3 = X3 7;

X0 = X0 X1 X3;

X2 = X2 X3 (X1 7);

X0 = X0 5;

X2 = X2 22

and returns X0; X1; X2; X3, where X s stands for rotation of X by s bits to the left and X s means left shift of X by s bits.

The S-boxes used in Serpent have the following properties:

1.Probabilities of di erential characteristics are smaller than 1=4 and a one-bit di erence never translates into a one-bit output di erence (for de nitions of di erential characteristics see Section 3.4).

2.Probabilities of linear characteristics are within the range 0:5 1=4 and the correlation between pairs of input/output bits expressed by a probability in

the range 0:5 1=8,	(for de nitions of linear characteristics see Section 3.5).
3. The nonlinearity of	the output bits is maximum (see Section 3.5).

The designers of Serpent intended to convince potential users that the S-boxes used in the algorithm had no hidden trapdoors. The S-boxes can be obtained using a simple procedure that rst takes a subset of permutations from the DES S-boxes and next modi es them so the resulting permutations (S-boxes) have \good" di erential and linear properties. The procedure uses an array sbox[][] with 32 rows and 16 columns. The rows of the array are initialized by 32 permutations from the DES S-boxes. An array serpent[] with 16 four-bit entries is used to point out the entry of sbox[][] which is chosen for modi cation. The array serpent[] is initialized to the least signi cant four bits of each of 16 ASCII characters in the string sboxesforserpent. The following procedure is used to generate the necessary eight S-boxes:

3.3 Modern Private-Key Cryptographic Algorithms

117

index=0 repeat

currentsbox=index mod 32 for i=0 to 15 do

j=sbox[(currentsbox+1)mod32][serpent[i]] swapentries(sbox[currentsbox][i],sbox[currentsbox][j])

if sbox[currentsbox][] has the desired properties, save it index=index+1

until eight S-boxes have been saved

The modi cation of S-boxes is based on swapping entries of the row indexed by the currentsbox index. S-boxes obtained according to the prescription described above are shown in Table 3.12.

The encryption begins with an initial permutation (IP), runs through 32 rounds and concludes with the nal permutation (FP) which is the inverse of IP (Figure 3.24). The input to the ith round is rst XORed with the round key Ki and next put into inputs of 32 copies of the same S-box (one of the eight generated from DES S-boxes); i = 0; : : : ; 30. The outputs are transformed by the linear transformation L. The last (32nd) round replaces L by XOR of the key K32.

There are eight S-boxes only so the execution of 32 rounds requires that the same S-box is used in four rounds. The S-box Si is used in rounds i;8 + i; 16 + i; 24 + i for i = 0; : : : ; 7. The decryption requires that the inverse operations (including inverse S-boxes) have to be used in reverse order.

Key scheduling is used to produce 33 128-bit subkeys used. As we have already mentioned, the main key is expanded to the 256-bit primary key K. Denote the key K as a sequence of eight 32-bit words K = (w 8; : : : ; w 1). The necessary key material is generated word by word according to the following equation:

wi = (wi 8 wi 5 wi 1 i) 11

where is the part of decimal extension of the golden ratio ( =0x9e3779b9); i = 0; : : : ; 131. The words of round keys are computed using consecutive four words pieces (w4i; w4i+1; w4i+2; w4i+3) for i = 1; 2; : : : ; 32 as

118 3 PRIVATE-KEY CRYPTOSYSTEMS

PlainText

IP

			Round Key Ki
	Si mod 8	Si mod 8	Si mod 8	Repeat
				31
				Times
			L
			K 31
	S7	S7	S7	Last
				Round

K 32

FP

CipherText

Fig. 3.24. Serpent encryption

K0 = (k0; k1; k2; k3) = S3(w0; w1; w2; w3);

K1 = (k4; k5; k6; k7) = S2(w4; w5; w6; w7);

K2 = (k8; k9; k10; k11) = S1(w8; w9; w10; w11);

K3 = (k12; k13; k14; k15) = S0(w12; w13; w14; w15);

K4 =. (k16; k17; k18; k19) = S7(w16; w17; w18; w19);

.

.

K31 = (k124; k125; k126; k127) = S4(w124; w125; w126; w127);

K32 = (k128; k129; k130; k131) = S3(w128; w129; w130; w131):

The Serpent cipher is one of the ve nalists chosen in the second round of the AES call. The 32-round Serpent is a strong cipher, and standard attacks based on linear and di erential cryptanalysis are not better than the exhaustive attack. Even signi cantly reduced versions of Serpent preserve their

3.3 Modern Private-Key Cryptographic Algorithms

119

cryptographic strength well. Following the results in [286], 6-round Serpent can be attacked using di erential cryptanalysis with 283 chosen plaintexts and 290 trail encryptions. The 256-bit Serpent with nine rounds can be broken after 2252 trail encryptions and with 2110 chosen plaintexts using the ampli ed boomerang technique.

3.3.6 Other Ciphers

The LOKI algorithm was designed in Australia. The rst version called LOKI89 was published at AUSCRYPT'90 Conference [69]. The revised version LOKI91 can be found in the proceedings of ASIACRYPT91 Conference [68]. Interestingly enough, LOKI applies many copies of a single S-box which is based on cubing in GF(28).

The GOST algorithm is a Russian cipher [385] with the Feistel structure. It applies eight S-boxes which are permutations of 4-bit integers. The details of the S-boxes, however, are left unspeci ed suggesting that the algorithm was designed to encourage users to apply for S-boxes to the central authority. Note that the central authority could choose weak S-boxes on purpose to be able to read encrypted data. This looks like the Russian version of key escrowing.

The 2nd-round nalists of the AES call were RC6, Rijndael, Serpent, MARS, and Two sh. We have described the rst three. Now let us brie y discuss the remaining two.

The MARS algorithm is an IBM cipher (see http://www.nist.gov/aes). The designers di erentiated between internal rounds and external ones (also called \wrapper layers"). The internal rounds are seen as \the core" of the algorithm (provide mostly confusion) while external ones are using noncryptographic mixing (di usion).

The Two sh algorithm was an AES candidate designed by a team of researchers from Counterpane Systems, Hi/fn, Inc. and University of California, Berkeley. It is a Feistel cipher with 16 uniform rounds. The round function F : 64 ! 64 consists of two copies of the function g : 32 ! 32 . The function g is built using four 8-bit S-boxes. Each S-box is a permutation controlled by a cryptographic key. The outputs from the four S-boxes are mixed using maximum distance separable code. The outputs from the two copies of g are combined using modular addition.

120 3 PRIVATE-KEY CRYPTOSYSTEMS

3.4 Di erential Cryptanalysis

Private-key cryptographic algorithms can be subject to the following general attacks:

{Ciphertext-only attack { the cryptanalyst knows cryptograms only. They know Ek(m1), Ek(m2), : : :, Ek(m`) and want to nd out either the key k or one or more messages mi for some i = 1; : : : :`. This attack takes place if the cryptanalyst is able to eavesdrop the communication channel.

{Known-plaintext attack { the adversary has access to a collection of pairs

f(mi; Ek(mi)) j i = 1; : : : ; `g and wants to determine the key k or to decrypt a cryptogram Ek(m`+1) not included in the collection. The adversary in this attack can not only eavesdrop the communication channel but also can, in some way, access to a part of the plaintext. This happens, if for example, messages have a predictable structure so the attacker knows or can guess that the header of the plaintext starts from \How are you?" or \Dear Sir/Madam" and ends with \Sincerely yours."

{Chosen-plaintext attack { this is a known-plaintext attack for which the cryptanalyst may choose messages and read the corresponding cryptograms. This scenario may happen if the encryption equipment is left without supervision for some time, and the attacker can play with it assuming they cannot access the key.

{Chosen-ciphertext attack { the enemy can select their own cryptograms and observe the corresponding messages for them. The aim of the enemy is tond out the secret key or encrypt a new message into the valid cryptogram. This attack may happen if the decryption equipment is left unsupervised and the attacker can try di erent cryptograms (assuming that the equipment is tamper proof, the attacker cannot access the secret key).

Biham and Shamir invented the di erential cryptanalysis in 1990 [33, 35]. This is a chosen-plaintext attack which is not only applicable for encryption algorithms but also can be used for other cryptographic algorithms including hashing.