- 
,
and finishes in minutes or hours of computation on a standard workstation.
This demonstrates that CMEA is deeply flawed.
David Wagner Bruce Schneier John Kelsey
University of California, Berkeley Counterpane
Systems
[email protected] {schneier,kelsey}@counterpane.com
May 30, 1997
This paper analyzes the Telecommunications Industry Association's
Cellular Message Encryption Algorithm (CMEA),
which is used for confidentiality of the control channel
in the most recent American digital cellular telephony systems.
We describe an attack on CMEA which requires 40-80 known plaintexts,
has time complexity about - ,
and finishes in minutes or hours of computation on a standard workstation.
This demonstrates that CMEA is deeply flawed.
Keywords: cryptanalysis, block ciphers, cellular telephone
As the US cellular telephony industry has boomed, the need for security has increased: both for privacy and fraud prevention. Because all cellular communications are sent over a radio link, anyone with the appropriate receiver can passively eavesdrop on all cellphone transmissions in the area without fear of detection. The earliest U.S. cellular telephony systems relied on the high cost of cellular-capable receivers (or scanners) for security. When such scanners become affordable and widely available, the cellphone industry lobbied for protective legislation. But these legal prohibitions have failed to solve the problem, and systems architects have been forced to turn increasingly to cryptography for more robust security.
The cellular telephony industry players are especially concerned with fraud prevention. The FCC estimates that the cellular industry loses more than $400 million per year to fraud [FCC97]. Cellphone cloning is probably the foremost form of this problem. Because most of today's cellphones identify themselves over public radio links by sending their identity information in the clear, eavesdroppers can (and do) easily misappropriate others' identity information to make fraudulent phone calls. While the latest digital cellphones currently offer some weak protection against casual eavesdroppers because digital technology is so new that inexpensive digital scanners have not yet become widely available, the president of the Cellular Telecommunications Industry Association testified in recent Congressional hearings [Whe97] that ``history will likely repeat itself as digital scanners and decoders, though expensive now, drop in price in the future.''
Cryptographic mechanisms are one obvious way to combat cloning fraud, and indeed, the industry is turning to cryptography for protection. In 1992, the TR-45 working group within the Telecommunications Industry Association (TIA) developed a standard for integration of cryptographic technology into tomorrow's digital cellular systems [TIA92], which has been updated at least once [TIA95]. Some of the most recent cellphones to hit the market already include these cryptographic protection mechanisms [Nok96].
The TIA standard [TIA95] describes four cryptographic primitives for use in North American digital cellular systems:
.Note that CMEA is not used to protect voice communications. Instead, it is intended to protect sensitive control data, such as the digits dialed by the cellphone user. A successful break of CMEA might reveal user calling patterns. Also sent CMEA-encrypted are digits dialed (all DTMF tones) by the remote endpoint and alphanumeric personal pages recieved by the cellphone user. Finally, compromise of the control channel contents could lead to any confidential data the user types on the keypad: calling card PIN numbers may be an especially widespread concern, and credit card numbers, bank account numbers, and voicemail PIN numbers are also at risk.
This paper is organized as follows. We describe CMEA in Section 2 for reference. Next, Section 3 lists some observations that form a foundation for our later analysis. Then we give effective chosen- and known-plaintext attacks on CMEA in Sections 4 and 5. Finally, Section 6 concludes.
We describe the CMEA specification fully here for reference. CMEA is a byte-oriented variable-width block cipher with a 64 bit key. Block sizes may be any number of bytes; in practice, US cellular telephony systems typically apply CMEA to 2-6 byte blocks, with the block size potentially varying without any key changes. CMEA is quite simple, and appears to be optimized for 8-bit microprocessors with severe resource limitations.
CMEA consists of three layers. The first layer performs one non-linear pass on the block; this effects left-to-right diffusion. The second layer is a purely linear, unkeyed operation intended to make changes propagate in the opposite direction. One can think of the second step as (roughly speaking) XORing the right half of the block onto the left half. The third layer performs a final non-linear pass on the block from left to right; in fact, it is the inverse of the first layer.
CMEA obtains the non-linearity in the first and third layer from a 8-bit keyed lookup table known as the T-box. The T-box calculates its 8-bit output as
given input byte x and 8-byte key 
.
In this equation C is an unkeyed 8-bit lookup table known as the CaveTable;
all operations are performed using 8-bit arithmetic.
The CaveTable is given in Figure 1,
We now provide a specification of CMEA.
The algorithm encrypts a n-byte message 
to a ciphertext 
under the key as follows:
Here all operations are byte-wide arithmetic: + and - are addition and subtraction modulo 256,
for
¯
for
for
stands for a logical bitwise exclusive or,
represents a logical bitwise or,
and the keyed T function is as described previously.
CMEA is specified in [TIA92, TIA95]; it is also described in U.S. Patent 5,159,634 [Ree91], though a different T-box method is listed.
First, we list some preliminary observations:
J. Hillyard [Hil97] has noted that codebook attacks may still be possible in practice. In some contexts, each digit dialed will be encrypted in a separate CMEA block (with fixed padding); because CMEA is used in ECB mode, the result is a simple substitution cipher on the digits 0-9. Techniques from classical cryptography may well suffice to recover useful information about the dialed digits, especially when side information is available.
and 
leaves the action of the T-box unchanged;
the same holds for 
and 
for i=0,1,2,3.
Therefore for the rest of the paper
we take the MSBs of 
and 
to all be 0, without loss of generality,
and we see that the effective key length of CMEA is at most 60 bits. is never recovered.
from 
;
one cannot trivially predict where other T-box entries are
likely to be used.
Knowing T(0) lets one learn the inputs to the T-box lookups
that modify the second byte in the message.The skew in the CaveTable means that the T-box values are skewed, too: we know T(i)-i must appear in the CaveTable, so for any input to the T-box, we can immediately rule out 92 possibilities for the corresponding T-box output without needing any knowledge of the CMEA key.
CMEA is weak against chosen-plaintext attacks:
one can recover all of the T-box entries with about 338 chosen texts
(on average) and very little work.
This attack works on any fixed block length n;SPMgt;2; the attacker
is not assumed to have control over n.
We have implemented the attack to empirically verify it for correctness;
the attack is extremely successful in our tests.
The attack proceeds in two stages, first recovering T(0),
and then recovering the remainder of the T-box entries;
the CMEA key itself is never identified.
First, one learns T(0) with (256-92)/2=82 chosen plaintexts (on average).
For each guess x at the value of T(0), obtain the
encryption of the message 
,
e.g. the message P where each byte has the value 1-x;
if the result is of the form 
then we can conclude with high probability that indeed T(0)=x.
False alarms occasionally occur, but they can be ruled out quickly in
the second phase because of the skewed CaveTable distribution.
Note that there are only 256-92=164 possible values of T(0),
since T(0) must appear in the CaveTable, and therefore we expect
to identify the correct value after about 164/2=82 trials, on average.
In the second phase of the attack,
one learns all of the remaining T-box entries with
256 more chosen plaintexts.
For each byte j, to learn the value of T(j), let
, where the desired blocks are n
bytes long. Obtain the encryption of the message
;
if the result is of the form 
, then we may conclude
that T(j) = t, except for a possible error in the LSB.
A more sophisticated analysis can resolve the uncertainty in
the LSB of the T-box entries.
In practice, chosen-plaintext queries may be available in some special situations. Suppose the targeted cellphone user can be persuaded to a call a phone number under the attacker's control--perhaps a menuized survey, answering machine, or operator. The phone message the user receives might prompt the user to enter digits (chosen in advance by the attacker), thus silently enabling a chosen-plaintext attack on CMEA. Alternatively, the phone message might send chosen DTMF tones to the targetted cellphone user, thus mounting chosen-plaintext queries at will.
We now describe a known plaintext attack on CMEA needing about 40-80
known texts.
The attack assumes that each known plaintext is enciphered
with a 3-byte block width.
Our (unoptimized) implementation has a time
complexity of to , and can be easily parallelized.
Our cryptanalysis has two phases. The first phase
gathers information about the T-box entries from the known
CMEA encryptions, eliminating many possibilities for the values of each
T-box output. In this way we reduce the problem to that of
cryptanalysis of the T-box algorithm, given some partial information
about T-box input/output pairs. In the second phase, we take advantage
of the statistical biases in the CaveTable to cryptanalyze the T-box and
recover the CMEA key , using pruned search and
meet-in-the-middle techniques to enhance performance.
The first phase is implemented as follows.
Because T(0) occupies a position of special importance,
we exhaustively search over the 164 possibilities for T(0).
(Remember that T(0) must appear in the CaveTable, and so there
are only 256-92=164 possibilities for it.)
For each guess at T(0),
we set up a 
array 
which records for each i,j whether T(i)=j is possible.
All values for T(i), i;SPMgt;0 are initially listed as possible.
Since T(i)-i is a CaveTable output
and the CaveTable has an uneven distribution,
we can immediately rule out 92 values for T(i).
Next, we gradually eliminate impossible values using the known texts as follows. The general idea is that each known plaintext/ciphertext pair lets us establish several implications of the form
If we have already eliminated T(i')=j' as impossible,
then we can conclude that T(i)=j is also impossible
via the contrapositive of (1).
In this way, we successively rule out more and more possibilities
in the array, until we either reach a contradiction
(in which case we start over with another guess at T(0))
or until we run out of logical deductions to make
(in which case we proceed to the second phase).
The second phase recovers the CMEA key from the information about T
previously accumulated in the array.
Our simplest key recovery algorithm is based on pruned search.
First, one guesses and 
.
Then, we peel off the effect of the last 1/4 of the T-box,
and check whether the intermediate value is a possible CaveTable output.
The intermediate value must always be one of the 164 possible
CaveTable outputs when we find the correct 
;
because the CaveTable is so heavily skewed,
incorrect guesses will usually be quickly identified by
this test, if we have knowledge about a number of T-box entries.
Next, one continues by guessing 
, pruning the search
as before, and continuing the pruned search until the entire key
is recovered.
This technique is very effective if enough information is available
in the array.
Unfortunately, pruned search very quickly becomes extremely
computationally intensive if too few known texts are available:
at each stage, too many candidates survive the pruning, and
the search complexity grows exponentially.
We have a more sophisticated key recovery algorithm which can reduce
the computation workload dramatically in these instances.
The basic idea is that the T-box is subject to a classic
meet-in-the-middle optimization:
one can work halfway through the T-box given only 
,
and one can work backwards up to the middle given just 
.
This enables us to precompute a lookup table that contains the
intermediate value corresponding to each value.
Then, we try each possible value, work backwards
through some known T-box outputs, and look for a match in
the precomputed lookup table.
Of course the search pruning techniques can be applied to
to further reduce the complexity of the
meet-in-the-middle algorithm.
The combination of pruned search and meet-in-the-middle cryptanalysis
allows us to efficiently recover the entire CMEA key
with as few as 40-80 known plaintexts.
We describe how to derive implications of the form (1)
from some known CMEA encryptions for the first phase.
Knowing T(0) lets us recover (for each plaintext/ciphertext pair P,C)
and thus we learn the inputs to the two T-boxes
lookups used to modify 
.
We make a guess (e.g. T(i)=j)
about the output of the first aforementioned T-box lookup.
We can derive the (implied) output of the second T-box lookup
by using the known text pair.
Then we deduce the (implied) values of 
and
thus the inputs to the two T-box lookups used to modify 
.
Next we derive the quantity XORed into in the second
CMEA layer, which lets us calculate the (implied) outputs of the
two T-box lookups that modify .
Therefore our assumption T(i)=j implies
three other derived equations of the form T(i')=j';
if any of those three derived input/output pairs i',j' is listed as
impossible in 
, then we have
found a contradiction, and we may conclude that our original
assumption was wrong--namely, that the assumed value of
the T-box entry was in fact impossible, and that value may
be marked as impossible in .
In this way, we can gradually rule out many entries as impossible.
We loop over all i,j and all known texts, until no more deductions
can be made.
If our guess at T(0) was incorrect, then there will probably
be a T-box input for which no possible output values remain,
and in this case we will be able to discard our incorrect guess at T(0).
Otherwise, we tentatively conclude that our guess at T(0) was
correct, and we can usually identify several other known T-box
input/output pairs;
with this information in hand, we proceed to the second phase.
Typically the first phase will identify T(0) uniquely when sufficiently
many known plaintexts (about 50 or more) are available;
if more possibilities for T(0) are found,
the second phase will be invoked for such possibility.
First, we describe how to prune key trials during the key recovery search. Note that a T-box output is of the form
for some unknown CaveTable output O.
We can calculate 
for all CaveTable
outputs and check whether each such j is listed as possible in ;
if every such j is listed as impossible,
then we can recognize our guess at as incorrect.
Because there are only 164 possible CaveTable outputs,
incorrect guesses at will usually be ruled out
by some i as long as there is enough information in the array.
These incorrect guesses at can thus be
pruned from the search tree without any further work.
Next, we give some more details on the meet-in-the-middle approach.
This approach is only applicable when we have enough known plaintexts
to identify 4 known T-box input/output values
(a,T(a)),(b,T(b)),(c,T(c)),(d,T(d))
from the array.
For each 
, we compute the intermediate values a',b',c',d'
formed after computing T through the known key bytes;
for example, 
.
Next we form the 24-bit index n = (a'-d',b'-d',c'-d'),
and insert the pair 
into a large hash
table keyed on n.
After repeating for all 
possible 
values,
we have built a precomputed lookup table suitable for use in the
meet-in-the-middle optimization.
To check a trial value, we work backwards from
T(a),T(b),T(c),T(d) as far possible given only
and identify the intermediate values a'',b'',c'',d''.
The intermediate values
reflect the values of the T-box computations just after addition
of 
: for example,
We see that a'' can be identified from a,T(a) by working
backwards through the T-box computation and inverting the CaveTable
where necessary,
and b'',c'',d'' can be found similarly.
Then we form the 24-bit index m = (a''-d'',b''-d'',c''-d''),
search in the precomputed hash table for a matching entry
with n=m, and use trial encryption to check
the resulting value.
Note that if our guess at was correct, we have
etc., so that the correct value of
will show up in our search of the precomputed hash table and the
correct value of can be derived as a''-a';
this ensures that we will identify correctly.
Pruned search lets us dramatically reduce the number of key candidates
tried, if there is enough information in the 
array.
The meet-in-the-middle optimization is a time-space tradeoff that
further reduces the computational workload when 4 known T-box
input/output values are available.
Combining the two approaches yields a key recovery algorithm for
the second phase that is very efficient on a standard 100 MHz Pentium
with 40 Mb of memory.
Furthermore, the search algorithm can easily be parallelized for
even greater performance if necessary.
Note that we make heavy use of the non-uniform output distribution
of the CaveTable, and these analysis techniques would not work
if the CaveTable were unbiased.
This known plaintext attack is much more devastating than the chosen plaintext attack described in Section 3.1. Chosen plaintext may be difficult to obtain in practice, but known plaintext is likely to be much easier to acquire.
There are a number of realistic ways that the required known plaintext can be collected in practice. Dialed digits are typically CMEA-encrypted with 3-byte blocks; typically each block will contain only one digit, and often the telephone number dialed will be known. DTMF tones sent on the line will usually be CMEA-encrypted. If the user can be persuaded to dial a number under adversarial control, using their calling card, then the DTMF tones and user-dialed digits will be known to the attacker, providing a ready source of known plaintext; after recovering the CMEA key in a known-plaintext attack, the attacker could decrypt the calling card number and make false calls billed to the victim's name. Furthermore, alphanumeric pages sent to cellular phones are becoming increasingly common, and alphanumeric pages are sent over the control channel. These pages may have a large known component, which will provide some known plaintext. It should be clear that known plaintext may be available from a number of potential sources.
In this section, we have discussed cryptanalysis of CMEA with 3-byte
block widths.
A block width of 3 bytes is a natural choice to examine.
Known plaintext with 3-byte block widths
is often readily available in practice;
for instance, dialed digits are typically
encrypted and transmitted using 3-byte block widths in nearly all digital
cellular architectures.
Moreover, CMEA appears to be easiest to analyze for short block widths,
and most cellular standards avoid block widths shorter
than 3 bytes.
Therefore, 3-byte blocks are a good indicator of the strength of CMEA
as used in phone systems; by giving a known-plaintext
attack on CMEA with 3-byte blocks,
we show that the control channel is not protected adequately in nearly
all of the North American digital cellular phone systems.
We saw above that CMEA is insecure when used with a 3-byte block width; now we show that the situation is even worse for 2-byte blocks. In this section, we present an attack on CMEA needing just 4 known plaintexts when 2-byte blocks are in use. Most cellular standards avoid using CMEA with 2-byte blocks. However, this is not just a theoretical attack: a few cellular systems, such as IS-95 (CDMA), do apply CMEA with a 2-byte block width to protect dialed digits, and they will be vulnerable to the improved attack.
The known-plaintext attack on 2-byte blocks
follows immediately from our earlier discussion.
First, we guess T(0);
that lets us recover 4 more T-box values from the first two known texts.
(There is no need for a stage corresponding to the first phase of
the attack on 3-byte blocks, as we can trivially derive 4 known input/output
pairs for the T-box from the known texts.)
With those known T-box input/output pairs,
we perform a pruned meet-in-the-middle search
to derive a number of possibilities for the full CMEA key,
as described in Section 4.2.
The correct CMEA key can be quickly recognized by trial decryption.
The pruned meet-in-the-middle search has work factor
- , and we will need to do about 30 iterations
of the search to handle each of the possibilities for T(0).
In sum, this attack requires just 4 known 2-byte plaintexts
and has time complexity about 
- 
.
In fact, the plaintext requirements can be reduced even further, to just two known 2-byte plaintexts and some extra ciphertexts. We don't need to know the decryption of the extra ciphertexts: the extra ciphertexts must merely be enough to information-theoretically determine the CMEA key, so that all incorrect key trials can be recognized and discarded. Note the plaintext often contains redundancy--for instance, when it contains dialed digits, there are only 10 possible values for each nibble, and often much of the input is a public fixed value--so in practice obtaining the necessary extra ciphertexts should be very easy.
We have presented several attacks on CMEA, and some of them may be realistically exploitable in practice. We described several possible ways to obtain known plaintext information. One attack that applies to nearly all North American digital cellular standards needs about 40-80 known plaintexts; that many known texts may be available in some situations, although availability is likely to depend on subtleties of the cellular phone system implementation. Though it does not apply to most digital cellphone standards, another attack needs just 4 known plaintexts, which is a much more realistic assumption. At a minimum, these attacks illuminate fundamental certificational weaknesses in CMEA. At worst, widespread attacks on CMEA might be possible in practice.
Our cryptanalysis of CMEA underscores the need for an open cryptographic review process. Betting on new algorithms is always dangerous, and closed-door design and proprietary standards are not conducive to the best odds.
Since being exposed to public scrutiny, three of the four proprietary TIA cryptographic algorithms have been broken: the voice privacy protection was shown to be insecure as early as 1992 [Bar92, CFP93], this paper cryptanalyzes CMEA, and ORYX was recently broken by the authors [WSK97]. This poor success rate provides a strong argument against closed-door design.
In addition, our analysis also shows the importance of explicitly stating security assumptions during every step of the design and development process, and of not reusing security components without throroughly examining the implications of reuse. The CaveTable was designed to have the security properties CAVE needed. Designers reused it for CMEA because they were low on space; this turned out to be a bad idea. CMEA requires different properties from the CaveTable than CAVE does.
In short, CMEA is deeply flawed, and should be carefully reconsidered.
Greg Rose first pointed out the insecurity of CMEA, and he deserves the credit for that discovery. We were not aware of serious flaws in CMEA until we heard over the grapevine that he had found an effective known-plaintext attack on CMEA; this tip provided the motivation to look more closely at CMEA until we managed to independently re-derive the attack described in this paper. Unfortunately he is not free to publish his analysis, so we offer ours instead. We are extremely grateful to Greg Rose for his immeasurable help.
Also, we thank an anonymous party (for scanning the cellphone cryptography standard and posting it to the Internet [TIA92]), John Young (for acting as a clearinghouse for resources on cellphone crypto), Ron Rivest (for many helpful comments on the presentation of our results), Steve Schear (for some assistance navigating the maze of cellular standards), Niels Ferguson (for useful feedback), and all those early readers who independently pointed out that the number of possibilities for T(0) could be reduced from 256 to 164 in the known plaintext attack.
Cryptanalysis of the Cellular Message Encryption Algorithm
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html paper10.tex.
The translation was initiated by David Wagner on Fri May 30 15:57:40 PDT 1997
