Cryptography – Communication system using cryptography – Wireless communication
Reexamination Certificate
1999-11-11
2004-08-03
Darrow, Justin T. (Department: 2132)
Cryptography
Communication system using cryptography
Wireless communication
C380S262000, C380S270000, C380S273000, C455S411000, C455S436000, C455S437000, C455S438000
Reexamination Certificate
active
06771776
ABSTRACT:
BACKGROUND OF THE INVENTION
I. Field of the Invention
The present invention relates to encryption. More particularly, the present invention relates to a method and apparatus for re-synchronizing encryption stream ciphers.
II. Background
Encryption is a process whereby a random process manipulates data such that the data is made unintelligible by all but the intended recipient. One method of encryption for digitized data is through the use of stream ciphers, which are generated by secret keys. A widely used secret key system is the Data Encryption Standard (DES) which employs a 56 bit key and 8 non-key parity bits. DES was published as a U.S. Federal Information Processing Standard in 1977. In an encryption scheme using a stream cipher, data and a stream of pseudo-random bits (or encryption bit stream) are combined, usually with the exclusive-or (XOR) operation. Many of the techniques used for generating the stream of pseudo-random numbers are based on linear feedback shift registers over a Galois finite field. The register is updated by shifting a new bit into the register, shifting the other bits over by one bit position, and calculating a new output bit. Decryption is simply the process of generating the same encryption bit stream and removing the encryption bit stream with the corresponding operation from the encrypted data. If the XOR operation was performed at the encryption side, the same XOR operation is also performed at the decryption side. For a secured encryption, the encryption bit stream must be computationally difficult to predict.
An exemplary application that utilizes stream ciphers is wireless telephony. An exemplary wireless telephony communication system is a code division multiple access (CDMA) system. The operation of a CDMA system is disclosed in U.S. Pat. No. 4,901,307, entitled “SPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS,” assigned to the assignee of the present invention, and incorporated by reference herein. The CDMA system is further disclosed in U.S. Pat. No. 5,103,459, entitled SYSTEM AND METHOD FOR GENERATING SIGNAL WAVEFORMS IN A CDMA CELLULAR TELEPHONE SYSTEM, assigned to the assignee of the present invention, and incorporated by reference herein. Another CDMA system includes the GLOBALSTAR communication system for worldwide communication utilizing low earth orbiting satellites. Other wireless telephony systems include time division multiple access (TDMA) systems and frequency division multiple access (FDMA) systems. The CDMA systems can be designed to conform to the “TIA/EIA/IS-95 Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System,” hereinafter referred to as the IS-95 standard. Similarly, the TDMA systems can be designed to conform to the TIA/EIA/IS-54 (TDMA) standard or to the European Global System for Mobile Communication (GSM) standard.
Encryption of digitized voice data in wireless telephony has been hampered by the lack of computational power in the remote station. This has led to weak encryption processes such as the Voice Privacy Mask used in the TDMA standard or to hardware generated stream ciphers such as the A5 cipher used in the GSM standard. The disadvantages of hardware-based stream ciphers are the additional manufacturing cost of the hardware and the longer time and larger cost involved in the event the encryption process needs to be changed. Since many mobile stations in wireless telephony systems and digital telephones comprise a microprocessor and memory, a stream cipher that is fast and uses little memory is well suited for these applications.
However, a problem arises in the use of stream ciphers in a wireless telephone system. A mobile station can travel from the range of a first base station to a second base station throughout the wireless telephone system. While the mobile station is travelling within the range of the system, the mobile station communicates with the base station from which the mobile station receives the strongest signal. It should be noted that a mobile station can detect the broadcasts of multiple base stations, not just the two base stations that are used herein for illustrative purposes. In most instances, the strength of a transmission signal is directly proportional to the distance between the mobile station and the base station. As the mobile station enters the range of a second base station, the mobile station begins communications with the second base station while concurrently maintaining communications with the first base station. The process in which the mobile station establishes communications with the second base station while ending communications with the first base station is called a “soft handoff,” and is described in U.S. Pat. No. 5,267,261, entitled “MOBILE STATION ASSISTED SOFT HANDOFF IN A CDMA CELLULAR COMMUNICATIONS SYTEM,” which is assigned to the assignee of the present invention, and incorporated by reference herein. If the mobile station is in the midst of a secure, encrypted data exchange with the first base station during handoff, it is necessary to re-synchronize the stream cipher so that the second base station and the mobile station can communicate securely without an interruption in the handoff process.
In order to achieve this goal, the second base station must be able to encrypt and decrypt in the same manner as the first base station. Hence, the second base station must have the state information or the synchronization parameters of the first base station. One simple method of re-synchronizing the stream cipher at the second base station is to pass information about the state of the encryption process from the first base station to the second base station through the wireless telephone system. However, the process of passing state information from one base station to another is problematic. If there is no mechanism for passing state information in a secure manner, the state information can be intercepted by unintended recipients and can then be used to compromise the security of the encrypted transmissions between the mobile station and the second base station.
Another simple method of re-synchronizing the stream cipher is to have both the mobile station and the second base station restart the entire encryption process from the same initial state as used by the mobile station and the first base station. However, this method results in a reused stream cipher, which is insecure. Thus, there is a need for a method that will provide secure resynchronization of a stream cipher while a mobile station is travelling within the range of a first base station to a second base station.
SUMMARY
The present invention is directed to a method and apparatus for securely re-synchronizing a stream cipher while a mobile station is travelling from the range of a first base station to a second base station. In one aspect of the invention, a secret key and a unique non-secret key are used to reinitialize the stream cipher used by the mobile station. (The unique non-secret key can also be referred to as a quasi-secret key.) A quasi-secret key is transmitted from a first base station to a second base station, and the second base station uses the quasi-secret key and a secret key to initialize a stream cipher generator. Hence, both the mobile station and the second base station will start generating the stream cipher from the same initial state.
In another aspect of the invention, a secret key and a quasi-secret key are used to create a new key. During a soft handoff process, a quasi-secret key is transmitted from a first base station to a second base station. The second base station uses the quasi-secret key and a secret key to generate a new key. The mobile station and the second base station use the new key to generate a new stream cipher for encrypting the data stream flowing between the mobile station and the second base station.
REFERENCES:
patent: 5060266 (1991-10-01), Dent
patent: 5267261 (1993-11-01), Blakeney, II et al.
patent: 5778075 (1998-07-01), Haartsen
patent: 5805992
Choi Jae-Hee
Darrow Justin T.
Minhas Sandip (Micky) S.
Qualcomm Incorporated
Wadsworth Philip R.
LandOfFree
Method and apparatus for re-synchronization of a stream... 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 re-synchronization of a stream..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for re-synchronization of a stream... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3350923