Transcript CryptoAnalysis

Chapter 3
Block Ciphers and the
Advanced Encryption Standard
1
Outline







3.1
3.2
3.3
3.4
3.5
3.6
3.7
Introduction
Substitution-Permutation Networks
Linear cryptanalysis
Differential cryptanalysis
The Data Encryption Standard
The Advanced Encryption Standard
Modes of Operation
2
3.1 Introduction

A commonly used design for modern-day block
ciphers is that of an iterated cipher:
 The cipher requires the specification of a round
function and a key schedule, and the encryption
of a plaintext will proceed through Nr similar
rounds.





random key K: used to construct Nr round keys (also
called subkeys), which are denoted K1,…,KNr.
key schedule (K1,…,KNr): constructed from K using a
fixed, public algorithm.
round function g: takes two inputs: a round key (Kr)
and a current state (wr-1). wr=g(wr-1,Kr) is the next state.
plaintext x: the initial state w0.
Ciphertext y: the state after all Nr rounds done.
3
Introduction

Encryption operations:
Decryption operations:
w0  x
w Nr  y
w1  g ( w0 , K 1 )
w2  g ( w1 , K 2 )

w Nr 1  g ( w Nr  2 , K Nr 1 )
w Nr  g ( w Nr 1 , K Nr )
y  w Nr
w Nr 1  g 1 ( w Nr , K Nr )

w1  g 1 ( w2 , K 2 )
w0  g 1 ( w1 , K 1 )
x  w0
Note: function g is injective
(one-to-one)
4
3.2 Substitution-Permutation
Networks (SPN)

Cryptosystem 3.1: SPN

l, m and Nr are positive integers
 S : {0,1}l  {0,1}l is a substitution
 P : {1,..., lm}  {1,..., lm} is a permutation.

P  C  {0,1}lm , and K  ({0,1}lm ) Nr 1 consist of all



possible key schedules that could be derived from
an initial key K using the key scheduling algorithm.
For a key schedule ( K 1 ,..., K Nr 1 ) , we encrypt the
plaintext x using Algorithm 3.1.
5
Substitution-Permutation
Networks

Algorithm 3.1: SPN ( x,  S ,  P , ( K 1 ,..., K Nr 1 ))
w0  x
for r  1 to Nr  1
u r  w r 1  K r

for i  1 to m
do 
r
r
do
v


(
u
(
i
)
S
(
i) )

w r  (v r ,..., v r
 P (1)
 P ( lm ) )

u Nr  w Nr 1  K Nr
for i  1 to m
do v(Nri)   S (u(Nri) )
y  v Nr  K Nr 1
ur is the input to the Sboxes in round r.
vr is the output of the Sboxes in round r.
wr is obtained from vr by
applying  P .
ur+1 is constructed from
wr by xor-ing with the
round key Kr+1 (called
round key mixing).
The very first and last
operations are xors with
subkeys (called whitening).
output ( y )
6
Substitution-Permutation
Networks

Example 3.1:
 Suppose
l  m  Nr  4 . Let  S be defined as follows,
where the input and the output are written in hexadecimal:
Let  P be defined as follows:
See Figure 3.1 for a pictorial representation of this
particular SPN, where Sir means i-th round, r-th S-box.
7
x
u1
v1
w1
u2
v2
w2
u3
v3
w3
u4
Figure 3.1: A substitutionpermutation network
v4
y
8
Substitution-Permutation
Networks



Key schedule: suppose we begin with a 32-bit key
K  (k1 ,..., k32 )  {0,1}32 . For 1  r  5 , define Kr to consist of
16 consecutive bits of K, beginning with k4r-3.
K= 0011 1010 1001 0100 1101 0110 0011 1111
Round keys:
K1= 0011 1010 1001 0100
K2= 1010 1001 0100 1101
K3= 1001 0100 1101 0110
K4= 0100 1101 0110 0011
K5= 1101 0110 0011 1111
9
Substitution-Permutation
Networks


