1
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.5.19
Block ciphers-DES
DATA ENCRYPTION STANDARD
2
DES
? 1973,NBS solicits proposals for cryptosystems
for,unclassified” documents,
? 1974,NBS repeats request,
IBM responds with modification of LUCIFER,
NBS asks NSA to evaluate,
IBM holds patent for DES,
? 1975,details of the algorithm published,public
discussion begins,
? DES became a federal standard in November 76
– NBS (NIST) hardware standard in January 77
– ANSI X3.92-1981 (hardware + software)
– ANSI X3.106-1983 (modes of operation)
– Australia AS2805.5-1985
3
DES
? 1983,no problem,First publicly available
algorithm certified by NSA as secure,Certificate
to be renewed every 5 years,
? 1987,passed,but
– NSA says that DES soon will be vulnerable to brute-
force attack,This is the last time,
– Business lobbies to keep it,since so the had much
invested,
? 1993,still passed (no alternatives),
? 1997,call for proposals,AES,
4
DES Design Controversy
? Originally designed to be efficient in hardware,
A LOT of money has been invested in hardware,
? although DES standard is public there was
considerable controversy over design
– in choice of 56-bit key (vs Lucifer 128-bit)
– and because design criteria were classified
? subsequent events and public analysis show in
fact design was appropriate
? DES has become widely used,especially in
financial applications
5
DES Standard
? Cipher Iterative
Action,
– Input,64 bits
– Key,48 bits
– Output,64 bits
? Key Generation
Box,
– Input,56 bits
– Output,48 bits
One round (Total 16 rounds)
6
Feistel Networks
f1,…,fk, {0,1}n ? {0,1}n
? Arbitrary functions
? Not necessarily
invertible
f1 ?
f2 ?
fk-1 ?
fk ?
L0, R0,
L1, R1,
Lk-2, Rk-2,
Lk-1, Rk-1,
Lk, Rk,
n bits n bits
Ro
un
d 1
Ro
un
d 2
Ro
un
d k
-1
Ro
un
d k
…
Li = Ri-1
Ri = Li-1 ? fi(Ri-1)
7
Inverting a Feistel Network
f1 ?
f2 ?
fk-1 ?
fk ?
L0, R0,
L1, R1,
Lk-2, Rk-2,
Lk-1, Rk-1,
Lk, Rk,
… Li-1 = Ri ? fi(Li)
Ri-1 = Li
Theorem
For any f1,…,fk, {0,1}n ? {0,1}n,
a Feistel network computes a
permutation p, {0,1}n ? {0,1}n
Inverse,
8
Feistel Cipher Design Principles
? block size
– increasing size improves security,but slows cipher
? key size
– increasing size improves security,makes exhaustive
key searching harder,but may slow cipher
? number of rounds
– increasing number improves security,but slows
cipher
? subkey generation
– greater complexity can make analysis harder,but
slows cipher
? round function
– greater complexity can make analysis harder,but
slows cipher
? fast software en/decryption & ease of analysis
– are more recent concerns for practical use and testing
9
Inside DES
DES is a Feistel network with
– 16 rounds
– 64 bit cleartext blocks
– 56 bits key
– f1,…,f16 derived from key
– Initial permutation p (public)
– Decryption
? Apply f16,…,f1 (in reverse order)
? Same chip
cleartext
ciphertext
16-round
Feistel
Network
p
p-1
key 64
64
64
64
56
10
Inside DES
? x0 = IP(m) = L0R0,
? 16 Rounds,i = 1,2,…,16,
Li,= Ri-1,
Ri,= Li-1 ? f (Ri-1,Ki),where
f (Ri-1,Ki) = P(S(E(Ri-1) ? Ki)),
with operations E (expansion),
S (S-box lookup),and P some
(permutation),
? c = IP-1(L16R16),
11
? x0 = IP(m) = L0R0
Initial Permutation
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
Initial Permutation
12
Rounds of Confusion and
Diffusion
Initial Permutation Strip Parity (56 bits)
Key (64 bits)
Round 1
Round 2
Round 16
Reverse Permutation
Plaintext Block (64 bits)
Ciphertext Block (64 bits)
13
14
One Round of DES
Expansion Permutation
48
P-Box Permutation
S-Box Substitution
32
Shift Shift
48
Compression
Permutation
Feistel
Network
56
32
32
Keyi-1 Ri-1 Li-1
Keyi Ri Li
32
32 56
15
Round function
The round function is,
g([Li-1,Ri-1 ]),Ki ) = (Li,Ri),
where
Li = Ri-1 and Ri = Li-1 ? f (Ri-1,Ki ),
16
f function
x 32
E
E(x)48
ki 48
B1(1-6)
f(x,ki)32
S1
C1(1-4)
B2(7-12)
S2
C2
B3
S3
C3
B4
S4
C4
B5
S5
C5
B6
S6
C6
B7
S7
C7
B8(42-48)
S8
C8(28-32)
+
P
17
f function
Combine 32 bit input and 48 bit key into 32 bit output
? Expand 32 bit input to 48 bits
? XOR the 48 bit key with the expanded 48 bit input
? Apply the S-boxes to the 48 bit input to produce 32
bit output
? Permute the resulting 32 bits
18
Expansion
?f (Ri-1,Ki) = P(S(E(Ri-1) ? Ki))
Expansion E,
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
19
S Boxes
? f (Ri-1,Ki) = P(S(E(Ri-1) ? Ki))
? There are 8 different S-Boxes,1 for each chunk
? S-box process maps 6 bit input to 4 bit output
? S box performs substitution on 4 bits
? There are 8 possible substitutions in each S box
? Inner 4 bits are fed into an S box
? Outer 2 bits determine which substitution is used
20
S-Box
? 48 bits ==> 32 bits,(8*6 ==> 8 *4)
? 2 bits used to select amongst 4
permutations for the rest of the 4-bit
quantity
2 bits
row
S i
i = 1,…8,
I1
I2
I3
I4
I5
I6
O1
O2
O3
O4
4 bits
column
21
S Boxes
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111
01 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000
10 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000
11 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101
Use bits 1 & 6 to select the row
Bits 2-5 to select the substitution
22
? Properties of S-boxes in DES (per NSA)
– Each S-box has 6 input bits and 4 output bits,This
was the largest that could be put on one chip back in
1974,
– All rows of all the S-boxes are permutations of 0,1,…,
15
– S-Boxes are not affine transformations of their input
– Change in an input bit changes at least two output
bits of the S-box
– For any x and any S-box S,S(x),S(x ?001100)
differs by at least two bits
S Boxes
23
Permutation
? f (Ri-1,Ki) = P(S(E(Ri-1) ? Ki))
P fixed permutation
16 7 20 21 29 12 28 17
1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9
19 13 30 6 22 11 4 25
? Result,bitstring of length 32!!
24
Per-Round Key Generation
28 bits 28 bits
48 bits
Ki
One
round
Circular Left Shift Circular Left Shift
28 bits 28 bits
Permutation
with Discard
Initial Permutation of DES key
C i-1 D i-1
C i D i
Round 1,2,9,16,
single shift
Others,two bits
25
Key schedule
? Key schedule K1,K2,…,K16
? Discard the parity-check bits of K,
? Compute PC-1(K) = C0D0,
where PC-1 is a fixed permutation,
C0,D0 left and right halves,28-bit each,
? For i = 1,2,…,16,
Ci,= LSi(Ci-1),Di,= LSi(Di-1),
where LSi left cyclic shift of one
(i= 1,2,9,16) or two positions (else),
Ki,= PC-2(CiDi),
PC-2 fixed permutation selecting 48 bits,
26
Key schedule
? PC-1(K) = C0D0
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
? Ki,= PC-2(Ci Di)
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
27
Final Permutations
The final permutation is the inverse of the initial
permutation
? c = IP-1(R16L16)
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
28
Decrypting DES
? How do we decrypt?,Decryption is performed by
exactly the same procedure,except that the keys
K1,…,K16 are used in reverse order,The reason
why this works is the following,
? The first decryption step takes R16L16 and gives
the output,[L16] [R16 ? f(L16,K16)],But we know
from the encryption procedure that,
L16 = R15; R16 = L15 ? f(R15,K16),Therefore,
[R15][L15 ]=[L16] [R16 ? f(R15,K16)] = [L16] [R16 ?
f(L16,K16)]
29
Decrypting DES
? Similarly,the second step of decryption sends
R15L15 to R14L14,Continuing we see that the
decryption process leads us back to R0L0 as
desired,
? Note that the encryption process is essentially the
same as the encryption process,Therefore both,
the sender and the receiver use a common key
and they can use identical machines,
30
Weak Keys
? If all the bits in each half are either 0 or 1,then the
key used for any cycle of the algorithm is the same
for all the cycles of the algorithm,
? There are 4 weak keys in the keyspace (256)
– *C0 = All zeros & D0 = All zeros
– C0 = All ones & D0 = All zeros
– C0 = All zeros & D0 = All ones
– C0 = All ones & D0 = All ones
* Co and Do are the 28 bit key halves
31
Weak Keys
? Additionally,some pairs of keys encrypt plaintext to the
identical ciphertext,these keys generate only two
different subkeys,Each of these subkeys is used eight
times in the algorithm,These keys are called
semiweak keys,There are 12 semi-weak keys,
? Some keys produce only four subkeys,each used four
times in the algorithm,There are 48 semi-weak keys,
? Before condemning DES for having weak keys,
consider that this list of 64 keys is minuscule compared
to the total set of 72,057,594,037,927,936 possible
keys,
32
Complement Keys
? If x’ is the complement of x,then the identity is as
follows,
? EK(P) = C ;
? EK’(P’) = C’,
? This property reduces the complexity of a brute-force
attack by a factor of two,
33
Algebraic Structure
If DES were closed,then for any K1 and K2
there would always be a K3 such that
EK2(EK1(P)) = EK3(P)
?In other words,the DES encryption operation
would form a group,and encrypting a set of
plaintext blocks with K1 followed by K2 would be
identical to encrypting the blocks with K3,
?It wasn’t until 1992 that cryptographers proved
that DES is not a group
34
Attacks on DES
? Attacks on DES
? 1977,Diffie & Hellman suggested a VLSI chip
that could test 106 keys/sec,A machine with 106
chips could test the entire key space in 10 hours,
Cost,$20,000,000,56-bit keys have 256 = 7.2 x
1016 values
? 1990,differential cryptanalysis,Eli Biham,Adi
Shamir (Israel),
? 1993,linear cryptanalysis,Mitsuru Masui (Japan),
35
Attacks on DES
? Exhaustive search
– Given plaintext m and ciphertext x,with high
probability there is a single key k s.t,
x = DES(m,k)
– Trying 106 keys/sec,it takes 2,000 years
? However …
– 1993,$106 homemade supercomputer breaks
DES in 7 hours (CPA)
? More sophisticated attacks
– Use properties (e.g,DES(m,k) = DES(m,k))
– Linear / differential crypto-analysis
36
DES variations
? Double DES,
– Use 2 keys,K1 and K2,
– Encryption is EK1(EK2(P))
– Is double DES reducible to DES? (Crypto 92)
? Triple DES
– Use 2 or 3 keys
– Encryption,
? EK1(EK2(EK3(P))))
? EK1(DK2(EK1(P))))
37
Avoiding Exhaustive Search–3DES
3DESk1,k2(m) = Ek1(Dk2(Ek1(m)))
? Key length,112 bits
? Very popular
DES
encryption
DES
decryption
1,TDEA encryption operation
O = EK3(DK2(EK1(m))),
2,TDEA decryption operation
O = DK1(EK2(DK3(c)))
1,K1,K2 and K3 are
independent keys;
2,K1 and K2 are independent
keys and K3 = K1;
3,K1 = K2 = K3,
38
2DES
2DESk1,k2(m) = Ek1( Ek2(m))
? Meet-in-the-middle attack!
? Effective key length is just 57 bits!
? Applies to any encryption algorithm
E m X D
X1
X2
X2 56
…
m1
m2
m2 56
…
Try all possible keys
=? For key length n,
total work is,only”
2n + 2n = 2n+1
39
Meet-in the middle attack
? Assume Eve has intercepted a message m and
a doubly encrypted ciphertext c = Ek2(Ek1(m)),
She wants to find k1 and k2,
? She first computes and stores Ek(m) for all
possible keys k,
? She then computes Dk(c) for all possible keys k,
? Finally she compares both lists,She knows as a
fact that there will be at least one match,since
the correct pair of keys should be one of them,
40
DESX
DESXk1,k2,k3(m) = k1 ? Ek2(m ? k3)
? DESX is a DES variant from RSA Data Security,
Inc,that has been included in the MailSafe
electronic mail security program since 1986 and
the BSAFE toolkit since 1987,
? Key length,56 + 2*64 = 184 bits
? However,effective key length is only about 100
bits
DES
encryption
41
International Data Encryption
Standard (IDEA)
? Developed in Switzerland,The first incarnation of the
IDEA cipher,by Xuejia Lai and James Massey,surfaced
in 1990, It was called PES (Proposed Encryption
Standard),
? IPES (Improved Proposed Encryption Standard),IDEA
(International Data Encryption Algorithm) in 1992
? 128 bit key,64 bit blocksize,8 rounds
? Current software implementations of IDEA are about
twice as fast as DES,
? used in Pretty Good Privacy (PGP)
42
IDEA Top View
Round 17
Round 1
Round 2
Round 16
key expansion
k5k6
64-bit Output
48-bit K1 64-bit Input 128-bit Key
…..,
k1k2k3k4
k49k50k51k52
43
IDEA Primitive Operations
? 2 16-bit to 1 16-bit
? ?
? + mod 216
? ? mod (216 + 1)
? reversible
44
Blowfish
? 1993 – Bruce Schneier
? Popular alternative to DES
? Variable length keys - 128 bits but up to 448 bits
? up to 16 rounds
? 64 bit blocksize
? used in many commercial software packages
45
RC5
? 1994 – Ron Rivest
– one of inventors of RSA public key algorithm
? RFC 2040
? good for either hard/software implementations
? fast
? adaptable to processors of different word sizes
? variable length keys,variable number of rounds
? low memory requirements
? intended for high security applications
? included in a number of RSA Data Securities products
46
Theory of Block Cipher Design
? Shannon’s principles of confusion and diffusion
remain the cornerstone of good block cipher design,
? Confusion serves to hide any relationship between the
plaintext,the ciphertext,and the key,Remember how
linear and differential cryptanalysis can exploit even a
slight relationship between these three things?
? Diffusion spreads the influence of individual plaintext or
key bits over as much of the ciphertext as possible,This
also hides statistical relationships and makes
cryptanalysis more difficult,
? product cipher,substitution-permutation network,
iterated block cipher
47
Theory of Block Cipher Design
? Feistel Networks:Most block algorithms are Feistel
networks,This idea dates from the early 1970s
? Simple Relations:If EK(P) = C,then Ef(K) (g(P,K)) =
h(C,K), where f,g,and h are simple functions,In a
good block cipher,there are no simple relations,
? Group Structure:When discussing an algorithm,the
question of whether it is a group arises,
? Weak Keys:In a good block cipher,all keys are
equally strong,Algorithms with a small number of
weak keys,like DES,are generally no problem,
? Strength against Differential and Linear
Cryptanalysis,
? S-Box Design,
48
Theory of Block Cipher Design
? Choosing good S-boxes,
? They should not be linear or affine,nor even close
to linear or affine,There should be a balance of
zeros and ones,and no correlations between
different combinations of bits,
? One property that seems very important is the
avalanche effect,The strict avalanche criteria
(SAC) guarantees that exactly half of the output
bits change when one input bit changes,
? 1,Choose randomly,
? 2,Choose and test,
? 3,Man-made,
? 4,Math-made,
49
Modes of Operation
? block ciphers encrypt fixed size blocks
? need way to use in practise,given you usually
have arbitrary amount of information to encrypt
? subsequently now have 5 for DES and AES
? have block and stream modes
? An algorithm for the cryptographic
transformation of data that features a symmetric
key block cipher algorithm,
50
Modes of operation
Five basic modes of operation are available for
block ciphers,
? Electronic codebook mode,ECB
? Cipher block chaining mode,CBC
? Cipher feedback mode,CFB
? Output feedback mode,OFB
? Counter Mode:CTR
51
Electronic Codebook mode,ECB
Each plaintext xi is encrypted with the same key K,
yi = eK(xi),
? The problem with ECB mode is that if a cryptanalyst has
the plaintext and ciphertext for several messages,he can
start to compile a code book without knowing the key,
? A more serious problem with ECB mode is that an
adversary could modify encrypted messages without
knowing the key,or even the algorithm,in such a way as
to fool the intended recipient,
52
ECB
x1 x2 x3 x4
y4 y3 y2 y1
DES DES DES DES
53
Cipher Block Chaining mode,CBC
Each cipher block yi-1 is xor-ed with the next plaintext
xi,
yi = eK(yi-1 XOR xi)
before being encrypted to get the next plaintext yi,
The chain is initialized with
an initialization vector,y0 = IV
with length,the block size,
? The IV need not be secret; it can be transmitted in
the clear with the ciphertext,
54
CBC
x1
+ + + +
IV
x2 x3 x4
y4 y3 y2 y1
DES DES DES DES
55
Cipher and Output feedback
modes (CFB & OFB)
CFB
y0 = IV and recursively,
zi = eK(yi-1) and yi = xi XOR zi
OFB
z0 = IV and recursively,
zi = eK(zi-1) and yi = xi XOR zi
56
CFB mode
IV eK
eK
y1
+
x1
eK
x2
y2
+
57
OFB mode
IV eK
eK
y1
+
x1 x2
y2
+
58
Counter Mode
? Block ciphers in counter mode use
sequence numbers as the input to the
algorithm,
xi-1 xi xi+1
Yi-1
ctr+i-1
Yi Yi+1
eK eK
ctr+i ctr+i+1
eK
59
Choosing a Cipher Mode
? If simplicity and speed are your main concerns,
ECB is the easiest and fastest mode to use a
block cipher,It is also the weakest,
? CBC is generally best for encrypting files,
? OFB is most often used in high-speed
synchronous systems where error propagation is
intolerable,OFB is also the mode of choice if
preprocessing is required,
? OFB is the mode of choice in a error-prone
environment,because it has no error extension,
60
References
? NIST fips-46-3 Data Encryption Standard
(DES); specifies the use of Triple DES
http://csrc.nist.gov/publications/fips/fips46-
3/fips46-3.pdf 1999.10
? NIST Special Publication 800-38A
Recommendation for Block Cipher Modes of
Operation Methods and Techniques 2001.12
? Block Ciphers,version 2.0,TR 601,August 2,
1995
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.5.19
Block ciphers-DES
DATA ENCRYPTION STANDARD
2
DES
? 1973,NBS solicits proposals for cryptosystems
for,unclassified” documents,
? 1974,NBS repeats request,
IBM responds with modification of LUCIFER,
NBS asks NSA to evaluate,
IBM holds patent for DES,
? 1975,details of the algorithm published,public
discussion begins,
? DES became a federal standard in November 76
– NBS (NIST) hardware standard in January 77
– ANSI X3.92-1981 (hardware + software)
– ANSI X3.106-1983 (modes of operation)
– Australia AS2805.5-1985
3
DES
? 1983,no problem,First publicly available
algorithm certified by NSA as secure,Certificate
to be renewed every 5 years,
? 1987,passed,but
– NSA says that DES soon will be vulnerable to brute-
force attack,This is the last time,
– Business lobbies to keep it,since so the had much
invested,
? 1993,still passed (no alternatives),
? 1997,call for proposals,AES,
4
DES Design Controversy
? Originally designed to be efficient in hardware,
A LOT of money has been invested in hardware,
? although DES standard is public there was
considerable controversy over design
– in choice of 56-bit key (vs Lucifer 128-bit)
– and because design criteria were classified
? subsequent events and public analysis show in
fact design was appropriate
? DES has become widely used,especially in
financial applications
5
DES Standard
? Cipher Iterative
Action,
– Input,64 bits
– Key,48 bits
– Output,64 bits
? Key Generation
Box,
– Input,56 bits
– Output,48 bits
One round (Total 16 rounds)
6
Feistel Networks
f1,…,fk, {0,1}n ? {0,1}n
? Arbitrary functions
? Not necessarily
invertible
f1 ?
f2 ?
fk-1 ?
fk ?
L0, R0,
L1, R1,
Lk-2, Rk-2,
Lk-1, Rk-1,
Lk, Rk,
n bits n bits
Ro
un
d 1
Ro
un
d 2
Ro
un
d k
-1
Ro
un
d k
…
Li = Ri-1
Ri = Li-1 ? fi(Ri-1)
7
Inverting a Feistel Network
f1 ?
f2 ?
fk-1 ?
fk ?
L0, R0,
L1, R1,
Lk-2, Rk-2,
Lk-1, Rk-1,
Lk, Rk,
… Li-1 = Ri ? fi(Li)
Ri-1 = Li
Theorem
For any f1,…,fk, {0,1}n ? {0,1}n,
a Feistel network computes a
permutation p, {0,1}n ? {0,1}n
Inverse,
8
Feistel Cipher Design Principles
? block size
– increasing size improves security,but slows cipher
? key size
– increasing size improves security,makes exhaustive
key searching harder,but may slow cipher
? number of rounds
– increasing number improves security,but slows
cipher
? subkey generation
– greater complexity can make analysis harder,but
slows cipher
? round function
– greater complexity can make analysis harder,but
slows cipher
? fast software en/decryption & ease of analysis
– are more recent concerns for practical use and testing
9
Inside DES
DES is a Feistel network with
– 16 rounds
– 64 bit cleartext blocks
– 56 bits key
– f1,…,f16 derived from key
– Initial permutation p (public)
– Decryption
? Apply f16,…,f1 (in reverse order)
? Same chip
cleartext
ciphertext
16-round
Feistel
Network
p
p-1
key 64
64
64
64
56
10
Inside DES
? x0 = IP(m) = L0R0,
? 16 Rounds,i = 1,2,…,16,
Li,= Ri-1,
Ri,= Li-1 ? f (Ri-1,Ki),where
f (Ri-1,Ki) = P(S(E(Ri-1) ? Ki)),
with operations E (expansion),
S (S-box lookup),and P some
(permutation),
? c = IP-1(L16R16),
11
? x0 = IP(m) = L0R0
Initial Permutation
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
Initial Permutation
12
Rounds of Confusion and
Diffusion
Initial Permutation Strip Parity (56 bits)
Key (64 bits)
Round 1
Round 2
Round 16
Reverse Permutation
Plaintext Block (64 bits)
Ciphertext Block (64 bits)
13
14
One Round of DES
Expansion Permutation
48
P-Box Permutation
S-Box Substitution
32
Shift Shift
48
Compression
Permutation
Feistel
Network
56
32
32
Keyi-1 Ri-1 Li-1
Keyi Ri Li
32
32 56
15
Round function
The round function is,
g([Li-1,Ri-1 ]),Ki ) = (Li,Ri),
where
Li = Ri-1 and Ri = Li-1 ? f (Ri-1,Ki ),
16
f function
x 32
E
E(x)48
ki 48
B1(1-6)
f(x,ki)32
S1
C1(1-4)
B2(7-12)
S2
C2
B3
S3
C3
B4
S4
C4
B5
S5
C5
B6
S6
C6
B7
S7
C7
B8(42-48)
S8
C8(28-32)
+
P
17
f function
Combine 32 bit input and 48 bit key into 32 bit output
? Expand 32 bit input to 48 bits
? XOR the 48 bit key with the expanded 48 bit input
? Apply the S-boxes to the 48 bit input to produce 32
bit output
? Permute the resulting 32 bits
18
Expansion
?f (Ri-1,Ki) = P(S(E(Ri-1) ? Ki))
Expansion E,
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
19
S Boxes
? f (Ri-1,Ki) = P(S(E(Ri-1) ? Ki))
? There are 8 different S-Boxes,1 for each chunk
? S-box process maps 6 bit input to 4 bit output
? S box performs substitution on 4 bits
? There are 8 possible substitutions in each S box
? Inner 4 bits are fed into an S box
? Outer 2 bits determine which substitution is used
20
S-Box
? 48 bits ==> 32 bits,(8*6 ==> 8 *4)
? 2 bits used to select amongst 4
permutations for the rest of the 4-bit
quantity
2 bits
row
S i
i = 1,…8,
I1
I2
I3
I4
I5
I6
O1
O2
O3
O4
4 bits
column
21
S Boxes
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111
01 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000
10 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000
11 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101
Use bits 1 & 6 to select the row
Bits 2-5 to select the substitution
22
? Properties of S-boxes in DES (per NSA)
– Each S-box has 6 input bits and 4 output bits,This
was the largest that could be put on one chip back in
1974,
– All rows of all the S-boxes are permutations of 0,1,…,
15
– S-Boxes are not affine transformations of their input
– Change in an input bit changes at least two output
bits of the S-box
– For any x and any S-box S,S(x),S(x ?001100)
differs by at least two bits
S Boxes
23
Permutation
? f (Ri-1,Ki) = P(S(E(Ri-1) ? Ki))
P fixed permutation
16 7 20 21 29 12 28 17
1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9
19 13 30 6 22 11 4 25
? Result,bitstring of length 32!!
24
Per-Round Key Generation
28 bits 28 bits
48 bits
Ki
One
round
Circular Left Shift Circular Left Shift
28 bits 28 bits
Permutation
with Discard
Initial Permutation of DES key
C i-1 D i-1
C i D i
Round 1,2,9,16,
single shift
Others,two bits
25
Key schedule
? Key schedule K1,K2,…,K16
? Discard the parity-check bits of K,
? Compute PC-1(K) = C0D0,
where PC-1 is a fixed permutation,
C0,D0 left and right halves,28-bit each,
? For i = 1,2,…,16,
Ci,= LSi(Ci-1),Di,= LSi(Di-1),
where LSi left cyclic shift of one
(i= 1,2,9,16) or two positions (else),
Ki,= PC-2(CiDi),
PC-2 fixed permutation selecting 48 bits,
26
Key schedule
? PC-1(K) = C0D0
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
? Ki,= PC-2(Ci Di)
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
27
Final Permutations
The final permutation is the inverse of the initial
permutation
? c = IP-1(R16L16)
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
28
Decrypting DES
? How do we decrypt?,Decryption is performed by
exactly the same procedure,except that the keys
K1,…,K16 are used in reverse order,The reason
why this works is the following,
? The first decryption step takes R16L16 and gives
the output,[L16] [R16 ? f(L16,K16)],But we know
from the encryption procedure that,
L16 = R15; R16 = L15 ? f(R15,K16),Therefore,
[R15][L15 ]=[L16] [R16 ? f(R15,K16)] = [L16] [R16 ?
f(L16,K16)]
29
Decrypting DES
? Similarly,the second step of decryption sends
R15L15 to R14L14,Continuing we see that the
decryption process leads us back to R0L0 as
desired,
? Note that the encryption process is essentially the
same as the encryption process,Therefore both,
the sender and the receiver use a common key
and they can use identical machines,
30
Weak Keys
? If all the bits in each half are either 0 or 1,then the
key used for any cycle of the algorithm is the same
for all the cycles of the algorithm,
? There are 4 weak keys in the keyspace (256)
– *C0 = All zeros & D0 = All zeros
– C0 = All ones & D0 = All zeros
– C0 = All zeros & D0 = All ones
– C0 = All ones & D0 = All ones
* Co and Do are the 28 bit key halves
31
Weak Keys
? Additionally,some pairs of keys encrypt plaintext to the
identical ciphertext,these keys generate only two
different subkeys,Each of these subkeys is used eight
times in the algorithm,These keys are called
semiweak keys,There are 12 semi-weak keys,
? Some keys produce only four subkeys,each used four
times in the algorithm,There are 48 semi-weak keys,
? Before condemning DES for having weak keys,
consider that this list of 64 keys is minuscule compared
to the total set of 72,057,594,037,927,936 possible
keys,
32
Complement Keys
? If x’ is the complement of x,then the identity is as
follows,
? EK(P) = C ;
? EK’(P’) = C’,
? This property reduces the complexity of a brute-force
attack by a factor of two,
33
Algebraic Structure
If DES were closed,then for any K1 and K2
there would always be a K3 such that
EK2(EK1(P)) = EK3(P)
?In other words,the DES encryption operation
would form a group,and encrypting a set of
plaintext blocks with K1 followed by K2 would be
identical to encrypting the blocks with K3,
?It wasn’t until 1992 that cryptographers proved
that DES is not a group
34
Attacks on DES
? Attacks on DES
? 1977,Diffie & Hellman suggested a VLSI chip
that could test 106 keys/sec,A machine with 106
chips could test the entire key space in 10 hours,
Cost,$20,000,000,56-bit keys have 256 = 7.2 x
1016 values
? 1990,differential cryptanalysis,Eli Biham,Adi
Shamir (Israel),
? 1993,linear cryptanalysis,Mitsuru Masui (Japan),
35
Attacks on DES
? Exhaustive search
– Given plaintext m and ciphertext x,with high
probability there is a single key k s.t,
x = DES(m,k)
– Trying 106 keys/sec,it takes 2,000 years
? However …
– 1993,$106 homemade supercomputer breaks
DES in 7 hours (CPA)
? More sophisticated attacks
– Use properties (e.g,DES(m,k) = DES(m,k))
– Linear / differential crypto-analysis
36
DES variations
? Double DES,
– Use 2 keys,K1 and K2,
– Encryption is EK1(EK2(P))
– Is double DES reducible to DES? (Crypto 92)
? Triple DES
– Use 2 or 3 keys
– Encryption,
? EK1(EK2(EK3(P))))
? EK1(DK2(EK1(P))))
37
Avoiding Exhaustive Search–3DES
3DESk1,k2(m) = Ek1(Dk2(Ek1(m)))
? Key length,112 bits
? Very popular
DES
encryption
DES
decryption
1,TDEA encryption operation
O = EK3(DK2(EK1(m))),
2,TDEA decryption operation
O = DK1(EK2(DK3(c)))
1,K1,K2 and K3 are
independent keys;
2,K1 and K2 are independent
keys and K3 = K1;
3,K1 = K2 = K3,
38
2DES
2DESk1,k2(m) = Ek1( Ek2(m))
? Meet-in-the-middle attack!
? Effective key length is just 57 bits!
? Applies to any encryption algorithm
E m X D
X1
X2
X2 56
…
m1
m2
m2 56
…
Try all possible keys
=? For key length n,
total work is,only”
2n + 2n = 2n+1
39
Meet-in the middle attack
? Assume Eve has intercepted a message m and
a doubly encrypted ciphertext c = Ek2(Ek1(m)),
She wants to find k1 and k2,
? She first computes and stores Ek(m) for all
possible keys k,
? She then computes Dk(c) for all possible keys k,
? Finally she compares both lists,She knows as a
fact that there will be at least one match,since
the correct pair of keys should be one of them,
40
DESX
DESXk1,k2,k3(m) = k1 ? Ek2(m ? k3)
? DESX is a DES variant from RSA Data Security,
Inc,that has been included in the MailSafe
electronic mail security program since 1986 and
the BSAFE toolkit since 1987,
? Key length,56 + 2*64 = 184 bits
? However,effective key length is only about 100
bits
DES
encryption
41
International Data Encryption
Standard (IDEA)
? Developed in Switzerland,The first incarnation of the
IDEA cipher,by Xuejia Lai and James Massey,surfaced
in 1990, It was called PES (Proposed Encryption
Standard),
? IPES (Improved Proposed Encryption Standard),IDEA
(International Data Encryption Algorithm) in 1992
? 128 bit key,64 bit blocksize,8 rounds
? Current software implementations of IDEA are about
twice as fast as DES,
? used in Pretty Good Privacy (PGP)
42
IDEA Top View
Round 17
Round 1
Round 2
Round 16
key expansion
k5k6
64-bit Output
48-bit K1 64-bit Input 128-bit Key
…..,
k1k2k3k4
k49k50k51k52
43
IDEA Primitive Operations
? 2 16-bit to 1 16-bit
? ?
? + mod 216
? ? mod (216 + 1)
? reversible
44
Blowfish
? 1993 – Bruce Schneier
? Popular alternative to DES
? Variable length keys - 128 bits but up to 448 bits
? up to 16 rounds
? 64 bit blocksize
? used in many commercial software packages
45
RC5
? 1994 – Ron Rivest
– one of inventors of RSA public key algorithm
? RFC 2040
? good for either hard/software implementations
? fast
? adaptable to processors of different word sizes
? variable length keys,variable number of rounds
? low memory requirements
? intended for high security applications
? included in a number of RSA Data Securities products
46
Theory of Block Cipher Design
? Shannon’s principles of confusion and diffusion
remain the cornerstone of good block cipher design,
? Confusion serves to hide any relationship between the
plaintext,the ciphertext,and the key,Remember how
linear and differential cryptanalysis can exploit even a
slight relationship between these three things?
? Diffusion spreads the influence of individual plaintext or
key bits over as much of the ciphertext as possible,This
also hides statistical relationships and makes
cryptanalysis more difficult,
? product cipher,substitution-permutation network,
iterated block cipher
47
Theory of Block Cipher Design
? Feistel Networks:Most block algorithms are Feistel
networks,This idea dates from the early 1970s
? Simple Relations:If EK(P) = C,then Ef(K) (g(P,K)) =
h(C,K), where f,g,and h are simple functions,In a
good block cipher,there are no simple relations,
? Group Structure:When discussing an algorithm,the
question of whether it is a group arises,
? Weak Keys:In a good block cipher,all keys are
equally strong,Algorithms with a small number of
weak keys,like DES,are generally no problem,
? Strength against Differential and Linear
Cryptanalysis,
? S-Box Design,
48
Theory of Block Cipher Design
? Choosing good S-boxes,
? They should not be linear or affine,nor even close
to linear or affine,There should be a balance of
zeros and ones,and no correlations between
different combinations of bits,
? One property that seems very important is the
avalanche effect,The strict avalanche criteria
(SAC) guarantees that exactly half of the output
bits change when one input bit changes,
? 1,Choose randomly,
? 2,Choose and test,
? 3,Man-made,
? 4,Math-made,
49
Modes of Operation
? block ciphers encrypt fixed size blocks
? need way to use in practise,given you usually
have arbitrary amount of information to encrypt
? subsequently now have 5 for DES and AES
? have block and stream modes
? An algorithm for the cryptographic
transformation of data that features a symmetric
key block cipher algorithm,
50
Modes of operation
Five basic modes of operation are available for
block ciphers,
? Electronic codebook mode,ECB
? Cipher block chaining mode,CBC
? Cipher feedback mode,CFB
? Output feedback mode,OFB
? Counter Mode:CTR
51
Electronic Codebook mode,ECB
Each plaintext xi is encrypted with the same key K,
yi = eK(xi),
? The problem with ECB mode is that if a cryptanalyst has
the plaintext and ciphertext for several messages,he can
start to compile a code book without knowing the key,
? A more serious problem with ECB mode is that an
adversary could modify encrypted messages without
knowing the key,or even the algorithm,in such a way as
to fool the intended recipient,
52
ECB
x1 x2 x3 x4
y4 y3 y2 y1
DES DES DES DES
53
Cipher Block Chaining mode,CBC
Each cipher block yi-1 is xor-ed with the next plaintext
xi,
yi = eK(yi-1 XOR xi)
before being encrypted to get the next plaintext yi,
The chain is initialized with
an initialization vector,y0 = IV
with length,the block size,
? The IV need not be secret; it can be transmitted in
the clear with the ciphertext,
54
CBC
x1
+ + + +
IV
x2 x3 x4
y4 y3 y2 y1
DES DES DES DES
55
Cipher and Output feedback
modes (CFB & OFB)
CFB
y0 = IV and recursively,
zi = eK(yi-1) and yi = xi XOR zi
OFB
z0 = IV and recursively,
zi = eK(zi-1) and yi = xi XOR zi
56
CFB mode
IV eK
eK
y1
+
x1
eK
x2
y2
+
57
OFB mode
IV eK
eK
y1
+
x1 x2
y2
+
58
Counter Mode
? Block ciphers in counter mode use
sequence numbers as the input to the
algorithm,
xi-1 xi xi+1
Yi-1
ctr+i-1
Yi Yi+1
eK eK
ctr+i ctr+i+1
eK
59
Choosing a Cipher Mode
? If simplicity and speed are your main concerns,
ECB is the easiest and fastest mode to use a
block cipher,It is also the weakest,
? CBC is generally best for encrypting files,
? OFB is most often used in high-speed
synchronous systems where error propagation is
intolerable,OFB is also the mode of choice if
preprocessing is required,
? OFB is the mode of choice in a error-prone
environment,because it has no error extension,
60
References
? NIST fips-46-3 Data Encryption Standard
(DES); specifies the use of Triple DES
http://csrc.nist.gov/publications/fips/fips46-
3/fips46-3.pdf 1999.10
? NIST Special Publication 800-38A
Recommendation for Block Cipher Modes of
Operation Methods and Techniques 2001.12
? Block Ciphers,version 2.0,TR 601,August 2,
1995
