. 6
( 16)


Alice and Bob can use a modern block cipher as if it were a codebook. To
(lo so, they must first agree on a key K , which they share and nobody else
knows. This key distribution problem (which we discuss in Chapter 6) is a
major issue in practice, but in this chapter, we assume that Alice and Bob
know K , and nobody else knows K .
Given that Alice and Bob share the key K , then Alice can encrypt the
plaintext block by block, and send the resulting ciphertext to Bob. We call

this method of encrypting with a block cipher electronic codebook mode, or
ECB mode, since it is the “electronic” equivalent of a classic codebook cipher.
When a block cipher is used in ECB mode, a problem arises that can have
disastrous consequences for security. The problem is that as long as the key
has not changed, the same plaintext block will be encrypted to the same ci-
phertext block. If this is the case, then whenever the attacker, Trudy, observes
that ciphertext blocks Ci is the same as Cj, she immediately knows Pi = Pj.
If Trudy should happen to know Pi then she knows Pj, and even if she does
not know Pi, some information about the plaintext has leaked.
While this ECB issue may not seem like a serious concern, Figure 4.2
illustrates a case where it is devastating. In this example, an (uncompressed)
image file has been encrypted using ECB mode. However, the encrypted file
clearly does not protect the confidentiality of the data. This result occurs
simply because plaintext blocks that are the identical, encrypt to the same
ciphertext block, which allows patterns in the plaintext to bleed through into
the ciphertext. For this reason, ECB mode should generally be avoided.

Figure 4.2: Trudy lovcts ECB mode [142].

An “additive” would solve the problem inherent in ECB mode, since iden-
tical plaintext blocks would then result in distinct ciphertext blocks. But is
there a practical way to implement an electronic equivalent of an additive?
In fact, there is a surprisingly straightforward technique that will achieve the
desired result.
We define cipher block chaining mode, or CBC mode, as follows. Let IV

be a non-secret initialization vector, which is n bits in length, where n is the
size of a plaintext or ciphertext block. Then CBC encryption is defined as

C, = E(P, @ Cz--l, ) , for i = 0 , 1 , 2 , . . . ,
where thc first block, Co, requires special handling, since there is no C-1.
This is where we use the IV by defining C-1 = IV. It is necessary that we
can decrypt, which is accomplished via

O,1,2,. . . ,
Pi = D ( C i , K )CE Ci-1, for i =

where, again, C-1 = IV. Since the IV is playing the role of a ciphertext
block, it need not be secret-in practice, the IV is often sent as the first
hlock, immediately before the first ciphertext block.
With CBC mode, if Pi = Pj, we almost certainly have Ci # Cj. This is
the same effect that would be achieved by an additive in a classic codebook
cipher. To see that this actually works, consider Figure 4.3, which shows
Alice˜s image encrypted in CBC mode. Comparing this to Figure 4.2, the
value of CBC mode is readily apparent.

Figure 4.3: Trudy hates CBC mode [142]

CBC mode can also be used to provide data integrity. A message authen-
tication code (MAC) consists of only the final block of CBC mode encryption,
and this can be used to detect unauthorized changes to the data. Suppose
Alice has plaintext blocks Po, P I . . . . , P and Alice and Bob share a symmetric
key K . Then Alice generates a random IV and CBC “encrypts” her blocks

of plaintext using this IV and the key K . She saves only the final ciphertext
block Ce, which is the MAC. Alice can then send Ce, the IV and her plaintext
message to Bob. Upon receiving the message, Bob uses the IV and the shared
key K to CBC “encrypt” the received data. He compares the final ciphertext
block with the received MAC, and if they agree he can be virtually certain
that the data he has received is the data that Alice sent (see Problem 2 ) . The
MAC computation works because any change to a plaintext block will almost
certainly propagate through the CBC encryption, resulting in a different fi-
nal ciphertext block. Note that this is in stark contrast to CBC decryption,
where changes do not propagate, as discussed above.
There are, in fact, many other block cipher modes.™ One of the most
useful modes is counter mode, or CTR mode (see Problem 3), which allows
a block cipher to be used like a stream cipher [142].

Feistel Cipher
Before we dive into the cryptanalysis of specific block ciphers, we briefly
consider one popular block cipher design strategy, due to Horst Feistel [70].
In a Feistel Cipher the plaintext block P is split into a left half LOand a right
half Ro, that is,
p = (Lo,Ro).
1 , 2 , . . . , n a new left half Li and a new right half Ri
Then for each round i =
are computed as

where Ki is the subkey for round i, and F is the round function. The sub-
key Ki is derived from the key K , via a key schedule algorithm. The cipher-
text C is the output of the final round, that is,

To decrypt, we can simply solve for Li-1 and Ri-1 and run the Feistel
process backwards from n to 1. More precisely, starting with C = (L n ,Rn),
for i = n, n - 1,.. . ,I,we computc

( L ORo).
and the result is the corresponding plaintext P =

˜But, so far as the authors are aware, there is no block cipher & la mode.

Mathematically, any round function F that outputs n/2 bits will work.
However, it is also clear that the security of a Feistel Cipher depends on F , and
not every F will result in a secure cipher. For example, F(Ri-1, K i ) = Ri-1
will yield an insecure cipher. One nice feature of a Feistel Cipher is that all
questions of security boil down to questions about the round function F . The
round function may be simple or complex, but at least the analyst knows to
focus on F .
Many well-known block ciphers are Feistel Ciphers. For example, the most
famous block cipher in history, the Data Encryption Standard (DES), is a
Feistel Cipher. Even today, many block ciphers follow Feistel™s approach, and
many others (such as TEA [158]) vary only slightly from the strict definition
given here. In an effort to decrease the number of rounds required, some
recent block cipher designs (such as the AES) differ significantly from the
standard Feistel approach.
Next, we turn our attention to Hellman™s time-memory trade-off attack.
This is an interesting attack method that can be applied to any block cipher.
Then for the remainder of this chapter, we focus on the cryptanalysis of
three specific block ciphers, namely, CMEA, Akelarre and FEAL. These three
ciphers are each weak enough to be broken with a relatively small amount of
work, and each attack has some interesting and noteworthy aspects.
The CMEA cipher is extremely simple, at least by block cipher standards.
We discuss a chosen plaintext attack on CMEA, as well as a more realistic
known plaintext attack. The known plaintext attack is particularly interest-
ing, since it lends itself well to several algorithmic techniques that significantly
improve the attack.
Akelarre combines important features from two different highly-regarded
Mock ciphers. In spite of these “two rights,” Akelarre is a “wrong™?[82],since
it is very weak.
FEAL is a seriously flawed cipher that, nevertheless, proved extremely im-
portant in the development of modern cryptanalysis. While there are many
versions of FEAL, in this chapter we only consider the original version, now
known as FEAL-4. We discuss both linear and differential cryptanalytic
attacks on FEAL-4. In fact, differential cryptanalysis was originally devel-
oped to attack FEAL, and it later proved its true worth when applied to t,he
cryptanalysis of the Data Encryption Standard (DES). In a sense, linear and
differential cryptanalysis form the foundation on which modern block ciphers
are constructed, since all block ciphers are designed to withstand attacks
based on these two powerful techniques. Generally, these techniques arc only
of theoretical interest, but in the case of FEAL they yield practical attacks.
Differential crypt,analysis is also particularly well-suited for attacking hash
functions. In Chapter 5, we present attacks on two well-known hash functions
(MD4 and MD5) and both of these attacks rely on differential cryptanalytic
OFF 133

Hellman™s Time-Memory Trade-off

I t usually takes a long time to find a shorter way.
- Anonymous

The objective of a time-memory trade-off (TMTO) is to do some one-time
work so that each time the algorithm is executed it is more efficient. A TMTO
is a general technique that can be applied to improve the performance of many
types of algorithms.
In this section, we present Hellman™s cryptanalytic TMTO, which was
developed to attack the Data Encryption Standard (DES), but the approach
will work against any block cipher. Our discussion here closely follows that
given in [142].

Cryptanalytic TMTO
Martin Hellman describes his namesake cryptanalytic TMTO attack in [65].
Hellman™s TMTO is a generic attack on a block cipher, but it is particularly
effective against the Data Encryption Standard (DES) due to the small key
size of 56 bits. Hellman™s TMTO is a chosen plaintext attack.
Let P be a specified chosen plaintext block, and let C = E ( P , K ) be
the corresponding ciphertext block. We assume that whenever Trudy wants
to attack this cipher, she can specify the plaintext block P and obtain the
corresponding ciphertext block C . Trudy™s goal is to recover the key K .
The most obvious way to attempt to break a cipher is an exhaustive key
search. If the block cipher key K consists of k bits, then there are 2k keys
and via an exhaustive key search, Trudy would expect to find K after trying
about half of the keys. Then the exhaustive key search attack has a “time”
requirement of about and no “memory” (pre-computation) requirement.
Since we are assuming a known plaintext attack is possible, Trudy could
instead pre-compute the ciphertext C for every possible key K for her spec-
ified chosen plaintext P . This attack requires a one-time pre-computation
of 2k encryptions and storage of these 2k results. Then each time Trudy ex-
ecutes the attack, only a single table lookup is required, provided that the
pre-computed list is sorted. Neglecting the one-time work, the time per at-
tack is negligible. However, the one-time work is significantly larger than
an exhaustive key search, so unless the attack is conducted many times, an
exhaustive key search is more efficient.
Hellman™s TMTO attack achieves a middle ground between the exhaustive
key search and the massive pre-computation (and sorting) of all possible
ciphertexts for a given plaintext. The TMTO attack requires some one-time
work to generate a table of results (the “memory” part of the TMTO) that

is then used t o reduce the amount of work required (the “time” part of the
TMTO) each time the attack is executed.
Suppose that, Trudy wants t o attack a block cipher where the block size
is n = 64 bits and key is k = 64 bits. Since the key is 64 bits, t,here are 264
distinct keys. Trudy first chooses a fixed plaintext P and she obtains the
corresponding ciphertext C = E ( P ,K ) . Trudy wants t o recover the unknown
key K .
Trudy first randomly select a 64-bit “starting point,” denoted S P . She
then constructs a chain, of encryptions beginning from S P as follows. Trudy
chooses a positive integer t and she successively computes

where El™ = Kt-1 is the “ending point” of the chain of encryptions of length t .
Note that Trudy uses the ciphertext generated at one step as the key for the
next step. Since the block size and the key size are identical, this works.
Figure 4.4 illustrates this the process of generating a chain of encryptions
from S P to E P . To construct such a chain requires no knowledge of the inner
workings of the block cipher. The only fact we have used here is that the
block size and the key size are the same, but the process is easily modified if
this is not the casc.


Figure 4.4: A chain of encryptions.

Another view of an encryption chain is given in Figure 4.5. Here, we have
illustrated the chain as a path in the keyspace of the given block cipher.
Continuing with the example above, Trudy will generate m encryption
chains, each of length t . Now suppose that Trudy computes m = 232 encryp-
tion chains, each of length t = 232, and none of the resulting chains overlap.
This is unrealistic, since the chains essentially select elements o f t>hekeyspace

Figure 4.5: Chain of encryptions in the keyspace.

at random, but this assumption allows us to easily illustrate the concept be-
hind Hellman™s TMTO (below we consider a more realistic scenario). Then
each of the 264 keys lies within one exactly one chain. This idealized situation
is illustrated in Figure 4.6.

Figure 4.6: Trudy™s ideal scenario.

Only the starting points and ending points of the chains are savec., that
is, Trudy stores

For m = 232, the storage requirement is 2 m = 233 words, where each word
is 64 bits. In general, 2 m words must be stored, where each word is n bits.
Generating the starting points and computing the corresponding end points
is one-time work. The set of starting points and end points will be used each
time Trudy conducts the attack to recover an unknown key K , so the pre-
computation work can be amortized over the number of times the attack is
Once the pre-computation is completed, the attack is implemented as
follows. Trudy chooses the same plaintext P that was used in the pre-
computation phase, and she obtains the corresponding ciphertext C. To
find the key K , Trudy computes an encryption chain beginning with C of

maximum length t. That is, Trudy computes

and at each step i = 1 , 2 , . . . (up to a maximum of t steps), she compares X i
to each of the stored endpoints

Since C is itself a possible key value, by our idealized assumption, C lies
somewhere within exactly one chain. Suppose C is on chain j . Then for
some i E (0, l , . .. , t - l}, Trudy will find X i = EP,. This situation is
illustrated in Figure 4.7.

Figure 4.7: Path from C to EPj.

Once Trudy has found i and j such that X ; EPj, she can reconstruct
the initial part of chain j from SPj as

Since C = Xo = E ( P , K ) , we have K = Yt-,-l, as illustrated in Figure 4.8.
In this unrealistic example, the pre-computation phase of the attack re-
quires about trn = 264 work. Having paid this initial price, each time Trudy
executes the attack, she can expect that about 231 encryptions will be required
before an endpoint is found and another Z3' encryptions (approximately) will
be needed until C is recovered from the starting point of the chain, giving a
total work factor of 232 per attack.

Figure 4.8: Finding K from SP,.

If the attack is only to be executed once then an exhaustive key search,
with an expected work of 263, would be more efficient. But if the attack is to
be conducted many times, the pre-computation work can be amortized, since
the work of 232 per attack is negligible in comparison to the pre-computation.
Several refinements are possible. For example, Trudy could reduce the
pre-computation work by computing chains that only cover a part of the key
space. Then the probability of successfully finding an unknown key would
precisely equal the percentage of the key space that is covered by chains.
Necessarily, this is the way that Hellman™s cryptanalytic TMTO attack works
in practice.

4.4.2 Bad Chains
In reality, encryption chains are far different from the idealized case described
above. Instead of obtaining chains that nicely partition the keyspace, Trudy
will instead find chains that frequently merge with other chains or cycle.
Chains that misbehave (from Trudy™s perspective) in this way, create extra
work during the labor intensive pre-computation phase, since beyond the
point of a merge (or cycle), all encryptions are duplicating previous work.
Merging and cycling chains are illustrated in Figure 4.9.

Figure 4.9: Bad chains.

In the pre-computation phase work is wasted due to cycling and merging.
In addition, during the attack phase, cycles and merging lead to false alarms.
To see why this is the case, suppose Trudy executes a TMTO attack beginning
from C in Figure 4.9. Following the algorithm outlined above, she eventually
arrives at the endpoint E P . She then starts from corresponding S P and
reconstructs the chain that ends at E P , and she expects this to lead to the
key K . In this case, she does not find K since C does not lie on the ( S P ,E P )
If she can decrease the cycling and merging of chains, Trudy can reduce the

number of false alarms, and thereby reduce the work effective factor during
the pre-computation phase. To accomplish this, a “random function” F is
used. With such a function, a chain is computed as

When n = k , we can choose F to be a permutation.
The advantage of using random functions is apparent if we compare Fig-
ures 4.10 and 4.11. In Figure 4.10, where no random function (or the same
random) is used, once the two chains collide, they merge into a single chain.
The points on the merged chains represented duplicated work which makes
the pre-computation phase more expensive while not increasing the success
rate in the attack phase.

Figure 4.10: Merging chains.

On the other hand, in Figure 4.11 we see the effect of using different
random functions. In this example, the functions Fo and FI cause the chains
to (almost certainly) diverge immediately after a collision. Consequently,
with the use of different random functions, collisions can still occur, but the
effects of merging and cycling are mitigated.

F,, chain

SPI Fl chain

Figure 4.1 1: Non-merging chains.

Trudy could use a different random function for each chain, but it would
be resource intensive to store all of these functions. Instead. she can obtain

reasonable results by choosing r different functions, that is, we choose func-
tions Fi, for i = O , 1 , . . . ,T - 1, and for each of these construct m chains, each
beginning from a random starting point. As above, each chain is of length t.
The set of chains that correspond to a specific function is known as a table.
To summarize, we have r tables, m chains per table and t is the length of
each chain.
The pre-computation will cover some percentage of the key space with
chains. The resulting TMTO attack will find any key that lies within some
chain, but it cannot recover any key that is not within a t least one chain.
The attack is therefore probabilistic and Trudy™s objective is to maximize the
probability of success for a given amount of work. This is accomplished by
reducing merging and cycling as much as possible.
As above, we assume that the key length k is equal t o the cipher block
length n. Then the algorithm for pre-computing T tables of chains, each table
having m chains, with each chain of length t , is given in Table 4.1.

Table 4.1: Algorithm to Find ( S P ,E P ) Pairs

// Find (SPij,EPij),i = O , 1 , . . . , r - 1 and j = O , l , . . . , m - 1
for i = 0 t o r - 1
Choose a random function Fi
// Generate table i
Generate a random starting point SPij
KO= SPij
f o r e = 1 to t - 1
K!!= Fz(E(P,Ke-1))
next e
EPij = Kt-1
next j
next i
end findchains

The findchains algorithm in Table 4.1 finds a set of starting points and
ending points for r m chains, each of length t . Consequently, at most rmt
different keys could be recovered in the attack phase although, due to the
inevitable cycling and merging, the actual number will be significantly less
than rmt, as discussed below. If the desired key K is within one or more of
the chains, then it will be found following the algorithm in Table 4.2.
The definition of the function findKey in Table 4.2 is given in Table 4.3.
Note that findKey corresponds to the steps illustrated in Figure 4.8, while

Table 4.2: Algorithm to Find E P from C

// Given C , search for an endpoint E P
for i = 0 to r - 1
Y = F,(C)
for j = 1t o t
for t =0 to m- 1
i f Y == EPie t h e n
found = findKey(i,l,j)
i f not found t h e n
false alarm
e l s e / / found = K
r e t u r n ( found)
end i f
end i f
next t
Y = Fz(E(P,Y ) )
next j
next i
r e t u r n ( k e y not found)
end findEP

the algorithm in Table 4.2 corresponds to the steps illustrated in Figure 4.7.
Recall that r is the number of tables, m is the number of chains per table
and t is the length of each chain. Also note that searching for a matching
endpoint EPij in Table 4.2 can bc made considerably more efficient if the
pairs (SPij,EPij) within each table are sorted by endpoints. That is, we sort
the pairs (SPij,EPij) by EPij, where j = 0 , 1 , . . . , m - 1.
In Trudy™s ideal world, all of the rmt chain elements would be distinct,. If
this werc the case, then the chance of finding a randomly selected key would
he r m t / 2 k (assuming rmt 5 2 k ; otherwise the probability would be one).
Due to the merging and cycling discussed above, the real world is not so kind
tjo Trudy (which is fortunate for Alice and Bob). While random functions
help: they can only reduce the severity of the problem. Below we consider
the probability of success in more detail.
For many block ciphers k # n; DES has ri = 64 and k = 56, for exam-
ple, while AES offers several combinations of block and key lengths. If the
hlock length is not equal to thc key length, then we cannot directly use the
Ciphertext C as a key K . This situation is only a minor nuisance which is
easily resolved in practice by either truncating or expanding the ciphertext

Table 4.3: Algorithm to Find the Key from S P

// Is key K at position t 1 in chain t of table i?
- -

Y = Spa&
1t o t - j - 1
for Q=
Y = Fz(E(P,Y ) )
next q
c = E ( P , K ) then
e l s e / / false alarm
r e t u r n (not found)
end i f
end findKey

block as necessary. In contrast, the issue of merging and cycling chains is of
fundamental importance in this TMTO attack.

4.4.3 Success Probability
What is Trudy™s probability of success when she uses Hellman™s TMTO at-
tack? The fundamental problem is that keys can appear within more than
one chain. Therefore, estimating the probability of success is equivalent esti-
mating the probability of such duplication.
Perhaps the easiest2 way to estimate the success probability for Hellman™s
TMTO attack is to use the classic occupancy problem, which is described
nicely by Feller [49]. The details of the derivation are left as a homework
problem, but the result is that Trudy™s probability of successfully finding a
key is approximately

P(success) = 1 - e--mt+“. (4.3)
The probabilities given by (4.3) for various choices of mtr are given in Ta-
ble 4.4. Hellman suggests choosing

m = t = r = 2˜13 (4.4)
and, as can be seen in Table 4.4, the estimated probability of success for this
choice of parameters is about 0.63.
In general, the cryptanalytic TMTO pre-computation requires mtr en-
cryptions. The necessary storage is proportional to rm; the number of chains.
“Easiest” is not necessarily the same as “easy.”

Table 4.4: Approximate TMTO Success Probabilities

mtr P(success)
0 0
0 0

If key K lies on one of the pre-computed chains then the time required when
the attack is executed is about t (that is, t / 2 steps, on average, are needed to
find the matching E P and then another t / 2 steps are required. on average, to
find K ) . For the parameters in equation (4.4), this gives a pre-computation
of 2k encryptions, a memory requirement of 2 2 k / 3 , and a time requirement
of 22k/“. For example for DES-the cipher for which Hellman originally de-
veloped his attack --this yields a costly pre-computation of 256, but then the
resulting time and memory requirements for each instance of the attack phase
are both less than 238, with a high probability of success. Although the at-
tack is only probabilistic, the probability of success is high, provided that the
necessary pre-computation is feasible.

4.4.4 Distributed TMTO
Hellman™s TMTO is easily adapted to a distributed attack. This version of
the attack employs “distinguished points” \20]. The crucial insight is that
we need not use fixed-length chains, but, instead, we can simply construct

