L 13 Part 2 of DES Block Ciher Systems

Data Encryption Standard (DES)
General Notes:
 DES is by far the most popular private-key algorithm.
 It was published in 1975 and standardized in 1977.
 Expired in 1998.
4.1 Encryption
System Parameters:
! block cipher.
! 64 input/output bits.
! 56 bits of key.
Principle: 16 rounds of encryption.
28
Initial
Permutation
Final
Permutation
Encryption
16
Encryption
1
K
1
K
16
K
X Y
Figure 4.1: General Model of DES
29
4.1.1 Overview
f
32
32
32
L 0 R 0
Initial Permutation
IP(X)
Message X
64
64
f
32
32
32
L 1 R 1
L 15 R 15
K16
K1
Transform 1
Final Permutation
Key K
56
32
32
32
32
56
Cipher Y = DES (X) K
IP (R , L ) -1
16 16
L 16 R 16
48
48
Transform 16
round 1
round 16
Figure 4.2: The Feistel Network
30
4.1.2 Permutations
a) Initial Permutation IP.
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
X
1 50 58 64
1 2 40
IP(X)
Figure 4.3: Initial permutation
b) Inverse Initial Permutation IP??1 (nal permutation).
Note:
IP??1(IP(X)) = X.
4.1.3 Core Iteration / f-Function
General Description:
Li = Ri??1.
31
-1
IP (Z)
1
Z
40
Figure 4.4: Final permutation
Ri = Li??1  f(Ri??1; ki).
The core iteration is the f-function that takes the right half
of the output of the previous round and the key as input.
E bit table
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
S-boxes:
Contain look-up tables (LUTs) with 64 numbers ranging from 0 : : : 15.
Input: Six bit code selecting one number.
Output: Four bit binary representation of one number out of 64.
32
i-1
S 1 S 8
Permutation P
Ri
L i-1
Ri-1
Ki
page 75 in Stinson
confusion: obscures
ciphertext/cleartext
relationship
E(R )
f-function
Expansion
4
6 6
4
48
48
48
8 * 4 = 32
32
32
32
32
Diffusion: Spreading influence
of single bits
Figure 4.5: Core function of DES
33
Example:
S1
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S-Box 1
Input: Six bit vector with MSB and LSB selecting the row and four inner bits
selecting column.
b = (100101).
! row = (11)2 = 3 (forth row).
! column = (0010)2 = 2 (third column).
S1(37 = 1001012) = 8 = 10002.
Remark:
S-boxes are the most crucial elements of DES because they introduce a non-
linear function to the algorithm, i.e., S(a) XOR S(b) 6= S(a XOR b).
4.1.4 Key Schedule
Note:
7 1
P
7
64
1
P
P = parity bits
Figure 4.6: 64 bit DES block
34
In practice the DES key is articially enlarged with odd parity bits. These bits
are \stripped" in PC-1.
PC - 2
PC - 2
PC - 1
C0 D0
LS1 LS1
LS2 LS2
LS16 LS16
C16 D16
C1 D
64
1
K 16
K 1
28
28 28
48 28 28
48
28
56
56
56
K
Figure 4.7: DES key scheduler
The cyclic Left-Shift (LS) blocks have two modes of operation:
a) for LSi where i = 1; 2; 9; 16, the block is shifted once.
b) for LSi where i 6= 1; 2; 9; 16, the block is shifted twice.
35
Remark:
The total number of cyclic Left-Shifts is 4
1 + 12
2 = 28. As a results of this
C0 = C16 and D0 = D16.
4.2 Decryption
One advantage of DES is that decryption is essentially the same as encryption. Only the
key schedule is reversed. This is due to the fact that DES is based on a Feistel network.
Question: Why does decryption work essentially the same as encryption?
a) Find what happens in the initial stage of decryption!
(Ld
0; Rd
0) = IP(Y ) = IP(IP??1(R16; L16)) = (R16; L16).
(Ld
0; Rd
0) = IP(Y ) = (R16; L16).
Ld
0 = R16.
Rd
0 = L16 = R15.
b) Find what happens in the iterations!
What are (Ld
1; Rd
1) ?
Ld
1 = Rd
0 = L16 = R15.
substitute into the above equation to get:
Rd
1 = Ld
0  f(Rd
0; k16) = R16  f(L16; k16).
Rd
1 = [L15  f(R15; k16)]  f(R15; k16).
Rd
1 = L15  [f(R15; k16)  f(R15; k16)] = L15.
in general: Ld
i = R16??i and Rd
i = L16??i;
such that: Ld
16 = R16??16 = R0 and Rd
16 = R0.
c) Find what happens in the nal stage!
IP??1(Rd
16; Ld
16) = IP??1(L0; R0)
:=
IP??1(IP(X)) = X q.e.d.
36
f
32
32
32
Key K
56
32
32
32
32
f
32
32
32
Initial Permutation
IP
K16
K1
Transform 1
Transform 16
IP -1
Final Permutation
L 15 R15
d d
d
L 1 R1
d d
L 0 R0
d d
64
Cipher Y = DES(X)
X = DES (Y) = DES (DES(X))
-1 -1
56
64
PC-1
L 16 R16
48
48
64
d
Figure 4.8: Decryption of DES
37
Reversed Key Schedule:
Question: Given K, how can we easily generate k16?
k16 = PC2(C16;D16) = PC2(C0;D0) = PC2(PC1(k)).
k15 = PC2(C15;D15) = PC2(RS1(C16); RS1(D16)) = PC2(RS1(C0); RS1(D0)).
4.3 Implementation
Note:
One design criteria for DES was fast hardware implementation.
4.3.1 Hardware
Since permutations and simple table look-ups are fast in hardware, DES can be implemented
very eciently [AM97, page 362].
Fastest Implementation:
) 9 Gbit/s as 0:6 m technology ASIC [WPR+99] with 16 stage pipeline.
4.3.2 Software
Record: 130 Mbits/s by Biham [Bih97].
Typically: a few 10 Mbit/s.
4.4 Attacks
There have been two major points of criticism about DES from the beginning:
i) key size is too small,
ii) the S-boxes contained secret design criteria.
38
PC - 2
K
PC - 1
C 0 C 16 = D0 D16 =
RS1 RS1
D15 C 15
RS2 RS2
RS15 RS15
PC - 2
PC - 2
C 1 D
56
K 1 1
56
28
28 28
28 28
48
28
56
56
K 16
48 56
K 15
48
Figure 4.9: Reversed key scheduler for decryption of DES
4.4.1 Exhaustive Key Search
Known Plaintext Attack:
known: X and Y .
unknown: K, such that Y = DESk(X).
39
idea: test all 256 possible keys ! DESki(X) ?
=
Y ; i = 0; 1; : : : ; 256 ?? 1.
4.4.2 Dierential Cryptanalysis
Proposed by Biham/Shamir in 1990.
Principle:
To consider dierences in plain and ciphertext pairs and deduce the likelihood
of certain keys.
16-round DES requirements:
With chosen plaintext, 247 (X,Y) pairs are needed.
With known plaintext, 255 (X,Y) pairs are needed.
237 arithmetic operations are needed.
Since each (X,Y) pair is 128 bits long, large storage is needed which makes this attack
highly impractical!
Remark: The DES S-boxes are optimized against dierential cryptanalysis.
4.4.3 Linear Cryptanalysis
Proposed by Matsui in 1993 and presented at CRYPTO 94.
Principal:
To consider dierences in plain and ciphertext pairs and deduce the likelihood
of certain key bits.
The actual attack was implemented:
! with 243 known plaintexts, the key was recovered in 50 days.
! using 12 HP RISC workstations running at 99MHz.
Remark: The S-box design of DES is not optimized for this attack.
40
Date Proposed/implemented attack
1977 Die & Hellman, estimate cost of key search machine (underestimate)
1990 Biham & Shamir propose dierential cryptoanalysis (247 chosen ciphertexts)
1993 Mike Wiener proposes detailed hardware design for key search machine:
average search time of 36 h @ $100,000
1993 Matsui proposes linear cryptoanalysis (243 chosen ciphertexts)
Jun. 1997 DES Challenge I broken, distributed eort took 4.5 months
Feb. 1998 DES Challenge II{1 broken, distributed eort took 39 days
Jul. 1998 DES Challenge II{2 broken, key-search machine built by the
Electronic Frontier Foundation (EFF), 1800 ASICs, each with 24
search units, $250K, 15 days average (actual time 56 hours)
Jan. 1999 DES Challenge III broken, distributed eort combined with EFF s
key-search machine, it took 22 hours and 15 minutes.
Table 4.1: History of full-round DES attacks
4.5 DES Alternatives
There exists a wealth of other block ciphers. A small collection of as of yet unbroken ciphers
is:
Algorithm Year Inventor X/Y bits Key Core Operation
AES 2000+ ? 128 128/192/256 ?
Triple DES 64 112 S-box
IDEA 90/92 Lai/Massey 64 128 modulo arithmetic
Cast 93 Adams/Tavares 64 64 variable S-boxes
Safer 94 Massey 64 64/128 modulo arithmetic
41
For further reading, consult Chapters 13 and 14 in [Sch93].
42