CS计算机代考程序代写 algorithm chain ER Advanced Cryptanalysis Linear and Differential Cryptanalysis CS 3IS3

Advanced Cryptanalysis Linear and Differential Cryptanalysis CS 3IS3
Ryszard Janicki
Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada
Acknowledgments: Material based on Information Security by Mark Stamp (Chapter 6.4)
Ryszard Janicki
Linear and Differential Cryptanalysis 1/41

Introduction
Both linear and differential cryptanalysis developed to attack DES (Data Encryption Standard)
Applicable to other block ciphers
Differential
For analyzing ciphers, not a practical attack A chosen plaintext attack
Linear cryptanalysis
Slightly more feasible than differential A known plaintext attack
Ryszard Janicki
Linear and Differential Cryptanalysis 2/41

Operator ‘XOR’: ⊕
Formally,forallx,y∈{,1}:x⊕y=x+y mod2,i.e: 0⊕0=0
0⊕1=1 1⊕0=1 1⊕1=0
Fundamental property used in cryptography:
(x ⊕ y) ⊕ y = x
Standard interpretation (but not always!): x – plaintext, y – key
Ryszard Janicki
Linear and Differential Cryptanalysis 3/41

Feistel Cipher: Encryption
Feistel Cipher: Encryption (Repetition)
 Feistel cipher is a type of block cipher o Not a specific block cipher
 Split plaintext block into left and right halves: P = (L0, R0)
 For each round i = 1, 2, …, n, compute Li = Ri1
Ri = Li1  F(Ri1, Ki)
where F is round function and Ki is subkey
 Ciphertext: C = (Ln, Rn)
Part 1  Cryptography 53
Ryszard Janicki
Linear and Differential Cryptanalysis 4/41

Feistel Cipher: Decryption
Feistel Cipher: Decryption (Repetition)
 Start with ciphertext C = (Ln, Rn)
 For each round i = n, n1, …, 1, compute
Ri1 = Li
Li1 = Ri  F(Ri1, Ki)
where F is round function and Ki is subkey
 Plaintext: P = (L0, R0)
 Decryption works for any function F o But only secure for certain functions F
Part 1  Cryptography
Ryszard Janicki
54
Linear and Differential Cryptanalysis 5/41

DES Numerology
DES: Data Encryption Standard (Repetition)
 DES is a Feistel cipher with… o 64 bit block length
o 56 bit key length
o 16 rounds
o 48 bits of key used each round (subkey)
 Round function is simple (for block cipher)
 Security depends heavily on “S-boxes” o Each S-box maps 6 bits to 4 bits
Part 1  Cryptography
Ryszard Janicki
56
Linear and Differential Cryptanalysis 6/41

One Round of DES (Repetition)
32
expand
48
Ki
48
32 32

32
28
28
shift
key
32
One Round
of DES

48
S-boxes
28
28
28 28
compress
32
L
R
P box
key
shift
L
R
Part 1  Cryptography
DES round function F can be written as:
57
F(Ri−1,Ki) = P-box(S-boxes(Expand(Ri−1) ⊕ Ki)).
Ryszard Janicki
Linear and Differential Cryptanalysis 7/41

L
R
DES Overview
Linear stuff
 8 S-boxes
 Each S-box maps
Ki subkey
6 bits to 4 bits  Example: S-box 1
XOR
input bits (0,5)
 input bits (1,2,3,4)
|0 123456 789ABC DEF ———————————– 0|E4 D12FB 83A6C5 907 1|0F 74E2D 1A6CB9 534 2|41 E8D62 BFC973 A50 3|FC 82491 75B3EA 06D
Part 1  Cryptography 228
S-boxes
Linear stuff
L
R
Ryszard Janicki
Linear and Differential Cryptanalysis 8/41

Differential Cryptanalysis I
Recall that all of DES is linear except for the S-boxes
Differential attack focuses on overcoming this nonlinearity
Idea is to compare input and output differences Differential Cryptanalysis
For simplicity, first consider only one round and only one S-box
 Suppose a cipher has 3-bit to 2-bit S-box
Suppose a cipher has 3-bit to 2-bit S-box
row
column
00 01 10 11
0 1
10 01 11 00 00 10 01 11
Sbox(abc) is element in row a column bc
 Sbox(abc) is element in row a column bc
Example: Sbox(010) = 11  Example: Sbox(010) = 11
Part 1  Cryptography 231
Ryszard Janicki
Linear and Differential Cryptanalysis 9/41

Operator ‘XOR’: ⊕ – Repetition
Formally,forallx,y∈{,1}:x⊕y=x+y mod2,i.e: 0⊕0=0
0⊕1=1 1⊕0=1 1⊕1=0
Fundamental property used in cryptography:
(x ⊕ y) ⊕ y = x Interpretation: x – plaintext, y – key
Ryszard Janicki
Linear and Differential Cryptanalysis 10/41

 Suppose a cipher has 3-bit to 2-bit S-box
