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

	3.6 S-box Theory	161
S3.	Any nonzero linear combination of f1, f2, f3 satis es the propagation crite-
	rion except for a single vector.
S4.	S(x) is regular as it is a permutation.
S5.	S(x) has a good XOR pro le, i.e. S(x) S(x ) runs through some 22
	vectors in 3 each twice while x runs through 3 once and does not take

on other 22 vectors. More precisely, let = (001). Then S(x) S(x ) runs through vectors (010), (011), (100), (101) twice while x runs through3 once. If = (111), then S(x) S(x ) runs through vectors (001), (011), (101), (111) twice while x runs through 3 once.

Permutations de ned in GF (2n) also need to be chosen as some of them exhibit good cryptographic properties. It turns out [405] that exponentiation can produce cryptographically strong S-boxes. Being more speci c, the S-boxes S : n ! n de ned as S(x) = x3, x 2 GF (2n) where n is odd, are permutations with the following properties [405, 377, 378, 30]:

S10 Any nonzero linear combination of the coordinate functions, is balanced. This results from the fact that cubing is a permutation. Any nonzero linear combination f of the coordinate functions has a high nonlinearity and Nf

2n 1 212 (n 1).

S30 Any nonzero linear combination of the coordinate functions satis es the propagation criterion except for a single nonzero vector.

S50 S(x) has a good XOR pro le, i.e. S(x) S(x ) runs through a subset of 2n 1 vectors in n twice while x runs through n once. The remaining 2n 1 vectors do not occur.

The design of S-boxes is not free from some pitfalls. A special care needs to be exercised when a cryptographically strong S-box is modi ed by adding or reducing output bits. Consider an S-box S(x) = (f1(x); : : : ; fk(x)) which is regular and has a good XOR pro le where fi : n ! GF (2) for i = 1; : : : ; k. It turns out [462] that S(x) = (f1(x); : : : ; ft(x)) where t < k is regular but does not have a good XOR pro le.

On the other hand, for any regular S-box S(x) = (f1(x); : : : ; fk(x)) with a

good XOR pro le, there is a collection of functions fk+1(x); : : : ; fs(x) such that the extended S-box S0(x) = (f1(x); : : : ; fk(x), fk+1(x); : : : ; fs(x)) is a regular mapping from n to s but does not have a good XOR pro le.

162 3 PRIVATE-KEY CRYPTOSYSTEMS

3.7 Problems and Exercises

1.Write C programs for the implementation of the following ciphers:

