Cryptography – Cellular telephone cryptographic authentication
Reexamination Certificate
2003-05-09
2004-07-27
Morse, Gregory (Department: 2137)
Cryptography
Cellular telephone cryptographic authentication
C380S028000, C380S044000, C380S250000, C380S270000, C713S152000, C455S410000, C455S411000
Reexamination Certificate
active
06768797
ABSTRACT:
BACKGROUND OF THE INVENTION
I. Field of the Invention
The present invention relates to communications systems. More particularly, the present invention relates to a novel and improved method for encrypting data for security in wireless communication systems.
II. Description of the Related Art
In a wireless communication system, it is desirable for the service provider to be able to verify that a request for service from a remote station is from a valid user. In some current cellular telephone systems, such as those deploying the AMPS analog technology, no provision is made to deter unauthorized access to the system. Consequently, fraud is rampant in these systems. One fraudulent means for obtaining service is known as cloning, in which an unauthorized user intercepts the information necessary to initiate a call. Subsequently, the unauthorized user can program a mobile telephone using the intercepted information and use that telephone to fraudulently receive telephone service.
To overcome these and other difficulties, many cellular telephone systems have implemented authentication schemes such as that standardized by the Telecommunications Industry Association (TIA) in EIA/TIA/IS-54-B. One facet of this authentication scheme is encryption of information, transmitted over the air, that is required to receive service. This information is encrypted using the Cellular Message Encryption Algorithm (CMEA). The CMEA algorithm is disclosed in U.S. Pat. No. 5,159,634, entitled “CRYPTOSYSTEM FOR CELLULAR TELEPHONY”, incorporated by reference herein.
Several major weaknesses have been discovered in CMEA which allow encrypted information to be deciphered using current standard computational equipment in a relatively short period of time. These weaknesses will be thoroughly outlined hereinafter followed by a description of the present invention which overcomes these weaknesses. CMEA has been published on the Internet, hence these weaknesses are open for discovery by anyone with an interest in doing so. Thus, a new algorithm for encryption is desirable to replace CMEA to avoid the interception and fraudulent use of authentication information necessary to initiate cellular service.
SUMMARY OF THE INVENTION
The present invention is a novel and improved method for data encryption. The present invention is referred to herein as Block Encryption Variable Length (BEVL) encoding, which overcomes the identified weaknesses of the CMEA algorithm. The preferred embodiment of the present invention has the following properties:
Encrypts variable length blocks, preferably at least two bytes in length;
Self-inverting;
Uses very little dynamic memory, and only 512 bytes of static tables;
Efficient to evaluate on 8-bit microprocessors; and
Uses a 64 bit key, which can be simply modified to use a longer or shorter key.
The first weakness identified in CMEA is that the CAVE (Cellular Authentication Voice Privacy and Encryption) table used for table lookups is incomplete. It yields only 164 distinct values instead of 256. The existence of a large number of impossible values makes it possible to guess return values of tbox( ) or key bytes, and verify the guesses. This first weakness is mitigated in the present invention by replacing the CAVE table with two different tables chosen to eliminate the exploitable statistical characteristics of the CAVE table. These tables, called t1box and t2box, are strict permutations of the 256 8-bit integers, where no entry appears at its own index position. In addition, t1box[i] does not equal t2box[i], for all values of i. These two tables were randomly generated with candidates being discarded which did not meet the above criteria.
The second weakness of CMEA is the repeated use of the value of a function called tbox( ), evaluated at zero. The value tbox(0) is used twice in the encryption of the first byte. This makes it possible to guess tbox(0) and use the guess in determining other information about the ciphering process, notably the result of the first step of CMEA for the last byte, and the arguments of the two values of tbox( ) used in encrypting the second byte. It also makes it possible, through a chosen-plaintext attack, to determine tbox( ) by trying various plaintext values until a recognized pattern appears in the ciphertext. This second weakness is mitigated by changing the self-inverting procedures used in CMEA to a preferred set of procedures providing better mixing. This is done by introducing a second pass using a different table (t2box). In this situation there are two values of tbox( ) derived from different tables with equal significance which serve to mask each other.
A related weakness in CMEA is that information gathered from analyzing texts of different lengths can generally be combined. The use of the second critical tbox( ) entry in BEVL depends on the length of the message and makes combining the analysis of different length texts less feasible.
A third weakness discovered in CMEA is incomplete mixing of upper buffer entries. The last n/2 bytes of the plaintext are encrypted by simply adding one tbox( ) value and then subtracting another value, the intermediate step affecting only the first half of the bytes. The difference between ciphertext and plaintext is the difference between the two values of tbox( ). BEVL addresses this third weakness by performing five passes over the data instead of three. The mixing, performed by CMEA only in the middle pass, is done in the second and fourth passes which mix data from the end of the buffer back toward the front. The middle pass of CMEA also guarantees alteration of at least some of the bytes to ensure that the third pass does not decrypt. In an improved manner, BEVL achieves this goal in the middle pass by making a key dependent transformation of the buffer in such a way that at most a single byte remains unchanged.
CMEA's fourth weakness is a lack of encryption of the least significant bit (LSB) of the first byte. The repeated use of tbox(0) and the fixed inversion of the LSB in the second step of CMEA results in the LSB of the first byte of ciphertext being simply the inverse of the LSB of the first byte of plaintext. BEVL avoids this fourth weakness through a key dependent alteration of the buffer during the middle pass which makes the LSB of the first byte unpredictable on buffers of two bytes or more in length.
A fifth weakness of CMEA is that the effective key size is 60 rather than 64 bits. As such, each key is equivalent to 15 others. BEVL increases the number of table lookups while decreasing the number of arithmetic operations, ensuring that all 64 bits of the key are significant.
Finally, CMEA's tbox( ) function can be efficiently compromised by a meet-in-the-middle attack. Once four tbox( ) values are derived, the meet-in-the-middle attack can be accomplished with space and time requirements on the order of 2{circumflex over ( )}30, independent of the composition of the CAVE table. BEVL addresses this in a number of ways. The construction of the tbox( ) function recovers two unused bits of the key. The repetition of the combination with the least 8 bits of the encryption key at both the beginning and end of tbox( ) means that the minimum computation and space should be increased by eight bits. Since there are two sides of each table, and two different tables, the minimum complexity should be increased by another two bits, leading to a minimum space and time requirement on the order of 2{circumflex over ( )}42. Further, the meet-in-the-middle attack on CMEA requires the recovery of at least some of the tbox( ) entries. This is made more difficult using BEVL, which requires simultaneous attacks on two separate sets of tbox( ) values, which tend to disguise each other.
REFERENCES:
patent: 4275265 (1981-06-01), Davida et al.
patent: 5159634 (1992-10-01), Reeds, III
patent: 5214703 (1993-05-01), Massey et al.
patent: 5687238 (1997-11-01), Shimada
patent: 5794139 (1998-08-01), Mizikovsky et al.
patent: 5991407 (1999-11-01), Murto
patent: 6075859 (2000-06-01), Rose
pat
Callahan Paul E.
Morse Gregory
Qualcomm Inc.
Wadsworth, Philip Minhas, Sandip S. Choi, Jae-Hee
LandOfFree
Method and apparatus for encrypting data in a wireless... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for encrypting data in a wireless..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for encrypting data in a wireless... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3235298