Differential Cryptanalysis II (One Round Attack)
row
0 1
column
00 01 10 11
10 01 11 00 00 10 01 11
SupposeX =110,X =010,K=011 12
 Sbox(abc) is element in row a column bc
ThenX ⊕K=101andX ⊕K=001
 Example: Sbox(0110) = 11 2
Sbox(X1 ⊕ K) = 10 and Sbox(X2 ⊕ K) = 01
Part 1  Cryptography 231 Suppose
Unknown key: K
Known inputs: X = 110, X = 010
Known outputs: Sbox(X ⊕ K) = 10, Sbox(X ⊕ K) = 01
Know X ⊕ K ∈ {000, 101}, X ⊕ K ∈ {001, 110} Since (X ⊕ K ) ⊕ X = K , we conclude that
K ∈{110,011}∩{011,100} =⇒ K =011
Attacking one S-box in one round of DES does not appear to
be particularly useful.
In addition, the attacker will not know the input to any round
except for the first, and the attacker will not know the output of any round but the last.
Ryszard Janicki
Linear and Differential Cryptanalysis 11/41

Differential Cryptanalysis III
We deal with input and output differences Suppose we know inputs X and X
For X the input to S-box is X ⊕ K
For X the input to S-box is X ⊕ K
Key K is unknown
Input difference: (X ⊕K)⊕(X ⊕K)=X ⊕X
Input difference is independent of key K
Output difference: Y ⊕ Y is (almost) input difference to next round
Goal is to “chain” differences through rounds
If we obtain known output difference from known input difference. . .
May be able to chain differences thru rounds
It’s OK if this only occurs with some probability If input difference is 0. . .
. . . output difference is 0
Allows us to make some S-boxes “inactive” with respect to differences
Ryszard Janicki
Linear and Differential Cryptanalysis 12/41

