This is a Chapter from the Handbook of Applied Cryptography, by A. Menezes, P. van
Oorschot, and S. Vanstone, CR C Press, 1996.
For further information, see www.cacr.math.uwaterloo.ca/hac
CRC Press has granted the following specific permissions for the electronic vers ion of this
book:
Permission is granted to retrieve, print and store a single copy of this chapter for
personal use. This permission does not extend to binding multiple chapters of
the book, photocopying or producing copies for other than personal use of the
person creating the copy, or making electronic copies available for retrieval by
others without prior permissi on in writing from CRC Press.
Except where over-ridden by the specific permission abo ve, the standard copyright notice
from CRC Press applies to this electronic v ersion:
Neither this book nor any part may be reproduced or transmitted in any form or
by any means, electronic or mechanical, including photocopying, microfilming,
and recording, or by any information storage or retrieval system, without prior
permission in writing from the publisher.
The consent of CR C Press does not extend to copying for general distribution,
for promotion, for creating new works, or for resale. Specific permission must be
obtained in writing from CRC Press for such copying.
c
1997 by CRC Press, Inc.
Chapter
7
Block Ciphers
Contents in Brief
7.1 Introduction and overview ..................... 223
7.2 Background and general concepts .................224
7.3 Classical ciphers and historical development ............ 237
7.4 DES ................................. 250
7.5 FEAL ................................ 259
7.6 IDEA ................................263
7.7 SAFER, RC5, and other block ciphers ...............266
7.8 Notes and further references ....................271
7.1 Introduction and overview
Symmetric-keyblock ciphersare the most prominentand importantelementsin many cryp-
tographic systems. Individually, they provide confidentiality. As a fundamental building
block, their versatility allows construction of pseudorandom number generators, stream ci-
phers, MACs, and hash functions. They may furthermore serve as a central component in
message authentication techniques, data integrity mechanisms, entity authentication proto-
cols, and (symmetric-key)digital signatureschemes. This chapter examines symmetric-key
block ciphers, including both general concepts and details of specific algorithms. Public-
key block ciphers are discussed in Chapter 8.
No block cipher is ideally suited for all applications, even one offering a high level of
security. This is a result of inevitable tradeoffs required in practical applications, including
those arising from, for example, speed requirements and memory limitations (e.g., code
size, data size, cache memory), constraints imposed by implementation platforms (e.g.,
hardware, software, chipcards), and differingtolerancesof applications to propertiesof var-
iousmodesofoperation. In addition, efficiencymust typicallybetradedoffagainstsecurity.
Thus it is beneficial to have a number of candidate ciphers from which to draw.
Of the many block ciphers currently available, focus in this chapter is given to a sub-
set of high profile and/or well-studied algorithms. While not guaranteed to be more secure
than other published candidate ciphers (indeed, this status changes as new attacks become
known), emphasis is given to those of greatest practical interest. Among these, DES is
paramount; FEAL has received both serious commercial backing and a large amount of in-
dependentcryptographicanalysis; and IDEA (originally proposedas a DES replacement) is
widely known and highly regarded. Other recently proposed ciphers of both high promise
and high profile (in part due to the reputation of their designers) are SAFER and RC5. Ad-
ditional ciphers are presented in less detail.
223
224 Ch. 7 Block Ciphers
Chapter outline
Basic background on block ciphers and algorithm-independent concepts are presented in
§7.2, including modes of operation, multiple encryption, and exhaustive search techniques.
Classical ciphers and cryptanalysisthereofareaddressed in §7.3, includinghistoricaldetails
on cipher machines. Modern block ciphers covered in chronological order are DES (§7.4),
FEAL (§7.5), and IDEA (§7.6), followed by SAFER, RC5, and other ciphers in §7.7, col-
lectively illustrating a wide range of modern block cipher design approaches. Further notes,
including details on additional ciphers (e.g., Lucifer) and references for the chapter, may be
found in §7.8.
7.2 Background and general concepts
Introductory material on block ciphers is followed by subsections addressing modes of op-
eration, and discussion of exhaustive key search attacks and multiple encryption.
7.2.1 Introduction to block ciphers
Block ciphers can be either symmetric-key or public-key. The main focus of this chapter is
symmetric-key block ciphers; public-key encryption is addressed in Chapter 8.
(i) Block cipher definitions
A block cipher is a function (see §1.3.1) which maps n-bit plaintext blocks to n-bit cipher-
text blocks; n is called the blocklength. It may be viewed as a simple substitution cipher
with large character size. The function is parameterized by a k-bit key K,
1
taking values
from a subset K (the key space)ofthesetofallk-bit vectors V
k
. It is generally assumed
that the key is chosen at random. Use of plaintextand ciphertext blocks of equal size avoids
data expansion.
To allow unique decryption, the encryption function must be one-to-one (i.e., invert-
ible). For n-bit plaintext and ciphertext blocks and a fixed key, the encryption function is
a bijection, defining a permutation on n-bit vectors. Each key potentially defines a differ-
ent bijection. The number of keys is |K|,andtheeffective key size is lg |K|; this equals the
key length if all k-bit vectors are valid keys (K = V
k
). If keys are equiprobable and each
defines a different bijection, the entropy of the key space is also lg |K|.
7.1 Definition An n-bit block cipher is a function E : V
n
×K→V
n
, such that for each
key K ∈K, E(P, K) is an invertible mapping (the encryption function for K) from V
n
to V
n
, written E
K
(P ). The inverse mapping is the decryption function, denoted D
K
(C).
C = E
K
(P ) denotes that ciphertext C results from encrypting plaintext P under K.
Whereas block ciphers generally process plaintext in relatively large blocks (e.g., n ≥
64), stream ciphers typically process smaller units (see Note 6.1); the distinction, however,
is not definitive (see Remark 7.25). For plaintext messages exceeding one block in length,
various modes of operation for block ciphers are used (see §7.2.2).
The most general block cipher implements every possible substitution, as per Defini-
tion 7.2. To represent the key of such an n-bit (true) random block cipher would require
1
This use of symbols k and K may differ from other chapters.
c
1997 by CRC Press, Inc. — See accompanying notice at front of chapter.
§
7.2 Background and general concepts 225
lg(2
n
!) ≈ (n − 1.44)2
n
bits, or roughly 2
n
times the number of bits in a message block.
This excessive bitsize makes (true) random ciphers impractical. Nonetheless, it is an ac-
cepted design principle that the encryption function corresponding to a randomly selected
key should appear to be a randomly chosen invertible function.
7.2 Definition A(true) randomcipheris an n-bit block cipherimplementing all 2
n
! bijections
on 2
n
elements. Each of the 2
n
! keys specifies one such permutation.
A block cipher whose block size n is too small may be vulnerable to attacks based on
statistical analysis. Onesuch attack involves simplefrequencyanalysisof ciphertextblocks
(see Note 7.74). This may be thwarted by appropriate use of modes of operation (e.g., Al-
gorithm 7.13). Other such attacks are considered in Note 7.8. However, choosing too large
a value for the blocksize n may create difficulties as the complexity of implementation of
many ciphers grows rapidly with block size. In practice, consequently, for larger n, easily-
implementable functions are necessary which appear to be random (without knowledge of
the key).
An encryption function per Definition 7.1 is a deterministic mapping. Each pairing of
plaintextblock P andkey K maps to a unique ciphertextblock. Incontrast, in a randomized
encryption technique (Definition 7.3; see also Remark 8.22), each (P, K) pair is associated
with a set C
(P,K)
of eligible ciphertext blocks; each time P is encrypted under K, an out-
put R from a random source non-deterministically selects one of these eligible blocks. To
ensure invertibility, for every fixed key K, the subsets C
(P,K)
over all plaintexts P must be
disjoint. Since the encryption function is essentially one-to-many involving an additional
parameter R (cf. homophonicsubstitution, §7.3.2), the requirement for invertibility implies
data expansion, which is a disadvantage of randomized encryption and is often unaccept-
able.
7.3 Definition A randomized encryption mapping is a function E from a plaintext space V
n
to a ciphertext space V
m
, m>n, drawing elements from a space of random numbers R
= V
t
. E is defined by E : V
n
×K×R→V
m
, such that for each key K ∈Kand R ∈R,
E(P, K, R), also written E
R
K
(P ), maps P ∈ V
n
to V
m
; and an inverse (corresponding
decryption) function exists, mapping V
m
×K→V
n
.
(ii) Practical security and complexity of attacks
The objective of a block cipher is to provide confidentiality. The corresponding objective
of an adversary is to recover plaintext from ciphertext. A block cipher is totally broken if a
key can be found, and partially broken if an adversary is able to recover part of the plaintext
(but not the key) from ciphertext.
7.4 Note (standard assumptions) To evaluate block cipher security, it is customary to always
assume that an adversary (i) has access to all data transmitted over the ciphertext channel;
and (ii) (Kerckhoffs’ assumption) knows all details of the encryption function except the
secret key (which security consequently rests entirely upon).
Under the assumptions of Note 7.4, attacks are classified based on what information
a cryptanalyst has access to in addition to intercepted ciphertext (cf. §1.13.1). The most
prominent classes of attack for symmetric-key ciphers are (for a fixed key):
1. ciphertext-only – no additional information is available.
2. known-plaintext – plaintext-ciphertext pairs are available.
Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.
226 Ch. 7 Block Ciphers
3. chosen-plaintext – ciphertexts are available corresponding to plaintexts of the adver-
sary’s choice. A variation is an adaptive chosen-plaintext attack, where the choice of
plaintexts may depend on previous plaintext-ciphertext pairs.
Additional classes of attacks are given in Note 7.6; while somewhat more hypothetical,
these are nonetheless of interest for the purposes of analysis and comparison of ciphers.
7.5 Remark (chosen-plaintext principle) It is customary to use ciphers resistant to chosen-
plaintext attack even when mounting such an attack is not feasible. A cipher secure against
chosen-plaintext attack is secure against known-plaintext and ciphertext-only attacks.
7.6 Note (chosen-ciphertextand related-key attacks)Achosen-ciphertext attack operates un-
der the following model: an adversary is allowed access to plaintext-ciphertext pairs for
some number of ciphertexts of his choice, and thereafter attempts to use this information
to recover the key (or plaintext corresponding to some new ciphertext). In a related-key at-
tack, an adversary is assumed to have access to the encryption of plaintexts under both an
unknown key and (unknown) keys chosen to have or known to have certain relationships
with this key.
With few exceptions (e.g., the one-time pad), the best available measure of security for
practical ciphers is the complexity of the best (currently) known attack. Various aspects of
such complexity may be distinguished as follows:
1. data complexity – expected number of input data units required (e.g., ciphertext).
2. storage complexity – expected number of storage units required.
3. processingcomplexity– expectednumberof operationsrequiredto processinputdata
and/or fill storage with data (at least one time unit per storage unit).
The attack complexity is the dominant of these (e.g., for linear cryptanalysison DES, essen-
tially the data complexity). When parallelization is possible, processing complexitymay be
divided across many processors (but not reduced), reducing attack time.
Given a data complexity of 2
n
, an attack is always possible; this many different n-
bit blocks completely characterize the encryption function for a fixed k-bit key. Similarly,
givena processing complexityof 2
k
, an attack is possible by exhaustive key search (§7.2.3).
Thus as a minimum, the effective key size should be sufficiently large to preclude exhaus-
tive key search, and the block size sufficiently large to preclude exhaustive data analysis.
A block cipher is considered computationallysecure if these conditions hold and no known
attack has both data and processing complexity significantly less than, respectively, 2
n
and
2
k
. However, see Note 7.8 for additional concerns related to block size.
7.7 Remark (passive vs. active complexity) For symmetric-key block ciphers, data complex-
ity is beyond the control of the adversary, and is passive complexity (plaintext-ciphertext
pairs cannot be generated by the adversary itself). Processing complexity is active com-
plexity which typically benefits from increased resources (e.g., parallelization).
7.8 Note (attacks based on small block size) Security concerns which arise if the block size
n is too small include the feasibility of text dictionary attacks and matching ciphertext at-
tacks. A text dictionary may be assembled if plaintext-ciphertext pairs become known for
a fixed key. The more pairs available, the larger the dictionary and the greater the chance of
locating a random ciphertext block therein. A complete dictionary results if 2
n
plaintext-
ciphertext pairs become known, and fewer suffice if plaintexts contain redundancy and a
non-chainingmode of encryption (such as ECB) is used. Moreover, if about 2
n/2
such pairs
c
1997 by CRC Press, Inc. — See accompanying notice at front of chapter.
