CS-381 Network Security
Week-5 Lecture-1
Data Encryption Standard
Dr. Razi Arshad
Outline
Data Encryption Standard (DES)
DES Key Schedule
DES Encryption and Decryption Process
Security of DES
DES History
In 1973, NBS (NIST) issued a public request for proposals
for a national cipher standard, which must be
Secure
Public
Easy to understand and validate
Available to all users
Efficient in hardware
Exportable
IBM submitted LUCIFER (Feistel). In 1977, it was adopted by
NBS (NIST) as DES (Data Encryption Standard, Federal
Information Processing Standard 46 (FIPS PUB 46))
In 1999, NIST indicated that triple DES be used
Overall Scheme of DES Encryption
• 64-bit input data goes through
initial permutation.
• Then 16 rounds of the same
iteration (round function is
applied)
• For each round, sub-key is
generated through key generation
module
• After 16 rounds of iterations, the
contents of L and R are swapped
and input to Inverse permutation.
• Finally, a 64-bit ciphertext is
done!
Input of DES
Data needs to be broken into 64-bit blocks; add
padding at the last message if necessary.
Example:
Secret key
A string of 64 bits long including 8 parity bits.
1 parity bit in each 8-bit byte of the key may be utilized
for error detection in key generation, distribution, and
storage
The bits can be used for parity check
DES Key Schedule
Steps for Generating Subkeys
64 bits of secret key are input to the key
generator, 8 parity bits are removed; So, DES
key has only 56 bits
Objective: Use these 56 bits to generate a
different 48 bit sub-key for each round of DES
PC1 is a P box where 8 parity bits are
removed with input of 64 bits key
56-bit output of PC1 is split into two 28 bit
keys which is input into shift registers C
and D
The contents are circularly shifted to left
by 1 or 2 bits (according to a shift table)
prior to each iteration
PC2 is also a P box which ignores certain
input bits and permutes to a 48-bit sub-key
DES Key Schedule
Subkey Generations
Given a secret key K of 64 bits long (includes 8
parity bits) by the sender
Permuted Choice 1 (PC1)
Shift Registers C and D
•
•
Permuted Choice 2 (PC2)
• PC2 is determined by the table below:
• Consider the following input X
The Keys for 16 Rounds
DES Encryption
Initial Permutation (IP)
IP is determined as the following table
It occurs before round one
Bits in the plaintext are moved as following,
e.g. bit 58 to bit 1, bit 50 to bit 2 and bit 42 to
bit 3, etc
Initial Permutation (IP): Example
• M=[00000001001000110100010101100111100010011010101111
00110111101111]=[0123456789ABCDEF]HEX
• IP(M)=[1100110000000000110011001111111111110000101010
101111000010101010]=[CC00CCFFF0AAF0AA]HEX
Thus
• L0=11001100000000001100110011111111=[CC00CCFF]HEX
• R0=11110000101010101111000010101010=[F0AAF0AA]HEX
• L0and R0is ready for iteration
DES Round Function
Operates on 32-bit units
32-bit → 48-bit expansion/permutation
(E table)
XOR with 48 bit subkey
S-box computation returns 32 bits
Round permutation (P)
Followed by Feistel XOR and swap
Single Round of DES
Computation of Round
Function F(R ,K ) i-1 i
Three types of boxes: E, S, P
R (32 bits) are passed to expansion permutation box E-
box
48 bits output of E-box is XORed to 48 bits sub-key and
result sent to S boxes
S boxes (S1, S2...S8) store a set of numbers; input 48 (=6×8)
bits used to look up numbers like a code book and 32 bits
output is sent to permutation box P
Permutation box P permutes 32 bit input producing a 32
bit output
E-box used in DES
The E-box expands 32 bits to 48 bits; it
changes the order of the bits as well as repeating
certain bits.
■ L 0 =11001100000000001100110011111111=[CC00CCFF] HEX
R 0 =11110000101010101111000010101010=[F0AAF0AA] HEX
E(R 0 )=[011110100001010101010101011110100001010101010101]
= [7A15557A1555]HEX
Substitution Boxes S
Have eight S-boxes which map 6 bits to 4 bits
Each S-box is actually 4 * 16 matrix
Outer bits 1 & 6 (row bits) select one rows
Inner bits 2-5 (col bits) are substituted
Result is 8 lots of 4 bits, or 32 bits
DES S-Boxes
P-box used in DES
• The P-box permutation is determined as below
which is a straight permutation; no bits are used
twice, and no bits are ignored.
L 1 = R 0 = 1 1 1 1 0 0 0 0 1 01 0 1 0 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 = [F 0 A A F 0 A A ] H E X
Round Outputs L i, Ri
L 0 = 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 = [ C C 0 0 C C F F ] H EX
R 0=11110000101010101111000010101010=[F0AAF0AA]HEX
L 1= 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 = [ F 0 A A F 0 A A ] H E X
R1=11101111010010100110010101000100=[EF4A6544]HEX
L 2 =11101111010010100110010101000100=[EF4A6544]HEX
R 2 =11001100000000010111011100001001=[CC017709]HEX
L 3 =11001100000000010111011100001001=[CC017709]HEX
R 3 = 1 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 = [A 2 5 C O B F 4 ] H E X
L 4=10100010010111000000101111110100=[A25COBF4]HEX
R 4=01110111001000100000000001000101=[77220045]HEX
L 5 =01110111001000100000000001000101=[77220045]HEX
R 5 = 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 = [8 A 4 F A 6 3 7 ] H E X
L 6 = 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 = [8 A 4 F A 6 3 7 ] H EX
R 6=11101001011001111100110101101001=[E967CD69]HEX
L 7 = 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 = [ E 9 6 7 C D 6 9 ] H EX
R 7 = 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 = [0 6 4 A B A 1 0 ] H E X
L 8 = 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 = [0 6 4 A B A 1 0 ] H E X
R 8=11010101011010010100101110010000=[D5694B90]HEX
Round Outputs Li,Ri
L 9=11010101011010010100101110010000=[D5694B90]HEX
R 9 = 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 = [2 4 7 C C 6 7 A ] H E X
L 10 = 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 = [2 4 7 C C 6 7 A ] HEX
R 1 0 = 1 0 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 0 0 1 0 = [B 7 D 5 D 7 B 2 ] H E X
L11=10110111110101011101011110110010=[B7D5D7B2]HEX
R11=11000101011110000011110001111000=[C5783C78]HEX
L12=11000101011110000011110001111000=[C5783C78]HEX
R12=01110101101111010001100001011000=[75BD1858]HEX
L13=01110101101111010001100001011000=[75BD1858]HEX
R13=00011000110000110001010101011010=[18C3155A]HEX
L 14 = 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 = [1 8 C 3 1 5 5 A ] H EX
R 1 4 = 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1 1 0 1 = [C 2 8 C 9 6 0 D ] H E X
L15=11000010100011001001011000001101=[C28C960D]HEX
R15=01000011010000100011001000110100=[43423234]HEX
L16=01000011010000100011001000110100=[43423234]HEX
R16=00001010010011001101100110010101=[0A4CD995]HEX
Inverse Initial Permutation
• IP-1 is determined using the following table:
Final Ciphertext
DES Decryption
DES Avalanche Effect
In any good cipher, any change in
the key or plaintext, no matter
how large or small, should change
approximately half the ciphertext
bits
Examples
(a) Change one bit in the
plaintext with the same key
(b) Change one bit in the key
with the same plaintext
After 3 or 4 rounds,
approximately half of the
ciphertext bits are changed.
After 16 rounds, a lot
of scrambling has taken
place.
Security of Data Encryption
Standard (DES)
Security of DES
■ DES was be broken in just 22 hours (EFF-
DES Cracker (Deep Cracker),1998)
■ 3DES with 2 keys & 3DES with 3 keys
make DES resistant to brute force attack
DES Options
Advent new algorithm
Use DES with multiple keys – No investment in new
software and hardware
Double DES
■ C=E k2 (E k1 (P))
■ P=D k1 (D k2 (C))
• Key Space = ?
• 256x256=2112
Triple DES with two keys
• 3DES with two keys is a relatively popular alternative
to DES and has been adopted for use in the key
management standards
■ C=E(K 1,D(K 2 ,E(K 1,P))) Key Space=
■ P=D(K 1,E(K 2 ,D(K 1,C))) 256x256=2112
Triple DES with three keys
• A number of Internet-based applications have adopted
three-key 3DES, including PGP and S/MIME
• C=E(K 3 ,D(K 2 ,E(K 1,P)))
• Key Space=
P=D(K 1,E(K 2 ,D(K 3 ,C)))
256x256x256=2168
Overview- DES
