Arab Open University(AOU)

Faculty of Computing Study

Network & Security program

T318
APPLIED NETWORK SECURITY

Dr. Mahmoud Attalah

[email protected]

Chapter 3
Block Ciphers and the Data Encryption Standard

1
 Agenda

❖ Block Cipher Principles

❖ The Data Encryption Standard

❖ Simplified-DES

❖ DES Details

❖ DES Design Issues and Attacks

❖ 3DES, AES and Other Block Ciphers

Version 2 2
 Agenda

❖ Block Cipher Principles

❖ The Data Encryption Standard

❖ Simplified-DES

❖ DES Details

❖ DES Design Issues and Attacks

❖ 3DES, AES and Other Block Ciphers

Version 2 3
 Stream Ciphers
❖ Encrypts a digital data stream one bit or one byte
at a time.
❖ One time pad is example; but practical
limitations.
❖ Typical approach for stream cipher:
▪ Key (K) used as input to bit-stream generator algorithm
▪ Algorithm generates cryptographic bit stream (𝑘𝑖 ) used to
encrypt plaintext
▪ Users share a key; use it to generate keystream

Version 2 4
 Block Ciphers

❖ Encrypt a block of plaintext as a whole to

produce same sized ciphertext.

❖ Typical block sizes are 64 or 128 bits.

❖ Modes of operation used to apply block ciphers

to larger plaintexts.

Version 2 5
 Reversible and Irreversible Mappings
❖ 𝑛 − 𝑏𝑖𝑡 block cipher takes n bit plaintext and
produces n bit ciphertext.
❖ 2𝑛 possible different plaintext blocks.
❖ Encryption must be reversible (decryption
possible).
❖ Each plaintext block must produce unique
ciphertext Block.
❖ Total transformations is 𝟐𝒏 !

Version 2 6
 Ideal Block Cipher

❖ n-bit input maps to 2𝑛 possible input states.

❖ Substitution used to produce 2𝑛 output states.

❖ Output states map to n-bit output

❖ Ideal block cipher allows maximum number of

possible encryption mappings from plaintext block.

❖ Problems with ideal block cipher:

▪ Small block size: equivalent to classical substitution cipher;
cryptanalysis based on statistical characteristics feasible.
▪ Large block size: key must be very large; performance /
implementation problems
Version 2 7
 General Block Substitution

Version 2 8
 Block Substitution(Cont.)

Version 2
 Feistel Structure for Block Ciphers

❖ Feistel proposed applying two or more simple

ciphers in sequence so final result is
cryptographically stronger than component
ciphers.
❖ 𝑛 − 𝑏𝑖𝑡 block length; 𝑘 − 𝑏𝑖𝑡 key length; 2𝑘
transformations.
❖ Feistel chiper alternantes: substitutions,
transpositions (permutations).
❖ Applies concepts of diffusion and confusion.
❖ Applied in many ciphers today.

Version 2 10
Feistel Structure for Block Ciphers(Cont.)

❖ Approach:
▪ Plaintext split into halves

▪ Subkeys (or round keys) generated from key

▪ Round function, 𝐹, applied to right half.

▪ Apply substitution on left half using XOR

▪ Apply permutation: interchange to halves.

Version 2 11
 Diffusion and Confusion

❖ Terms introduced by Claude Shannon to capture the two

basic building blocks for any cryptographic system
▪ Shannon’s concern was to thwart cryptanalysis based on statistical
analysis

Diffusion
•The statistical structure of the plaintext is dissipated into long-range
statistics of the ciphertext
•This is achieved by having each plaintext digit affect the value of many
ciphertext digits

Confusion
•Seeks to make the relationship between the statistics of the ciphertext
and the value of the encryption key as complex as possible
•Even if the attacker can get some handle on the statistics of the
ciphertext, the way in which the key was used to produce that
ciphertext is so complex as to make it difficult to deduce the key

Version 2
 Feistel Encryption and Decryption

Version 2 13
 Using the Feistel Structure

❖ Exact implementation depends on various

design features
▪ Block size, e.g. 64, 128 bits: larger values leads to more
diffusion
▪ Key size, e.g. 128 bits: larger values leads to more confusion,
resistance against brute force.
▪ Number of rounds, e.g. 16 rounds.
▪ Subkey generation algorithm: should be complex.
▪ Round function F: should be complex
❖ Other factors include fast encryption in software
and ease of analysis
❖ Trade-off: security vs performance.

