Cryptography and Network

Security
Block Ciphers and DES, and
modes of operation
M. Sakalli
Reviewed, from Stallings
 Goals
• To introduce the notion of block ciphers,
ideal block cipher and its infeasibility, the
Feistel Cipher Structure.
• DES: its strength and weakness.

2
 Stream vs. Block Ciphers
• Symmetric cipher: same key used for
encryption and decryption
– Block cipher: encrypts a block of plaintext at a
time (typically 64 or 128 bits), cryptographic
checksum to ensure content not changed..
Hardware friendly.
– Stream cipher: encrypts data one bit or one
byte at a time, all classical ciphers 3
 Claude Shannon and Substitution-
Permutation Ciphers
• in 1949 Claude Shannon introduced idea
of substitution-permutation (S-P) networks
• Modern substitution-transposition product
cipher based on these two primitive
operations:
– substitution (S-box), provide confusion to
dissipate statistical structure of PT over the
bulk of CT
– permutation (P-box), provide diffusion make
the relationship between CT and key as
complex as possible
 Ideal Block Cipher
• A block of N PT bits
replaced wt a block of N CT
bits. (N = 64 or 128.), a
block cipher is a mono-
alphabetic cipher, and each
block represents a gigantic
“character.” Each particular
cipher is a one-to-one
mapping from the PT
alphabet to the CT alphabet.
• 2N! such mappings, and
block cipher would allow the
use of any such mapping
and the secret key indicates
which mapping to use.
5
 Key Size of Ideal Block Cipher
• Since there are 2N! different mappings, there are 2N!
different keys. the required key length will be log 2(2N!) ≈
N × 2N ≈ 1021 bits ≈ 1011 GB.
• That is infeasible!
• Modern block ciphers use a key of K bits to specify a
random subset of 2K mappings.
• If N ≈ K,
– 2K is much smaller than 2N!
– But is still very large
• If the selection of the 2K mappings is random, a good
approximation of the ideal block cipher is possible.
• Horst Feistel, in1970s, proposed a method to achieve
this.
6
The Feistel Cipher Structure

• Partitions the input block into halves of L and

R.
• Goes through a number of rounds.
– R goes intact to left.
– L goes through an operation that depends on R
and a round key derived from the encryption key.
• LUCIFER

7
 Li-1 Ri-1
2w bits partitioned
into halves; Ki
F
• L & R each 32 bits

• Li = Ri–1
• Ri = Li–1  F(Ri–1, Ki)
DES: The Data Encryption Standard
• Adopted by NIST in 1977. Most widely used
block cipher in the world.
• Features: Based on the Feistel cipher, block
size = 64 bits, key size 56 bits, number of
rounds =16
• Specifics: Subkey generation, and the
design of the round function F.
• Speed: fast software en/decryption & ease
of analysis
– Any further increase in key or/and block size and
the # of rounds improves the security, but slows
the cipher. 10
 • 16 round keys are
generated from the
main key by a
sequence of
permutations.
• Each round key is
results in 48 bits.
• Initial Permutation: IP,
reorders the input data bits.
The last step is inverse IP.
IP and IP-1: specified by
tables, has no impact on
security, due to the
implementation in chips.

DES Encryption
 DES Round Structure

1- Expands 32 bit R to 48-

bits using expansion
L (even) &R (odd) perm E,
each has 32 bits, 2- XOR 48- K and
expanded R both 48-
as in any Feistel bit,
cipher: 3- S boxes (8 of) to
Li = Ri–1 shrinks to 32-bits,
4- Permuting 32-bit
Ri = Li–1  F(Ri–1, Ki)
1- Expands 32 bit R to 48-bits using
expansion perm E,
2- XOR 48b K and expanded R both 48-bit,
3- S boxes (8 of) to shrinks to 32-bits,
4- Permuting 32-bit

DES Round
Structure
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1
0 15 7 4 14 2 13 1 10 6 12 11 6 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

• Eight S-boxes, each map 6 bits to 4 bits S Boxes