it chain until some easily distinguished point is found. For example, we can
construct each chain until we obtain an output of the form

. . , Zs-1, 0 , 0 , . . . , 0 ) .

Then each chain will, on average, be of length 271-s. In practice we would
want to set a limit, on the maximum length of a chain and reject, any chain
that exceeds the limit.
Using distinguished points, the pre-computation is similar to the case
4.4 HELLMA 143

described above, except that we now retain triples

where l j is the length of chain j (that is, the number of elements computed
before a distinguished point was found). We must also keep track of the
maximum length of any chain within a table; for table i, denote this as Mi.
Now suppose that r computers are available. Then each computer can
search one of the T tables of chains. Computer i only needs to know the
function Fi along with the ciphertext C and Mi, as well as the definition of a
distinguished point. In particular, the triples in equation (4.5) do not need to
be transmitted to any of the r computers, saving significant bandwidth and
reducing the storage requirement on the individual computers.
Each computer then proceeds with the attack as described above, with the
exception that instead of looking for a matching EPj at each step, a distin-
guished point is sought. If computer i finds such a point within Mi iterations,
the distinguished point is returned. Then secondary testing is necessary to
determine whether the putative solution is an actual endpoint from table i
or a false alarm. This secondary testing requires access t o all (SPj,E P j , l j )
triples in (4.5). Note that the overall work for secondary testing can be ad-
justed by selecting the definition of a distinguished point appropriately. If
an endpoint is found, the process of attempting to recover K from the cor-
responding starting point proceeds exactly as in the non-distinguished point
case discussed above.