Suppose the plaintext is x= 0010 0110 1011 0111.
Then the encryption of x proceeds as follows:
w0= 0010 0110 1011 0111
K1= 0011 1010 1001 0100
u1= 0001 1100 0010 0011
v1= 0100 0101 1101 0001
w1= 0010 1110 0000 0111
K2= 1010 1001 0100 1101
u2= 1000 0111 0100 1010
v2= 0011 1000 0010 0110
w2= 0100 0001 1011 1000
10
Substitution-Permutation
Networks
K3= 1001 0100 1101 0110
u3= 1101 0101 0110 1110
v3= 1001 1111 1011 0000
w3= 1110 0100 0110 1110
K4= 0100 1101 0110 0011
u4= 1010 1001 0000 1101
v4= 0110 1010 1110 1001
K5= 1101 0110 0011 1111, and
y= 1011 1100 1101 0110
is the ciphertext.
11
3.3 Linear Cryptanalysis



We want to find a probability linear relationship
between a subset of plaintext bits and a subset of
data bits preceding the last round. This relation
behaves in a non-random fashion.
The attacker has a lot of plaintext-ciphertext pairs
(known plaintext attack).
For each candidate subkey, we partially decrypt the
cipher and check if the relation holds. If the relation
holds then increment its corresponding counter. At
the end, the candidate key that counts furthest from
½ is the most likely subkey.
12
Linear Cryptanalysis

3.3.1 The Piling-up Lemma

Suppose X1, X2,… are independent random variables from
{0,1}. And
Pr[ X i  0]  pi ,
i  1,2,... Hence,
Pr[ X i  1]  1  pi , i  1,2,...

The independence of Xi, Xj implies
Pr[ X i  0, X j  0]  pi p j
Pr[ X i  0, X j  1]  pi (1  p j )
Pr[ X i  1, X j  0]  (1  pi ) p j
Pr[ X i  1, X j  1]  (1  pi )(1  p j )
13
Linear Cryptanalysis

Now consider X i  X j .
Pr[ X i  X j  0]  pi p j  (1  pi )(1  p j )
Pr[ X i  X j  1]  pi (1  p j )  (1  pi ) p j


The bias of Xi is defined to be the quantity
 i  pi  12
And we have
 12   i  12 ,
Pr[ X i  0]  12   i ,
Pr[ X i  1]  12   i .
14
Linear Cryptanalysis


Let
 i ,i ,..., i denote the bias of
1 2
k
X i1      X ik .
Lemma 3.1 (Piling-up lemma) : Let  i1 ,i2 ,..., ik denote
the bias of the random variable X i      X i . Then
1
k
k
 i ,i ,..., i  2 k 1   i .
1 2
k
j
j 1
Corollary 3.2: Let  i1 ,i2 ,..., ik denote the bias of the
random variable X i      X i . Suppose that  i j  0 for
some j. Then  i1 ,i2 ,..., ik  0 .
1
k
15
Linear Cryptanalysis

3.3.2 Linear Approximations of S-boxes



Consider an S-box  S : {0,1}  {0,1}.
Let the input m-tuple be X=(x1,…,xm). And the output n-tuple be
Y=(y1,…,yn).
We can see that
Pr[ X 1  x1 ,..., X m  xm , Y1  y1 ,..., Yn  yn ]  0
m
n
if ( y1 ,..., yn )   S ( x1 ,..., xm ) ; and
Pr[ X 1  x1 ,..., X m  xm , Y1  y1 ,..., Yn  yn ]  2 m
if ( y1 ,..., yn )   S ( x1 ,..., xm ).

Now we can compute the bias of the form
X i1      X ik  Y j1      Y jl
using the formulas stated above.
16
Linear Cryptanalysis

Example 3.2: We use the S-box as Example 3.1.
17
Linear Cryptanalysis


Consider X1  X 4  Y2 . The probability that X1  X 4  Y2  0
can be determined by counting the number of rows in which
X1  X 4  Y2  0 , and then dividing by 16.
It is seen that
Pr[ X 1  X 4  Y2  0]  12

Hence, the bias is 0.
If we instead analyze X 3  X 4  Y1  Y4 , we find that the
bias is –3/8.
18
Linear Cryptanalysis


We can record the bias of all 28=256 possible
random variables.
We represent the relevant random variable in the
form  4
  4

  ai X i     biYi 
 i 1
  i 1


where ai {0,1}, bi {0,1}, i  1,2,3,4 .
We treat (a1,a2,a3,a4) and (b1,b2,b3,b4) as
hexadecimal digit (they are called input sum and
output sum, respectively)
19
Linear Cryptanalysis