• Each: 4 x 16 table
– each row is a permutation of 0-15
– outer bits of 6 bits indicates one of the four rows
– inner 4 bits are to select the column
• For example, S1(101010) = 6 = 0110
• Each box has a different layout. 14
 Round Key Generation
• Main key: 64 bits, but only 56 bits are
used.
57 49 41 33 25 17 9
• 16 round keys (48 bits each) are
1 58 50 42 34 26 18
generated from the main key by a
10 2 59 51 43 35 27
sequence of permutations.
19 11 3 60 52 44 36
• Select and permute 56-bits using
Permuted Choice One (PC1). 63 55 47 39 31 23 15
7 62 54 46 38 30 22
• Then divide them into two 28-bit
halves. 14 6 61 53 45 37 29

• At each round: 21 13 5 28 20 12 4

– Rotate each half separately by either 1 or

2 bits according to a rotation schedule.
– Select 24-bits from each half & permute
them (48 bits) by PC2. This forms a
round key.
 Avalanche Effect
• A small change in the PT or in the KEY results in a
significant change in the CT. This is an evidence
of high degree of diffusion and confusion.
• SAC strict avalanche condition, any output bit of ct
should change with pr = ½, when any input is
changed.
• BIC bit independence criterion, states that out bits
should change independently, when any input bit is
changed.
• Both criteria seems strengthening confusion.
• DES exhibits a strong avalanche effect
– Changing 1 bit in the plaintext affects 34 bits in the
ciphertext on average.
– 1-bit change in the key affects 35 bits in the ciphertext
on average.
 Strength of DES – Key Size
• Brute force search looks hard, key search
– needs plaintext-ciphertext samples
– trying 1 key per microsecond would take 1000+ years on
average, due to the large key space size, 256 ≈ 7.2×1016.
• DES is theoretically broken using Differential or Linear
Cryptanalysis
• In practise it says unlikely to be a problem yet. But the
rapid advances in computing speed though have
rendered the 56 bit key susceptible to exhaustive key
search, as predicted by Diffie & Hellman. Have
demonstrated breaks:
– 1997 on a large network of computers in a few months
– 1998 on dedicated h/w in a few days, des cracker worth of $250,
containing1536 chips, (EFF).
– 1999 above combined in 22hrs!
 Differential Cryptanalysis
• one of the most significant recent (public)
advances in cryptanalysis
• known by NSA in 70's cf DES design
• Murphy, Biham & Shamir published 1990
• powerful method to analyse block ciphers
• used to analyse most current block ciphers
with varying degrees of success
• DES reasonably resistant to it, cf Lucifer
 Differential Cryptanalysis
• a statistical attack against Feistel ciphers
• uses cipher structure not previously used
• design of S-P networks has output of
function f influenced by both input & key
• hence cannot trace values back through
cipher without knowing values of the key
• Differential Cryptanalysis compares two
related pairs of encryptions
 Differential Cryptanalysis
Compares Pairs of Encryptions
• with a known difference in the input
• searching for a known difference in output
• when same subkeys are used
 Differential Cryptanalysis
• perform attack by repeatedly encrypting plaintext pairs
with known input XOR until obtain desired output XOR
• when found
– if intermediate rounds match required XOR have a right pair
– if not then have a wrong pair, relative ratio is S/N for attack
• can then deduce keys values for the rounds
– right pairs suggest same key bits
– wrong pairs give random values
• for large numbers of rounds, probability is so low that
more pairs are required than exist with 64-bit inputs
• Biham and Shamir have shown how a 13-round iterated
characteristic can break the full 16-round DES
 Linear Cryptanalysis
• another recent development
• also a statistical method
• must be iterated over rounds, with
decreasing probabilities
• developed by Matsui et al in early 90's
• based on finding linear approximations
• can attack DES with 247 known plaintexts,
still in practise infeasible
 Block Cipher Design Principles

• basic principles still like Feistel in 1970’s

• number of rounds
– more is better, exhaustive search best attack
• function f:
– provides “confusion”, is nonlinear, avalanche
• key schedule
– complex subkey creation, key avalanche
 Modes of Operation
