Introduction to Cryptography
CS 355
Lecture 16
Encryption Modes & Other Block Ciphers
CS 355 Fall 2005 / Lecture 16 1
Announcements
• Homework due
• Mid-term exam Thursday October 13 (7pm to
9pm) in CS G066
CS 355 Fall 2005 / Lecture 16 2
Review: Feistel Network
w bits w bits
L0 R0 Encryption:
⊕ f1
L1=R0 R1=L0 ⊕ f1(R0)
L2=R1 R2=L1 ⊕ f2(R1)
L1 R1 …
⊕ f2 Ld=Rd-1 Rd=Ld-1⊕fd(Rd-1)
Decryption:
Rd-1=Ld Ld-1=Rd ⊕ fd(Ld)
Ld-1 Rd-1 …
⊕ fd R0=L1; L0=R1 ⊕f1(L1)
Rd Ld
CS 355 Fall 2005 / Lecture 16 3
Review: DES
CS 355 Fall 2005 / Lecture 16 4
Rijndael Features
• Designed to be efficient in both hardware
and software across a variety of platforms.
• Not a Feistel Network
• Uses a variable block size, 128,192, 256-
bits, key size of 128-, 192-, or 256-bits.
• Variable number of rounds (10, 12, 14):
– 10 if B = K = 128 bits
– 12 if either B or K is 192 and the other is ≤ 192
– 14 if either B or K is 256 bits
• Note: AES uses a 128-bit block size.
CS 355 Fall 2005 / Lecture 16 5
Lecture Outline
• Encryption Modes
• Other Block Ciphers
CS 355 Fall 2005 / Lecture 16 6
Block Cipher Encryption Modes: ECB
• Message is broken into independent blocks of
block_size bits;
• Electronic Code Book (ECB): each block
encrypted separately.
• Encryption: ci = Ek(xi)
• Decrytion: x i = Dk(ci)
CS 355 Fall 2005 / Lecture 16 7
Properties of ECB
• Deterministic: the same data block gets
encrypted the same way, reveals patterns of
data when a data block repeats
• Malleable: reordering ciphertext results in
reordered plaintext.
• Errors in one ciphertext block do not
propagate.
• Usage: not recommended to encrypt more
than one block of data
CS 355 Fall 2005 / Lecture 16 8
DES Encryption Modes: CBC
• Cipher Block Chaining (CBC): next input
depends upon previous output
Encryption: Ci= Ek (Mi⊕Ci-1), with C 0=IV
Decryption: Mi= Ci-1⊕Dk(C i), with C0=IV
M1 M2 M3
IV ⊕ ⊕ ⊕
Ek Ek Ek
C1 C2
CS 355 Fall 2005 / Lecture 16 9
Properties of CBC
• Randomized encryption: repeated text gets mapped to
different encrypted data.
– can be proven to be “secure” assuming that the block cipher has
desirable properties and that random IV’s are used
• A ciphertext block depends on all preceding plaintext
blocks; reorder affects decryption
• Errors in one block propagate to two blocks
– one bit error in Cj affects all bits in Mj and one bit in Mj+1
• Sequential encryption, cannot use parallel hardware
• Usage: chooses random IV and protects the integrity of IV
• Observation: if Ci=Cj then Ek (Mi⊕Ci-1) = Ek (Mj⊕Cj-1); thus
Mi⊕Ci-1 = Mj⊕Cj-1; thus Mi⊕ Mj = Ci-1 ⊕Cj-1
CS 355 Fall 2005 / Lecture 16 10
Use DES to construct Stream Ciphers
• Cipher Feedback (CFB)
• Output feedback (OFB)
• Counter Mode (CTR)
• Common properties:
– uses only the encryption function of the cipher both for
encryption and for decryption
– malleable: possible to make predictable bit changes
CS 355 Fall 2005 / Lecture 16 11
Encryption Modes: CFB
• Cipher Feedback (CFB): the message is XORed
with the feedback of encrypting the previous block
Encryption Decryption
r-bit shift r-bit shift
I1=IV Ij Ij
k E E k
Oj Oj
cj cj
xj xj
CS 355 Fall 2005 / Lecture 16 12
Properties of CFB
• Randomized encryption
• A ciphertext block depends on all preceding
plaintext blocks; reorder affects decryption
• Errors propagate for several blocks after the
error, but the mode is self-synchronizing (like
CBC).
• Decreased throughput.
– Can vary the number of bits feed back, trading off
throughput for ease of use
• Sequential encryption
CS 355 Fall 2005 / Lecture 16 13
Encryption Modes: OFB
• Output feedback (OFB):
– construct a PRNG using DES
– y0=IV yi = Ek[yi-1]
Encryption Decryption
Oj-1 Oj-1
I1=IV Ij Ij I1=IV
k E E k
Oj Oj
xj cj cj xj’
CS 355 Fall 2005 / Lecture 16 14
Properties of OFB
• Randomized encryption
• Sequential encryption, but pre-processing
possible
• Error propagation limited
• Subject to limitation of stream cipher
CS 355 Fall 2005 / Lecture 16 15
Encryption Modes:CTR
• Counter Mode (CTR): Another way to
construct PRNG using DES
– yi = Ek[counter+i]
– Sender and receiver share: counter (does not
need to be secret) and the secret key.
CS 355 Fall 2005 / Lecture 16 16
Properties of CTR
• Software and hardware efficiency: different
blocks can be encrypted in parallel.
• Preprocessing: the encryption part can be
done offline and when the message is known,
just do the XOR.
• Random Access: decryption of a block can be
done in random order, very useful for hard-
disk encryption.
• Messages of Arbitrary Length: ciphertext is
the same length with the plaintext (i.e., no IV).
CS 355 Fall 2005 / Lecture 16 17
International Data Encryption
Algorithm (IDEA)
• Originally designed by Massey and Lai at ETH
(Zurich), 1990.
• Based on mixing operations from different algebraic
groups (XOR, addition mod 216 , multiplication mod 216
+1).
• All operations are on 16-bit sub-blocks, with no
permutations used.
• Speed: faster than DES in software.
CS 355 Fall 2005 / Lecture 16 18
IDEA
• Features:
– 128-bit key
– 64 bit blocks
– 8 rounds,
– operates on 16-bit numbers
CS 355 Fall 2005 / Lecture 16 19
RC5
• Proprietary cipher owned by RSA Data
Security (designed by Ron Rivest).
• Very fast, operates on words.
• Variable key size, block size and number of
rounds.
• Clean and simple design.
CS 355 Fall 2005 / Lecture 16 20
RC5 Features
• RC5 is a family of ciphers rc5-w/r/b
– W = word size in bits (16/32/64) nb data=2w
– R = number of rounds (0..255)
– B = number of bytes in the key (0..255)
• Widely used version is RC5-32/12/16
– 32-bit words so encrypts 64-bit data blocks
– Using 12 rounds
– 16 bytes (128-bit) secret key
CS 355 Fall 2005 / Lecture 16 21
Coming Attractions …
• Cryptanalysis of DES
• Security of Block Ciphers
CS 355 Fall 2005 / Lecture 16 22