Let NL(a,b) denote the number of binary eight-tuples
(x1,x2,x3,x4,y1,y2,y3,y4) s.t
( y1 , y2 , y3 , y4 )   S ( x1 , x2 , x3 , x4 )
and 4
4

 

  ai X i     biYi   0
 i 1
  i 1



The bias is computed as  (a, b)  ( N L (a, b)  8) / 16 .
The table of all NL is called the linear approximation
table (Figure 3.2).
20
Example
3.2
Figure 3.2: Linear approximation table: values of
NL(a,b)-8
21
Linear Cryptanalysis

3.3.3 Linear Attack on an SPN


Linear cryptanalysis requires a set of linear approximations
of S-boxes that can be used to derive a linear approximation
of the entire SPN (excluding the last round).
Figure 3.3 illustrates the structure of the approximation we
will use.

Arrows are the random variables involved in the
approximations and the labeled S-boxes (active S-boxes) are
used in the approximations.
22
x
u1
v1
w1
u2
v2
w2
u3
v3
w3
u4
Figure 3.3: A linear
approximation of an SPN
v4
y
23
Linear Cryptanalysis

The approximation incorporates four active S-boxes:





In
In
In
In
S12,
S22,
S32,
S34,
T1  U 51  U 71  U 81  V61 has bias ¼
T2  U 62  V62  V82 has bias -¼
T3  U 63  V63  V83 has bias -¼
T4  U143  V143  V163 has bias -¼
T1 , T2 , T3 , T4 have biases that are high in absolute
value. Further, we will see their XOR will lead to
cancellations of “intermediate” random variables.
24
Linear Cryptanalysis

Using Piling-up lemma, T1  T2  T3  T4 has bias equal
to 23(1/4)(-1/4)3=-1/32.


Note: we assume the four r.v are independent.
Then T1 , T2 , T3 , T4 can be expressed in terms of
plaintext bits, bits of u4 (input to the last round) and
key bits as follows:
T1  U 51  U 71  U 81  V61  X 5  K 51  X 7  K 71  X 8  K 81  V61
T2  U 62  V62  V82
 V61  K 62  V62  V82
T3  U 63  V63  V83
 V62  K 63  V63  V83
T4  U143  V143  V163
 V82  K143  V143  V163
25
Linear Cryptanalysis

XOR the right side and we get
X 5  X 7  X 8  V63  V83  V143  V163
 K51  K 71  K81  K 62  K 63  K143


(3.1)
Then replace Vi 3 by U i4 and key bits:
V63  U 64  K 64
V83  U144  K144
V143  U 84  K84
V163  U164  K164
Now substitute them into 3.1:
X 5  X 7  X 8  U 64  U 84  U144  U164
 K 51  K 71  K81  K 62  K 63  K143  K 64  K84  K144  K164 (3.2)
26
Linear Cryptanalysis


The expression above only involves plaintext bits, bits
of u4 and key bits.
Suppose the key bits are fixed. Then
K 51  K 71  K 81  K 62  K 63  K143  K 64  K 84  K144  K164

has the (fixed) value 0 or 1.
It follows that
X 5  X 7  X 8  U 64  U 84  U144  U164
(3.3)
has bias -1/32 or 1/32 where the sign depends on
the key bits (=0 or =1).
27
Linear Cryptanalysis


The fact that (3.3) has bias bounded away from 0
allows us to carry out linear attack.
Suppose that we have T plaintext-ciphertext pairs
(denoted by  ), all use the same unknown key, K.
The attack will allow us to obtain the eight key bits,
K 55 , K 65 , K 75 , K 85 , K135 , K145 , K155 , K165

There are 28=256 possibilities for the eight key bits.
We refer to a binary 8-tuple as a candidate subkey.
28
Linear Cryptanalysis


For each ( x, y )  and for each candidate subkey, we
compute a partial decryption of y and obtain the
resulting value for u(42) ,u(44) .
Then we compute the value
x5  x7  x8  u64  u84  u144  u164


(3.4)
We maintain an array of counters indexed by the 256
possible candidate subkeys, and increment the
counter corresponding to a particular subkey when
(3.4) has the value 0.
In the end, we expect most counters will have a
value close to T/2, but the correct candidate subkey
will close to T/2±T/32.
29
Linear Cryptanalysis

