Transcript DIFFERENTIAL CRYPTANALYSIS

DIFFERENTIAL
CRYPTANALYSIS
Chapter 3.4
Ciphertext only attack.
 The
cryptanalyst knows the cryptograms.
This happens, if he can eavesdrop the
communication channels.
Known-plaintext attack.
 The
adversary can access not only the
communication channels but also parts of
plaintext.
Chosen-plaintext attack.

This is a known plaintext attack for which the
cryptanalyst may choose messages and
corresponding cryptograms.
Chosen-ciphertext attack.

The enemy selects his own cryptogram and
corresponding message and then tries to find the
secret key of the cryptosystem.
3.4.1 XOR profiles
The function to transfer the input string of an Sbox.
f : 
such that s1, s2  n and then
n
m
f (s1 ), f (s2 )   or s , s  
where
*
*
s1  f (s1 ), s2  f (s2 ).
m
*
1
*
2
m
Define   s1  s2 ,   s1*  s2* and four-tuples
S  {(s1, s2 ; s1* , s2* ), | (s1  s2   , s1*  s2*  )}
and denote S  the number of four-tuples in the
set.
For example,
S23C  {(3, 3F , F , D), (17, 2B, B, 9)
(2B, 17, 9, B), (3F , 3, D, F )}
and
S   4.
S2
S1
S  k
S
S1
S2
k
1
f
*
1
S
S
*
2
k
2
k
The XOR profile of an S-box defined by
n
m
f : 
is a table which has 2n rows and
2m columns. Each row and column is indexed
by  and  respectively. Each entry (, ) of the
table shows the number of elements in the set
S 
The example of an element of XOR profiles
If the set is
19 x
1x
S
 {(2 x , 1Bx ; 4 x , 5 x ), (1Bx , 2 x ; 5 x , 4 x ),
(22 x ,3Bx ; 1x ,0 x ), (2C x ,35 x ; 2 x ,3x ),
(35 x ,2Cx ; 3x ,2 x ), (3Bx ,22 x ; 0 x ,1x )}.
Then the element (19, 1) in the table of XOR profile is
S  6
The properties of XOR profiles
 All
entries in the table are zeroes or positive
even integers.
row for  = 0 has only one nonzero entry
equal to 2n (n is the number of input bits of
the S-box).
 The
 The
sum of entries in each row is equal to 2n.
input difference  may cause output
difference  with probability p  n .
 An
2
an entry (, ) is zero, then the input
difference  cannot cause the difference 
on the output.
 If
What can we say about value of the input?
( s1  k )  ( s2  k )  s1  s2
The XOR profile does not depend on the cryptographic key used.
What can we say about the key?
k  {si  s1 ,, si  s1}
1
j
Example:

Let an input ( s1, s2 )  (21x ,38 x ) have the output
difference   1x .
  100001  111000  011001  19
The set
19 x
1x
S
 {(2 x , 1Bx ; 4 x , 5 x ), (1Bx , 2 x ; 5 x , 4 x ),
(22 x ,3Bx ; 1x ,0 x ), (2C x ,35 x ; 2 x ,3x ),
(35 x ,2Cx ; 3x ,2 x ), (3Bx ,22 x ; 0 x ,1x )}.
The input is
  {2x , 1Bx , 22x , 3Bx , 2Cx , 35x }.
The applied key must be in the set
1    s1    s2
that is
1  {23x , 3 Ax , 3x , 1Ax , Dx , 14 x }
The following demonstrate how to calculate the bit-to-bit
addition.
21  2  100001  000010  100011  23
21  1B  100001  011011  111010  3 A
21  22  100001  100010  000011  3
21  3B  100001  111011  011010  1A
21  2C  100001  101100  001101  D
21  35  100001  110101  010100  14
If the second input is (s1, s2 )  (14 x ,23x ),  37 x
and   2 x Then the set S 237 is as following.
x
x
S 237x x

{( E x ,39x ;8 x , Ax ), ( Fx ,38x ;1x ,3 x ),
(11x ,26x ; Ax ,8 x ), (12x ,25x ; Ax ,8 x ),
(18x ,2 Fx ;5 x ,7 x ), (19x ,2 E x ;9 x , Bx ),
(25x ,12x ;8 x , Ax ), (26x ,11x ;8 x , Ax ),
(2 E x ,19x ; Bx ,9 x ), (2 Fx ,18x ;7 x ,5 x ),
(38x , Fx ;3 x ,1x ), (39x , E x ; Ax ,8 x )}
The set of input is
  {Ex ,39 x , Fx ,38 x ,11x ,26 x ,12 x ,25 x ,
18 x ,2 Fx ,19 x ,2 Ex }
The key set is
 2  {1Ax ,2 Dx ,2Cx ,1Bx ,32 x ,5x ,31x ,6 x ,
3Bx , Cx ,3 Ax , Dx }
Take another observation, (s1, s2 )  (14 x ,1Cx ),   9x
and then   {6 x , Ex , 20 x , 28x , 25x , 2Dx }
and  3  {12 x , 1Ax , 34 x , 3Cx , 31x , 39 x }
The key must be contained in the three set, so
the key is
1   2   3  {1Ax }
The XOR profile of an S-box with the secret key
XORed with the input is identical to the XOR
profile of the S-box without the key.
 Every input observation (s1, s2) and the
