Cryptanalysis of TIA's Common Cryptographic Algorithms

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] .

Introduction

There are four cryptographic primitives used in North American digital cellular systems and described in the [TIA95] . They are:

-CMEA (Cellular Message Encryption Algorithm), a block cipher, which is used to encrypt the control messages (and other messages) in cellular phones.

-ORYX, a LSFR (Linear Feedback Shift Register)-based stream cipher, which is intended for wireless data services.

-CAVE (Cellular Authentication and Voice Encryption algorithm), a non-linear mixing function, which is intended for challenge-response authentication protocols and for key generation.

-For voice privacy, TDMA systems use an XOR mask, or CDMA systems use keyed spread spectrum techniques combined with an LFSR mask.

A description of CMEA

CMEA is a variable-width block cipher with a 64 bit key (Block sizes may be any number of bytes).The CMEA cipher consists of three layers:

•1st layer performs one non-linear pass on the block;

•2nd layer is a linear, un-keyed operation, which intended to make changes propagate in the opposite direction. Man can think of that as XORing the left half of the block onto the right half; •3rd layer represents a final non-linear pass on the block from left to right (in fact, it is the inverse of the first layer).

In the first and third layer CMEA gets the non-linearity from a 8-bit keyed lookup table known as the T-box. And the T-box calculates its 8-bit output as:

T(x) = C(((C(((C(((C((x⊕K0) +K1) +x)⊕K2)+K3)+x)⊕K4)+K5)+x)⊕K6)+K7)+x [ [Wagner D, Schneier B, Kelsey J, Cryptanalysis of the Cellular Message Encryption Algorithm] ]

Where "x" is the input byte, K0,...,K7 are 8-byte keys, "⊕" is the XOR function, "+" denotes modulo 256 addition, C( ) is the outcome of a CAVE 8-bit lookup table.

The ORYX Cipher

The cipher ORYX has four components: [ [Wagner D, Schneier B, Kelsey J, Cryptanalysis of ORYX] ] three 32-bit LFSRs which labeled as LFSRA, LFSRB and LFSRK, and an S-box containing a known permutation P of the integer values 0 to 255.

•The feedback function for LFSRK is defined as:

Lt+32= Lt+28⊕Lt+19⊕Lt+18⊕Lt+16⊕Lt+14⊕Lt+11⊕Lt+10⊕Lt+9⊕Lt+6⊕Lt+5⊕Lt+1⊕Lt

•The feedback functions for LFSRA are defined as:

Lt+32=Lt+26⊕Lt+23⊕Lt+22⊕Lt+16⊕Lt+12⊕Lt+11⊕Lt+10⊕Lt+8⊕Lt+7⊕Lt+5⊕Lt+4⊕Lt+2⊕Lt+1⊕Lt

and

Lt+32=Lt+27⊕Lt+26⊕Lt+25⊕Lt+24⊕Lt+23⊕Lt+22⊕Lt+17⊕Lt+13⊕Lt+11⊕Lt+10⊕Lt+9⊕Lt+8⊕Lt+7⊕Lt+2⊕Lt+1⊕Lt

•The feedback function for LFSRB is:

Lt+32=Lt+31⊕Lt+21⊕Lt+20⊕Lt+16⊕Lt+15⊕Lt+6⊕Lt+3⊕Lt+1⊕Lt

For the duration of a call the permutation P is fixed, and is formed from a known algorithm, initialized with a value which is transmitted in the clear during call setup. Every keystream byte is generated as follows:

•LFSRK is stepped once.

•LFSRA is stepped once, with one of two different feedback polynomials depending on the content of a stage of LFSRK.

•LFSRB is stepped once or twice, which depending on the content of another stage in LFSRK.

•The high bytes of the current states of LFSRK, LFSRA, and LFSRB are combined to form a keystream byte. The combining function is defined as:Keystream = {High8K +P [High8A] + P [High8B] } mod 256 [ [Wagner D, Schneier B, Kelsey J, Cryptanalysis of ORYX] ]

CAVE

CAVE is a non-linear mixing hash function primitive which is used in ANSI-41 wireless networks for authentication, data protection, anonymity and key generation.

And it consists of three components: [ [W.Millan and P.Gauravaram, Cryptanalysis of the Cellular Authentication and Voice Encryption Algorithm] ]

•a 32-bit Linear-Feedback Shift Register (LFSR);

•sixteen 8-bit mixing registers (R00,R01,R02,...,R15); •and a 256-entry lookup table with two 8-bit offset_1 and offset_2 as pointer.

The algorithm operation consists of three steps: Step1. An initial loading.

Step2. A repeated randomization which consists of four or eight rounds with each round having 16 register update phases.

Step3. Processing of the output.

Conclusions

The CaveTable was designed to have the security properties CAVE needed. Designers reused it for CMEA because they were low on space. This seems to be a bad idea. CMEA requires different properties from the CaveTable than CAVE does.In short, CMEA is deeply awed, and should be carefully reconsidered.

The decision to replace CAVE with Authenticated Key Agreement (AKA) was made in 1999. The slow standardization process, added to that slower adoption by the operators is delaying its replacement. Considering the threats we strongly recommend that where CAVE is still in use, it should be replaced with AKA as possible.

References