# 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 2^{fc_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 2^{55} 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 2^{56} keys, the expected number of unfiltered incorrect keys is 2^{36}/2^{8}*. 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.

**Figure ***7.2: Multiple enayption.*

7.31 Definition *Double enayption* is defined as *E(x) = Ek*_{2} (Ek_{3} (#)), 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) = Ek** _{3}*(Dk

*(Ek*

_{2}*(x))) is called*

_{1}*E-D-E triple-encryption*; the subcase

*K*=

*K*

*is often called*

_{3}*two-key triple-encryption.*

Independent stage keys *K* and *K** _{2}* 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 *2 ^{2k}* key pairs. The attack of Fact 7.33 reduces time from

*2*at the cost of substantial space.

^{2k},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 *2** ^{k}* operations and

*2*

*storage.*

^{k}*Justification* (basic meet-in-the-middle): Noting Figure 7.2(a), given a (*P*, *C*) pair, compute *Mi = Ei(P)* under all *2 ^{k}* possible key values

*K*=

*i*store all pairs

*(Mi, i),*sorted or indexed on

*M,*(e.g., using conventional hashing). Decipher

*C*under all

*2*possible values

^{k}*K*

_{2}*= 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 *2*^{Lk}~^{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 *2** ^{k}* randomly and with equal probabilities, and associate these with the

*2*

*keys.*

^{k}- 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 2^{48}=*2*and the likelihood of a false key pair satisfying a second^{k}■ 2^{k}/2^{n},*(P', C)*sample is 2^{-1G}= 2^{48}/2^{n}. 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 2^{112} time and negligible space, while the meet-in-the-middle attack (Fact 7.33) requires 2^{5G} 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

- 2
^{112}(e.g., 2^{72}time, 2^{40}space). - 7.37 Note (
*time-memory tradeoff-double-encryption)*In the attack of Example 7.36, memory may be reduced (from tables of 2^{5(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*2*entries (fixing s key bits eliminates^{k}~^{s}*2*entries), but the attack must be run over 2^{s}^{s}•*2*pairs of such tables to allow all possible key pairs. The memory requirement is 2 •^{s}*2*entries (each^{k}~^{s}*n+k—**s*bits, omitting*s*fixed key bits), while time is on the order of 2^{2s}•*2*The time-memory product j^{k}~^{s}= 2^{k+s}._{s}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}.* _{2}k(L-1)/2* - .

_{space and 2}

*KL+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 *2 ^{2k}* 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 *2** ^{k}* 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 *2 ^{k}* 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

*2*values

^{k}*K*=

*i,*compute

*P, = E~*). Submit each resulting

^{l}(A*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*,

*K*

_{2}*= 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 2^{80}.

- 7.40 Fact If
*t*known plaintext-ciphertext pairs are available, an attack on two-key triple-DES requires 0(f) space and 2^{120_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.