Exhaustive key search and multiple encryption

A fixed-size key defines an upper bound on the security of a block cipher, due to exhaustive key search (Fact 7.26). While this requires either known-plaintext or plaintext containing redundancy, it has widespread applicability since cipher operations (including decryption) are generally designed to be computationally efficient.

A design technique which complicates exhaustive key search is to make the task of changing cipher keys computationally expensive, while allowing encryption with a fixed key to remain relatively efficient. Examples of ciphers with this property include the block cipher Khufu and the stream cipher SEAL.

7.26 Fact (exhaustive key search) For an n-bit block cipher with /.--bit key, given a small number (e.g., [(k + 4)/n]) of plaintext-ciphertext pans encrypted under key К, К can be recovered by exhaustive key search in an expected time on the order of 2fc_1 operations.

Justification: Progress through the entire key space, decrypting a fixed ciphertext C with each trial key, and discarding those keys which do not yield the known plaintext P. The target key is among the undiscarded keys. The number of false alarms expected (non-target keys which map C to P) depends on the relative size of к and n, and follows from unicity distance arguments; additional (P', C) pairs suffice to discard false alarms. One expects to find the correct key after searching half the key space.

7.27 Example (exhaustive DES key search) For DES, к = 56, n = 64, and the expected requirement by Fact 7.26 is 255 decryptions and a single plaintext-ciphertext pair. □

If the underlying plaintext is known to contain redundancy as in Example 7.28, then ciphertext-only exhaustive key search is possible with a relatively small number of cipher- texts.

7.28 Example (ciphertext-only DES key search) Suppose DES is used to encrypt 64-bit blocks

of 8 ASCn characters each, with one bit per character serving as an even parity bit. Trial decryption with an incorrect key К yields all 8 parity bits correct with probability 2-8, and correct parity for t different blocks (each encrypted by K) with probability 2_8f. If this is used as a filter over all 256 keys, the expected number of unfiltered incorrect keys is 236/28*. For most practical purposes, t = 10 suffices. □

(i) Cascades of ciphers and multiple encryption

If a block cipher is susceptible to exhaustive key search (due to inadequate keylength), encipherment of the same message block more than once may increase security. Various such techniques for multiple encryption of n-bit messages are considered here. Once defined, they may be extended to messages exceeding one block by using standard modes of operation (§7.2.2), with E denoting multiple rather than single encryption.

7.29 Definition A cascade cipher is the concatenation of L > 2 block ciphers (called stages), each with independent keys. Plaintext is input to first stage; the output of stage г is input to stage i + 1; and the output of stage L is the cascade’s ciphertext output.

In the simplest case, all stages in a cascade cipher have к-bit keys, and the stage inputs and outputs are all n-bit quantities. The stage ciphers may differ (general cascade of ciphers), or all be identical (cascade of identical ciphers).

7.30 Definition Multiple encryption is similar to a cascade of L identical ciphers, but the stage keys need not be independent, and the stage ciphers may be either a block cipher E or its corresponding decryption function D = E~l.

Two important cases of multiple encryption are double and triple encryption, as illustrated in Figure 7.2 and defined below.

Multiple enayption

Figure 7.2: Multiple enayption.

7.31 Definition Double enayption is defined as E(x) = Ek2 (Ek3 (#)), where Ek denotes a block cipher Е with key К.

7.32 Definition Triple encryption is defined as E(x) = (ж))), where Ep denotes either Ek or Dk = Ejp. The case E(x) = Ek3(Dk2(Ek1(x))) is called E-D-E triple-encryption; the subcase K = K3 is often called two-key triple-encryption.

Independent stage keys K and K2 are typically used in double encryption. In triple encryption (Definition 7.32), to save on key management and storage costs, dependent stage keys are often used. E-D-E triple-encryption with K = K-2 = К г is backwards compatible with (i.e., equivalent to) single encryption.

(ii) Meet-in-the-middle attacks on multiple encryption

A naive exhaustive key search attack on double encryption tries all 22k key pairs. The attack of Fact 7.33 reduces time from 22k, at the cost of substantial space.

7.33 Fact For a block cipher with a /.--bit key, a known-plaintext meet-in-the-middle attack defeats double encryption using on the order of 2k operations and 2k storage.

Justification (basic meet-in-the-middle): Noting Figure 7.2(a), given a (P, C) pair, compute Mi = Ei(P) under all 2k possible key values K = i store all pairs (Mi, i), sorted or indexed on M, (e.g., using conventional hashing). Decipher C under all 2k possible values K2 = j, and for each pair (Mj.j) where Mj = Dj(C), check for hits Mj = Mi against entries M,; hr the first table. (This can be done creating a second sorted table, or simply checking each Mj entry as generated.) Each hit identifies a candidate solution key pair (i,j), since EjfP) = M = Dj(C). Using a second known-plaintext pair (P', C) (cf. Fact 7.35), discard candidate key pahs which do not map P' to C.

A concept analogous to unicity distance for ciphertext-only attack (Definition 7.69) can be defined for known-plaintext key search, based on the following strategy. Select a key; check if it is consistent with a given set (history) of plaintext-ciphertext pairs; if so, label the key a hit. A hit that is not the target key is a false key hit.

7.34 Definition The number of plaintext-ciphertext pahs required to uniquely determine a key under a known-plaintext key search is the known-plaintext unicity distance. This is the smallest integer t such that a history of length t makes false key hits improbable.

Using Fact 7.35, the (known-plaintext) unicity distance of a cascade of L random ciphers can be estimated. Less than one false hit is expected when t > Lk/n.

7.35 Fact For an L-stage cascade of random block ciphers with n-bit blocks and /.--bit keys, the expected number of false key hits for a history of length t is about 2Lk~tn.

Fact 7.35 holds with respect to random block ciphers defined as follows (cf. Definitions 7.2 and 7.70): given n and k, of the possible (2”)! permutations on 2" elements, choose 2k randomly and with equal probabilities, and associate these with the 2k keys.

  • 7.36 Example (meet-in-the-middle - double-DES) Applying Fact 7.33 to DES (n = 64, к =
  • 56), the number of candidate key pairs expected for one (P, C) pah is 248 = 2k ■ 2k/2n, and the likelihood of a false key pair satisfying a second (P', C) sample is 2-1G = 248 /2n. Thus with high probability, two (P, C) pahs suffice for key determination. This agrees with the unicity distance estimate of Fact 7.35: for L = 2, a history of length t = 2 yields 2_1G expected false key hits. □

A naive exhaustive attack on all key pairs in double-DES uses 2112 time and negligible space, while the meet-in-the-middle attack (Fact 7.33) requires 25G time and 2 56 space. Note 7.37 illustrates that the latter can be modified to yield a time-memory trade-off at any point between these two extremes, with the time-memory product essentially constant at

  • 2112 (e.g., 272 time, 240 space).
  • 7.37 Note (time-memory tradeoff-double-encryption) In the attack of Example 7.36, memory may be reduced (from tables of 25(1 entries) by independently guessing s bits of each of K, K'2 (for any fixed s,0 < s < k). The tables then each have 2k~s entries (fixing s key bits eliminates 2s entries), but the attack must be run over 2s2s pairs of such tables to allow all possible key pairs. The memory requirement is 2 • 2k~s entries (each n+k— s bits, omitting s fixed key bits), while time is on the order of 22s2k~s = 2k+s. The time-memory product js 22fc+l
  • 7.38 Note (generalized meet-in-tlie-middle trade-off) Variations of Note 7.37 allow time-space tradeoffs for meet-in-the-middle key search on any concatenation of L > 2 ciphers. For L even, meeting between the first and last Lf 2 stages results in requirements on the order of 2 . 2(kL/2)-s space and 2(fcL/2)+s time, 0 < s < kL/2. For L odd, meeting after the

first (L - 1)/2 and before the last (L + 1)/2 stages results in requirements on the order of

2.2k(L-1)/2 - . space and 2KL+i)/2 + s time> { < 8 < Ц1 _ !)/2.

For a block cipher with А-bit key, a naive attack on two-key triple encryption (Definition 7.32) involves trying all 22k key pairs. Fact 7.39 notes a chosen-plaintext alternative.

7.39 Fact For an n-bit block cipher with /.--bit key, two-key triple encryption may be defeated by a chosen-plaintext attack requiring on the order of 2k of each of the following: cipher operations, words of (n + A)-bit storage, and plaintext-ciphertext pairs with plaintexts chosen.

Justification (chosen-plaintext attack on two-key triple-encryption): Using 2k chosen plaintexts, two-key triple encryption may be reduced to double-encryption as follows. Noting Figure 7.2(b), focus on the case where the result after the first encryption stage is the allzero vector A = 0. For all 2k values K = i, compute P, = E~l (A). Submit each resulting Pi as a chosen plaintext, obtaining the corresponding ciphertext C,. For each, compute B, = E~1 (C,), representing an intermediate result В after the second of three encryption stages. Note that the values P, also represent candidate values B. Sort the values Pj and B, in a table (using standard hashing for efficiency). Identify the keys corresponding to pairs Pj = B, as candidate solution key pairs K = i, K2 = j to the given problem. Confirm these by testing each key pair on a small number of additional known plaintext-ciphertext pairs as required.

While generally impractical due to the storage requirement, the attack of Fact 7.39 is referred to as a certificational attack on two-key triple encryption, demonstrating it to be weaker than triple encryption. This motivates consideration of triple-encryption with three independent keys, although a penalty is a third key to manage.

Fact 7.40, stated specifically for DES (n = 64, к = 56), indicates that for the price of additional computation, the memory requirement in Fact 7.39 may be reduced and the chosen-plaintext condition relaxed to known-plaintext. The attack, however, appears impractical even with extreme parallelization; for example, for lg t = 40, the number of operations is still 280.

  • 7.40 Fact If t known plaintext-ciphertext pairs are available, an attack on two-key triple-DES requires 0(f) space and 2120_lg' operations.
  • (iii) Multiple-encryption modes of operation

In contrast to the single modes of operation in Figure 7.1, multiple modes are variants of multiple encryption constructed by concatenating selected single modes. For example, the combination of three single-mode CBC operations provides triple-inner-CBC', an alternative is triple-outer-CBC, the composite operation of triple encryption (per Definition 7.32) with one outer ciphertext feedback after the sequential application of three single-ECB operations. With replicated hardware, multiple modes such as triple-inner-CBC may be pipelined allowing performance comparable to single encryption, offering an advantage over triple-outer-CBC. Unfortunately (Note 7.41), they are often less secure.

  • 7.41 Note (security of triple-inner-CBC) Many multiple modes of operation are weaker than the corresponding multiple-ECB mode (i.e., multiple encryption operating as a black box with only outer feedbacks), and in some cases multiple modes (e.g., ECB-CBC-CBC) are not significantly stronger than single encryption. In particular, under some attacks triple- inner-CBC is significantly weaker than triple-outer-CBC; against other attacks based on the block size (e.g., Note 7.8), it appears stronger.
  • (iv) Cascade ciphers

Counter-intuitively, it is possible to devise examples whereby cascading of ciphers (Definition 7.29) actually reduces security. However, Fact 7.42 holds under a wide variety of attack models and meaningful definitions of '‘breaking”.

7.42 Fact A cascade of n (independently keyed) ciphers is at least as difficult to break as the first component cipher. Corollary: for stage ciphers which commute (e.g., additive stream ciphers), a cascade is at least as strong as the strongest component cipher.

Fact 7.42 does not apply to product ciphers consisting of component ciphers which may have dependent keys (e.g., two-key triple-encryption); indeed, keying dependencies across stages may compromise security entirely, as illustrated by a two-stage cascade wherein the components are two binary additive stream ciphers using an identical keystream - in this case, the cascade output is the original plaintext.

Fact 7.42 may suggest the following practical design strategy: cascade a set of key- stream generators each of which relies on one or more different design principles. It is not clear, however, if this is preferable to one large keystream generator which relies on a single principle. The cascade may turn out to be less secure for a fixed set of parameters (number of key bits, block size), since ciphers built piecewise may often be attacked piecewise.

< Prev   CONTENTS   Source   Next >