Lecture 3 Dr.
Alshaimaa Abo-alian
Block Ciphers & the Data A_alian@[Link]
Encryption Standard (DES)
LECTURE OUTLINE
➢What is Block Cipher?
➢Feistel Cipher
➢Data Encryption Standard (DES)
➢DES properties and strength
2
What is Block Cipher?
▪ A block of plaintext is treated as a whole and used to
produce a ciphertext block of equal length.
▪ Typically, a block size of 64 or 128 bits is used.
▪ Most network-based symmetric cryptographic applications
make use of block ciphers.
▪ For the encryption to be reversible (i.e., for decryption to
be possible with no data loss), each must produce a unique
ciphertext block.
3
Reversible vs. Irreversible
Mapping
4
Feistel Cipher
▪ Feistel proposed that the ideal block cipher utilizes the concept of a
product cipher
–Consists two or more simple ciphers in sequence so that the result is
cryptographically stronger than any of the component ciphers.
➔ Confusion & Diffusion Concepts.
Remember:
In a strongly ideal cipher:
➢ all statistics of the ciphertext are independent of the particular key
used.
➢ statistical patterns in plaintexts are hidden (each plaintext digit
affect the value of many ciphertext digits)
5
Feistel Cipher
–The inputs to the encryption algorithm
are a plaintext block of length 2w
bits and a key K .
–The plaintext block is divided into
two halves, LE0 and RE0 .
–The two halves of the data pass
through n rounds of processing and
then combine to produce the
ciphertext block
–Each round i has as inputs LEi-1 and
REi-1 derived from the previous round,
as well as a subkey Ki derived from
the overall K .
–16 rounds are used, although any
number of rounds could be
implemented. 6
Feistel Cipher Parameters
1. Block size
Larger block sizes mean greater security but reduced
encryption/decryption speed for a given algorithm
2. Key size
Larger key size means greater security but may
decrease encryption/decryption speeds
3. Number of rounds
A single round offers inadequate security, but multiple
rounds offer increasing security
4. Subkey generation algorithm
Greater complexity in this algorithm should lead to
greater difficulty of cryptanalysis
5. Round function F
7
Data Encryption Standard
(DES)
▪ Issued in 1977 by the National Bureau of Standards (NBS;
now NIST)
▪ Also referred to as the Data Encryption Algorithm (DEA)
▪ Based on Feistel structure.
▪ In 1997, A machine called Deep Crack built to brute-force
DES in 56 hours.
▪ In 2001, NIST adopted the Advanced Encryption Standard
(AES) replacing DES as the official encryption standard
8
DES Features
– Block size = 64 bits
– Key size = 56 bits (in reality, 64 bits, but 8 are used as
parity-check bits for error control)
– Number of rounds = 16
– 16 intermediary keys (Subkeys) , each 48 bits
9
General Structure of DES
10
11
Initial and Final Permutation
Steps in DES
12
Initial Permutation (IP)
the first bit of the output is taken from the 58th bit of the
input; the second bit from the 50th bit, and so on, with the
last bit of the output taken from the 7th bit of the input.
13
Final Permutation (IP -1)
The final permutation is the inverse of the initial permutation; the
table is interpreted similarly.
The output of the IP-1 has bit 40 of the pre-output block as its first
bit, bit 8 as its second bit, and so on.
14
DES Rounds
DES has 16 rounds; each round is a
Feistel cipher
Li = Ri-1
Ri = Li-1⊕ f(Ri-1, Ki)
15
DES Mangler Function f(•)
E is an expansion
function which takes a
block of 32 bits as input
and produces a block of
48 bits as output
8 X 6 bits
8 X 4 bits
16
The Expansion (E) Permutation
Example:
R0 = 1111 0000 1010 1010 1111 0000 1010 1010
E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
17
S-BOXES
18
S-boxes
The S-boxes provides the real
confusion in DES
DES uses 8 different S-boxes,
each with 6-bit input and 4-
bit output.
The most significant bit (MSB)
and the least significant bit
(LSB) of each 6-bit input select
the row of the table
While the four inner bits select
the column.
19
20
Example (S1)
B = 110010
Row = (10)2 = 2
Column =(1001)2 = 9
S1 output = 12 = 1100
The S-boxes are the most crucial elements of DES because they
introduce a non-linearity to the cipher
𝑆 𝑎 ⊕ 𝑆 𝑏 ≠ 𝑆 (𝑎 ⊕ b)
21
Straight Permutation (P)
The final stage in the calculation of f is to do a
permutation P of the S-box output
22
DES Key Schedule (Subkey
Generation)
▪ The key schedule derives 16 round keys (subkeys) ki, each consisting
of 48 bits, from the original 56-bit key.
▪ However, the DES input key is often stated as 64-bit, where every 8th
bit is used as a parity bit over the preceding 7 bits.
✓ First, the parity bits are stripped in the
initial PC −1 permutation.
✓ The resulting 56-bit key is split into 2
halves C0 and D0
✓ The two 28-bit halves are cyclically
shifted (rotated) left by 1 or 2 bit
positions depending on the round i
23
DES Key Generation
Round Shift
1, 2, 9, 16 One bit
otherwise Two bits
24
Note That:
➢ We now form the keys Ki (for all 16 rounds), by applying
PC-2 permutation table to each of the concatenated pairs
Ci Di.
➢ PC −2 permutes the 56 input bits coming from Ci and Di
and ignores 8 of them (the resulting round key Ki is 48 bits)
➢ The total number of rotation positions is 4*1+12*2 = 28.
This leads to the interesting property that C0 = C16 and D0
= D16.
25
Example
Let M be the plaintext message and K be the secret key in
the binary format
M = 0000 0001 0010 0011 0100 0101 0110 0111
1000 1001 1010 1011 1100 1101 1110 1111
K = 00010011 00110100 01010111 01111001
10011011 10111100 11011111 11110001
26
Step 1: Key Schedule
Create 16 Subkeys, Each 48-bits.
The 64-bit key is permuted according to the following table, PC-1.
K = 00010011 00110100
01010111 01111001
10011011 10111100
11011111 11110001
After 56-bit permutation:
K+ = 1111000 0110011
0010101 0101111
0101010 1011001
1001111 0001111
27
Step 1: Key Schedule
Create 16 Subkeys, Each 48-bits.
Next, split this key into left and right halves, C0 and D0,
where each half has 28 bits.
From the permuted key K+ = 1111000 0110011 0010101
0101111 0101010 1011001 1001111 0001111
we get
C0 = 1111000 0110011 0010101 0101111
D0 = 0101010 1011001 1001111 0001111
Each part is shifted left (circular shift) one or two bits.
C1 = 1110000110011001010101011111 Round Shift
1, 2, 9, 16 One bit
D1 = 1010101011001100111100011110
otherwise Two bits 28
Step 1: Key Schedule
Create 16 Subkeys, Each 48-bits.
We applying the following PC-2
table to the concatenated pairs
C nDn
Each pair has 56 bits, but PC-2
only uses 48 of these.
For the first key, we have
C1D1 = 1110000 1100110
0101010 1011111 1010101
0110011 0011110 0011110
K1 = 000110 110000 001011 101111 111111 000111 000001 110010
29
Step 2: Encode Each 64-bit
Block of Data
Rearrange the 64 bits of plaintext M according to the following
initial permutation IP table
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010
1011 1100 1101 1110 1111
IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010
1010 1111 0000 1010 1010 30
Step 2: Encode
Each 64-bit Block
of Data
Next divide the permuted
block IP into a left half L0 and
a right half R0 (32 bits each).
L0 = 1100 1100 0000 0000 1100 1100 1111 1111
R0 = 1111 0000 1010 1010 1111 0000 1010 1010
for 1<=n<=16:
Li = Ri-1
Ri = Li-1⊕ f(Ri-1, Ki)
For 1st round:
L1 = R0 = 1111 0000 1010 1010 1111 0000 1010 1010
R1 = L0 ⊕ f(R0,K1)
31
Step 2: Encode Each 64-bit
Block of Data
To calculate f, we first expand each block Rn-1 from 32 bits to
48 bits.
R0 = 1111 0000 1010 1010 1111 0000 1010 1010
E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
Then, we XOR the output E(Rn-1) with the key Kn:
K1 = 000110 110000 001011 101111 111111 000111 000001 110010
E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
K1 ⊕E(R0) = 011000 010001 011110 111010 100001 100110 010100
100111
We now have 48 bits, or eight groups of six bits.
32
Step 2: Encode Each 64-bit Block
of Data
the eight groups of 6 bits are transformed into eight groups of
4 bits by using eight substitution boxes (S-boxes)
B1 = 011000
Row = (00)2 = 0
Column =(1100)2 = 12
S1 output = 5 = 0101
33
Step 2: Encode Each 64-bit
Block of Data
the output of the eight S boxes
0101 1100 1000 0010 1011 0101
1001 0111
34
Step 2: Encode Each 64-bit
Block of Data
The final stage in the calculation of f is to do a permutation P
of the S-box output
f = 0010 0011 0100 1010 1010 1001 1011 1011
Then we calculate:
R1 = L0 ⊕ f(R0 , K1 )
= 1100 1100 0000 0000 1100 1100 1111 1111
⊕0010 0011 0100 1010 1010 1001 1011 1011
= 1110 1111 0100 1010 0110 0101 0100 0100
35
Step 2: Encode Each 64-bit
Block of Data
IP-1
At the end of the 16th round,
we reverse the order of the
two blocks L16 and R16 into
the 64-bit block R16L16
Then, apply a final
permutation IP-1
R16L16 = 00001010 01001100 11011001 10010101 01000011 01000010
00110010 00110100
C = IP-1 = 10000101 11101000 00010011 01010100 00001111
00001010 10110100 00000101
36
39
DES Properties & Strength
1. The Use of 56-Bit Keys
▪ With a key length of 56 bits, there are 256possible keys, which
is ~ 7.2 X 1016 keys
▪ A brute-force attack appears impractical while using a single
machine performing one DES encryption per microsecond that
would take more than a thousand years to break the cipher.
▪ If multiple PCs work in parallel, the time is drastically shortened.
▪ Today’s supercomputers can find a key in about an hour.
➔ Key sizes of 128 bits or greater are effectively unbreakable
using simply a brute-force approach.
42
Average Time Required For
Exhaustive Key Search
Time Required
Key Size Number of Time Required at 109 at 1013
(bits) Cipher Alternative Keys Decryptions/s Decryptions/s
56 DES 256 ≈ 7.2 × 1016 255 ns = 1.125 years 1 hour
128 AES 2128 ≈ 3.4 × 2127 ns = 5.3 × 1021 5.3 × 1017
1038 years years
168 Triple DES 2168 ≈ 3.7 × 2167 ns = 5.8 × 1033 5.8 × 1029
1050 years years
192 AES 2192 ≈ 6.3 × 2191 ns = 9.8 × 1040 9.8 × 1036
1057 years years
256 AES 2256 ≈ 1.2 × 2255 ns = 1.8 × 1060 1.8 × 1056
1077 years years
43
DES Weak Keys & Semi-weak
Keys
DES has 4 weak keys and 6 pairs of semi-weak keys.
Weak Key: A key K such that EK(EK(x)) = x
After parity drop operation, consists either of all 0s, all 1s, or half 0s
and half 1s.
Makes the same sub-key to be generated in more than one round.
44
DES Weak Keys & Semi-weak
Keys
Semi-weak Key:
A pair of DES semi-weak keys is a pair (K1,K2) with EK1(EK2 (x)) = x.
creates only two different round keys and each of them is repeated
eight times.
the round keys created from each pair are the same with different
orders.
45
DES Properties & Strength
2. Avalanche effect
▪ A small change in either the plaintext or the key produces
a significant change in the ciphertext.
➔ If the change were small, this might provide a way to
reduce the size of the plaintext or key space to be searched.
46
DES Properties & Strength
3. Number of Rounds
▪ The greater the number of rounds, the more difficult it is to
perform cryptanalysis
➔ If DES had 15 or fewer rounds, cryptanalysis would
require less effort than a brute-force key search.
47
DES Properties & Strength
4. Design of Function F
▪ The more nonlinear F, the more difficult any type of
cryptanalysis will be.
▪ Both Strict Avalanche Criterion (SAC) and Bit Independence
Criterion (BIC) are cryptographic properties that strengthen
the effectiveness of the Mangler function
Strict Avalanche Each output bit should change with a probability
Criterion (SAC) of 50% when a single input bit is changed.
➔ Ensures diffusion
Bit Independence Any two output bits should change
Criterion (BIC) independently when one input bit is changed.
➔ No correlations between output bits 48
Thank you
49