Version 2 14
 Feistel Example

Version 2 15
 Agenda

❖ Block Cipher Principles

❖ The Data Encryption Standard

❖ Simplified-DES

❖ DES Details

❖ DES Design Issues and Attacks

❖ 3DES, AES and Other Block Ciphers

Version 2 16
 Data Encryption Standard(DES)

❖ Symmetric block cipher

▪ 56-bit key, 64-bit input block, 64-bit output block

❖ One of most used encryption systems in world

▪ Developed in 1977 by NBS/NIST
▪ Designed by IBM (Lucifer) with input from NSA
▪ Principles used in other ciphers, e.g. 3DES, IDEA

❖ Simplified DES (S-DES)

▪ Cipher using principles of DES
▪ Developed for education (not real world use)

Version 2 17
 Agenda

❖ Block Cipher Principles

❖ The Data Encryption Standard

❖ Simplified-DES

❖ DES Details

❖ DES Design Issues and Attacks

❖ 3DES, AES and Other Block Ciphers

Version 2 18
 Simplified DES

❖ Input (plaintext) block: 8-bits

❖ Output (ciphertext) block: 8-bits
❖ Key: 10-bits.
❖ Rounds: 2
❖ Round keys generated using permutations and
left shifts
❖ Encryption: initial permutation, round function,
switch halves.
❖ Decryption: Same as encryption, except round
keys used in opposite order

Version 2 19
 S-DES Algorithm

Version 2 20
 S-DES Algorithm(Cont..)

❖ P10 (permutate)
▪ Input : 1 2 3 4 5 6 7 8 9 10
▪ Output: 3 5 2 7 4 10 1 9 8 6
❖ P8 (select and permutate)
▪ Input : 1 2 3 4 5 6 7 8 9 10
▪ Output: 6 3 7 4 8 5 10 9
❖ P4 (permutate)
▪ Input : 1 2 3 4
▪ Output: 2 4 3 1

Version 2 21
 S-DES Key Generation

Version 2 22
 S-DES Encryption Details

Version 2 23
 S-DES S-Boxes
❖ S-DES (and DES) perform substitutions using S-
Boxes
❖ S-Box considered as a matrix: input used to
select row/column; selected element is output.
❖ 4-bit input: 𝒃𝒊𝒕𝟏 ; 𝒃𝒊𝒕𝟐 ; 𝒃𝒊𝒕𝟑 ; 𝒃𝒊𝒕𝟒 .
❖ 𝒃𝒊𝒕𝟏 , 𝒃𝒊𝒕𝟒 species row (0, 1, 2 or 3 in decimal).
❖ 𝒃𝒊𝒕𝟐 , 𝒃𝒊𝒕𝟑 species column.
❖ 2-bit output

Version 2 24
 S-DES Example

Plaintext: 01110010

Key: 1010000010

Ciphertext: 01110111

Version 2 25
 S-DES Summary

❖ Educational encryption algorithm

❖ S-DES expressed as functions:

Ciphertext= 𝐼𝑃−1 (𝑓𝑘2 𝑠𝑤 𝑓𝑘1 𝐼𝑃 𝑝𝑎𝑙𝑖𝑛𝑡𝑒𝑥𝑡 )

P𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡 = 𝐼𝑃−1 (𝑓𝑘1 (𝑠𝑤 𝑓𝑘2 𝐼𝑃 Ciphertext ))

❖ Security of S-DES:
▪ 10-bit key, 1024 keys: brute force easy.
▪ If know plaintext and corresponding ciphertext, can we
determine key? Very hard
Version 2 26
 Comparing DES and S-DES
S-DES DES
8-bit blocks 64-bit blocks
10-bit key: 2 x 8-bit 56-bit key: 16 x 48-bit
round keys round keys
IP: 8-bits IP: 64 bits
F operates on 4 bits F operates on 32 bits
2 S-Boxes 8 S-Boxes
2 rounds 16 rounds

❖ S-DES encryption:
Ciphertext= 𝐼𝑃−1 𝑓𝑘2 𝑠𝑤 𝑓𝑘1 𝐼𝑃 𝑝𝑎𝑙𝑖𝑛𝑡𝑒𝑥𝑡

