1
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.5.16
Block ciphers
Linear and Differential Cryptanalysis
2
Block cipher
Definition An n-bit block cipher is a function
E, Vn?K?Vn,such that for each key K ?K,
E(P;K) is an invertible mapping (the encryption
function for K) from Vn to Vn,written EK(P),
The inverse mapping is the decryption function,
denoted DK(C),P denotes that ciphertext
results from encrypting plaintext P under K,
3
Iterating Block ciphers
Definition A product cipher combines two or more
transformations in a manner intending that the resulting
cipher is more secure than the individual components,
Definition An iterated block cipher is a block cipher
involving the sequential repetition of an internal
function called a round function,Parameters include the
number of rounds Nr,the block bitsize n,and the bitsize
k of the input key K from which Nr subkeys Ki (round
keys) are derived,For invertibility (allowing unique
decryption),for each value Ki the round function is a
bijection on the round input,
4
Iterating Block ciphers
1,Iterated block cipher
Random (binary) key K ? round keys,K1,...,KNr,
2,Round function g
w
r = g(w
r-1,K
r),
where w
r-1 is the previous state
5
Iterated cipher …
Encryption operation,
w0 ? x
w1 = g(w0,K1),
w2 = g(w1,K2),
wNr = g(wNr-1,KNr),
y ? wNr
6
Iterated cipher …
For decryption we must have,
g(.,K) must be invertible for all K
Then decryption is the reverse of encryption
(bottom-up)
7
Diffusion and Confusion -- Shannon
? Diffusion,The relationship between the statistics
of the plaintext and the ciphertext is as complex
as possible,the value of each plaintext bit
affects many ciphertext bits,
? Confusion,the relationship between the statistics
of the plaintext and the value of the key is as
complex as possible,
8
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC
Substitution Table - Caesar‘s Cipher
Shannon‘s Principle of Confusion
Substitution Cipher
MESSAGE FROM MARY STUART KILL THE QUEEN
PHVVD JHIUR PPDUB VWXDU WNLOO WKHTX HHQ PHVVD J PHVVD PHVV PH P
key = 3 cyclic shifts
ABCDEFGHIJKLMNOPQRSTUVWXYZ
EYUOBMDXVTHIJPRCNAKQLSGZFW
General Substitution Table
26! possible keys
JBKKE DBMAR JJEAF KQLEA QHVII QXBNL BBP
9
4 9 1 7 5 3 2 8 6
Extended key,
order of columns
9! = 362‘880 keys
Shannon‘s Principle of Diffusion
Transposition Cipher
MESSAGE FROM MARY STUART KILL THE QUEEN
M E S S A G E
F R
O M
M A R Y S T U
A R T
T H
E
K I L L
Q U E E N
Plaintext in
Ciphertext out
MOAEE MRQ MOAE MOAEE MRQSM TU MOAEE MRQSM TUSAK E MOAEE MRQSM TUSAK EARIE RUH MOAEE MRQSM TUSAK EARIE GYLN MOAEE MRQSM TUSAK EARIE GYLNE SL FTT
Diffusion means permutation of bit or byte positions !
1 2 3 4 5 6 7 8 9 Key = 9 columns
SMTUE SLGYL NMOAE ARIER UHSAK EFTTE MRQ
10
Exclusive OR
Fundamental operation of many ciphers
1 0 1
0 1 1
1 1 0
0 0 0
y ? z z y ? Properties
? y ? y = 0
? y ? 0 = y
? y ? 1 = y
? y ? z ? z = y
11
Substitution-Permutation Networks,SPN
? Substitution pS,{0,1}l ? {0,1}l
? Permutation pP,{1,…,lm} ? {1,…,lm}
The plaintext has lm bits,x = x(1)||,,, ||x(m)
where,x(i)= (x(i-1)l+1,.,,,xil)
The SPN has Nr rounds,in which we perform on x
m substitutions pS followed by one permutation pP,
to get the ciphertext y,
Definition A substitution-permutation (SP) network is a
product cipher composed of a number of stages each
involving substitutions and permutations
12
SPN
13
14
Kerchoffs’ assumption
The adversary knows all details of the
encrypting function except the secret key
15
Linear and Differential
cryptanalysis
? Linear cryptanalysis was introduced by
Matsui at EUROCRYPT ’93 as a theoretical
attack on DES and later successfully used in
the practical cryptanalysis of DES
? Differential cryptanalysis was first
presented by Biham and Shamir at
CRYPTO ’90 to attack DES,
16
A Basic Substitution-Permutation
Network Cipher
? The cipher that we shall use to present the
concepts is a basic Substitution-Permutation
Network (SPN),
? Each round consists of (1) substitution,(2) a
transposition of the bits (i.e.,permutation of
the bit positions),and (3) key mixing,
? This basic structure was presented by Feistel
back in 1973 and these basic operations are
similar to what is found in DES and many
other modern ciphers,including Rijndael,
17
Figure 1,Basic
Substitution-Permutation
Network (SPN) Cipher
18
Substitution
? In our cipher,we break the 16-bit data block
into four 4-bit sub-blocks,Each sub-block
forms an input to a 4?4 S-box (a substitution
with 4 input and 4 output bits),
? we shall use the same nonlinear mapping for
all S-boxes,
Table 1,S-box Representation (in hexadecimal)
19
Permutation
? The permutation portion of a round is simply
the tranposition of the bits or the permutation
of the bit positions,
Table 2,Permutation
20
Key Mixing
? In our cipher,we break the 16-bit data block
into four 4-bit sub-blocks,Each sub-block
forms an input to a 4?4 S-box (a substitution
with 4 input and 4 output bits),we use a
simple bit-wise exclusive-OR between the
key bits,
? In our cipher,we shall assume that all bits of
the subkeys are independently generated and
unrelated,
21
Decryption
? In order to decrypt,data is essentially passed
backwards through the network,Hence,
decryption is also of the form of an SPN,
? all S-boxes must be bijective,
? the subkeys are applied in reverse order and
the bits of the subkeys must be moved around
according to the permutation,
? Note also that the lack of the permutation
after the last round ensures that the decryption
network can be the same structure as the
encryption network,
22
Linear Cryptanalysis
? Linear cryptanalysis tries to take advantage of
high probability occurrences of linear
expressions involving plaintext bits,
"ciphertext" bits (actually we shall use bits
from the 2nd last round output),and subkey
bits,
? It is a known plaintext attack,
23
Overview of Basic Attack
? The basic idea is to approximate the operation
of a portion of the cipher with an expression
that is linear where the linearity refers to a
mod-2 bit-wise operation,
? The approach in linear cryptanalysis is to
determine expressions of the form above
which have a high or low probability of
occurrence,
24
Overview of Basic Attack
? If we randomly selected values for u + v bits,
the probability that the expression would hold
would be exactly 1/2,
? It is the deviation or bias from the probability
of 1/2 for an expression to hold that is
exploited in linear cryptanalysis,
? Hence,if the expression holds with
probability pL for randomly chosen plaintexts
and the corresponding ciphertexts,then the
probability bias is pL – 1/2,
25
Piling-Up Principle
Suppose that X1,X2,X3… are independent random
variables taking the values from set {0,1},
Let p1,p2,p3…,Be real number such that 0<= p i <=1 ;
Pr[Xi = 0] = pi; (i = 1,2,3,4 ……..)
Pr[Xi = 1] = 1-pi; (i = 1,2,3,4 ……..)
Suppose i != j,
the independence implies that:-
Pr[Xi = 0,Xj = 0] = pi*pj;
Pr[Xi = 0,Xj = 1] = pi*(1-pj);
Pr[Xi = 1,Xj = 0] = (1-pi)*pj;
Pr[Xi = 1,Xj = 1] = (1-pi)*(1-pj);
26
Piling-Up Principle
Consider the discrete random variable,Xi ? Xj;
the probability distribution will be,
Pr[Xi ? Xj = 0] = pi*pj + (1-pi)*(1-pj);
Pr[Xi ? Xj = 1] = pi*(1-pj) + (1-pi)*(pj);
bias of Xi is,? i = pi –1/2; -1/2 <= ?i <= ?;
Pr[Xi = 0] = ? + ? i;
Pr[Xi = 1] = ? - ? i;
for I = 1,2,…… and i 1 < i2 < i3……<i k;
let ?i1,i2,i3,….ik be the bias of the random variable Xi1
? ….,? Xik;
then ? i1,i2,= 2 ? i1* ? i2
27
Piling-Up Principle
Piling-Up Lemma (Matsui)
For n independent,random binary variables,X1,X2,...Xn,
Pr(X1 ??..,??Xn = 0) = 1/2 +
or,equivalently,
?
?1,2,..,n =
where ?1,2,..,n represents the bias of X1 ??..,??Xn = 0,
28
Analyzing the Cipher Components
? Consider the S-box representation of Figure 2
with input X = [X1 X2 X3 X4] and a
corresponding output Y = [Y1 Y2 Y3 Y4],
29
Analyzing the Cipher Components
? we are examining all expressions of the form of
equation (1) where X and Y are the S-box input and
outputs,respectively,
? For example,for the S-box used in our cipher,
consider the linear expression
X2 ??X3 ??Y1 ??Y3 ??Y4 =0 or equivalently
X2 ??X3 =?Y1 ??Y3 ??Y4
? Applying all 16 possible input values for X and
examining the corresponding output values Y,it
may be observed that for exactly 12 out the 16 cases,
the expression above holds true,Hence,the
probability bias is 12/16-1/2 = 1/4,
30
Table 3,Sample Linear Approximations of S-box
31 Table 4,Linear Approximation Table
A complete enumeration of all linear approximations of the S-box in
our cipher is given in the linear approximation table of Table 4,
32
Analyzing the Cipher Components
? For a linear combination of input variables
represented as a1× X1?a2× X2?a3× X3?a4× X4
where ai ??{0,1} and "× " represents binary AND,
the hexadecimal value represents the binary value
a1a2a3a4,where a1 is the most significant bit,
? Similarly,for a linear combination of output bits
b1× Y1 ??b2× Y2 ??b3× Y3 ??b4× Y4 where bi ??
{0,1},the hexadecimal value represents the binary
vector b1b2b3b4,
? Hence,the bias of linear equation X3 ??X4 = Y1 ??Y4
(hex input 3 and hex output 9) is -6/16 = -3/8
33
Constructing Linear Approximations
for the Complete Cipher
? Consider an approximation involving S12,S22,S32,and S34,
? We use the following approximations of the S-box,
? S12,X1?X3?X4 = Y2 with probability 12/16 and bias +1/4
? S22,X2 = Y2?Y4 with probability 4/16 and bias -1/4
? S32,X2 = Y2?Y4 with probability 4/16 and bias -1/4
? S34,X2 = Y2?Y4 with probability 4/16 and bias -1/4
34
Figure 3,Sample Linear
Approximation
35
Constructing Linear Approximations
for the Complete Cipher
? Letting Ui (Vi) represent the 16-bit block of bits at the
input (output) of the round i Sboxes and Ui,j (Vi,j)
represent the j-th bit of block Ui (Vi) (where bits are
numbered from 1 to 16 from left to right in the figure of
the cipher),
? Similarly,let Ki represent the subkey block of bits
exclusive-ORed at the input to round i,with the
exception that K5 is the key exclusive-ORed at the
output of round 4,
? Hence,U1 = P ??K1 where P represents the block of 16
plaintext bits and "?" represents the bit-wise exclusive-
OR,
36
Constructing Linear Approximations
for the Complete Cipher
Using the linear approximation of the 1st round,we have
V1,6 = U1,5 ??U1,7 ??U1,8 = (P5 ??K1,5) ??(P7 ??K1,7) ??(P8 ??K1,8)
with probability 3/4,(2)
For the approximation in the 2nd round,we have
V2,6 ??V2,8 = U2,6 with probability ?,
Since U2,6 = V1,6 ??K2,6,we can get the form
V2,6 ??V2,8 = V1,6 ??K2,6 with probability ? and combining this
with (2) which holds with probability of ? gives
V2,6 ??V2,8 ??P5 ??P7 ??P8 ??K1,5 ??K1,7 ??K1,8 ??K2,6 = 0 (3)
which holds with probability of 1/2 + 2(3/4-1/2)(1/4-1/2) =
3/8
37
Constructing Linear Approximations
for the Complete Cipher
For round 3,we note that
V3,6 ??V3,8 = U3,6
with probability 1/4 and
V3,14 ??V3,16 = U3,14
with probability ?,Since U3,6= V2,6 ??K3,6,U3,14 =V2,8 ??K3,14,
V3,6 ??V3,8 ??V3,14 ??V3,16 ??V2,6 ??K3,6 ??V2,8 ??K3,14 = 0 (4)
with probability of 1/2 + 2(1/4-1/2)2 = 5/8
Now combining (3) and (4),to incorporate all four S-box
approximations,
V3,6 ??V3,8 ??V3,14 ??V3,16 ??P5 ??P7 ??P8 ??K1,5 ??K1,7 ??K1,8 ??
K2,6 ??K3,6 ??K3,14 =?0,
38
Constructing Linear Approximations
for the Complete Cipher
Noting that U4,6 = V3,6 ??K4,6,U4,8 = V3,14 ??K4,8,U4,14 = V3,8 ??K4,14,
and U4,16 = V3,16 ?K4,16,we can then write
U4,6 ??U4,8 ??U4,14 ??U4,16 ??P5 ??P7 ??P8 ???K = 0,
?K = K1,5 ??K1,7 ??K1,8 ??K2,6 ??K3,6 ??K3,14 ??K4,6 ??K4,8 ??K4,14
??K4,16?
and ?K is fixed at either 0 or 1 depending on the key of the
cipher,By application of the Piling-Up Lemma,the
above expression holds with probability 1/2+23(3/4-
1/2)(1/4-1/2)3 = 15/32 (that is,with a bias of -1/32),
U4,6 ??U4,8 ??U4,14 ??U4,16 ??P5 ??P7 ??P8 = 0 (5)
must hold with a probability of either 15/32 or (1-15/32) =
17/32,depending on whether ?K = 0 or 1,
39
Extracting Key Bits
? Once an R-1 round linear approximation is
discovered for a cipher of R rounds with a
suitably large enough linear probability bias,it is
conceivable to attack the cipher by recovering
bits of the last subkey,
? In the case of our example cipher,it is possible to
extract bits from subkey K5 given a 3 round linear
approximation,
? We shall refer to the bits to be recovered from the
last subkey as the target partial subkey,
40
Extracting Key Bits
? The linear expression of (5) affects the inputs to S-boxes
S42 and S44 in the last round,
? For each plaintext/ciphertext sample,we would try all
256 values for the target partial subkey [K5,5...K5,8,
K5,13...K5,16],
? For each partial subkey value,we would increment the
count whenever equation (5) holds true,where we
determine the value of [U4,5...U4,8,U4,13...U4,16] by
running the data backwards through the target partial
subkey and S-boxes S24 and S44,
41
Extracting Key Bits
? We have simulated attacking our basic cipher by
generating 10000 known plaintext/ciphertext values and
following the cryptanalytic process described for partial
subkey values [K5,5...K5,8],= [0010] (hex 2) and
[K5,13...K5,16] = [0100] (hex 4),
? | bias | = | count ?-?5000 | / 10000
where the count is the count corresponding to the particular
partial subkey value,
The experimentally determined bias value of 0.0336 is very
close to the expected value of
1/32 = 0.03125,
42
Table 5,Experimental Results for Linear Attack
43
Complexity of Attack
? We refer to the S-boxes involved in the linear
approximation as active S-boxes,
? In Figure 3,the four S-boxes in rounds 1 to 3 influenced
by the highlighted lines are active,
? Let ??represent the bias from 1/2 of the probability that
the linear expression for the complete cipher holds,
? Matsui shows that the number of known plaintexts
required in the attack is proportional to ?-2 and,letting
NL represent the number of known plaintexts required,it
is reasonable to approximate NL by
? NL ???-2,
44
Differential Cryptanalysis
? Differential cryptanalysis exploits the high
probability of certain occurrences of plaintext
differences and differences into the last round of
the cipher,
? Differential cryptanalysis is a chosen plaintext
attack,meaning that the attacker is able to select
inputs and examine outputs in an attempt to
derive the key,
45
Overview of Basic Attack
? Consider a system with input X = [X1 X2,.,Xn]
and output Y = [Y1 Y2,.,Yn],Let two inputs to the
system be X??and X??with the corresponding
outputs Y??and Y?,respectively,
? The input difference is given by DX = X????X??
D X=[D?X1 D X2,.,D Xn]
where D?Xi =Xi ????Xi ????with Xi??and Xi??
representing the i-th bit of X??and X?
D Y=[D?Y?1 D Y 2,.,D Y n]
46
Analyzing the Cipher Components
? All difference pairs of an S-box,(DX,DY),can be
examined and the probability of DY given DX can
be derived by considering input pairs (X?,X?)
such that X????X??= DX,
? we can see that the number of occurrences of DY
= 0010 for DX = 1011 is 8 out of 16 possible
values (i.e.,a probability of 8/16); the number of
occurrences of DY = 1011 given DX = 1000 is 4
out of 16; the number of occurrences of DY =
1010 given DX = 0100 is 0 out of 16,
47
Table 6,Sample Difference Pairs of the S-box
48
Table 7,Difference Distribution Table
49
Analyzing the Cipher Components
? We discuss the influence of
the key on the S-box
differential,
? Consider Figure 4,The
input to the "unkeyed" S-
box is X and the output Y,
However,in the cipher
structure we must consider
the keys applied at the
input of each S-box,
Figure 4,Keyed S-box
50
Analyzing the Cipher Components
? if we let the input to the "keyed" S-box be W = [W1 W2
W3 W4],we can consider the input difference to the
keyed S-box to be
D W=[D?W 1 D W 2,.,D W n] W ????W ??= D?W
Since the key bits remain the same for both W??and W?,
DWi = Wi????Wi??= (Xi????Ki) ??(Xi????Ki)
= Xi????Xi??= DXi
Hence,the key bits have no influence on the input
difference value and can be ignored,
51
Constructing Differential
Characteristics
? Once the differential information has been compiled
for the S-boxes in an SPN,we have the data to proceed
with determining a useful differential characteristic of
the overall cipher,
? This can be done by concatenating appropriate
difference pairs of S-boxes,
? By constructing a differential characteristic of certain
S-box difference pairs in each round,such that a
differential involves plaintexts bits and data bits to the
input of the last round of S-boxes,it is possible to
attack the cipher by recovering a subset of the subkey
bits following the last round,
52
Constructing Differential
Characteristics
? Consider a differential characteristic involving S12,S23,
S32,and S33,
? We use the following difference pairs of the S-box,
? S12,DX = B ??DY = 2 with probability 8/16
? S23,DX = 4 ??DY = 6 with probability 6/16
? S32,DX = 2 ??DY = 5 with probability 6/16
? S33,DX = 2 ??DY = 5 with probability 6/16
? All other S-boxes will have zero input difference and
consequently zero output difference,
53
Figure 5,Sample
Differential
Characteristic
DP = [0000 1011 0000 0000]
54
Constructing Differential
Characteristics
? The input difference to the cipher is equivalent to the
input difference to the first round and is given by
D?P?=?D?U1 =[ 0000 1011 0000 0000 ]
? where again,as with our presentation of linear
cryptanalysis in Section 3,we are using Ui to represent
the input to the i-th round S-boxes and Vi to represent
the output of the i-th round S-boxes,
? Hence,DUi and DVi represent the corresponding
differences.DV1 =[0000?0010?0000 0000 ]?considering
the difference pair for S12,
55
? and following the round 1 permutation
DU 2 =?[0000 0000 0100 0000]?
with probability of 8/16 = 1/2 given the plaintext
difference DP,
Now the second round differential using the difference
pair for S23 results in
DV 2 =?[0000 0000 0110 0000]?
and the permutation of round 2 gives
DU 3 =[0000 0010 0010 0000]
with probability 6/16 given DU2 and a probability of 8/16
??6/16 = 3/16 given DP,
56
Subsequently,we can use the differences for the S-boxes
of the third round,S32 and S33,and the permutation of
the third round to arrive at
DV 3 =[0000 0101 0101 0000]
and
DU 4 =[0000 0110 0000 0110 ]????????????????(6)
with a probability of (6/16)2 given DU3 and,hence,a
probability of 8/16 ??6/16 ??(6/16)2
= 27/1024 given plaintext difference DP,where again we
have assumed independence
between the difference pairs of S-boxes in all rounds,
57
Extracting Key Bits
? Once an R-1 round differential characteristic is
discovered for a cipher of R rounds with a suitably
large enough probability,it is conceivable to attack the
cipher by recovering bits from the last subkey,
? In the case of our example cipher,it is possible to
extract bits from subkey K5,
? The process followed involves partially decrypting the
last round of the cipher and examining the input to the
last round to determine if a right pair has probably
occurred,
58
Extracting Key Bits
? For each ciphertext pair,we would try all 256
values for [K5,5...K5,8,K5,13...K5,16],
? For each partial subkey value,we would
increment the count whenever the input
difference to the final round determined by the
partial decryption is the same as (6),where we
determine the value of [DU4,5..,DU4,8,DU4,13..,
DU4,16] by running the data backwards through
the partial subkey and S-boxes S24 and S44,
59
Extracting Key Bits
? We have simulated attacking our basic cipher keyed
using randomly generated subkeys by generating 5000
chosen plaintext/ciphertext pairs (i.e.,10000
encryptions with plaintext pairs satisfying DP = [0000
1011 0000 0000]) and following the process described
above,
? prob = count / 5000,
? In our example,we would expect the probability of the
occurrence of the right pair to be pD = 27/1024 =
0.0264 and we found experimentally the probability
for the correct subkey value [2,4] gave pD = 0.0244,
60
Table 8,Experimental Results for Differential Attack
61
Complexity of the Attack
? For differential cryptanalysis,we refer to the S-boxes
involved in a characteristic which have a non-zero
input difference (and hence a non-zero output
difference) as active Sboxes,
? In general it is very complex to determine exactly the
number of chosen plaintext pairs required to mount the
attack,However,it can be shown that a good rule-of-
thumb for the number of chosen plaintext pairs,ND,
required to distinguish right pairs when trying subkey
candidates is ND ? c / pD
? where pD is the differential characteristic probability
for the R-1 rounds of the R-round cipher and c is a
small constant,
62
Advanced Concepts
? Several extensions and modifications to the
basic attacks of linear and differential
cryptanalysis have been proposed and analyzed
since the original presentation of the attacks,
? Many papers in recent years have discussed the
application of linear and differential
cryptanalysis to ciphers proposed before the
existence of the attacks was known,
63
References
? [1] M,Matsui,"Linear Cryptanalysis Method for
DES Cipher",Advances in Cryptology-
EUROCRYPT ’93 (Lecture Notes in Computer
Science no,765),Springer-Verlag,pp,386-397,
1994,
? [2] E,Biham and A,Shamir,"Differential
Cryptanalysis of DES-like Cryptosystems",
Journal of Cryptology,vol,4,no,1,pp,3-72,
1991,
? [3]Howard M.Heys,A Tutorial on Linear and
Differential Cryptanalysis
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.5.16
Block ciphers
Linear and Differential Cryptanalysis
2
Block cipher
Definition An n-bit block cipher is a function
E, Vn?K?Vn,such that for each key K ?K,
E(P;K) is an invertible mapping (the encryption
function for K) from Vn to Vn,written EK(P),
The inverse mapping is the decryption function,
denoted DK(C),P denotes that ciphertext
results from encrypting plaintext P under K,
3
Iterating Block ciphers
Definition A product cipher combines two or more
transformations in a manner intending that the resulting
cipher is more secure than the individual components,
Definition An iterated block cipher is a block cipher
involving the sequential repetition of an internal
function called a round function,Parameters include the
number of rounds Nr,the block bitsize n,and the bitsize
k of the input key K from which Nr subkeys Ki (round
keys) are derived,For invertibility (allowing unique
decryption),for each value Ki the round function is a
bijection on the round input,
4
Iterating Block ciphers
1,Iterated block cipher
Random (binary) key K ? round keys,K1,...,KNr,
2,Round function g
w
r = g(w
r-1,K
r),
where w
r-1 is the previous state
5
Iterated cipher …
Encryption operation,
w0 ? x
w1 = g(w0,K1),
w2 = g(w1,K2),
wNr = g(wNr-1,KNr),
y ? wNr
6
Iterated cipher …
For decryption we must have,
g(.,K) must be invertible for all K
Then decryption is the reverse of encryption
(bottom-up)
7
Diffusion and Confusion -- Shannon
? Diffusion,The relationship between the statistics
of the plaintext and the ciphertext is as complex
as possible,the value of each plaintext bit
affects many ciphertext bits,
? Confusion,the relationship between the statistics
of the plaintext and the value of the key is as
complex as possible,
8
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC
Substitution Table - Caesar‘s Cipher
Shannon‘s Principle of Confusion
Substitution Cipher
MESSAGE FROM MARY STUART KILL THE QUEEN
PHVVD JHIUR PPDUB VWXDU WNLOO WKHTX HHQ PHVVD J PHVVD PHVV PH P
key = 3 cyclic shifts
ABCDEFGHIJKLMNOPQRSTUVWXYZ
EYUOBMDXVTHIJPRCNAKQLSGZFW
General Substitution Table
26! possible keys
JBKKE DBMAR JJEAF KQLEA QHVII QXBNL BBP
9
4 9 1 7 5 3 2 8 6
Extended key,
order of columns
9! = 362‘880 keys
Shannon‘s Principle of Diffusion
Transposition Cipher
MESSAGE FROM MARY STUART KILL THE QUEEN
M E S S A G E
F R
O M
M A R Y S T U
A R T
T H
E
K I L L
Q U E E N
Plaintext in
Ciphertext out
MOAEE MRQ MOAE MOAEE MRQSM TU MOAEE MRQSM TUSAK E MOAEE MRQSM TUSAK EARIE RUH MOAEE MRQSM TUSAK EARIE GYLN MOAEE MRQSM TUSAK EARIE GYLNE SL FTT
Diffusion means permutation of bit or byte positions !
1 2 3 4 5 6 7 8 9 Key = 9 columns
SMTUE SLGYL NMOAE ARIER UHSAK EFTTE MRQ
10
Exclusive OR
Fundamental operation of many ciphers
1 0 1
0 1 1
1 1 0
0 0 0
y ? z z y ? Properties
? y ? y = 0
? y ? 0 = y
? y ? 1 = y
? y ? z ? z = y
11
Substitution-Permutation Networks,SPN
? Substitution pS,{0,1}l ? {0,1}l
? Permutation pP,{1,…,lm} ? {1,…,lm}
The plaintext has lm bits,x = x(1)||,,, ||x(m)
where,x(i)= (x(i-1)l+1,.,,,xil)
The SPN has Nr rounds,in which we perform on x
m substitutions pS followed by one permutation pP,
to get the ciphertext y,
Definition A substitution-permutation (SP) network is a
product cipher composed of a number of stages each
involving substitutions and permutations
12
SPN
13
14
Kerchoffs’ assumption
The adversary knows all details of the
encrypting function except the secret key
15
Linear and Differential
cryptanalysis
? Linear cryptanalysis was introduced by
Matsui at EUROCRYPT ’93 as a theoretical
attack on DES and later successfully used in
the practical cryptanalysis of DES
? Differential cryptanalysis was first
presented by Biham and Shamir at
CRYPTO ’90 to attack DES,
16
A Basic Substitution-Permutation
Network Cipher
? The cipher that we shall use to present the
concepts is a basic Substitution-Permutation
Network (SPN),
? Each round consists of (1) substitution,(2) a
transposition of the bits (i.e.,permutation of
the bit positions),and (3) key mixing,
? This basic structure was presented by Feistel
back in 1973 and these basic operations are
similar to what is found in DES and many
other modern ciphers,including Rijndael,
17
Figure 1,Basic
Substitution-Permutation
Network (SPN) Cipher
18
Substitution
? In our cipher,we break the 16-bit data block
into four 4-bit sub-blocks,Each sub-block
forms an input to a 4?4 S-box (a substitution
with 4 input and 4 output bits),
? we shall use the same nonlinear mapping for
all S-boxes,
Table 1,S-box Representation (in hexadecimal)
19
Permutation
? The permutation portion of a round is simply
the tranposition of the bits or the permutation
of the bit positions,
Table 2,Permutation
20
Key Mixing
? In our cipher,we break the 16-bit data block
into four 4-bit sub-blocks,Each sub-block
forms an input to a 4?4 S-box (a substitution
with 4 input and 4 output bits),we use a
simple bit-wise exclusive-OR between the
key bits,
? In our cipher,we shall assume that all bits of
the subkeys are independently generated and
unrelated,
21
Decryption
? In order to decrypt,data is essentially passed
backwards through the network,Hence,
decryption is also of the form of an SPN,
? all S-boxes must be bijective,
? the subkeys are applied in reverse order and
the bits of the subkeys must be moved around
according to the permutation,
? Note also that the lack of the permutation
after the last round ensures that the decryption
network can be the same structure as the
encryption network,
22
Linear Cryptanalysis
? Linear cryptanalysis tries to take advantage of
high probability occurrences of linear
expressions involving plaintext bits,
"ciphertext" bits (actually we shall use bits
from the 2nd last round output),and subkey
bits,
? It is a known plaintext attack,
23
Overview of Basic Attack
? The basic idea is to approximate the operation
of a portion of the cipher with an expression
that is linear where the linearity refers to a
mod-2 bit-wise operation,
? The approach in linear cryptanalysis is to
determine expressions of the form above
which have a high or low probability of
occurrence,
24
Overview of Basic Attack
? If we randomly selected values for u + v bits,
the probability that the expression would hold
would be exactly 1/2,
? It is the deviation or bias from the probability
of 1/2 for an expression to hold that is
exploited in linear cryptanalysis,
? Hence,if the expression holds with
probability pL for randomly chosen plaintexts
and the corresponding ciphertexts,then the
probability bias is pL – 1/2,
25
Piling-Up Principle
Suppose that X1,X2,X3… are independent random
variables taking the values from set {0,1},
Let p1,p2,p3…,Be real number such that 0<= p i <=1 ;
Pr[Xi = 0] = pi; (i = 1,2,3,4 ……..)
Pr[Xi = 1] = 1-pi; (i = 1,2,3,4 ……..)
Suppose i != j,
the independence implies that:-
Pr[Xi = 0,Xj = 0] = pi*pj;
Pr[Xi = 0,Xj = 1] = pi*(1-pj);
Pr[Xi = 1,Xj = 0] = (1-pi)*pj;
Pr[Xi = 1,Xj = 1] = (1-pi)*(1-pj);
26
Piling-Up Principle
Consider the discrete random variable,Xi ? Xj;
the probability distribution will be,
Pr[Xi ? Xj = 0] = pi*pj + (1-pi)*(1-pj);
Pr[Xi ? Xj = 1] = pi*(1-pj) + (1-pi)*(pj);
bias of Xi is,? i = pi –1/2; -1/2 <= ?i <= ?;
Pr[Xi = 0] = ? + ? i;
Pr[Xi = 1] = ? - ? i;
for I = 1,2,…… and i 1 < i2 < i3……<i k;
let ?i1,i2,i3,….ik be the bias of the random variable Xi1
? ….,? Xik;
then ? i1,i2,= 2 ? i1* ? i2
27
Piling-Up Principle
Piling-Up Lemma (Matsui)
For n independent,random binary variables,X1,X2,...Xn,
Pr(X1 ??..,??Xn = 0) = 1/2 +
or,equivalently,
?
?1,2,..,n =
where ?1,2,..,n represents the bias of X1 ??..,??Xn = 0,
28
Analyzing the Cipher Components
? Consider the S-box representation of Figure 2
with input X = [X1 X2 X3 X4] and a
corresponding output Y = [Y1 Y2 Y3 Y4],
29
Analyzing the Cipher Components
? we are examining all expressions of the form of
equation (1) where X and Y are the S-box input and
outputs,respectively,
? For example,for the S-box used in our cipher,
consider the linear expression
X2 ??X3 ??Y1 ??Y3 ??Y4 =0 or equivalently
X2 ??X3 =?Y1 ??Y3 ??Y4
? Applying all 16 possible input values for X and
examining the corresponding output values Y,it
may be observed that for exactly 12 out the 16 cases,
the expression above holds true,Hence,the
probability bias is 12/16-1/2 = 1/4,
30
Table 3,Sample Linear Approximations of S-box
31 Table 4,Linear Approximation Table
A complete enumeration of all linear approximations of the S-box in
our cipher is given in the linear approximation table of Table 4,
32
Analyzing the Cipher Components
? For a linear combination of input variables
represented as a1× X1?a2× X2?a3× X3?a4× X4
where ai ??{0,1} and "× " represents binary AND,
the hexadecimal value represents the binary value
a1a2a3a4,where a1 is the most significant bit,
? Similarly,for a linear combination of output bits
b1× Y1 ??b2× Y2 ??b3× Y3 ??b4× Y4 where bi ??
{0,1},the hexadecimal value represents the binary
vector b1b2b3b4,
? Hence,the bias of linear equation X3 ??X4 = Y1 ??Y4
(hex input 3 and hex output 9) is -6/16 = -3/8
33
Constructing Linear Approximations
for the Complete Cipher
? Consider an approximation involving S12,S22,S32,and S34,
? We use the following approximations of the S-box,
? S12,X1?X3?X4 = Y2 with probability 12/16 and bias +1/4
? S22,X2 = Y2?Y4 with probability 4/16 and bias -1/4
? S32,X2 = Y2?Y4 with probability 4/16 and bias -1/4
? S34,X2 = Y2?Y4 with probability 4/16 and bias -1/4
34
Figure 3,Sample Linear
Approximation
35
Constructing Linear Approximations
for the Complete Cipher
? Letting Ui (Vi) represent the 16-bit block of bits at the
input (output) of the round i Sboxes and Ui,j (Vi,j)
represent the j-th bit of block Ui (Vi) (where bits are
numbered from 1 to 16 from left to right in the figure of
the cipher),
? Similarly,let Ki represent the subkey block of bits
exclusive-ORed at the input to round i,with the
exception that K5 is the key exclusive-ORed at the
output of round 4,
? Hence,U1 = P ??K1 where P represents the block of 16
plaintext bits and "?" represents the bit-wise exclusive-
OR,
36
Constructing Linear Approximations
for the Complete Cipher
Using the linear approximation of the 1st round,we have
V1,6 = U1,5 ??U1,7 ??U1,8 = (P5 ??K1,5) ??(P7 ??K1,7) ??(P8 ??K1,8)
with probability 3/4,(2)
For the approximation in the 2nd round,we have
V2,6 ??V2,8 = U2,6 with probability ?,
Since U2,6 = V1,6 ??K2,6,we can get the form
V2,6 ??V2,8 = V1,6 ??K2,6 with probability ? and combining this
with (2) which holds with probability of ? gives
V2,6 ??V2,8 ??P5 ??P7 ??P8 ??K1,5 ??K1,7 ??K1,8 ??K2,6 = 0 (3)
which holds with probability of 1/2 + 2(3/4-1/2)(1/4-1/2) =
3/8
37
Constructing Linear Approximations
for the Complete Cipher
For round 3,we note that
V3,6 ??V3,8 = U3,6
with probability 1/4 and
V3,14 ??V3,16 = U3,14
with probability ?,Since U3,6= V2,6 ??K3,6,U3,14 =V2,8 ??K3,14,
V3,6 ??V3,8 ??V3,14 ??V3,16 ??V2,6 ??K3,6 ??V2,8 ??K3,14 = 0 (4)
with probability of 1/2 + 2(1/4-1/2)2 = 5/8
Now combining (3) and (4),to incorporate all four S-box
approximations,
V3,6 ??V3,8 ??V3,14 ??V3,16 ??P5 ??P7 ??P8 ??K1,5 ??K1,7 ??K1,8 ??
K2,6 ??K3,6 ??K3,14 =?0,
38
Constructing Linear Approximations
for the Complete Cipher
Noting that U4,6 = V3,6 ??K4,6,U4,8 = V3,14 ??K4,8,U4,14 = V3,8 ??K4,14,
and U4,16 = V3,16 ?K4,16,we can then write
U4,6 ??U4,8 ??U4,14 ??U4,16 ??P5 ??P7 ??P8 ???K = 0,
?K = K1,5 ??K1,7 ??K1,8 ??K2,6 ??K3,6 ??K3,14 ??K4,6 ??K4,8 ??K4,14
??K4,16?
and ?K is fixed at either 0 or 1 depending on the key of the
cipher,By application of the Piling-Up Lemma,the
above expression holds with probability 1/2+23(3/4-
1/2)(1/4-1/2)3 = 15/32 (that is,with a bias of -1/32),
U4,6 ??U4,8 ??U4,14 ??U4,16 ??P5 ??P7 ??P8 = 0 (5)
must hold with a probability of either 15/32 or (1-15/32) =
17/32,depending on whether ?K = 0 or 1,
39
Extracting Key Bits
? Once an R-1 round linear approximation is
discovered for a cipher of R rounds with a
suitably large enough linear probability bias,it is
conceivable to attack the cipher by recovering
bits of the last subkey,
? In the case of our example cipher,it is possible to
extract bits from subkey K5 given a 3 round linear
approximation,
? We shall refer to the bits to be recovered from the
last subkey as the target partial subkey,
40
Extracting Key Bits
? The linear expression of (5) affects the inputs to S-boxes
S42 and S44 in the last round,
? For each plaintext/ciphertext sample,we would try all
256 values for the target partial subkey [K5,5...K5,8,
K5,13...K5,16],
? For each partial subkey value,we would increment the
count whenever equation (5) holds true,where we
determine the value of [U4,5...U4,8,U4,13...U4,16] by
running the data backwards through the target partial
subkey and S-boxes S24 and S44,
41
Extracting Key Bits
? We have simulated attacking our basic cipher by
generating 10000 known plaintext/ciphertext values and
following the cryptanalytic process described for partial
subkey values [K5,5...K5,8],= [0010] (hex 2) and
[K5,13...K5,16] = [0100] (hex 4),
? | bias | = | count ?-?5000 | / 10000
where the count is the count corresponding to the particular
partial subkey value,
The experimentally determined bias value of 0.0336 is very
close to the expected value of
1/32 = 0.03125,
42
Table 5,Experimental Results for Linear Attack
43
Complexity of Attack
? We refer to the S-boxes involved in the linear
approximation as active S-boxes,
? In Figure 3,the four S-boxes in rounds 1 to 3 influenced
by the highlighted lines are active,
? Let ??represent the bias from 1/2 of the probability that
the linear expression for the complete cipher holds,
? Matsui shows that the number of known plaintexts
required in the attack is proportional to ?-2 and,letting
NL represent the number of known plaintexts required,it
is reasonable to approximate NL by
? NL ???-2,
44
Differential Cryptanalysis
? Differential cryptanalysis exploits the high
probability of certain occurrences of plaintext
differences and differences into the last round of
the cipher,
? Differential cryptanalysis is a chosen plaintext
attack,meaning that the attacker is able to select
inputs and examine outputs in an attempt to
derive the key,
45
Overview of Basic Attack
? Consider a system with input X = [X1 X2,.,Xn]
and output Y = [Y1 Y2,.,Yn],Let two inputs to the
system be X??and X??with the corresponding
outputs Y??and Y?,respectively,
? The input difference is given by DX = X????X??
D X=[D?X1 D X2,.,D Xn]
where D?Xi =Xi ????Xi ????with Xi??and Xi??
representing the i-th bit of X??and X?
D Y=[D?Y?1 D Y 2,.,D Y n]
46
Analyzing the Cipher Components
? All difference pairs of an S-box,(DX,DY),can be
examined and the probability of DY given DX can
be derived by considering input pairs (X?,X?)
such that X????X??= DX,
? we can see that the number of occurrences of DY
= 0010 for DX = 1011 is 8 out of 16 possible
values (i.e.,a probability of 8/16); the number of
occurrences of DY = 1011 given DX = 1000 is 4
out of 16; the number of occurrences of DY =
1010 given DX = 0100 is 0 out of 16,
47
Table 6,Sample Difference Pairs of the S-box
48
Table 7,Difference Distribution Table
49
Analyzing the Cipher Components
? We discuss the influence of
the key on the S-box
differential,
? Consider Figure 4,The
input to the "unkeyed" S-
box is X and the output Y,
However,in the cipher
structure we must consider
the keys applied at the
input of each S-box,
Figure 4,Keyed S-box
50
Analyzing the Cipher Components
? if we let the input to the "keyed" S-box be W = [W1 W2
W3 W4],we can consider the input difference to the
keyed S-box to be
D W=[D?W 1 D W 2,.,D W n] W ????W ??= D?W
Since the key bits remain the same for both W??and W?,
DWi = Wi????Wi??= (Xi????Ki) ??(Xi????Ki)
= Xi????Xi??= DXi
Hence,the key bits have no influence on the input
difference value and can be ignored,
51
Constructing Differential
Characteristics
? Once the differential information has been compiled
for the S-boxes in an SPN,we have the data to proceed
with determining a useful differential characteristic of
the overall cipher,
? This can be done by concatenating appropriate
difference pairs of S-boxes,
? By constructing a differential characteristic of certain
S-box difference pairs in each round,such that a
differential involves plaintexts bits and data bits to the
input of the last round of S-boxes,it is possible to
attack the cipher by recovering a subset of the subkey
bits following the last round,
52
Constructing Differential
Characteristics
? Consider a differential characteristic involving S12,S23,
S32,and S33,
? We use the following difference pairs of the S-box,
? S12,DX = B ??DY = 2 with probability 8/16
? S23,DX = 4 ??DY = 6 with probability 6/16
? S32,DX = 2 ??DY = 5 with probability 6/16
? S33,DX = 2 ??DY = 5 with probability 6/16
? All other S-boxes will have zero input difference and
consequently zero output difference,
53
Figure 5,Sample
Differential
Characteristic
DP = [0000 1011 0000 0000]
54
Constructing Differential
Characteristics
? The input difference to the cipher is equivalent to the
input difference to the first round and is given by
D?P?=?D?U1 =[ 0000 1011 0000 0000 ]
? where again,as with our presentation of linear
cryptanalysis in Section 3,we are using Ui to represent
the input to the i-th round S-boxes and Vi to represent
the output of the i-th round S-boxes,
? Hence,DUi and DVi represent the corresponding
differences.DV1 =[0000?0010?0000 0000 ]?considering
the difference pair for S12,
55
? and following the round 1 permutation
DU 2 =?[0000 0000 0100 0000]?
with probability of 8/16 = 1/2 given the plaintext
difference DP,
Now the second round differential using the difference
pair for S23 results in
DV 2 =?[0000 0000 0110 0000]?
and the permutation of round 2 gives
DU 3 =[0000 0010 0010 0000]
with probability 6/16 given DU2 and a probability of 8/16
??6/16 = 3/16 given DP,
56
Subsequently,we can use the differences for the S-boxes
of the third round,S32 and S33,and the permutation of
the third round to arrive at
DV 3 =[0000 0101 0101 0000]
and
DU 4 =[0000 0110 0000 0110 ]????????????????(6)
with a probability of (6/16)2 given DU3 and,hence,a
probability of 8/16 ??6/16 ??(6/16)2
= 27/1024 given plaintext difference DP,where again we
have assumed independence
between the difference pairs of S-boxes in all rounds,
57
Extracting Key Bits
? Once an R-1 round differential characteristic is
discovered for a cipher of R rounds with a suitably
large enough probability,it is conceivable to attack the
cipher by recovering bits from the last subkey,
? In the case of our example cipher,it is possible to
extract bits from subkey K5,
? The process followed involves partially decrypting the
last round of the cipher and examining the input to the
last round to determine if a right pair has probably
occurred,
58
Extracting Key Bits
? For each ciphertext pair,we would try all 256
values for [K5,5...K5,8,K5,13...K5,16],
? For each partial subkey value,we would
increment the count whenever the input
difference to the final round determined by the
partial decryption is the same as (6),where we
determine the value of [DU4,5..,DU4,8,DU4,13..,
DU4,16] by running the data backwards through
the partial subkey and S-boxes S24 and S44,
59
Extracting Key Bits
? We have simulated attacking our basic cipher keyed
using randomly generated subkeys by generating 5000
chosen plaintext/ciphertext pairs (i.e.,10000
encryptions with plaintext pairs satisfying DP = [0000
1011 0000 0000]) and following the process described
above,
? prob = count / 5000,
? In our example,we would expect the probability of the
occurrence of the right pair to be pD = 27/1024 =
0.0264 and we found experimentally the probability
for the correct subkey value [2,4] gave pD = 0.0244,
60
Table 8,Experimental Results for Differential Attack
61
Complexity of the Attack
? For differential cryptanalysis,we refer to the S-boxes
involved in a characteristic which have a non-zero
input difference (and hence a non-zero output
difference) as active Sboxes,
? In general it is very complex to determine exactly the
number of chosen plaintext pairs required to mount the
attack,However,it can be shown that a good rule-of-
thumb for the number of chosen plaintext pairs,ND,
required to distinguish right pairs when trying subkey
candidates is ND ? c / pD
? where pD is the differential characteristic probability
for the R-1 rounds of the R-round cipher and c is a
small constant,
62
Advanced Concepts
? Several extensions and modifications to the
basic attacks of linear and differential
cryptanalysis have been proposed and analyzed
since the original presentation of the attacks,
? Many papers in recent years have discussed the
application of linear and differential
cryptanalysis to ciphers proposed before the
existence of the attacks was known,
63
References
? [1] M,Matsui,"Linear Cryptanalysis Method for
DES Cipher",Advances in Cryptology-
EUROCRYPT ’93 (Lecture Notes in Computer
Science no,765),Springer-Verlag,pp,386-397,
1994,
? [2] E,Biham and A,Shamir,"Differential
Cryptanalysis of DES-like Cryptosystems",
Journal of Cryptology,vol,4,no,1,pp,3-72,
1991,
? [3]Howard M.Heys,A Tutorial on Linear and
Differential Cryptanalysis