• block ciphers encrypt fixed size blocks
• eg. DES encrypts 64-bit blocks, with 56-bit key
• need way to use in practise, given usually have
arbitrary amount of information to encrypt
• four were defined for DES in ANSI standard
ANSI X3.106-1983 Modes of Use
• subsequently now have 5 for DES and AES
• have block and stream modes
Electronic Codebook Book (ECB)
• message is broken into independent
blocks which are encrypted
• each block is a value which is substituted,
like a codebook, hence name
• each block is encoded independently of
the other blocks
Ci = DESK1 (Pi)
• uses: secure transmission of single values
Electronic Codebook Book (ECB)
Advantages and Limitations of ECB

• repetitions in message may show in

ciphertext
– if aligned with message block
– particularly with data such graphics
– or with messages that change very little,
which become a code-book analysis problem
• weakness due to encrypted message
blocks being independent
• main use is sending a few blocks of data
Cipher Block Chaining (CBC)
• message is broken into blocks
• but these are linked together in the
encryption operation
• each previous cipher blocks is chained
with current plaintext block, hence name
• use Initial Vector (IV) to start process
Ci = DESK1(Pi XOR Ci-1)
C-1 = IV
• uses: bulk data encryption, authentication
Cipher Block Chaining (CBC)
 Advantages and Limitations of CBC
• each ciphertext block depends on all message blocks
• thus a change in the message affects all ciphertext
blocks after the change as well as the original block
• need Initial Value (IV) known to sender & receiver
– however if IV is sent in the clear, an attacker can change bits of
the first block, and change IV to compensate
– hence either IV must be a fixed value (as in EFTPOS) or it must
be sent encrypted in ECB mode before rest of message
• at end of message, handle possible last short block
– by padding either with known non-data value (eg nulls)
– or pad last block with count of pad size
• eg. [ b1 b2 b3 0 0 0 0 5] <- 3 data bytes, then 5 bytes pad+count
 Cipher FeedBack (CFB)
• message is treated as a stream of bits
• added to the output of the block cipher
• result is feed back for next stage (hence name)
• standard allows any number of bit (1,8 or 64 or
whatever) to be feed back
– denoted CFB-1, CFB-8, CFB-64 etc
• is most efficient to use all 64 bits (CFB-64)
Ci = Pi XOR DESK1(Ci-1)
C-1 = IV
• uses: stream data encryption, authentication
Cipher FeedBack (CFB)
Advantages and Limitations of CFB

• appropriate when data arrives in bits/bytes

• most common stream mode
• limitation is need to stall while do block
encryption after every n-bits
• note that the block cipher is used in
encryption mode at both ends
• errors propagate for several blocks after
the error
 Output FeedBack (OFB)
• message is treated as a stream of bits
• output of cipher is added to message
• output is then feed back (hence name)
• feedback is independent of message
• can be computed in advance
Ci = Pi XOR Oi
Oi = DESK1(Oi-1)
O-1 = IV
• uses: stream encryption over noisy channels
Output FeedBack (OFB)
 Advantages and Limitations of OFB
• used when error feedback a problem or where need to
encrypt before message is available
• superficially similar to CFB
• but feedback is from the output of cipher and is
independent of message
• a variation of a Vernam cipher
– hence must never reuse the same sequence (key+IV)
• sender and receiver must remain in sync, and some
recovery method is needed to ensure this occurs
• originally specified with m-bit feedback in the standards
• subsequent research has shown that only OFB-64
should ever be used
 Counter (CTR)
• must have a different key & counter value
for every plaintext block (never reused)
Ci = Pi XOR Oi
Oi = DESK1(i)
• uses: high-speed network encryptions
Counter (CTR)
Advantages and Limitations of CTR

• efficiency
– can do parallel encryptions
– in advance of need
– good for bursty high speed links
• random access to encrypted data blocks
• provable security (good as other modes)
• but must ensure never reuse key/counter
values, otherwise could break (cf OFB)
 Summary
• have considered:
– block cipher design principles
– DES
• details
• strength
– Differential & Linear Cryptanalysis
– Modes of Operation
• ECB, CBC, CFB, OFB, CTR