TMTO Conclusions

Hellman™s cryptanalytic TMTO does not rely on any particular properties
of the underlying block cipher. But for the attack to be worth the effort,
the keyspace must be small enough that the TMTO has a reasonable chance
of success for a feasible pre-computation. Hellman™s TMTO attack can be
applied to any block cipher, provided there is sufficient computing power
available for the initial pre-computation and enough storage to effectively
deal with the tabulated results. Perhaps the most interesting aspect of this
TMTO attack is that it requires no knowledge of the internal workings of the
underlying block cipher.
In the remaining section of this chapter, we analyze attacks on three
specific block ciphers, namely, CMEA, Akelarre, and FEAL. Each of these
attacks depends heavily on the details of the underlying algorithms and it is
therefore necessary to dig into the inner workings of these ciphers. While each
of these ciphers is relatively weak, the attack methods differ considerably.


TIA/EIA Standard [147]

According to United States patent 5,159,634, the Cellular Message Encryp-
tion Algorithm, or CMEA, was developed by James A. Reeds3 CMEA is
a block cipher that was employed in the Telecommunications Industry As-
sociation (TIA) cell phone security architecture. Yes, this is the same TIA
that was responsible for the deeply flawed ORYX stream cipher discussed in
Chapter 3 .
In this section we first describe a chosen plaintext attack on a simplified
version of CMEA. Then we show that this attack can be extended to the real
CNIEA cipher. Finally, we discuss an interesting--and more realistic-known
plaintext attack on our simplified version of CMEA and we show that, this
attack is also easily extended to the real CMEA cipher. The CMEA attacks
presented here follow those given by Wagner, Schneier, and Kelsey in [152].
Legend has it that these attacks (or similar) originated with Greg Rose,4 who
was mysteriously forbidden from publishing his work [124].

