First Aid for Homework 6 Since the Differential Cryptanalysis presentation was garbled, I'd like to provide these additional notes both on DES and on doing the HW. First, as I promised, here are two Differential Cryptanalysis references. The first is a downloadable paper (at the indicated site), the second is a book. You should be able to do the HW without consulting these but you might find them useful. http://www.cs.technion.ac.il/~biham/publications.html Eli Biham, Adi Shamir, Differential cryptanalysis of DES-like cryptosystems, Technical report CS90-16, Weizmann Institute of Science CRYPTO'90 & Journal of Cryptology, Vol. 4, No. 1, pp. 3-72, 1991. Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN: 0-387-97930-1, 3-540-97930-1. The point of differential cryptanalysis is to take advantage of the non-uniform distribution of xor differnces in input and output to rounds of an iterative cipher to obtain information about round keys (and hence cipher-wide keys). Differential cyptanalysis is targeted at iterative ciphers in which a round key, k[r] is xored (we'll use the symbols + and ^ for xor here, "+" when we wish to emphasize the additive properties of xor in a field of characteristic 2, eg GF(2), and ^ when we wish to emphasize a programming paradigm) with round input bits, input[r]. In such and iterative cipher, (k[r]+input[r]) is fed into a non-linear round trasformation to produce an output output[r]. Differential cryptanalysis studies the relationship between the xor of two inputs to the round denoted by input[r] and input*[r] and the xor of the outputs denoted by output[r] and output*[r]. In other words, it studies the quantities input'[r]= input[r] + input*[r]; and, output'[r]= output[r] + output*[r]. The basic idea (illustrated in slide 30 of the class notes entitled "Differential Profile of an S-Box) is that if we study the set: D[j](x',y')= {u: S[j](u) + S[j](u+x')= y'}, which measures the possible inputs to an S box with a specified input differential x' and output differential, y', we can obtain key information by observing that if input[r] is an input to S box j, D[j](input'[r],output'[r])+input[r]. These per round differntials can be used to build overall cipher differentials (that hold with predictable probability). Now, let's examine the example studied in class (slide 35). Given (a) two inputs to S-Box 1, 0x01 and 0x35 (note there was a misprint on slide 35 which mistakenly said the inputs were 0x01 and 0x034 which was one of the points of confusion), and a corresponding output differential, 0x0d and (b) another two inputs to S-Box 1, 0x21 and 0x15, and a corresponding output differential 0x03, find candidate keys by using differential cryptanalysis. Solution The input differential for (a) is 0x01 + 0x35 = 0x34 (remember + stands for xor here, not integer addition). Consulting the table below we find the line D1(34, 0d): (06,32) (10,24) (16,22) (1c,28) (22,16) (24,10) (28,1c) (32,06) Which means there are 8 pairs of inputs with the specified input differential that produces the output differential, so D[1](0x34,0x0d) ={06, 32, 10,24, 1c,28, 22, 16}. Note all the values are hex. The key must appear in 0x01 + {06, 32, 10,24, 1c,28, 22, 16}= Possible keys = {07, 33, 11, 25, 1d, 29, 23, 17} Applying the sanme analysis to (b) 0x21 + 0x15 = 0x34 yields the following D1(34, 03): (01,35) (02,36) (15,21) (21,15) (35,01) (36,02) So D[1](0x34,0x03) ={01, 35, 02, 36, 15, 21} Possible keys = 0x21 + {01, 35, 02, 36, 15, 21} = {0x20, 0x14, 0x23, 0x17, 0x34, 0x00} The intersection of the two possible key sets is {0x17, 0x23}. These are the possible keys. This example should make problem 1 fairly straightforward. Since we did not get a chance to discuss differentials that occur with probabilities or "chaining together differntial characteristics, we canceled problem 2 (although I'll show you how to do this next Tuesday). Problem 3 is a straightforward calculation Problem 4 calls on you to determine the odds that the outcome of an event with a priori probability. Hint 1: If the probability of successful one of two outcomes is p (and hence the probability oF an unsuccessful outcome is (1-p)), the odds of success are p/(1-p). Hint 2: Each of the three outcomes (1,1,0) is the result of and independant trial so you can easily calculate the joint probability of all three events both if "1" is the correct outcome and if "0" is the correct outcome. Ditto for the 4 event experriment (1,1,1,0). Hint 3: C calls for you to calculate the probability that the xor of 4 equations is correct if each of the equations is correct with probabilities p1, p2, p3, p4 respectively. We did an example of this in class. Hint 4: D calls for you to combine the analysis in (A) and (B) to calculate the probability that 4 independant equations are all correct and, given that they are correct, how that affects the search time for discovering the key of an underlying 40 bit block cipher. --------------------------------------------------------------------- Sbox1 0xd D1(00, 0d): 0 found D1(01, 0d): (0a,0b) (0b,0a) (22,23) (23,22) (3e,3f) (3f,3e) 6 found D1(02, 0d): (08,0a) (0a,08) (29,2b) (2b,29) (35,37) (37,35) 6 found D1(03, 0d): (14,17) (17,14) 2 found D1(04, 0d): (13,17) (17,13) (1b,1f) (1f,1b) (2a,2e) (2e,2a) (3b,3f) (3f,3b) 8 found D1(05, 0d): (01,04) (04,01) 2 found D1(06, 0d): (21,27) (27,21) 2 found D1(07, 0d): (18,1f) (1f,18) 2 found D1(08, 0d): (03,0b) (0b,03) 2 found D1(09, 0d): 0 found D1(0a, 0d): 0 found D1(0b, 0d): (03,08) (08,03) (20,2b) (2b,20) 4 found D1(0c, 0d): (01,0d) (0d,01) (12,1e) (1e,12) (36,3a) (3a,36) 6 found D1(0d, 0d): (21,2c) (2c,21) 2 found D1(0e, 0d): (23,2d) (2d,23) (33,3d) (3d,33) 4 found D1(0f, 0d): (11,1e) (1e,11) (36,39) (37,38) (38,37) (39,36) 6 found D1(10, 0d): (00,10) (06,16) (10,00) (16,06) (22,32) (32,22) 6 found D1(11, 0d): (0d,1c) (1c,0d) (24,35) (35,24) 4 found D1(12, 0d): 0 found D1(13, 0d): (06,15) (15,06) (28,3b) (2e,3d) (3b,28) (3d,2e) 6 found D1(14, 0d): (05,11) (09,1d) (11,05) (1d,09) (20,34) (25,31) (31,25) (34,20) 8 found D1(15, 0d): (0e,1b) (1b,0e) (2f,3a) (3a,2f) 4 found D1(16, 0d): (0e,18) (18,0e) (28,3e) (2f,39) (39,2f) (3e,28) 6 found D1(17, 0d): (05,12) (12,05) (26,31) (27,30) (30,27) (31,26) 6 found D1(18, 0d): (02,1a) (04,1c) (0c,14) (14,0c) (1a,02) (1c,04) 6 found D1(19, 0d): (09,10) (0f,16) (10,09) (16,0f) (25,3c) (2a,33) (33,2a) (3c,25) 8 found D1(1a, 0d): (0f,15) (15,0f) (26,3c) (3c,26) 4 found D1(1b, 0d): (02,19) (19,02) 2 found D1(1c, 0d): (24,38) (2c,30) (30,2c) (38,24) 4 found D1(1d, 0d): (00,1d) (07,1a) (1a,07) (1d,00) (29,34) (34,29) 6 found D1(1e, 0d): (07,19) (19,07) 2 found D1(1f, 0d): (0c,13) (13,0c) (2d,32) (32,2d) 4 found D1(20, 0d): (13,33) (33,13) 2 found D1(21, 0d): 0 found D1(22, 0d): 0 found D1(23, 0d): (1c,3f) (1f,3c) (3c,1f) (3f,1c) 4 found D1(24, 0d): (03,27) (12,36) (1e,3a) (27,03) (36,12) (3a,1e) 6 found D1(25, 0d): (06,23) (23,06) 2 found D1(26, 0d): (0a,2c) (0c,2a) (2a,0c) (2c,0a) 4 found D1(27, 0d): (10,37) (11,36) (14,33) (1e,39) (33,14) (36,11) (37,10) (39,1e) 8 found D1(28, 0d): 0 found D1(29, 0d): (01,28) (02,2b) (08,21) (21,08) (28,01) (2b,02) 6 found D1(2a, 0d): (0b,21) (17,3d) (1d,37) (21,0b) (37,1d) (3d,17) 6 found D1(2b, 0d): 0 found D1(2c, 0d): (07,2b) (0f,23) (23,0f) (2b,07) 4 found D1(2d, 0d): (0a,27) (27,0a) 2 found D1(2e, 0d): (1f,31) (31,1f) 2 found D1(2f, 0d): (03,2c) (2c,03) 2 found D1(30, 0d): (19,29) (29,19) 2 found D1(31, 0d): (09,38) (0c,3d) (38,09) (3d,0c) 4 found D1(32, 0d): (0e,3c) (3c,0e) 2 found D1(33, 0d): (07,34) (0d,3e) (1a,29) (29,1a) (34,07) (3e,0d) 6 found D1(34, 0d): (06,32) (10,24) (16,22) (1c,28) (22,16) (24,10) (28,1c) (32,06) 8 found D1(35, 0d): (00,35) (35,00) 2 found D1(36, 0d): (02,34) (0d,3b) (34,02) (3b,0d) 4 found D1(37, 0d): (15,22) (22,15) 2 found D1(38, 0d): (00,38) (08,30) (15,2d) (2d,15) (30,08) (38,00) 6 found D1(39, 0d): (19,20) (1d,24) (20,19) (24,1d) 4 found D1(3a, 0d): (04,3e) (14,2e) (1a,20) (20,1a) (2e,14) (3e,04) 6 found D1(3b, 0d): (0b,30) (16,2d) (2d,16) (30,0b) 4 found D1(3c, 0d): (05,39) (09,35) (35,09) (39,05) 4 found D1(3d, 0d): (0f,32) (12,2f) (13,2e) (17,2a) (18,25) (1b,26) (25,18) (26,1b) (2a,17) (2e,13) (2f,12) (32,0f) 12 found D1(3e, 0d): (01,3f) (11,2f) (18,26) (1b,25) (25,1b) (26,18) (2f,11) (3f,01) 8 found D1(3f, 0d): (04,3b) (05,3a) (0e,31) (31,0e) (3a,05) (3b,04) 6 found Total: 256 Sbox1 0x3 D1(00, 03): 0 found D1(01, 03): (1c,1d) (1d,1c) (2c,2d) (2d,2c) (3c,3d) (3d,3c) 6 found D1(02, 03): (05,07) (07,05) (0c,0e) (0e,0c) (21,23) (23,21) (30,32) (32,30) 8 found D1(03, 03): (38,3b) (3b,38) 2 found D1(04, 03): (00,04) (04,00) (09,0d) (0b,0f) (0d,09) (0f,0b) 6 found D1(05, 03): (22,27) (27,22) 2 found D1(06, 03): (29,2f) (2f,29) (38,3e) (3e,38) 4 found D1(07, 03): (02,05) (05,02) (08,0f) (0f,08) 4 found D1(08, 03): (11,19) (12,1a) (13,1b) (17,1f) (19,11) (1a,12) (1b,13) (1f,17) (26,2e) (2e,26) (37,3f) (3f,37) 12 found D1(09, 03): 0 found D1(0a, 03): (27,2d) (2d,27) 2 found D1(0b, 03): (11,1a) (12,19) (13,18) (18,13) (19,12) (1a,11) (25,2e) (2e,25) (35,3e) (3e,35) 10 found D1(0c, 03): (10,1c) (14,18) (18,14) (1c,10) (24,28) (28,24) (31,3d) (3d,31) 8 found D1(0d, 03): (00,0d) (04,09) (06,0b) (09,04) (0b,06) (0d,00) (34,39) (39,34) 8 found D1(0e, 03): (06,08) (08,06) (22,2c) (2c,22) (34,3a) (35,3b) (3a,34) (3b,35) 8 found D1(0f, 03): (14,1b) (1b,14) (20,2f) (2f,20) 4 found D1(10, 03): 0 found D1(11, 03): (01,10) (10,01) (2b,3a) (3a,2b) 4 found D1(12, 03): (2b,39) (39,2b) 2 found D1(13, 03): (0c,1f) (1f,0c) (21,32) (23,30) (30,23) (32,21) 6 found D1(14, 03): 0 found D1(15, 03): (03,16) (16,03) (26,33) (33,26) 4 found D1(16, 03): (03,15) (15,03) (20,36) (25,33) (2a,3c) (33,25) (36,20) (3c,2a) 8 found D1(17, 03): 0 found D1(18, 03): 0 found D1(19, 03): (07,1e) (0e,17) (17,0e) (1e,07) 4 found D1(1a, 03): 0 found D1(1b, 03): (24,3f) (2a,31) (31,2a) (3f,24) 4 found D1(1c, 03): (01,1d) (02,1e) (0a,16) (16,0a) (1d,01) (1e,02) 6 found D1(1d, 03): 0 found D1(1e, 03): 0 found D1(1f, 03): (0a,15) (15,0a) (28,37) (29,36) (36,29) (37,28) 6 found D1(20, 03): (03,23) (04,24) (0e,2e) (19,39) (1a,3a) (23,03) (24,04) (2e,0e) (39,19) (3a,1a) 10 found D1(21, 03): (06,27) (09,28) (27,06) (28,09) 4 found D1(22, 03): (13,31) (31,13) 2 found D1(23, 03): (0f,2c) (19,3a) (1a,39) (1d,3e) (2c,0f) (39,1a) (3a,19) (3e,1d) 8 found D1(24, 03): (1c,38) (38,1c) 2 found D1(25, 03): (05,20) (08,2d) (11,34) (14,31) (15,30) (18,3d) (20,05) (2d,08) (30,15) (31,14) (34,11) (3d,18) 12 found D1(26, 03): (0b,2d) (12,34) (16,30) (1b,3d) (1d,3b) (2d,0b) (30,16) (34,12) (3b,1d) (3d,1b) 10 found D1(27, 03): 0 found D1(28, 03): (00,28) (07,2f) (0f,27) (14,3c) (27,0f) (28,00) (2f,07) (3c,14) 8 found D1(29, 03): (0a,23) (0b,22) (0c,25) (0d,24) (1c,35) (22,0b) (23,0a) (24,0d) (25,0c) (35,1c) 10 found D1(2a, 03): (06,2c) (08,22) (0c,26) (22,08) (26,0c) (2c,06) 6 found D1(2b, 03): (10,3b) (3b,10) 2 found D1(2c, 03): (05,29) (1f,33) (29,05) (33,1f) 4 found D1(2d, 03): (02,2f) (2f,02) 2 found D1(2e, 03): (10,3e) (3e,10) 2 found D1(2f, 03): (13,3c) (3c,13) 2 found D1(30, 03): 0 found D1(31, 03): (03,32) (07,36) (17,26) (1b,2a) (1f,2e) (26,17) (2a,1b) (2e,1f) (32,03) (36,07) 10 found D1(32, 03): (17,25) (18,2a) (25,17) (2a,18) 4 found D1(33, 03): (04,37) (37,04) 2 found D1(34, 03): (01,35) (02,36) (15,21) (21,15) (35,01) (36,02) 6 found D1(35, 03): 0 found D1(36, 03): (09,3f) (3f,09) 2 found D1(37, 03): (16,21) (1e,29) (21,16) (29,1e) 4 found D1(38, 03): (0a,32) (32,0a) 2 found D1(39, 03): (01,38) (12,2b) (2b,12) (38,01) 4 found D1(3a, 03): (0d,37) (11,2b) (2b,11) (37,0d) 4 found D1(3b, 03): 0 found D1(3c, 03): 0 found D1(3d, 03): (0e,33) (33,0e) 2 found D1(3e, 03): (1e,20) (20,1e) 2 found D1(3f, 03): (00,3f) (3f,00) 2 found Total: 256