The attack is presented as Algorithm 3.2.




L1 and L2 are hexadecimal value.
 S 1 is the inverse of the S-box.
The output, maxkey, contains the most likely subkey.
In general, it is suggested that a linear attack based
on a linear approximation having bias  will be
successful if the number of plaintext-ciphertext pairs
2
c

is approximately
for some “small” constant c.
30
for ( L1 , L2 )  (0,0) to ( F , F )
do Count[ L1 , L2 ]  0
1
Algorithm 3.2: LINEARATTACK( , T ,  S )
for each ( x, y ) 
for ( L1 , L2 )  (0,0) to ( F , F )

4
 v( 2 )  L1  y( 2 )
  4
 v( 4 )  L2  y( 4 )
 u 4   1 (v 4 )
S
( 2)
  ( 2)
do   4
1
4
do u( 4 )   S (v( 4 ) )
 z  x  x  x  u 4  u 4  u 4  u 4
5
7
8
6
8
14
16
 
 if z  0
 
  then Count[ L1 , L2 ]  Count[ L1 , L2 ]  1
 
max  1
for ( L1 , L2 )  (0,0) to ( F , F )


Count[ L1 , L2 ]|Count[ L1 , L2 ]T / 2|

do if Count[ L1 , L2 ] max

 then maxCount[ L1 , L2 ]

maxkey( L1 , L2 )
output (maxkey)
31
3.4 Differential Cryptanalysis




The main difference from linear attack is that
differential attack involves comparing the XOR of two
inputs to the XOR of the corresponding outputs.
Differential attack is a chosen-plaintext attack.
We consider inputs x and x* having a specified XOR
value denoted by x'  x  x * .
We decrypt y and y* using all possible key and
determine if their XOR has a certain value. Whenever
it does, increment the corresponding counter. At the
end, we expect the largest one is the most likely
subkey.
32
Differential Cryptanalysis

Definition 3.1:

m
n

:
{
0
,
1
}

{
0
,
1
}
Let S
be an S-box. Consider an
(ordered) pair of bitstrings of length m, say (x,x*).
We say that the input XOR of the S-box is x  x *
and the output XOR is  S ( x)   S ( x*) .
For any x'{0,1}m, define the set  (x ' ) to consist
of all the ordered pairs (x,x*) having input XOR
equal to x’.
33
Differential Cryptanalysis


