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