 Background and general concepts

Introductory material on block ciphers is followed by subsections addressing modes of operation, and discussion of exhaustive key search attacks and multiple encryption.

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 A--bit key A', taking values from a subset K. (the key space) of the set of all Л -bit vectors 14. It is generally assumed that the key is chosen at random. Use of plaintext and ciphertext blocks of equal size avoids data expansion.

To allow unique decryption, the encryption function must be one-to-one (i.e., invertible). 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 different bijection. The number of keys is K, and the effective key size is lg |/C|; this equals the key length if all A -bit vectors are valid keys (K. = 14). If keys are equiprobable and each defines a different bijection, the entropy of the key space is also lg |/C|.

7.1 Definition An n-bit block cipher is a function E : Vn x K,Vn, such that for each key КК,, E(P. К) is an invertible mapping (the encryption function for K) from Vn to Vn, written Ek(P). The inverse mapping is the decryption function, denoted Dk{C). C = E[<(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 eveiy possible substitution, as per Definition 7.2. To represent the key of such an n-bit (true) random block cipher would require lg(2'M) « (» - 1.44)2” bits, or roughly 2” times the number of bits in a message block. This excessive bitsize makes (true) random ciphers unpractical. Nonetheless, it is an accepted 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) random cipher is an n-bit block cipher implementing all 2”! bijections on 2" elements. Each of the 2'M keys specifies one such permutation.

A block cipher whose block size n is too small may be vulnerable to attacks based on statistical analysis. One such attack involves simple frequency analysis of ciphertext blocks (see Note 7.74). This may be thwarted by appropriate use of modes of operation (e.g., Algorithm 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 plaintext block P and key К maps to a unique ciphertext block. In contrast, in a randomized encryption technique (Definition 7.3; see also Remark 8.22), each (P, K) pair is associated with a set C^ptK) of eligible ciphertext blocks; each time P is encrypted under K, an output R from a random source non-deterministically selects one of these eligible blocks. To ensure invertibility, for every fixed key К, the subsets CptK) over all plaintexts P must be disjoint. Since the encryption function is essentially one-to-many involving an additional parameter R (cf. hornophonic substitution, §7.3.2), the requirement for invertibility implies data expansion, which is a disadvantage of randomized encryption and is often unacceptable.

• 7.3 Definition A randomized encryption mapping is a function E from a plaintext space Vn to a ciphertext space Vm, m > n, drawing elements from a space of random numbers 7Z = Vt. E is defined by E : Vn x К xlZ -a Vm, such that for each key К e K, and R e'll, E(P, К. R), also written E\$(P), maps P e Vn to Vm and an inverse (corresponding decryption) function exists, mapping Vm x 1C -r Vn.
• (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 hr 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.

3. chosen-plaintext - ciphertexts are available corresponding to plaintexts of the adversary’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-ciphertext and related-key attacks) A chosen-ciphertext attack operates under 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 attack, 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. processing complexity> - expected number of operations required to process input data 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 cryptanalysis on DES, essentially the data complexity). When parallelization is possible, processing complexity may be divided across many processors (but not reduced), reducing attack time.

Given a data complexity of 2", an attack is always possible; this many different n- bit blocks completely characterize the encryption function for a fixed fc-bit key. Similarly, given a processing complexity of 2k, 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 exhaustive key search, and the block size sufficiently large to preclude exhaustive data analysis. A block cipher is considered computationally secure if these conditions hold and no known attack has both data and processing complexity significantly less than, respectively, 2" and 2k. 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 complexity 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 complexity’ 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 attacks. A text dictionary may be assembled if plaintext-ciphertext pans 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" plaintext- ciphertext pairs become known, and fewer suffice if plaintexts contain redundancy and a non-chaining mode of encryption (such as ECB) is used. Moreover, if about 2"/2 such pairs are known, and about 2"/2 ciphertexts are subsequently created, then by the birthday paradox one expects to locate a ciphertext in the dictionary. Relatedly, from ciphertext blocks alone, as the number of available blocks approaches 2"/2, one expects to find matching ciphertext blocks. These may reveal partial information about the corresponding plaintexts, depending on the mode of operation of the block cipher, and the amount of redundancy in the plaintext.

Computational and unconditional security are discussed in §1.13.3. Unconditional security is both unnecessary in many applications and impractical; for example, it requires as many bits of secret key as plaintext, and cannot be provided by a block cipher used to encrypt more than one block (due to Fact 7.9, since identical ciphertext implies matching plaintext). Nonetheless, results on unconditional security provide insight for the design of practical ciphers, and has motivated many of the principles of cryptographic practice currently in use (see Remark 7.10).

• 7.9 Fact A cipher provides perfect secrecy (unconditional security) if the ciphertext and plaintext blocks are statistically independent.
• 7.10 Remark {theoretically-motivatedprinciples) The unconditional security of the one-tune- pad motivates both additive stream ciphers (Chapter 6) and the frequent changing of cryptographic keys (§13.3.1). Theoretical results regarding the effect of redundancy on unicity distance (Fact 7.71) motivate the principle that for plaintext confidentiality, the plaintext data should be as random as possible, e.g., via data-compression prior to encryption, use of random-bit fields in message blocks, or randomized encryption (Definition 7.3). The latter two techniques may, however, increase the data length or allow covert channels.
• (iii) Criteria for evaluating block ciphers and modes of operation

Many criteria may be used for evaluating block ciphers in practice, including:

• 1. estimated security’ level. Confidence in the (historical) security of a cipher grows if it has been subjected to and withstood expert cryptanalysis over a substantial tune period, e.g., several years or more; such ciphers are certainly considered more secure than those which have not. This may include the performance of selected cipher components relative to various design criteria which have been proposed or gained favor in recent years. The amount of ciphertext required to mount practical attacks often vastly exceeds a cipher’s unicity distance (Definition 7.69), which provides a theoretical estimate of the amount of ciphertext required to recover the unique encryption key.
• 2. key size. The effective bitlength of the key, or more specifically, the entropy of the key space, defines an upper bound on the security of a cipher (by considering exhaustive search). Longer keys typically impose additional costs (e.g., generation, transmission, storage, difficulty to remember passwords).
• 3. throughput. Throughput is related to the complexity of the cryptographic mapping (see below), and the degree to which the mapping is tailored to a particular implementation medium or platform.
• 4. block size. Block size impacts both security (larger is desirable) and complexity (larger is more costly to implement). Block size may also affect performance, for example, if padding is required.
• 5. complexity> of cryptographic mapping. Algorithmic complexity affects the implementation costs both in terms of development and fixed resources (hardware gate count or software code/data size), as well as real-time performance for fixed resources (throughput). Some ciphers specifically favor hardware or software implementations.
• 6. data expansion. It is generally desirable, and often mandator}', that encryption does not increase the size of plaintext data. Homophonic substitution and randomized encryption techniques result in data expansion.
• 7. error propagation. Decryption of ciphertext containing bit errors may result in various effects on the recovered plaintext, including propagation of errors to subsequent plaintext blocks. Different error characteristics are acceptable in various applications. Block size (above) typically affects error propagation.

•  This use of symbols к and К may differ from other chapters.