corresponding output difference  enable the
cryptanalyst to find the set  of key candidates.
 The analysis of differences for a single S-box allows
one to retrieve the key that is XORed to the input of
a S-box.

3.4.2 DES Round Characteristics
An m-round characteristic of a Feistel-type
cryptosystem is a sequence
(in ,1 , 1 , ,  m ,  m , out )  (in ,  , out )
Where in and out are input and output differences.
The pairs ( i , i ); i  1, , m, are consecutive
input and output difference for the round fk.
Let input sequences be ( A1 , 0) and ( A2 , 0) .
A single round characteristic of DES
in  ( A ,0)
1  0
f
1  0
out  ( A ,0)
The first part of difference is A and the second part is 0.
Our goal is to find a characteristic that feeds a
nonzero input difference in to S1 while other
input differences of S2 … S8 are set to zero and
the characteristic should work with a high
probability.
Another single round characteristic of DES
in  ( A ,60 00 00 00 X )
1  00 80 82 00 X
1  60 00 00 00 X
f
out  ( A  00 80 82 00 X ,60 00 00 00 X )
The input difference in = (A, 60 00 00 00x).
 The binary string (00 80 82 00x) obtained by
permuting (E0 00 00 00x) using permutation block P
 For this case, the pair of difference (Cx, Ex) happens
with probability 14/64.
 And then we get the output

out  ( A  00 80 82 00 X ,60 00 00 00 X )
Any characteristic has a probability attached to it. Let
the m-round characteristic be
(in ,1 , 1 , ,  m ,  m , out )
Then its probability
m
P ()   p
i 1
i
i

p
where  is the probability that input difference i
causes the output difference i for the function fk in the
ith round.
i
i
A two-round characteristic of DES
in  (00 80 82 00 X , 60 00 00 00 X )
1  00 80 82 00 X
2  0
f
f
1  60 00 00 00 X
2  0
out  (60 00 00 00, 00 00 00 00) X
The probability of the second round happening is one.
3.4.3 Cryptanalysis of 4-Round DES
Our purpose is to recover the key.

To concentrate on the last round of the DES.
In last figure, we use characteristic
A= (20 00 00 00x), which works always (p=1).
In the last round
 4  out   2  1
Four round DES
Input Difference
1
f
1
2
f
2
f
3
f
4
3
4
Output Difference ( out ,  4 )

1 = 0 and 1 = 0.

So the input difference becomes (001000) on S1

and all other 7 S-boxes are zero.

Thus 28-bits of 2 are known.

From the last equation, 28-bits of 4 are known.

Another characteristic A = (04 44 44 44x).

The the missing part of key is recovered by the
differential analysis of S1.
Finding the partial key k4.
Strip off the last round and find k3.
Then k2.
Six-round DES
Input Difference

1

f
1
f

5
f
5

6
f
6
Output Difference
First 3-Round Characteristic
1in  40 08 00 00 04 00 00 00 x

40 08 00 00 x


f
0x
04 00 00 00 x
0x
f
40 08 00 00 x
04 00 00 00 x
f
1out  40 08 00 00 04 00 00 00 x
1
 
4
(1)
1
 
4
Second 3-Round Characteristic
in2  00 20 00 08 00 00 04 00 x

00 20 00 08 x


f
0x
00 00 04 00 x
0x
f
00 20 00 08 x
00 00 04 00 x
f
2
out
 00 20 00 08 00 00 04 00 x
1
 
4
(1)
1
 
4
3.4.5 The main features of
differential analysis
The differential analysis can be applied to
Feistal cryptosystems with t rounds,
where it is possible to use input to the round function
and deduce or guess the corresponding output
differences
Characteristics are useful in guessing the correct
output differences of the round function.
It is enough to have (t-3)-round characteristic to find out output
differences in the t-round Feistel cryptosystem.
As the differential analysis enables to find keys
applied in the last round function, it by-passes
the key schedule.
It works under the assumption that round keys are statistacally
independent.
Once the key in the last round is found, the last
round can be stripped off by applying the extra
round.
Feistel cryptosystem immune against the
differential analysis:
The XOR profile must not have entries with large number.
The best (t-3)-round characteristics should work with the
probability smaller than the probability of guessing the right key
(t is the number of rounds in the cryptosystem).
The S-boxes should depend upon the secret key in a nonlinear
way. This will cause that XOR profile of S-boxes become more
complex. One way of implementation of this idea would be an
on-the-fly selection of S-boxes depending on the round key.