{the Caesar cipher,

{the aÆne cipher,

{the monoalphabetic substitution cipher,

{the transposition cipher,

{the homophonic substitution cipher,

{the Vigenere cipher,

{the Beauford cipher.

Your programs should include routines for both encryption and decryption.

2.The Caesar cipher is relatively easy to break. Write a C program, which is rst fed by a sample text to collect statistical properties of the language. Then use the statistics to cryptanalyze a given ciphertext by comparing it with the statistics computed for the ciphertext.

3.Design and implement a C program for cryptanalysis of the aÆne cipher. Your program must not use the enumeration of all possible keys but should use the frequencies of characters to make \optimal" guesses about the key.

4.Write a computer program which calculates the index of coincidence. Run the program for di erent texts. Try an English text, a text of a high level programming language and a text of random characters generated by a pseudorandom generator. Compare and discuss the results.

5. Let	the message space M = Z264 and m = (m1; m2; m3; m4) where mi 2 Z26 for
i =	1; 2; 3; 4. Design a product cipher c = Ek(m) such that m; c; k 2 Z264 based on

the network of P-boxes and S-boxes. The P-box P : Z4 ! Z4 where P(x1; x2; x3; x4) =

26 26

(x1; x3; x2; x4) and the S-box S : Z262 ! Z262 is de ned as S(x; y) = (x + k1y mod 26; k2x + y mod 26)

where k = (k1; k2) and gcd (ki; 26) = 1 for i = 1; 2. Derive the encryption and decryption formulas for a cipher with n iterations. Analyze the cipher and try to break it under the known-plaintext attack. How the security depends on the number of iterations.

6.Consider the above product cipher with the S-box built using a Feistel permutation de ned as

S(x; y) = (x; y + k1xk2 mod 26):

Derive encryption and decryption formulas for the cipher with n iterations. Analyze the cipher for the known-plaintext attack and discuss its strength in relation to the number of iterations.

7.Design a DES type cryptosystem which encrypts 16-bit messages into 16-bit cryptograms and applies a functions f : 8e ! 8 of the form:

f (ki; Ri 1) = (ki Ri 1)

for e = 7 in GF(28). What would happen if the exponent was e = 2; 3; 4; 5; 6? Implement the cipher. Assume a reasonable key scheduling.

			3.7 Problems and Exercises	163
8.	The DES algorithm satis es the complementation property which can be expressed as
	E	k	(m) = E (m). Give a justi cation of why the property holds.
			k
9.	Key schedule is an essential component of any encryption algorithm. Assume that your
	key scheduling algorithm is to generate subkeys ki 2 8 from the key k 2 16			for
	i = 1; : : : ; 16. Consider the following key schedules:
	{ The key k is placed into 16-bit register. k1 is the 8-bit sequence of less signi cant
		bits. Next the contents of the register is rotated positions to the left. The key k2 is
		again the 8-bit sequence of less signi cant bits. The process continues for the requested
		number of times.
	{ The key k is an argument of a one-way function f : 512 ! 512. Subkeys are generated
		by applying one way function so k1 = f(k) j8 where f(k) j8 stands for 8-bit string of
		less signi cant bits, k2 = f(f(k)) j8 and so forth.
	Assume that you happen to know the last subkey k16 (for instance, extracted using the
	di erential cryptanalysis). What you can tell about the other subkeys and the key k for
	the two key scheduling algorithms?
10.	In the ECB mode, encryption is applied independently for each message block mi			for

i = 1; 2; : : :. The sequence of cryptograms ci = Ek(mi) is subject to many attacks which exploit the lack of links between consecutive cryptograms. Consider the following chaining scheme in which ci = Ek(mi) ci 1 for i = 1; 2; : : :. Is this scheme better than the ECB mode? Justify your answer.

11.Assume that encryption applies the CBC mode and during transmission a single cryp-

togram ci = Ek(mi ci 1) has been corrupted due to a noise in the communication channel. Which messages cannot be reconstructed at the receiver side? Support your answer by a detailed analysis.

12.Suppose the sender uses the CFB mode to protect the transmitted messages against tampering with the sequence of cryptograms. Let the sender transmit a sequence of cryptograms c1; c2; c3; c4; c5; c6. An attacker has changed the order of cryptograms so the receiver gets c1; c2; c4; c3; c5; c6. Which messages will be correctly recovered by the receiver?

13.Consider GF (23) with addition and multiplication given in Table 2.2. Let an S-box be

de ned by s = f(s) = s3 in GF (23) where s 2 GF(23). Construct an XOR pro le of the S-box.

14.An S-box is de ned by Table 3.17. The XOR pro le of the S-box is given below:

Æ n			0	1	2	3	4	5	6	7
0			8	-	-	-	-	-	-	-
1			-	2	-	2	-	2	-	2
2			-	-	2	2	2	2	-	-
3			-	2	2	-	2	-	-	2
4			-	-	-	-	2	2	2	2
5			-	2	-	2	2	-	2	-
6			-	-	2	2	-	-	2	2
7			-	2	2	-	-	2	2	-

164 3 PRIVATE-KEY CRYPTOSYSTEMS

The key is XOR-ed with the input of the S-box. Given two observations s1 k = 3 and s2 k = 7 and their corresponding output di erence = s1 s2 = 5, what can you tell about the key k?

15.Given a DES-type encryption algorithm which encrypts 6-bit messages into 6-bit cryptograms using four rounds. Each round applies the S-box described in Table 3.17. A subkey ki (i = 1; 2; 3; 4) is XORed to the input of the S-box where the subkey ki is used in the ith iteration. Assume some values of the subkeys and use the di erential cryptanalysis to break the algorithm.

16.Take the encryption algorithm from the previous exercise. Find the best linear approximation of the S-box outputs and derive the necessary linear characteristics. Apply the linear cryptanalysis to recover the cryptographic key.

17.Write the polynomial of a function over 3 whose truth table is (10101001).

18.Consider a Boolean function f : 3 ! such that f(x1; x2; x3) = x1x2 x1x3 x2. Find out its truth table. Is the function balanced?

19.Let f(x1; x2; x3; x4 ) = x1x2x3 x3x4 x2. Find the truth table, sequence and matrix of f, W (f), Nf and ( ) for = (1111).

20.Given two Boolean functions f(x1; x2; x3) = x1x2x3 x2 and g(x1; x2) = x1 x2. What is the distance d(f; g)?

21.Determine all aÆne functions from the set A3.

22.Find the nonlinearity of the function f(x1; x2; x3) = x1 x2x3. The function f can be extended for arbitrary number of variables. Let f(x1; : : : ; xn) = x1 x2x3 where n > 3, what is the nonlinearity of the extended function?

23.Assume that f, g and h be functions on n with W (f) = 0, W (g) = 1 and W (h) = 2n. Find the nonlinearities Nf , Ng and Nh.

24.Let f(x1; x2; x3; x4; x5) = x1x3 x2x5 x2x4x5. Determine the set of vectors < for which the function does not satisfy the SAC.

25.Prove that any function of the form f(x1; : : : ; xn) = x1x2 x3x4 xn 1xn is bent when n is even and bigger than 2.

26.	Calculate the nonlinearity of f(x1; : : : ; xn) = x1x2 x2x3 xn1 xn xnx1 where
	n 3 and is odd.
27.	Take two functions f (x1; x2; x3; x4) = x1x2 x2x3 x3x4 x4x1 and g(x1; x2; x3; x4) =
	x1 x2 x3 x4. Compute their autocorrelation functions f ( ) and g( ). Discuss the
	results.
28.	Let f be a function over n. Consider the following statements:
	{ If Nf = 0, then f = 0.

{ If Nf = 2, then W (f) = 2.

{ d(f; f g) = 2n 1 for some linear function g. { Nf g = Nf for any linear function g.

3.7 Problems and Exercises

165

									Column
	Row	0	1	2	3	4		5	6		7	8	9			101112131415Box
	0	14	413		1	21511					8	310			612		5 9		0 7
	1	015 7			414			213			110 6				1211 9 5				3 8		S1
	2	4 114			813			6			2111512				9 7		310		5 0
	3	1512 8			2 4			9 1			7 511				31410			0	613
	0	15	1	814 611					3		4	9 7			21312			0	510
	1	313		4 715				2	81412 0						110 6 911 5						S2
	2	014		71110				413 1 5 8							12 6		9 3 215
	3	13 810 1 315							4 211 6						712		0 514 9
	0	10	0	914 6			315				5	113			12	711		4 2		8
	1	13	7	0 9 3 4 610								2 8				514121115				1	S3
	2	13	6	4 9 815					3 011 1						212		51014			7
	3	11013 0 6					9 8 7 415								14 311			5	212
	0	71314			3 0		6		910			1 2			8	51112			415
	1	13 811			5 615				0 3			4 7			212 11014 9						S4
	2	10 6 9			01211				71315 1						314		5 2		8 4
	3	315 0			610		113 8 9 4								51112			7	214
	0	212		4	1 71011						6	8 5			31513			014		9
	1	1411		212 4 713							1	5 0			1510 3 9 8					6	S5
	2	4 2		1111013					7		815 9				12 5		6 3 014
	3	11 812 7 114							213 615						0 910			4 5 3
	0	12	11015 9				2		6		8	013			3	414		7 511
	1	1015 4 2 712							9		5	6 1			1314 011				3 8		S6
	2	91415 5 2					812				3	7 0			410		11311 6
	3	4 3 212 9					515101114								1 7		6 0		813
	0	411		21415				0	813			312			9	7	510		6	1
	1	13 011 7 4						9	11014 3						512		215		8	6	S7
	2	1 4111312						3	7141015						6 8		0 5		9	2
	3	61113 8 1						410 7 9 5							01514			2	312
	0	13	2	8	4 61511						110 9				314		5 012			7
	1	11513			810			3 7			412 5				611		014		9	2	S8
	2	711 4			1 91214						2 0 6				101315			3	5	8
	3	2 114			7 410						8131512						3 5		611
															9 0

Table 3.8. DES S-boxes

166 3 PRIVATE-KEY CRYPTOSYSTEMS

57 49 41 33 25 17			9
1	58	50 42 34 26	18
10	2 59 51 43 35		27
19 11		3 60 52 44	36
63 55 47 39 31 23			15
7	62	54 46 38 30	22
14	6 61 53 45 37		29
21 13		5 28 20 12	4

Table 3.9. Key permutation PC1

Iteration s Iteration s

1	1	9	1
2	1	10	2
3	2	11	2
4	2	12	2
5	2	13	2
6	2	14	2
7	2	15	2
8	2	16	1

Table 3.10. Key schedule of left shifts LSs

	14	17 11 24		1	5
	3	28	15 6	21	10
	23 19		12 4	26 8
	16	7	27 20	13 2
	41	52 31 37		47	55
	30	40 51 45		33	48
	44	49 39 56		34	53
	46	42 50 36		29	32

Table 3.11. Key permutation PC2

3.7 Problems and Exercises

167

S0	3	8	15	1	10	6	5	11 14		13	4	2	7	0	9	12
S1	15 12		2	7	9	0	5	10	1	11	14	8	6 13		3	4
S2	8	6	7	9	3	12 10		15 13		1	14	4	0 11		5	2
S3	0 15		11	8	12	9	6	3 13		1	2	4	10	7	5	14
S4	1 15		8	3	12	0 11		6	2	5	4 10		9 14		7	13
S5	15	5	2 11		4	10	9	12	0	3	14	8	13	6	7	1
S6	7	2	12	5	8	4	6	11 14		9	1 15		13	3	10	0
S7	1 13		15	0	14	8	2	11	7	4	12 10		9	3	5	6

Table 3.12. Serpent S-boxes

168 3 PRIVATE-KEY CRYPTOSYSTEMS

Output XOR -

Æ0x 1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex Fx

0x 64		0	0	0	0	0	0	0	0			0	0	0	0	0	0	0
1x	0	0	0	6	0	2	4	4	0 10				12	4	10	6	2	4
2x	0	0	0	8	0	4	4	4	0			6	8	6	12	6	4	2
3x 14		4	2	2 10		6	4	2	6			4	4	0	2	2	2	0
4x	0	0	0	6	0	10	10	6	0		4		6	4	2	8 6		2
5x	4	8	6	2	2	4	4	2	0			4	4	0	12	2	4	6
6x	0	4	2	4	8	2	6	2	8			4	4	2	4	2	0	12
7x	2	4 10		4	0	4	8	4	2			4	8	2	2	2	4	4
8x	0	0	0	12	0	8	8	4	0			6	2	8	8	2	2	4
9x 10		2	4	0	2	4	6	0	2			2	8	0	10	0	2	12
Ax	0	8	6	2	2	8	6	0	6			4	6	0	4	0	2	10
Bx	2	4	0	10	2	2	4	0	2			6	2	6	6	4	2	12
Cx	0	0	0	8	0	6	6	0	0			6	6	4	6	6	14	2
Dx	6	6	4	8	4	8	2	6	0			6	4	6	0	2	0	2
Ex	0	4	8	8	6	6	4	0	6			6	4	0	0	4	0	8
Fx	2	0	2	4	4	6	4	2	4			8	2	2	2	6	8	8
10x	0	0	0	0	0	0	2	14	0			6	6	12	4	6	8	6
11x	6	8	2	4	6	4	8	6	4			0	6	6	0	4	0	0
12x	0	8	4	2	6	6	4	6	6			4	2	6	6	0	4	0
13x	2	4	4	6	2	0	4	6	2			0	6	8	4	6	4	6
14x	0	8	8	0 10		0	4	2	8			2	2	4	4	8	4	0
15x	0	4	6	4	2	2	4	10	6			2	0	10	0	4	6	4
16x	0	8 10		8	0	2	2	6	10			2	0	2	0	6	2	6
17x	4	4	6	0 10		6	0	2	4			4	4	6	6	6	2	0
18x	0	6	6	0	8	4	2	2	2			4	6	8	6	6	2	2
19x	2	6	2	4	0	8	4	6	10			4	0	4	2	8	4	0
1Ax	0	6	4	0	4	6	6	6	6			2	2	0	4	4	6	8
1Bx	4	4	2	4 10		6	6	4	6			2	2	4	2	2	4	2
1Cx	0	10		6	6	0	0	12	6			4	0	0	2	4	4	0
			10
1Dx	4	2	4	0	8	0	0	2	10			0	2	6	6	6	14	0
1Ex	0	2	6	0 14		2	0	0	6			4	10	8	2	2	6	2
1Fx	2	4	10	6	2	2	2	8	6			8	0	0	0	4	6	4
20x	0	0	0	10	0	12	8	2	0			6	4	4	4	2 0		12
21x	0	4	2	4	4	8	10	0	4			4	10	0	4	0	2	8
22x 10		4	6	2	2	8	2	2	2			2	6	0	4	0	4	10
23x	0	4	4	8	0	2	6	0	6			6	2	10	2	4	0	10
24x 12		0	0	2	2	2	2	0	14			14	2	0	2	6	2	4
25x	6	4	4	12	4	4	4	10	2			2	2	0	4	2	2	2
26x	0	0	4	10 10		10	2	4	0			4	6	4	4	4 2		0
27x 10		4	2	0	2	4	2	0	4			8	0	4	8	8	4	4
28x 12		2	2	8	2	6	12	0	0			2	6	0	4	0	6	2
29x	4	2	2	10	0	2	4	0	0		14		10	2	4	6	0	4
2Ax	4	2	4	6	0	2	8	2	2		14		2	6	2	6	2	2
2Bx 12		2	2	2	4	6	6	2	0			2	6	2	6	0	8	4
2Cx	4	2	2	4	0	2	10	4	2			2	4	8	8	4	2	6
2Dx	6	2	6	2	8	4	4	4	2			4	6	0	8	2	0	6
2Ex	6	6	2	2	0	2	4	6	4			0	6	2	12	2	6	4
2Fx	2	2	2	2	2	6	8	8	2			4	4	6	8	2	4	2
30x	0	4	6	0 12		6	2	2	8			2	4	4	6	2	2	4
31x	4	8	2	10	2	2	2	2	6			0	0	2	2	4	10	8
32x	4	2	6	4	4	2	2	4	6			6	4	8	2	2	8	0
33x	4	4	6	2 10		8	4	2	4			0	2	2	4	6	2	4
34x	0	8	16	6	2	0	0	12	6			0	0	0	0	8	0	6
35x	2	2	4	0	8	0	0	0	14			4	6	8	0	2	14	0
36x	2	6	2	2	8	0	2	2	4			2	6	8	6	4	10	0

3.7 Problems and Exercises

169

No. of Chosen Analysed Complexity rounds plaintexts plaintexts of analysis

8	214	4	29
9	224	2	232
10	224	214	215
11	231	2	232
12	231	221	221
13	239	2	232
14	239	229	229
15	247	27	237
16	247	236	237

Table 3.14. Cryptanalysis of DES

s2s1	f	0	s1	s2	s1	s2	f s1	f s2	f s1	s2
00	0	0	0	0		0	0	0	0
01	0	0	1	0		1	1	0	1
10	0	0	0	1		1	0	1	1
11	1	0	1	1		0	0	0	1

Table 3.15. The truth table of f (s) = s1s2 and linear functions from L2

170 3 PRIVATE-KEY CRYPTOSYSTEMS

Combinations of Outputs

1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex Fx

0x 32		32	32	32	32	32	32 32	32	32	32	32	32	32	32
1x 32		32	32	32	32	32	32 32	32	32	32	32	32	32	32
2x 36		30	34	30	34	28	32 36	32	34	30	34	30	32	28
3x 32		34	26	34	34	28	36 32	32	34	26	34	34	28	36
4x 34		30	32	32	34	30	32 32	34	34	36	28	30	30	32
5x 30		30	36	32	22	38	36 32	30	42	32	28	34	30	28
6x 34		36	38	34	36	30	32 32	34	32	34	38	40	30	32
7x 34		32	34	30	40	38	32 28	38	32	26	30	32	26	28
8x 32		34	38	32	32	30	26 30	34	36	20	34	38	28	36
9x	36	26	34	32	36	38	38 26	34	32	36	30	38	40	36
Ax	28	32	32	34	38	30	30 30	30	34	30	28	36	36	32
Bx	36	36	36	38	34	30	30 30	30	30	34	32	24	28	32
Cx	30	32	34	32	30	28	22 34	28	34	40	34	28	38	36
Dx	38	32	34	32	30	36	22 30	32	30	36	30	40	26	32
Ex	30	30	32	30	36	32	34 30	32	36	34	28	38	30	28
Fx	34	34	24	26	28	32	30 30	28	24	34	24	38	30	32
10x	34	30	32	32	30	26	24 32	30	30	28	32	34	42	12
11x	30	34	32	28	30	34	36 28	30	30	32	40	38	30	28
12x	34	32	34	30	36	34	40 28	26	28	26	34	28	38	32
13x	26	32	34	30	36	34	32 36	26	36	34	26	36	30	32
14x	28	36	32	32	32	32	32 36	36	28	28	32	28	36	32
15x	36	32	28	28	36	24	24 32	32	28	36	40	36	32	36
16x	32	38	38	34	30	36	32 36	32	38	34	34	34	32	32
17x	28	38	34	26	34	36	28 28	36	38	30	34	30	32	28
18x	26	32	30	28	42	36	30 30	32	34	32	30	28	34	36
19x	34	36	26	32	30	36	30 38	40	38	36	42	32	34	28
1Ax 34		34	24	30	36	32	34 30	32	36	34	32	30	30	32
1Bx 30		26	36	38	32	32	30 26	24	32	34	36	38	34	32
1Cx 32		30	34	36	32	26	34 30	38	28	32	34	30	32	32
1Dx 28		34	26	40	32	34	30 22	34	40	40	30	30	32	28
1Ex 36		40	32	34	34	34	30 34	30	34	26	28	28	28	32
1Fx 28		40	24	34	26	26	30 30	34	30	30	24	32	32	28
20x	32	32	32	32	32	32	32 32	32	32	32	32	32	32	32
21x	32	32	32	32	32	32	32 32	32	32	32	32	32	32	32
22x	28	30	34	30	34	28	40 28	32	26	38	34	30	16	20
23x	32	34	34	26	34	36	28 32	32	34	34	34	26	28	36
24x	30	38	36	32	38	30	36 36	26	30	36	32	46	34	32
25x	26	30	32	32	26	30	32 36	38	30	40	32	34	26	36
26x	30	28	34	34	32	30	36 28	34	36	34	26	32	34	32
27x	22	32	30	38	36	38	28 32	38	20	34	34	32	38	28
28x	36	30	30	32	36	26	34 34	26	36	32	38	30	28	32
29x	32	30	26	32	32	26	30 30	34	40	32	34	38	32	32
2Ax 32		36	40	26	26	26	38 26	30	34	34	40	28	36	28
2Bx 40		32	36	38	30	26	38 34	38	30	38	28	32	36	36
2Cx 30		28	38	32	38	32	26 34	36	30	36	34	28	26	32
2Dx 30		28	30	32	30	24	34 30	32	26	24	30	32	30	36
2Ex 38		34	28	38	36	36	30 22	24	32	30	36	30	34	32
2Fx 26		38	36	26	36	28	34 30	28	28	38	32	30	34	36
30x	34	30	32	28	26	30	28 36	34	34	32	32	34	34	36
31x	30	34	32	32	34	30	32 32	34	34	36	32	30	30	28
32x	26	32	34	34	24	30	28 32	22	32	30	34	28	30	32
33x	26	32	42	34	32	30	28 32	38	32	22	34	36	30	32
34x	32	44	28	36	32	28	40 36	32	36	32	36	36	32	32
35x	24	32	32	40	28	36	32 32	28	28	32	36	36	28	36
36x	36	30	26	30	30	40	32 36	28	30	30	38	34	28	32