Differential Cryptanalysis IV
Table 6.6: S-box Difference Analysis
Input difference 000 not interesting
Input difference 010 always gives output difference 01
More biased, the better (for Trudy)
Xi®X2
000 001 010 011 100 101 110 111
Sbox(Xi) Θ Sbox(X2) 00 01 10 11 8 0 0 0 0 0 4 4 0 8 0 0 0 0 4 4 0 0 4 4 4 4 0 0 0 0 4 4 4 4 0 0
Interpretation of the above table: If X1 ⊕ X2 = 000 then Sbox(X ) ⊕ SBox(X ) = 00 eight (8) times i.e. always, if
1 For2any S-box, an input difference of 000 is not interesti X ⊕ X = 001vatlhuesnaSrebtohxe(sXam)e⊕anSdBthoex(SX-bo)x=is 1″i0nafcotiuvre”ti(mweitsh respect t
1212
since the output values must be the same.3For the example
and Sbox(X1) ⊕ SBox(X2) = 11 also 4 times (8 = 2 is
an input difference of 010 always gives an output of 01, whic
always total), etc.
biased possible result. And, as noted in equation (6.12), by Differential cryXp\taθnaΧl2ys=is0o1f0,DthEeSaicstufalirilnypuctodmifpfelrexn.ce to the S-box would
the key K drops out of the difference.
We will illustrate it using a scaled-down version of DES that
we call Tiny DES, or TDES.
Differential cryptanalysis of DES is fairly complex. To illust
nique more concretely, but without all of the complexity inh
we’ll present a sc
Ryszard Janicki
aled-down version of DES that we call Tiny D
Linear and Differential Cryptanalysis 13/41
n o
h s
e E

Linear Cryptanalysis I
Like differential cryptanalysis, we target the nonlinear part of the cipher
But instead of differences, we approximate the nonlinearity with linear equations
For DES-like cipher we need to approximate S-boxes by linear functions
How well can we do this?
Ryszard Janicki
Linear and Differential Cryptanalysis 14/41

Differential Cryptanalysis
Linear Cryptanalysis II
0⊕0=0 0⊕1=1 1⊕0=1 1⊕1=0
 Suppose a cipher has 3-bit to 2-bit S-box
row
column
00 01 10 11
0 1
10 01 11 00 00 10 01 11
 Sbox(abc) is element in row a column bc Input x0x1x2 means x0 is row and x2x3 is column, where xi are bits.
 Example: Sbox(010) = 11 Input x0x1x2 ⇒ output y0y1, i.e. 000 ⇒ 10, 110 ⇒ 01, etc.
Examples of linear equationsP:art 1  Cryptography 231 Always y0 = x0 ⊕ x2 ⊕ 1
y1 = x1 with probability 0.75
y0 ⊕ y1 = x1 ⊕ x2 with probability 0.75
Each equations describes linear properties of yi ’s (outputs) by linear properties of xi ’s (inputs)
Finding all linear equations for real S-Boxes of DES is tedious and not easy task, but it has been done in 1993.
Ryszard Janicki
Linear and Differential Cryptanalysis 15/41

Inputx x x meansx isrow 012 0
XI
X0 ®Xl X0®X2 Xl®X2 ΙθΦΐΐ® Χ2
 Sbox(abc) is element in row a column bc
and x x is column. 23
 Example: Sbox(010) = 11
Input x0x1x2 ⇒ output y0y1,
Part 1  Cryptography 231
i.e. 000 ⇒ 10, 110 ⇒ 01, etc.
How to interpret S-box Linear Analysis table?
Consider values of x ,x ,x ,y ,y . There are 25 = 8 possible cases.
0 T1he2res0ults1 in Table 6.7 show that, for example, yo =
The table representpsrtohbeabfiulintycti1onand yo φ y\ = x\ Θ X2 with probability 3/4. f(column,row)su=chnausmthbiesr, oinfotiumreasnathlyastiscwoleumcan=reprloawce the S-boxes by
Table 6.7: S-box Linear Analysis
 Suppose a cipher has 3-bit to 2-bit S-boSx-box Linear Analysis:
S-box:
output bits
input bits 2/0 2/1 2/o Θ 2/1
0444 x0 444
row
column
00 01 10 11
0 1
10 01 11 00 00 10 01 11
Χχ
4 6 2 444 422 0 4 4 4 6 6 462
The result is that, in effect, we’ve traded the nonlinear
Forexampley0 =x0⊕x2 neverhappenssof(y0,x0⊕x2)=0,
equations, where the linear equations do not hold with cert
which means that in this case y0 = x0 ⊕ x2 ⊕ 1 always happens!
the equations hold with some nontrivial probability.
Theequalitiesy1 =x1 andy0⊕y1 =x1⊕x2 occur6times,i.e.
For these linear approximations to be useful in attacki
their probability is 6/8 = 0.75.
such as DES, we’ll try to extend this approach so that w
The number 4 means 4/8 = 0.5, so the it can be interpreted as
equations for the key. As with differential cryptanalysis,
random, but values 0, 2 and 6 are valuable for potential attacks!
“chain” these
Ryszard Janicki
results through multiple rounds.
Linear and Differential Cryptanalysis 16/41
How well can we approximate a DES S-box with linear
U
S a
n
e w

Linear Cryptanalysis III
Consider a single DES S-box
Let Y = Sbox(X)
Suppose y3 = x2 ⊕ x5 with high probability
I.e., a good linear approximation to output y3
Can we extend this so that we can solve linear equations for the key?
As in differential cryptanalysis, we need to “chain” thru multiple rounds
DES is linear except for S-boxes
How well can we approximate S-boxes with linear functions?
DES S-boxes designed so there are no good linear approximations to any one output bit
But there are linear combinations of output bits that can be approximated by linear combinations of input bits
Ryszard Janicki
Linear and Differential Cryptanalysis 17/41

Linear and Differential Cryptanalysis
As with differential cryptanalysis, the linear cryptanalysis of DES is complex.
To illustrate a linear attack, we’ll next describe TDES, a scaled-down DES-like cipher.
Then we’ll perform differential and linear cryptanalysis on TDES.
Ryszard Janicki
Linear and Differential Cryptanalysis 18/41

Tiny DES (TDES)
Tiny DES (TDES)
 A much simplified version of DES o 16 bit block
o 16 bit key
o 4 rounds
o 2 S-boxes, each maps 6 bits to 4 bits o 12 bit subkey each round
 Plaintext = (L0, R0)
 Ciphertext = (L4, R4)
 No useless junk
Part 1  Cryptography 245
Ryszard Janicki
Linear and Differential Cryptanalysis 19/41

One Round of TDES
Ryszard Janicki
Linear and Differential Cryptanalysis 20/41

TDES Functional Facts
 TDES is a Feistel Cipher
 (L0,R0) = plaintext
 For i = 1 to 4
Li = Ri-1
Ri = Li-1  F(Ri-1, Ki)
 Ciphertext = (L4,R4)
 F(Ri-1, Ki) = Sboxes(expand(Ri-1)  Ki)
where Sboxes(x0x1x2…x11) = (SboxLeft(x0x1…x5), SboxRight(x6x7…x11))
Part 1  Cryptography 247
Ryszard Janicki
Linear and Differential Cryptanalysis 21/41
TDES Fun Facts

TDES Key Schedule
TDES Key Schedule
 Key: K = k0k1k2k3k4k5k6k7k8k9k10k11k12k13k14k15  Subkey
o Left: k0k1…k7 rotate left 2, select 0,2,3,4,5,7
o Right: k8k9…k15 rotate left 1, select 9,10,11,13,14,15
 Subkey K1 = k2k4k5k6k7k1k10k11k12k14k15k8  Subkey K2 = k4k6k7k0k1k3k11k12k13k15k8k9  Subkey K3 = k6k0k1k2k3k5k12k13k14k8k9k10  Subkey K4 = k0k2k3k4k5k7k13k14k15k9k10k11
Part 1  Cryptography 248
Ryszard Janicki
Linear and Differential Cryptanalysis 22/41

TDES expansion permutation
 Expansion permutation: 8 bits to 12 bits r0r1r2r3r4r5r6r7
r4r7r2r1r5r7r0r2r6r5r0r3
 We can write this as expand(r0r1r2r3r4r5r6r7) = r4r7r2r1r5r7r0r2r6r5r0r3
Part 1  Cryptography 249
Ryszard Janicki
Linear and Differential Cryptanalysis 23/41
TDES expansion perm

Figure 6.8: One Round of Tiny DES
TDES S-Boxes (hexadecimal)
We denote the left TDES S-box by SboxLeft(X). In hexadecimal, this
We denote the left TDES S-box by SboxLeft(X). In hexadecimal, this box is
box is
X0X
Left TDES S-box: SboxLeft(X) X0X5 012 34567
89ABCDEF 89ABCDEF
5
(6.15) (6.15)
012 34567
69A34D7 8E12B5CF0
0
0 69A34D7 8E12B5CF0
19EBA45078632CD1F 19EBA45078632CD1F
2 81C2D3EF095A4B67 2 81C2D3EF095A4B67
39025AD6E18BC347F
39025AD6E18BC347F hereas the right S-box, SboxRight (X), is
Right TDES S-box: SboxRight(X) hereas the right S-box, SboxRight (X), is
:ΕΙ:Τ2:Τ3:Τ4
:ΕΙ:Τ2:Τ3:Τ4
Z0Z5012 3456789,4.BC.D£F
Z0Z5012 3456789,4.BC.D£F 0C50AE728D4396F1S
0C50AE728D4396F1S 1 1C963££2F84 5DA07
1 1C963££2F84 5DA07 2FAE6D824179035BC
2FAE6D824179035BC 3 0 A 3 C 8 2 1 £7 9 7 F 6 B 5 D A
(6.16) (6.16)
3 0 A 3 C 8 2 1 £7 9 7 F 6 B 5 D A
s with DES, each row in a TDES S-box is a permutation of the hexadecimal
s with DES, each row in a TD
E
S
S
gits 0,1,2,…,E,F.
R
x
i
ys
zard
J

a
b
ni
o
ck
i
sa
p
e
r
m
u
t
a
t
i
o
n
o
Lin
f
t
h
e
h
exadecimal
ea
r
a
nd
Di
ff
er
e
n
ti
al C
ry
pt
a
na
lys
is
24/41
– –
i
igits 0,1,2,…,E,F.

Differential Cryptanalysis of TDES
Our differential attack on TDES will focus on the right S-box First we tabulate SboxRight(X1) ⊕ SboxRight(X2) for all pairs
X1 and X2, where X1 ⊕ X2 = 001000
We find that
X1 ⊕ X2 = 001000 =⇒ SboxRight(X1) ⊕ SboxRight(X2) = 0010 with probability 0.75
Recall that any S-box
X1 ⊕ X2 = 000000 =⇒ SboxRight(X1) ⊕ SboxRight(X2) = 0000 ThisisbecauseX1⊕X2 =000000 =⇒ X1 =X2
Our goal is to make use of these observations to develop a viable differential attack on TDES.
Select plaintext blocks P = (L, R) and P ̃ = (L ̃, R ̃) such that P ⊕ P ̃ = 0000 0000 0000 0010 = 0x0002
Sincefortwobitsx,y:x=y ⇐⇒ x⊕y=0,thenPandP ̃ differ in exactly one bit.
Ryszard Janicki
Linear and Differential Cryptanalysis 25/41

If Y1 ⊕ Y2 = 001000 then with probability 0.75 SboxRight(Y1) ⊕ SboxRight(Y2) = 0010
Y1 ⊕Y2 = 001000 =⇒ (Y1 ⊕K)⊕(Y2 ⊕K) = 001000 If Y1 ⊕ Y2 = 000000 then for any S-box, we have
Sbox(Y1) ⊕ Sbox(Y2) = 0000
Difference of (0000 0010) is expanded by TDES expand perm to difference (000000 001000)
Recall F(X,K) = Sboxes(expand(X) ⊕ K), where Sboxes(x0x1 . . . x11) = (SboxLeft(x0 . . . x5), SboxRight(x6 . . . x11))
Hence, If X1 ⊕ X2 = 0000 0010 then
F(X1,K)⊕F(X2,K) = 0000 0010 with probability 0.75, no matter what the value of K is!
The bottom line? With probability 0.75 . . .
Input to next round is the same as current round
So we can chain through multiple rounds
Ryszard Janicki
Linear and Differential Cryptanalysis 26/41

with probability (3/4) = 9/16 = 0.5625. The results given in Table 6.8 for
R3 Θ R3 and Ri ® R4 are obtained in a similar manner. We select plaintext blocks P and P ̃ such that
P ⊕ P ̃ = 00
sis of TDES
T
a
ble
6
0
al
C
ry
p
ta
n
a
ly
0
00
.8
0
:
D
0
0
if
0
fe
0
re
n
ti
L2 = Ri R2 =
L3 =R2 R3=L2®F{R2,K3)
Li = Rs
Ri = L3®F{R3,K4)
L2 = i?l R2 =
L3 =-R2 R3 =
Li®F{Ri,K2) L2®F{R2,K3)
Li®F{Ri,K2)
Li = A3 Ri=L3®F{R3,K4)
0x0002 (3/4) {Li, R4) ® {L4, R4) = 0x0202 (3/4)3
0
0
0
1
Then we have (C and C ̃ are ciphertexts derived from P and P ̃):
{LQ,RQ) = P
Li = Ro Ri=L0®F{Ro,Ki)
{L0,Ro) = P
Li = R0 Ri=L0®F{Ro,Ki)
P®P = 0x0002 {Li, Ri) ®{Li,Ri)=
{L2,R2)®{L2,R2) {L3, R3) ®{L3,R3)=
Prob. 0x0202 3/4
= 0x0200 (3/4)2
2
0
=
0
x
0
C= {Li,Ri) WehaveR4=L3⊕F(R3,K4),R ̃4=L ̃3⊕F(R ̃3,K4),L4=R3 and
C—{Li, Ri)
CΦC=0x0202
L ̃ =WeR ̃c.anHdeenricveRan=algLorit⊕hmF(frLom,KTa)b,leR ̃6.8=toL ̃re⊕coFve(rL ̃so,mKe)o,fatnhedun-
4343444344
known key bits. We’ll choose P ̃ and ̃P as in e ̃quation (6.19) and obtain the also: L3 =L3⊕F(L4,K4),L3 =L3⊕F(L4,K4).
corresponding ciphertext C and C. Since TDES is a Feistel cipher,
0
0
2
R4 = L ®F{R ,K ) a 334
Ryszard Janicki
nd R =L ®F{R,K). 4334
Linear and Differential Cryptanalysis 27/41

If C ⊕ C ̃ = 0000 0010 0000 0010 = 0x 0202, then we almost certainly have (L3, R3) ⊕ (L ̃3, R ̃3) = 0x0002 = 0000 0000 0000 0010 (see table on the previous slide), so we also almost certainly have L3 ⊕ L ̃3 = 0000 0000, i.e. L3 = L ̃3
SinceL3 =R4⊕F(L4,K4)andL ̃3 =R ̃4⊕F(L ̃4,K4),wehave R 4 ⊕ F ( L 4 , K 4 ) = R ̃ 4 ⊕ F ( L ̃ 4 , K 4 )
Notethatx1⊕y1 =x2⊕y2 =⇒ x1⊕x2 =y1⊕y2 (usethe rule (x ⊕ y) ⊕ y = x).
Hence: R4 ⊕R ̃4 =F(L4,K4)⊕F(L ̃4,K4). (††) Above only unknown is subkey K4. Can we recover some bits of it? Since
C ⊕ C ̃ = (L4, R4) ⊕ (L ̃4, R ̃4) = 0x0202 = 0000 0010 0000 0010,
we have L4 ⊕ L ̃4 = R4 ⊕ R ̃4 = 0000 0010
LetL =l l l l l l l l andL ̃ =l ̃l ̃l ̃l ̃l ̃l ̃l ̃l ̃. 4 01234567 4 01234567
Hencel =l ̃fori=0,…,5,7andl ̸=l ̃. ii 66
From (††) we have 0000 0010 =
(SboxLeft(l4l7l2l1l5l7 ⊕ k0k2k3k4k5k7), SboxRight(l0l2l6l5l0l3 ⊕
k13 k14 k15 k9 k10 k11 ))⊕
(SboxLeft(l ̃l ̃l ̃l ̃l ̃l ̃ ⊕k k k k k k ),SboxRight(l ̃l ̃l ̃l ̃l ̃l ̃ ⊕
472157 023457 026503 k13 k14 k15 k9 k10 k11 ))
Ryszard Janicki
Linear and Differential Cryptanalysis 28/41

Left S-box
From (††) we have 0000 0010 =
(SboxLeft(l4l7l2l1l5l7 ⊕ k0k2k3k4k5k7), SboxRight(l0l2l6l5l0l3 ⊕
k13 k14 k15 k9 k10 k11 ))⊕
(SboxLeft(l ̃l ̃l ̃l ̃l ̃l ̃ ⊕ k k k k k k ),SboxRight(l ̃l ̃l ̃l ̃l ̃l ̃ ⊕
472157 023457 k13 k14 k15 k9 k10 k11 ))
026503
Which means
0000 = SboxLeft(l4l7l2l1l5l7 ⊕ k0k2k3k4k5k7) ⊕
SboxLeft(l ̃l ̃l ̃l ̃l ̃l ̃ ⊕ k k k k k k ) 472157 023457
which holds for any choice of the bits k0k2k3k4k5k7, since l = l ̃ for all i ̸= 6.
ii
Therefore, we gain no information about the subkey K4 from the left S-box.
Ryszard Janicki
Linear and Differential Cryptanalysis 29/41

Right S-box
From (††) we have 0000 0010 =
(SboxLeft(l4l7l2l1l5l7 ⊕ k0k2k3k4k5k7), SboxRight(l0l2l6l5l0l3 ⊕
k13 k14 k15 k9 k10 k11 ))⊕
(SboxLeft(l ̃l ̃l ̃l ̃l ̃l ̃ ⊕ k k k k k k ),SboxRight(l ̃l ̃l ̃l ̃l ̃l ̃ ⊕
472157 023457 026503 k13 k14 k15 k9 k10 k11 ))
Which means
0010 = SboxRight(l0l2l6l5l0l3 ⊕ k13k14k15k9k10k11) ⊕
SboxRight(l ̃l ̃l ̃l ̃l ̃l ̃ ⊕ k k k k k k 026503 13 14 15 9 10 11
)
which must hold for the correct choice of subkey bits k13k14k15k9k10k11 and will only hold with some probability for an incorrect choice of these subkey bits
Since the right S-box and the bits of L4 and L ̃4 are known, we can determine the unknown subkey bits that appear in the above blue equation.
Ryszard Janicki
Linear and Differential Cryptanalysis 30/41

Table 6.9: Algorithm to Recover Subkey Bits
Algorithm to Recover Subkey K4 Bits
count[z] = 0, for i = 0,1,…, 63 for i = 1 to iterations
Choose P and P with P ΘP = 0x0002
Obtain corresponding C = CQC\ … C15 and C = coci… C15 if C Θ C = 0x0202 then
li —Ci and £; = Cj for i = 0,1,…, 7 for K = 0 to 63
if 0010== (SboxRight(444444 Θ K)
Θ SboxRight(444444 Θ K)) then
increment count[K] end if
next K end if
next i
Each time the for loop is executed, count[K] will be incremented
for the correct subkey bits, i.e. for K = k13k14k15k9k10k11, while for
Each time the for loop in Table 6.9 is executed, count[K] will be incre-
other indices K the count will be incremented with some probability.
mented for the correct subkey bits, that is, for K = k\zkuk\^kgkiokii, All K with maximal count[K] are possible (partial) K
while for other indices K the count will be incremented with some probability.
There may be more than one such maximum count, but with a Consequentlsyu,ffithceienmtanxuimubmercofuinttesraintidoincsa,tethpeosnsuibmlebesurbokfesyucvhaluceosu.ntTshsehreould be
may be morsemthaalln. one such maximum count, but with a sufficient number of
4
iterations, the number of such counts should
Ryszard Janicki
be small.
Linear and Differential Cryptanalysis 31/41

Experimental Results I
Choose 100 pairs P and P ̃ with P ⊕ P ̃ = 0x0002 Found 47 of these give C ⊕ C ̃ = 0x0202 Tabulated counts for these 47
Maximal x count of 47 for each
K ∈ {000001, 001001, 110000, 111000}
No other count exceeded 39
It implies that K4 is one of 4 values, that is, k13k14k15k9k10k11 ∈ {000001, 001001, 110000, 111000}
Which means k13k14k9k10k11 ∈ {00001, 11000} Actual key is K = 1010 1001 1000 0111, hence
k13k14k9k10k11 = 11000, as expected
The attacker does not know the key so Trudy must exhaustively search over the remaining 211 unknown key bits, and for each of these try both 00001 and 11000.
Ryszard Janicki
Linear and Differential Cryptanalysis 32/41

Experimental Results II
The total expected work to recover the entire key K by this method is about 211 encryptions
Plus the work required for the differential attack, which is insignificant in comparison.
As a result, we can recover the entire 16-bit key with a work factor of about 211 encryptions, which is much better than an exhaustive key search
Since an exhaustive search has an expected work of 215 encryptions.
This shows that a shortcut attack exists, and as a result TDES is insecure.
Ryszard Janicki
Linear and Differential Cryptanalysis 33/41

8/\
Linear Cryptanalysis
f TDES

R
XO
o
S-box is
right S-box, our linear cryptanalysis attack will focus on the left S-box (in hexadecimal notation):
8 LR
key
The linear cryptanalysis of TDES is simpler than the
Figure 6.8: One Round of Tiny DES
differential cryptanalysis.
Whereas the differential cryptanalysis of TDES focused on the
We denote the left TDES S-box by SboxLeft(X). In hexadecimal, this
X0X5 012 34567 89ABCDEF 0 69A34D7 8E12B5CF0 19EBA45078632CD1F
2 81C2D3EF095A4B67 39025AD6E18BC347F
(6.15)
whereas the right S-box, SboxRight (X), is :ΕΙ:Τ2:Τ3:Τ4
Z0Z5 0 1 2 3 Ry4szard5Jani6cki
L8inea9r an,d4Diff.erBentiCal Cr.ypDtana£lysiFs 34/41
7 2

We denote the left TDES S-box by SboxLeft(X). In hexadecimal, this
S-box is
The left S-box (in hexadecimal notation):
X0X5 012 34567 89ABCDEF 0 69A34D7 8E12B5CF0 19EBA45078632CD1F
2 81C2D3EF095A4B67 39025AD6E18BC347F
Notation:yyyy =SboxLeft(xxxxxx) whereas the right S-0bo1x,2 S3boxRight (X), i0s 1 2 3 4 5
(6.15)
for example, SboxLeft(0 0101 1) = 0101 :ΕΙ:Τ2:Τ3:Τ4
since x0x5 = 1 =⇒ x0x5 = 01,
Z0Z5012 3456789,4.BC.D£F
x1x2x3x4 = 5 =⇒ x1x2x3x4 = 0101, and 0C50AE728D4396F1S
y0y1y2y3 = 5 =⇒ y0y1y2y3 = 0101
1 1C963££2F84 5DA07
(6.16)
Note that in the above example y1 = x2 and y2 = x3! 2FAE6D824179035BC
It can be verified that each of the linear approximations 3 0 A 3 C 8 2 1 £7 9 7 F 6 B 5 D A
y1 = x2 and y2 = x3 hold with probability 0.75
As with DES, each row in a TDES S-box is a permutation of the hexadecimal
To develop a linear attack based on these equations, we must
digits 0,1,2,…,E,F.
be able to chain these results through multiple rounds
The TDES key schedule is very simple. The 16-bit key is denoted
Ryszard Janicki
Linear and Differential Cryptanalysis 35/41

Denote the plaintext by P = (L0, R0) and let R0 = r0r1r2r3r4r5r6r7.
Then expand(R0) = expand(r0r1r2r3r4r5r6r7) = r4r7r2r1r5r7r0r2r6r5r0r3
Recall F(R,K) = Sboxes(expand(R) ⊕ K), and K1 = k2k4k5k6k7k1k10k11k12k14k15k8
Hence the input to the left S-box in round one is: x0x1x2x3x4x5 = r4r7r2r1r5r7 ⊕ k2k4k5k6k7k1
i.e. x2 = r2 ⊕ k5 and x3 = r1 ⊕ k6.
Let y0y1y2y3 be the round-one output of the left S-box.
Since y1 = x2 and y2 = x3 hold with probability 0.75, then
y1 = r2 ⊕ k5 and y2 = r1 ⊕ k6 also hold with probability 0.75!
Ryszard Janicki
Linear and Differential Cryptanalysis 36/41

In TDES (as in DES) the output of the S-boxes is XORed with the bits of the old left half.
LetL =l l l l l l l l andR =r ̃r ̃r ̃r ̃r ̃r ̃r ̃r ̃ 0 01234567 1 01234567
Then the the output of the left S-box from round one is XORedwithl l l l toyieldr ̃r ̃r ̃r ̃,i.e. r ̃=y ⊕l for
i = 0, 1, 2, 3.
Since y1 = x2 and y2 = x3 hold with probability 0.75, then
y1 = r2 ⊕ k5 and y2 = r1 ⊕ k6 also hold with probability 0.75,
andalsor ̃ =r ⊕k ⊕l andr ̃ =r ⊕k ⊕l with 12512262
probability 0.75
An analogous result holds for subsequent rounds, where the specific key bits depend on the subkey Ki .
Hence, we can chain the linear approximation in equations y1 = x2 and y2 = x3 through multiple rounds.
This is illustrated by the table from the next slide.
01230123iii
Ryszard Janicki
Linear and Differential Cryptanalysis 37/41

6.4 LINEAR AND DIFFERENTIAL CRYPTANALYSIS 201
Li = R\ R2 =
L% = R2 R3 =
Li = R3 R4 =
L1®F(R1,K2) L2®F{R2,K3) L3®F{R3,K4)
P2®k6®k7, P2®k6®k7,
pi ®k5®k0
p i ®k5®k0 fa, pg®k7® k2
Linear cryptanalysis is a known plaintext attack, the attacker knows the plaintext P = p0p1 . . . p15 is and corresponding
Table 6.10: Linear Cryptanalysis of TDES
ciphertext C = c0c1 . . . c15
(L0,Ro) = (ρο-··Ρ7,Ρ8· •Pis) Bits 1 and 2 (numbered from 0)
Probability 1
3/4
3/4 (3/4)2
(3/4)2 (3/4)3
(3/4)3 (3/4)3
Li = Ro R1=L0®F(R0,K1)
Ρθ,Ριο
PiΘPio® fa, p2®pg®k6
PiΘPioΘ fa, p2®P9®k6
C = {L4,R4)
Pio ®k0®
Pio®ko® fa, p9®k7®k2
c\ = PioΘk0 Θ fa, c2 =pg®k7® k2 The final row in the table above follows from
L=cccccccc
It’s 4easy to0 im1 p2lem3en4t a5 li6ne7ar attack based on the results in Table 6.10.
We are given the known plaintexts P = P0P1P2 ■ ■ ■ P15 along with the corre- Moreover: c1 =p10 ⊕k0 ⊕k1 =⇒ k0 ⊕k1 =c1 ⊕p10 and
sponding ciphertext C = c®c\C2 .. .C15. For each such pair, we increment a c2=p9⊕k7⊕k2 =⇒k7⊕k2=c2⊕p9.
counter depending on whether
Hencek0⊕k1 =c1⊕p10 andk7⊕k2 =c2⊕p9 with
c\ Θ3Pio = 0 or ci Θ Pio = 1 probability (0.75) ≈ 0.42
and another counter dependRiynsgzarodnJawnichkei th
er Linear and Differential Cryptanalysis 38/41

k0⊕k1 =c1⊕p10 andk7⊕k2 =c2⊕p9 with probability (0.75)3 ≈ 0.42
Since c1, c2, p9, and p10 are all known, we have obtained some information about the key bits k0, k1, k2, and k7.
The attacker knows the plaintext P = p0p1 . . . p15 and the ciphertext C = c0c1 . . . c15
For each pair (P,C), we increment an appropriate counter dependingonwhetherc1⊕p10 =0orc1⊕p10 =1
And another counter depending on whether c2 ⊕ p9 = 0 or c2 ⊕ p9 = 1
Using 100 known plaintexts the following results were obtained:
c1 ⊕ p10 = 0 occurred 38 times c1 ⊕ p10 = 1 occurred 62 times c2 ⊕ p9 = 0 occurred 62 times c2 ⊕ p9 = 1 occurred 38 times
Weconcludedk0⊕k1 =c1⊕p10 =1and k7 ⊕k2 =c2 ⊕p9 =0
Ryszard Janicki
Linear and Differential Cryptanalysis 39/41

Weconcludedk0⊕k1 =1andk7⊕k2 =0
In this example, the actual key is K = 1010 0011 0101 0110,
Sok0⊕k1 =1andk7⊕k2 =0asitwasdeterminedviathe linear attack.
In this linear attack, we have only recovered the equivalent of two bits of information.
To recover the entire key K, we could do an exhaustive key search for the remaining unknown bits.
This would require an expected work of about 213 encryptions and the work for the linear attack, which is negligible in comparison.
Ryszard Janicki
Linear and Differential Cryptanalysis 40/41

To Build a Better Block Cipher. . .
To Build a Better Block Cipher…
 How can cryptographers make linear and differential attacks more difficult?
1. More rounds  success probabilities diminish with each round
2. Better confusion (S-boxes)  reduce success probability on each round
3. Better diffusion (permutations)  more difficult to chain thru multiple rounds
 Limited mixing and limited nonlinearity, means that more rounds required: TEA
 Strong mixing and nonlinearity, then fewer (but more complex) rounds: AES
Part 1  Cryptography 267
Ryszard Janicki
Linear and Differential Cryptanalysis 41/41