CMEA Cipher

The CMEA cipher employs a 64-bit key and a variable block size, where the
block size is specified in bytes. Typical block sizes are said to be two to six
bytes [152].
The cipher utilizes a fixed 256-byte lookup table known as the Cave Table,
which appears in Table 4.5. Contrary to what might be expected, the Cave
Table is not a permutation and, in fact, only 164 distinct byte values appear.
Furthermore, the distribution of the 164 values that do appear is not close to
uniform: 97 of the bytes occur only once, while 44 appear twice, 21 appear
three times and the remaining two both occur four times.
Given a byte that consists of hex digits 11: and y, let C[zy] be the entry
in row 11: and column y of the Cave Table. For example, C[Ox4e] = 0x09,
since Ox09 is in row 0x4 and column Oxe of Table 4.5.
Let K O K 1 , . . . , E(7 be the eight byt,es of the 64-bit CMEA key. Given the

˜In 1998, Reeds deciphered Trithemius™ Stegunogruphia, a cryptanalytic challenge that
had stood for nearly 500 years [119].
˜This is the same Greg Rose whose work figures proniinently in Section 5.4.5.
4.5 CMEA 145

Table 4.5: Cave Table
0 1 234 5 6 7 8 9 a bcde f
34 11 a5 8d
0 d9 23 5f e6 ca 97 bO 7b f2 Oc 4e
77 8d 10
1 46
Oa 9f 5e 62 fl 34 ec a5 c9 b3 d8 2b
59 e3 d2 ff ae ca 15 8b 7d 38 21 bc 96 00
49 23 15 97 70
3 e4 cb 6f f2 3c 8 ba dl Od
8 ae
ba 44 9f 65 fl 7 09
4 20
e2 38 5d lc de ab c7
e8 10 74 62
5 86 bd Oa fl 3c cb 45 5f de
a7 29 93
b8 80 dl 12 ac 6d e9 cf f3 54 3a Ob 95 4e
a4 96 f8 57
bl 30 49 8e If 7c c3 2b da ed
7 05
Od 7a 97
8 bb 86 13 6c 51 30 e5 f2 2f d8 c4 a9
9 91 76 fO 17 43 a2 db ef 65 5e ca Od bc
e7 fa d8 81 6f 14 7c 5d c9 9e b6 33 ab
00 25
37 a2
b 5a 6f 9b d9 fe 71 c5 88 2d 00 b6 13 ec
4e 96 a8 5a b5 d7 c3 8d 3f f2 ec 04 60 71 lb 29
04 79 e3 c7 lb 81 9d dc 5f 3e bO f8 a2
4a 25
34 f6 5c 67 73 05
e 91 89 aa cb ee bf 18 dO 4d
12 eO 77 6c
f f5 ae 01 2f c3 49 8b bd da

key, succcssively define

and, finally,
+ K7] +
T ( z ) c[(s(x)
@ K6) (4.7)

where x is a byte and the additions are all taken modulo 256. By the definition
of T , it is apparent that T ( x )- J: is in the Cave Table for any byte x and the
same is true of S ( x )- 2 , R ( x )
-z, and Q ( x )-x. We niake use of these facts-
and the fact that the Cave Table is heavily biased-in the attacks discussed
As mentioned above, the CMEA block length is a variable number of
bytes. Let n the number of bytes in the CMEA block. Then the CMEA
encryption routine appears in Table 4.6.
Interestingly, the CMEA cipher is its own inverse. As a result, the en-
cryption routine in Table 4.6 is also the decryption routine. That is, if we
input the ciphertext to the algorithm, we obtain the corresponding plaintext.
Recall that the Enigma cipher is also its own invcrse. For Enigma, there
was a clcar advantage to being self-inverse, since the same settings could
be used for encryption and decryption. However, for CMEA-and modern
ciphers in general-it is not clear that there is any significant advantage
gained by being self-inverse.

Table 4.6: CMEA Encryption

// all arithmetic is mod 256 and “V” is OR
// ( c [ 0 ] ,c[l],. . . , c[n - 11) = output block of ciphertext bytes
1. (p[O],p[l], . . , p [ n - 11) = input block of plaintext bytes
2. z = o
3. f o r i = O t o n - 1
k =T(z@i)
5. p[i] = p[i] k
z= z+p[i]
7. n e x t i
8 . h = Ln/2]
9. f o r i = O t o h - 1
p [ i ] = p[i] 8 ( p [ n 1 - 21 v 1)
10. ˜

11. n e x t i
12. z = 0
13. f o r i = O t o n - l
k = T ( z @ i)
˜ [ =]p [ i ] - k
17. n e x t

From the definition of CMEA in Table 4.6, we see that if the cryptanalyst,
Trudy, can determine the function T , defined in 4.7, then she does not need t o
recover the key. The chosen plaintext attack discussed below does just that,
while in the known plaintext attack, discussed further below, we recover the
key. Provided that sufficient plaintext (chosen or known, as the case may be)
is available, both attacks are extremely efficient.
The value T ( 0 )plays a special role in CMEA. Below, we show that in the
chosen plaintext attack, once T ( 0 )is known. then T ( i ) , i = 1 , 2 , . . . , 255,
can be recovered easily. In the known plaintext attack it is slightly more
subtle, but T ( 0 )again is the linchpin of the attack. Consequently, in both of
these attacks, the first priority is t o determine T ( 0 ) .
For simplicity we restrict our attention t o the case where the block size
is n = 3 bytes. Analogous results hold for any block size.

SCMEA Cipher

Before attacking CMEA, we first present a slightly simplified version of the
cipher, which we call simplified CMEA, or SCMEA. Our SCMEA cipher is
4.5 CMEA 147

identical to the CMEA cipher in Table 4.6 except that line 10 is replaced by

10. p [ i ] = p [ i ]a P[” 1 - il
3 -

that is, the “V 1” has been eliminated.
Next, we present a chosen plaintext attack on SCMEA. This attack will
then be extended to an effective attack on the (nonsimplified) CMEA cipher.
After analyzing the chosen plaintext attack, we turn our attention to a more
realistic -but more complex-known plaintext attack.

SCMEA Chosen Plaintext Attack
Suppose the plaintext block is of the form

for some e and j . Then it is not difficult to show that the first byte of SCMEA
ciphertext is
co = c‚¬ 1 c‚¬ T ( j ) ) T ( 0 ) .
- (4.9)
We can use this fact to develop an efficient chosen plaintext attack on the
SCMEA cipher. In this attack, we first determine T(O),then use T ( 0 ) to
obtain the remaining T ( j ) , j = 1 , 2 , . . . ,255.
We encrypt chosen plaintext blocks of the form

(PO,Pl,PZ) (1 - Zo, 1 - Z0,O)

until we obtain a ciphertext byte co that satisfies


Then according to (4.8) and (4.9), with l = 0 and j = 0, any zo for
which (4.10) holds is consistent with zo = T ( 0 ) . Since T ( 0 ) = T ( 0 )- 0,
and we know that T ( z )- z is always in the Cave Table, we can restrict our
attention to zo that are among the 164 distinct values that appear in the
Cave Table.
Consider an 20 for which (4.10) holds. Then 20 is a putative value for T ( 0 ) .
Now for each j = 1 , 2 , 3 , .. . ,255 we choose

(PO,Pl,PZ) = (1 - 2 0 , ( j @ 2) 20,O)

and compute the corresponding ciphertext. If, in fact, 20 =
from (4.8) and (4.9) with t = 0, we have

co = (1CE Zj)- 2 0 ,

where xj = T ( j ) .If (4.11) holds, we can solve for xj = (cg 2 0 )@ 1. Now, if
it is the case that xo z T(O),we have xj = T ( j )and we know that T ( j )- j
is in the Cave Table. Therefore, for each j , we check whether xj - j is in the
Cave Table. If for any j we find xj - j is not in the Cave Table, we know
that xo # T ( 0 )and we must, continue t o search for T ( 0 ) . If, on the other
hand, xj - j is in the Cave Table for all j , then with high probability we have
found T ( 0 ) .
Since there are 164 elements in the Cave Table, and since T ( 0 )must be in
the Cavc Table, we expect t o find T ( 0 )using about 82 chosen plaintexts. Once
we have determined T(O),we can find all T ( j ) ,for j = 1 , 2 , 3 , .. . ,255, with
another 255 chosen plaintexts using (4.11). Consequently, the total chosen
plaintext requirement is about 337 blocks. In addition, a small number of
chosen plaintexts are required to resolve any false alarms. We give a careful
analysis of these false alarms when we consider the corresponding CMEA
attack below.

CMEA Chosen Plaintext Attack
Now consider the CMEA cipher. As in the SCMEA attack, above, we choose
plaintext of the form

(PO,Pl,PZ) = ( ( ( @ I )- T ( O ) , ( j @ 2 ) -(4?@1) - T ( t ) , O ) .

From the algorithm in Table 4.6, it can be shown that CMEA encryption
of (4.12) yields
co = ( ( e@ 1 CE ( T ( j ) 1)) - T ( 0 )
v (4.13)

( l @ - T ( l @ (T(.j) 1)).
( j CE 2) (4.14)
1) V
c1 = -

The corresponding equation for c2 is slightly more complicated and somewhat
more difficult t o derive; see Problem 11.
Analogous t o the SCMEA attack discussed abovc, in the CMEA attack we
use (4.13) t o determine whether a byte xo is consistent with xg = T ( 0 ) .Once
we find a putative T(O), can then use (4.13) to find all putative T ( j ) I,
we V
for j = 1 , 2 , . . . , 255. However, due to the “V” we can only determine 7 ™ ( j )
up t o ambiguity in the low-order bit position. Fortunately, we can make use
of (4.14) to resolve this ambiguity in the recovered T ( j ) , discussed below.
how eve^., before we consider this issue, we first provide more details on the
recovery of T ( 0 ) .
To find T(O), let l = j = 0 in (4.12) in which case the plaintext is
4.5 CMEA 149

and, according to (4.13), (4.14), and the solution to Problem 11, the corre-
sponding ciphertext is

((1CB ( T ( 0 ) 1))- T ( 0 )
co =
c1 = 1 - T ( T ( 0 ) 1)
c2 = T ( 0 ) T(((1 ( T ( 0 ) 1)) 1) @ 2).

We therefore encrypt chosen plaintexts of the form

and any of these that satisfy

0 and 2 0 is even
cg = (1 @ 1))- 2 0 =
(20 V
and xo is odd

are consistent with xo = T ( 0 ) .To further reduce the false alarm rate, we use
the fact that if zo= T ( 0 )then

v 1)
1 - ˜1 - (4.15)

(((1@ ( 2 0 v 1)) 1) CB 2)
zo (4.16)
- -

must both be in the Cave Table. Any false alarms that survives these tests
will be discovered quickly.
After having found a putative 2 0 = T(O), choose plaintext using (4.12),
with e = 0 for j = 1 , 2 , 3 , .. . ,255. For each j , we recover a putative value
for xj = T ( j ) 1 from (4.13). If neither xj - j nor (xj@ 1)- j is in the Cave
Table, then we have detected a false alarm, and we discard zo and continue
searching for T ( 0 ) . Assuming that 2 0 = T(O),then if only one of xj - j
or (xj@ 1)- j is in the Cave Table, we have unambiguously determined T ( j ) .
On the other hand, for each case where both xj - .j and (zj CB 1) - j are in
the Cave Table, the low-order bit of T ( j )is ambiguous.
To resolve the ambiguous low-order bit of a recovered T ( j ) , can make
use of (4.14). First, we recover all T ( j ) , j = 1 , 2 , . . . ,255, using T ( 0 )and
the method described in the previous paragraph. We also maintain an auxil-
iary array, A , where Aj = 0 if the low-order bit of T ( j )is known, and Aj = 1
if the low-order bit of T ( j )is ambiguous. We can use A to resolve the am-
biguous cases as follows.
Suppose that the low-order bit of T ( k ) is ambiguous, that is, T ( k )- k
and ( T ( k )@ 1) - k are both in the Cave Table. Then we set A k = 1. Now
we find a t and j such that

k = t @ ( T ( j ) 1) and At = 0 (4.17)

(that is, T ( t )is not ambiguous). If such a t and j are found, we then set

po = ( t CE 1) - T ( 0 )
( t @ 1) - T ( t )
( j 6 2)
p1 = -

P2 =

and encrypt this plaintext block using CMEA, to obtain the the corresponding
ciphertext block (co,e l , c2). From (4.14), we have

T ( tQ ( T ( j ) 1)) = ( j @ a ) - ( t CB 1) - C I ,

which. by our choice of t and j gives

( t CE 1) - c1.
T ( k ) = ( j (22) -

There is no ambiguity in this equation, and consequently we have resolved
the low-order bit of T ( k ) . Problem 14 explores the probability that this
part of the attack will fail. Note that this part of the attack fails if for an
ambiguous T ( k ) ,we cannot find t and j satisfying (4.17).
Now we provide a careful analysis of the expected number of chosen plain-
texts required in this attack. Each time we test an element in the Cave Table
to see whether it is a possible T(O),there is a chance of a false alarm. As
noted above, letting ! j = 0 in (4.12), a plaintext of the form

= (1 - T(O), - T(O),O)
(PO,Pl,lnZ) 1
{ if T ( 0 )is even
co= if T ( 0 )is odd.
Another interesting and related property of CMEA encryption is considered
in Problem 12.
Since, on average, we require 82 iterations before we can determine T(O),
the probability of false alarms can be approximated by a binomial distribu-
tion with n = 81 and p = 1/128. Therefore, the expected number of false
alarms is about n p = 81/128 M 0.63. If we include a check that both (4.15)
and (4.16) are in the Cave Table, then the expected number of' false alarms
drops to 0.63( 164/256)' M 0.258.
Recall that 164 of the 256 elenients in the Cave Table are distinct. Also,
we have that T ( i )- i is in the Cave Table, for i = 0 , 1 , 2 , . . . ,255. Since T ( 0 )
is in the Cave Table, about 82 chosen plaintexts are required before we expect
to find T ( 0 ) .Once T ( 0 )has been recovered, one chosen plaintext is required
to determine each of the remaining values T ( i ) , i = 1 , 2 , 3 , .. . ,255. This
gives a total of 337 chosen plaintexts.
However, some of the recovered T ( i )will be ambiguous in the low order
bit. The low order bit of T ( i )is known if either T ( i )- i or ( T ( i ) 1) - i
4.5 CMEA 151

is not in the Cave Table. It can be shown (see Problem 9) that given any z
in the Cave Table, the probability that ((z i) @ 1) - i is in the Cave Table
is approximately 0.6. Consequently, we expect to find about 0.6. 255 M 153
ambiguous entries, and for each of these, one additional chosen plaintext is
required. Note that if neither T ( i )- i nor ( T ( i ) 1)- i is in the Cave Table,
then a false alarm has occurred, that is, the putative value of T ( 0 )is incorrect.
Assuming z E {0,1,2,.. . ,255}, is selected uniformly it can be shown (see
Problem 10) that the probability that z and z @ 1 are both not in the Cave
Table is about 0.11. A false alarm for T ( 0 )is detected as soon as such a
value is generated. Each additional step that is needed before detecting a
false alarm requires one chosen plaintext, so the expected number of chosen
plaintexts per false alarm is about 9. Overall, we expect false alarms to
require about 0.258 . 9 z 2.3 additional chosen plaintexts.
Combining these results, we find that the total expected number of chosen
+ +
plaintexts is 82 255 153 + 2.3 z 492.3. This accords remarkably well with
the empirical data in Table 4.7, which is the average of lo6 trials, using a
randomly generated key for each trial.

Average to Average Average
Find T ( 0 ) T ( j )V 1 Ambiguous
Trials False Alarms Total
106 81.84 255 152.89 2.43 492.16

In practice, this chosen plaintext attack is likely to be unrealistic, due to
the relatively large number of plaintext blocks required, and, especially, due
to the fact that we must choose the plaintext. Next, we consider a known
plaintext attack which is much more likely to be practical. First, we apply
the attack to SCMEA, then we explain how the attack can be extended to
CMEA. This known plaintext attack (for CMEA) appears in [152].

SCMEA Known Plaintext Attack
As with the chosen plaintext attack, above, this attack relies on the fact
that T ( 0 ) plays a special role in the CMEA cipher (and also in SCMEA).
The known plaintext attack we describe here has two phases, a primary
phase and a secondary phase, where the objective of the primary phase is
to determine T(O),or a small number of candidates for T ( 0 ) . Then in the
secondary phase, we determine the key, and simultaneously eliminate any
invalid put,ative T ( 0 )that survived the primary phase.
We briefly outline each of the two phases of the SCMEA attack before
providing more details on both phases. Then we extend the attack to CMEA.

Outline of Attack

In the primary phase of the attack, we make use of the fact that if we
know T(O),then known plaintext-ciphertext pairs place restrictions on the
possible values of other T ( j ) .In fact, we can show that each known plaintext
gives us three tests that can be used to check the validity of other puta-
tive T ( j ) .If any of these tests fail, then the computed value of T ( j )must be
incorrect, which implies that the assumed value of T ( 0 )is incorrect.
For the primary phase of the attack, we guess each possible value for T(O),
and use the known plaintext to deduce information about other T ( j )bytes.
If our guess for T ( 0 ) is incorrect, given sufficient known plaintext, we are
highly likely to arrive at a contradiction, at which point we can eliminate our
current putative T ( 0 )as a candidate for T ( 0 ) .
Once all possible T ( 0 )have been tested in the primary phase, we will
have determined T(O), a small number of candidates for T(O),
or depending
on the number of known plaintext blocks available. We then move on to the
secondary phase, where we use a combinatorial search technique known as
backtracking [87] to recover the key. This secondary phase relies on informa-
tion accumulated during the primary phase-information gleaned from the
known plaintext. The success of the secondary phase depends not only on
the fact that T ( j ) j is in the Cave Table, as can be seen from (4.7), but also
on the fact that the intermediate values, & ( j ) - j , R ( j )- j , and S ( j ) j , are

in the Cave Table, as can be seen in (4.6).
Of course, we want to minimize the amount of known plaintext that is
needed. But as we reduce the amount of known plaintext, we are increasingly
likely to find additional putative values for T ( 0 ) that survive the primary
phase of the attack, and we are more likely to lack sufficient information to
trim the keys found in the secondary phase to a sufficiently small number.
However, by using another combinatorial search technique, it is possible
to further reduce the known plaintext requirement. Provided that we have
uniquely determined a few T ( j )values in the primary phase, a m e e t - i n - t h e -
m i d d l e approach can be used to dramatically reduce the number of putative
keys recovered, as compared to the simpler (and more intuitive) backtrack-
ing method mentioned in the previous paragraph. Meet-in-the-middle is a
standard technique from the field of combinatorial search, where it goes by
the clever name of meet-in-the-middle. When it is applicable, a meet-in-the-
middle attack can essential provide a square root improvement in the work
fador, but it is can be relatively complex to implement.
Next, we describe this known plaintext attack in more detail. For sim-
plicity, we initially focus on the SCMEA cipher, then we show that the attack
extends easily to CMEA-although significantly more known plaintext is re-
quired to obtain comparable results.
4.5 C M E A 153

Primary Phase
Our first objective is to determine T ( 0 ) . Since T ( 0 )is in the Cave Table,
T ( 0 )is limited to one of the 164 distinct bytes that appear in the Cave Table.
For each of the 164 possible choices for T(O),we construct a 256 x 256
table A , such that Ai,j = 1 if it is possible that T ( i ) = j , and Ai,j = 0 if
it is not possible that T ( i ) = j . To begin, we initialize Ai,j = 1 for all i
and j . Then we make use of the restrictions inherent in the Cave Table
to find impossible entries in A , that is, we find i and j for which we must
have Ai,j = 0 due to the st,ructure of the Cave Table. Finally, we use the
known plaintext to mark additional impossible entries in the A table.
Denote the 164 distinct Cave Table bytes as

Since T ( j )- j is in the Cave Table for j = 0 , 1 , 2 , . . . ,255, we have

This immediately places 92 zeros in row j of A. We repeat this for each
row of A, so that each row has 164 ones and 92 zeros. Note that this is
independent of the known plaintext or any assumption on the value of T ( 0 ) .
Now for a given putative T(O), can use the known plaintext to deduce
additional information about various T ( j )and, in the process, place addi-
tional 0s in the table A. Ideally, for any incorrect choice of T(O),we will
arrive at a contradiction from the entries in A. In practice, it is sufficient to
simply reduce the number of possible choices for T ( 0 )to a small number.
As above, we are assuming that the block size is three bytes. Denote a
known 3-byte plaintext block as P = (po,pl,p2) and let C = ( C O , C ˜ , C be ˜)
the corresponding ciphertext block.
By carefully stepping through the SCMEA algorithm, where we are as-
suming a block size of n = 3, it can be shown that

which we rewrite as

Now if we are given a known plaintext block P = ( p o , p l , p ˜ ) and the corre-
sponding ciphertext byte CO, we can use (4.18) to eliminate some potential
values of T ( j ) .

For example, suppose the (po,pl,p2) = (Oxai, Ox95,0x71) and the corre-
sponding ciphertext block has co = 0x04. Further, suppose that for this key,
we guess T ( 0 )= 0x34. Then (4.18) reduces to

+ T(Oxd4)) 63 2)
Ox7c = T ((Ox6a

As rioted above, there are 164 possible value for T(Oxd4). Once we specify
one of these values for a putative T(Oxd4), the argument to the “outer” T
function is known, as is the value of the “inner” T function.
Now let y = (Ox6a + T(Oxd4)) @ 2. If Ay,Ox˜c 0, then this impossible
critry in the table immediately implies that our guess for T(Oxd4) is incorrect,
and we mark it as such in the A table.
For example, since 0 is in the Cave Table, we guess T(Oxd4) = Oxd4 to
see if an impossibility arises. In this case, (Oxd4 Ox6a) @ 2 = Ox3c and we
test whether T(Ox3c) = Ox7c is possible, based on the current, A table, that
is we check the value of A0x3c,0x7c. this is 0, we know that T(Oxd4) # Oxd4
a.nd we specify this in the A table by set.ting AOxd4,0xd4= 0. We then continue
to tcst each of the remaining 163 choices for T(Oxd4) in a similar mariner.
If it should happen that all of the 164 possible choices for T(Oxd4) are
impossible, then we know that our guess for T ( 0 )is incorrect and we proceed
to our next guess for T ( 0 ) . In any case, we have almost certainly placed
additional impossible entries in the A table, thereby increasing our knowledge
of T , assuming that the T ( 0 )assumption is correct.
We must repeat this for each known plaintext block. Furthermore, if any
new impossible entries are added to A, we must then repeat the entire process
for all of the known plaintext again. This must be iterated until no changes
are made to A during one entire pass through the known plaintexts.
With enough known plaintexts, we will uniquely determine T(O),and in
the process, we might uniquely determine additional values of T ( j ) .We will
also be able to place significant restrictions on many of the T ( j )that have
riot been uniquely determined.
Unfortunately, the amount of known plaintext to uniquely determine T ( 0 )
by this approach is large. However, we are not using all of the available in-
formation. Forniulas analogous to (4.18) can be found for both c1 and c2
(see Problem 15). By using this additional information, we can dramatically
reduce t,he known pla,intext required to uniquely determine T ( 0 ) . Ernpiri-
cal estimates of the number of plaintext blocks required are summarizcd in
Table 4.8.

Secondary Phase: Backtracking

After successful completion of the primary phase, we will have recovered T(O),
or a small number of candidates. We now discuss a method for determining
4.5 CMEA 155

Ciphertext bytes used co only co and c1 co,c1 and c2
300 90 60
Known plaintext blocks

the key from the information accumulated to this point. For the remain-
der of this section, we assume that in the primary phase we uniquely deter-
mined T ( 0 ) ;if not, we simply repeat this secondary phase for each candi-
date T ( 0 ) .
In the chosen plaintext attack, discussed above, we recovered T , without
finding the key. In contrast, in the secondary phase of the known plaintext
attack presented here, we recover the key, using the A table obtained in the
primary phase.
From (4.7) we have

+ K7] + z
T ( z )= c[(s(z)K6)

and S(z) is an element of the Cave Table. Consequently,

+ x) @ K6) + K7] + z
T ( z )= c [ ( ( V
for some z1 in the Cave Table. We select a putative ( K GK7), and a particu-
lar z. Then we test each z1 that is in the Cave Table, by computing

+ x) @ K6) + K7]+
=c[((v 2

and looking up the value of Ax,u.If for any z we find that every z1 in the Cave
Table yields Ax,v = 0, then the choice of ( K G , K must be incorrect. This
will reduce the number of possible partial keys ( K 6 ,K7), with the number of
survivors depending on the amount of information available in A, which, in
turn, depends on the number of known plaintexts. Typical results for this
secondary phase of the SCMEA attack are given in Table 4.9.

Table 4.9: Number of Surviving

Known plaintext blocks 50 75 100 150
Partial keys (K6,K7) 19800 2002 42 2

For each putative ( K G , K ˜ ) , can determine putative ( K 4 , K s )values
from the pair of equations

+ K5] +
S(z)= C [ ( R ( Z@ K4)
) 5


. 6
( 16)