It is easy to see that any set  (x ' ) contains 2m pairs,
and that
( x' )  {( x, x  x' ) : x {0,1}m }
For each pair in  (x ' ) , we can compute the output
XOR of the S-box. Then we can tabulate the
distribution of output XORs. There are 2m output
XORs which are distributed among 2n possible values.

A non-uniform output distribution will be the basis for a
successful attack.
34
Differential Cryptanalysis

Example 3.3:

We use the same S-box as before. Suppose we consider
input XOR x’=1011. Then
(1011)  {( 0000,1011), (0001,1010),..., (1111,0100)}

We compute the following table, where
x  x*  1011,
y   S ( x), y*   S ( x*),
y'  y  y *
35
x
x*
y
y*
y’
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
1011
1010
1001
1000
1111
1110
1101
1100
0011
0010
0001
0000
0111
0110
0101
0100
1110
0100
1101
0001
0010
1111
1011
1000
0011
1010
0110
1100
0101
1001
0000
0111
1100
0110
1010
0011
0111
0000
1001
0101
0001
1101
0100
1110
1000
1011
1111
0010
0010
0010
0111
0010
0101
1111
0010
1101
0010
0111
0010
0010
1101
0010
1111
0101
0000
0
1000
0
0001
0
1001
0
0010
8
1010
0
0011
0
1011
0
0100
0
1100
0
0101
2
1101
2
0110
0
1110
0
0111
2
1111
2
Number of output
Distribution table for x’=1011
36
Differential Cryptanalysis



In Example 3.3, only 5 of the 16 possible output
XORs occur. It has a very non-uniform distribution.
We can compute all possible input XORs as Example
3.3.
Define
N D ( x' , y' ) | {( x, x*)  ( x' ) :  S ( x)   S ( x*)  y'} |

ND(x’,y’) counts the number of pairs with input XOR equal to
x’ and output XOR equal to y’. (Figure 3.4)
37
Example
3.3
Figure 3.4: Difference distribution table: values of ND(x’,y’)
38
Differential Cryptanalysis

An input XOR is computed as
u(ri )  (u(ri ) )*  ( w(ri)1  K (ri ) )  (( w(ri)1 ) *  K (ri ) )
 w(ri)1  ( w(ri)1 ) *


Therefore, the input XOR does not depend on the subkey
bits used in round r; it is equal to the (permuted) output
XOR of round r-1.
Let a’ denote the input XOR and let b’ denote the
output XOR. (a’,b’) is called a differential.
39
Differential Cryptanalysis

propagation ratio Rp(a’,b’):
N D ( a ' , b' )
2m
Rp(a’,b’) can be interpreted as a conditional probability:
R p ( a ' , b' ) 

Pr[output XOR  b' | input XOR  a' ]  R p (a' , b' )

We combine differentials in consecutive rounds to
form a differential trail. A particular differential
trail is shown in Figure 3.5.
40
x
u1
v1
w1
u2
v2
w2
u3
v3
w3
u4
v4
y
Figure 3.5: A differential trail
for a SPN
41
Differential Cryptanalysis

The differential attack arising from Figure 3.5 uses
the following propagation ratios of differentials:





In
In
In
In
S12 , R p (1011,0010)  1 / 2
S 23 , R p (0100,0110)  3 / 8
S32 , R p (0010,0101)  3 / 8
S33 , R p (0010,0101)  3 / 8
We therefore obtain a propagation ratio for a
differential trail of the first three rounds of the SPN:
3
1  3
27
R p (0000 1011 0000 0000, 0000 0101 0101 0000)     
2  8  1024
42
Differential Cryptanalysis

In other words,
x'  0000 1011 0000 0000  (v3 )'  0000 0101 0101 0000
with probability 27/1024. However,
(v3 )'  0000 0101 0101 0000  (u 4 )'  0000 0110 0000 0110
Hence, it follows that
x'  0000 1011 0000 0000  (u 4 )'  0000 0110 0000 0110
with probability 27/1024.
43
Differential Cryptanalysis



Algorithm 3.3 presents the attack algorithm.
The input and output are similar to linear attack,
except that  is a set (x,x*,y,y*), where x’ is fixed.
Algorithm 3.3 makes use of a certain filtering
operation. Tuples (x,x*,y,y*) for which the
differential holds are often called right pairs, and
allow us to determine the key bits.
A right pair has the form
(u(41) )'  (u(43) )'  0000
Hence we consider those y(1)  ( y(1) ) * and y(3)  ( y(3) ) *.
44
for ( L1 , L2 )  (0,0) to ( F , F )
do Count[ L1 , L2 ]  0
for each ( x, y, x*, y*) 
Algorithm 3.3:
DIFFERENTIALATTACK(  , T ,  S 1)
if ( y(1)  ( y(1) )*) and ( y( 3)  ( y( 3) )*)

for ( L1 , L2 )  (0,0) to ( F , F )



v(42 )  L1  y( 2)


 4


v( 4 )  L2  y( 4 )


 4
1


u


(v(42) )

(
2
)
S


 4
1


u( 4 )   S (v(44) )



 4


(v( 2 ) )*  L1  ( y( 2 ) ) *

do 

 4
 then  do (v( 4 ) )*  L2  ( y( 4) ) *
 4


1
(
u
)*


((v(42) )*)


(
2
)
S

 4

1

(
u
)*


((v(44) )*)

(
4
)
S


 4

4
4

(
u
)'

u

(
u
(
2
)
(
2
)
(
2) ) *



 4


(u( 4 ) )'  u(44)  (u(44) ) *



if ((u 4 )'  0110) and ((u 4 )'  0110)


( 2)
( 4)



 then Count[ L1 , L2 ]  Count[ L1 , L2 ]  1


max  1
for ( L1 , L2 )  (0,0) to ( F , F )
if Count[ L1 , L2 ]  max

do
max  Count[ L1 , L2 ]
then


maxkey  ( L1 , L2 )

output (maxkey)
45
Differential Cryptanalysis

A differential attack based on a differential trail
having propagation ratio equal to  will often be
successful if the number of tuples (x,x*,y,y*), which
1
we denote by T, is approximately c , for a “small”
constant c.
46