❖ DES encryption:
Ciphertext= 𝐼𝑃−1 𝑓𝑘16 𝑠𝑤 𝑓𝑘15(𝑠𝑤(…(𝑓𝑘1 𝐼𝑃 𝑝𝑎𝑙𝑖𝑛𝑡𝑒𝑥𝑡 ….)

Version 2 27
 Agenda

❖ Block Cipher Principles

❖ The Data Encryption Standard

❖ Simplified-DES

❖ DES Details

❖ DES Design Issues and Attacks

❖ 3DES, AES and Other Block Ciphers

Version 2 28
 General DES Encryption Algorithm

Version 2 29
 Permutation Tables for DES

Version 2 30
 Permutation Tables for DES

Version 2 31
 Single Round of DES Algorithm

Version 2 32
 Calculation of F(R,K)

Version 2 33
 Definition of DES S-Boxes

Version 2 34
 Definition of DES S-Boxes(Cont..)

Version 2 35
 DES Key Schedule Calculation

Version 2 36
 Agenda

❖ Block Cipher Principles

❖ The Data Encryption Standard

❖ Simplified-DES

❖ DES Details

❖ DES Design Issues and Attacks

❖ 3DES, AES and Other Block Ciphers

Version 2 37
 The Avalanche Effect

❖ Aim: small change in key (or plaintext) produces

large change in ciphertext.
▪ Avalanche effect is present in DES (good for security).

▪ Following examples show the number of bits that change in

output when two different inputs are used, differing by 1 bit.
• Plaintext 1: 02468aceeca86420
• Plaintext 2: 12468aceeca86420
• Ciphertext difference: 32 bits
• Key 1: 0f1571c947d9e859
• Key 2: 1f1571c947d9e859
• Ciphertext difference : 30

Version 2 38
 Avalanche effect in DES:
Change in Plaintext

Version 2 39
 Avalanche effect in DES:
Change in Key

Version 2 40
 Key Size

❖ Although 64 bit initial key, only 56 bits used in

encryption (other 8 for parity check).
▪ 256 = 7.2x1016
• 1977: estimated cost 20m US$ to build machine to break in 10
hours.

• 1998: EFF built machine for 250k US$ to break in 3 days.

• Today: 56 bits considered too short to withstand brute force

attack.

▪ 3DES uses 128-bit keys

Version 2 41
 Attacks on DES

❖ Timing Attacks
▪ Information gained about key/plaintext by observing how
long implementation takes to decrypt
▪ No known useful attacks on DES
❖ Differential Cryptanalysis
▪ Observe how pairs of plaintext blocks evolve.
▪ Break DES in 247 encryptions (compared to255 ); but require 247 chosen
plaintexts.

❖ Linear Cryptanalysis
▪ Find linear approximations of the transformations.
▪ Break DES using 243 known plaintexts.

Version 2 42
 DES Algorithm Design

❖ DES was designed in private; questions about the

motivation of the design
▪ S-Boxes provide non-linearity: important part of DES,
generally considered to be secure.

▪ S-Boxes provide increased confusion.

▪ Permutation P chosen to increase diffusion.

Version 2 43
 Agenda

❖ Block Cipher Principles

❖ The Data Encryption Standard

❖ Simplified-DES

❖ DES Details

❖ DES Design Issues and Attacks

❖ 3DES, AES and Other Block Ciphers

Version 2 44
 Multiple Encryption with DES

❖ DES is vulnerable to brute force attack.

❖ Alternative block cipher that makes use of DES

software/equipment/knowledge: encrypt multiple
times with different keys.

❖ Options:
1. Double DES: not much better than single DES.

2. Triple DES (3DES) with 2 keys: brute force 2112.

3. Triple DES with 3 keys: brute force 2168.

Version 2 45
 Double Encryption

❖ For DES, 2 x 56-bit keys, meaning 112-bit key

length
❖ Requires 2111 operations for brute force?
❖ Meet-in-the-middle attack makes it easier

Version 2 46
 Meet-in-the-Middle Attack
❖ Double DES Encryption : C = E(𝒌𝟐 ,E(𝒌𝟏 ,P)).
❖ Say X = E(𝒌𝟏 ,P) = D(𝒌𝟐 ,C).
❖ Attacker knows two plaintext, ciphertext pairs (𝒑𝒂 ,
𝑪𝒂 ) and (𝒑𝒃 , 𝑪𝒃 ).
1. Encrypt 𝒑𝒂 using all 256 values of 𝒌𝟏 to get multiple values of X.
2. Store results in table and sort by X.
3. Decrypt 𝑪𝒂 using all 256 values of 𝒌𝟐 .
4. As each decryption result produced, check against table
5. If match, check current 𝒌𝟏 , 𝒌𝟐 on 𝑪𝒃 If 𝒑𝒃 obtained, then accept the
keys.
❖ With two known plaintext, ciphertext pairs,
probability of successful attack is almost 1.
❖ Encrypt/decrypt operations required: 256 (twice as
many as single DES).

Version 2 47
 Triple Encryption

❖ 2 keys, 112 bits.

❖ 3 keys, 168 bits.

❖ Why E-D-E? To be compatible with single DES:

𝑪 = 𝑬 𝒌𝟏 , 𝑫 𝒌𝟏 , 𝑬 𝒌𝟏 , 𝒑 = 𝑬(𝒌𝟏 , 𝒑)

Version 2 48
 Advanced Encryption Standard

❖ NIST called for proposals for new standard in

1997.
▪ Aims: security, efficient software/hardware implementations,
low memory requirements, parallel processing.

▪ Candidate algorithms from around the world.

▪ Rijndael chosen, standard called AES created in 2001.

Version 2 49
 Advanced Encryption Standard(Cont)

❖ NIST called for proposals for new standard in

1997.
❖ AES:
▪ Block size: 128 bits (others possible)
▪ Key size: 128, 192, 256 bits
▪ Rounds: 10, 12, 14 (depending on key)
▪ Operations: XOR with round key, substitutions using
▪ S-Boxes, mixing using Galois Field arithmetic.
❖ Widely used in le encryption, network
communications.
❖ Generally considered secure.

Version 2 50
 Other Symmetric Encryption Algorithms
❖ Blowsh (Schneier, 1993): 64 bit blocks/32{448 bit keys; Feistel
structure.
❖ Twosh (Schneier et al, 1998): 128/128, 192, 256; Feistel structure
❖ Serpent (Anderson et al, 1998): 128/128, 192, 256; Substitution-
permutation network
❖ Camellia (Mitsubishi/NTT, 2000): 128/128, 192, 256; Feistel
structure
❖ IDEA (Lai and Massey, 1991): 64/128
❖ CAST-128 (Adams and Tavares, 1996): 64/40{128; Feistel
structure
❖ CAST-256 (Adams and Tavares, 1998): 128/up to 256; Feistel
structure
❖ RC5 (Rivest, 1994): 32, 64 or 128/up to 2040; Feistel-like
structure
❖ RC6 (Rivest et al, 1998): 128/128, 192, 256; Feistel structure

Version 2 51
 Cryptanalysis on Block Ciphers

❖ Known data: chosen pairs of (plaintext, ciphertext).

❖ MITM: Meet-in-the-middle.
❖ Lucks: S. Lucks, Attacking Triple Encryption, in Fast
Software Encryption, Springer, 1998.
❖ Biclique: Bogdanov, Khovratovich and Rechberger,
Biclique Cryptanalysis of the Full AES, in
ASIACRYPT2011, Springer, 2011

Version 2 52
 Summary
❖ Traditional Block ❖ The strength of
Cipher Structure DES
▪ Stream ciphers ▪ Use of 56-bit keys
▪ Block ciphers ▪ Nature of the DES
▪ Motivation for the algorithm
Feistel cipher ▪ Timing attacks
structure ❖ Block cipher
▪ Feistel cipher design principles
❖ The Data ▪ Number of rounds
Encryption ▪ Design of function
Standard (DES) F
▪ Encryption ▪ Key schedule
▪ Decryption algorithm
▪ Avalanche effect
 References
❖ Cryptography and Network Security: Principles and Practice,
7th Ed., by William Stallings, Pearson, 2017. (Global Edition,
imported by Kai-Fa Publishing)

❖ Network Security Essentials: Applications and Standards, 6th

Ed., by William Stallings, Pearson, 2017. (International Edition,
imported by Kai-Fa Publishing)

❖ Computer Security: Principles and Practice, 4th Ed., by William

Stallings and Lawrie Brown, Pearson, 2017. (Global Edition,
imported by Kai-Fa Publishing)

Version 2 54