GSM Authentication and Encryption

Well, here it is, the final paper. Check it out in the link below.

I will warn you, it’s pretty deep and technical, but it’s pretty easy to read and understand.

Enjoy!
tm

GSM Authentication and Encryption:

Problems and Solutions

by Thomas Mason

1. What is GSM?
The development of cellular technology is based on the desire to provide users with a secure means to transmit voice and data without their conversations or messages being intercepted and by service providers’ desire to prevent phone fraud. The first systems of cellular communication (AMPS and TACS) were both analog systems making conversations easily intercepted by a police scanner. They were also easy to spoof because the Electronic Serial Number (ESN) was transmitted to the base station in the clear making it easy to a cheater to clone a cellular phone. GSM was developed by the Group Special Mobile in an attempt to secure both of these flaws and has evolved into a means to transmit short text messages (SMS) as well as voice. Part of the security in GSM is derived from the use of a speech encoding algorithm called Gaussian Minimum Shift Keying digital modulation (GMSK). The authentication mechanism (discussed below) also ensures that telephone conversations as well as subscriber identification information are kept from the prying eyes of an eavesdropper.

2. How does GSM work?
In a GSM system, a mobile device is identified by an International Mobile Subscriber Identity (IMSI) as well as an individual subscriber authentication key (Ki). These two pieces of information comprise the confidential identification key equivalent to the ESN in the TACS and AMPS systems. These pieces of information are never transmitted in the clear in a GSM system, preventing malicious listeners from spoofing a mobile device’s identifying information and thus cloning a device on the network. Transmissions on a GSM system are encrypted using a ciphering key (Kc), generated by the mobile device and base station independently, as well as a Temporary Mobile Subscriber Identity (TMSI) which is changed periodically for additional security.

There are three elements in a GSM system, the Subscriber Identity Module (SIM), the GSM Mobile Device and the GSM network. The IMSI and the Ki values are stored on the SIM card. This SIM card also contains the ciphering algorithms A8 and A3. The SIM card can be secured by a Personal Identification Number that must be entered on power up of the mobile device. The mobile device contains another algorithm, the A5 encryption algorithm. These algorithms (A8, A5 and A3) are all present in the GSM network as well.

The GSM network has many complex components. The part of the system that takes care of the authentication and ciphering is called the Operation and Maintenance Subsystem (OMS). The OMS consists of three basic parts, the Authentication Center (AUC), the Home Location Register (HLR) and the Visitor Location Register (VLR). The AUC contains a database of individual subscriber information, IMSI, TMSI, Ki and the Local Area Identity (LAI) and is also responsible for generating the components needed for authentication of a mobile device. The two location registers, HLR and VLR, are responsible for storing these values to expedite the authentication and change of location processes.

3. Authentication on a GSM System
To make a call using a mobile device on a GSM system, the device must authenticate itself to the network. To do this, the GSM tower sends a 128-bit random number (RAND), generated by the AUC, to the mobile device identified by a particular TMSI. The mobile device then computes a 32-bit signed response (SRES) by passing RAND and Ki through the authentication algorithm A3 and sends it (SRES) back to the AUC. The AUC has already performed this operation and stored its values in the HLR and VLR. When the AUC receives these values from the mobile device, it checks them in the HLR and VLR databases. If the SRES values match, the mobile device has successfully authenticated to the network, otherwise the connection is ended and an authentication failure message is sent to the device. The calculations made using the A3 algorithm are all performed on the SIM card making it possible to authenticate a device without transmitting the device’s IMSI and Ki to the mobile device or in the clear to the OMS.

4. Encryption on a GSM System
To generate the ciphering key, the SIM card uses the same random number (RAND) and the authentication key (Ki). These values are passed through the ciphering key algorithm, A8, and produce the ciphering key, Kc. Kc is a 64-bit key used to encrypt all information that is transmitted in the clear to the base station (OMS). The base station, since it has the same RAND and Ki stored, computes the same Kc, which allows it to decrypt the data sent from the mobile device.

To encrypt messages to be sent in the clear, the mobile device uses an encryption algorithm, A5. To begin the encryption, the base station sends a ciphering mode request to the mobile device. When the device receives this command, it starts encrypting the data using the ciphering key (Kc) and the encryption algorithm (A5). When the base station receives this data, it decrypts it using the same ciphering key and encryption algorithm. Since both the base station and the mobile device computed Kc independently, this public key is never transmitted in the clear.

The A5 encryption algorithm fits into a class of ciphers called “stream ciphers”. This means that the algorithm encrypts the data fed through it bit by bit, not as one whole chunk; this allows users on the system to be able to communicate in real time.

5. Subscriber Identity Module and Security in the Mobile Device
Most of the security in the GSM system is based on the Subscriber Identity Module (SIM) card. This is a small card, comparable to a smart card, that is assumed to be secure enough to not be spoofed. All of the confidential identification credentials are stored on this card. The IMSI and Ki are never transmitted to the mobile device; Kc, RAND, SRES and the TMSI are the only values known to the device. Since the mobile device does not have the algorithms A3 and A8, it cannot generate it’s own Kc or SRES therefore will not function without the SIM card. This separation of responsibilities is where the GSM system derives most of its security.

A device user can choose to secure his/her SIM card by using a Personal Identification Number (PIN). This PIN functions much like that on an ATM card. When the unit is powered up, the user must enter the PIN. The SIM card will not authenticate to the GSM network until the PIN is entered correctly. If the PIN is entered incorrectly a number of times (typically 3), the SIM card becomes locked. To unlock the SIM card, the user must obtain a PIN Unlock key (PUK) from their service provider. The SIM will allow a user to enter this number multiple times (typically 10) before the card becomes permanently locked, rendering the SIM useless and requiring the customer to get a new SIM card if they wish to continue using the GSM network.

6. How the Temporary Mobile Subscriber Identity Works
The GSM network is divided into areas. Each area is responsible for keeping track of what mobile devices are contained within its boundaries. This is done with the Temporary Mobile Subscriber Identity (TMSI). This is sufficient for keeping track of who is who as long as mobile devices are not passing from area to area. When a device leaves it’s home area, an additional piece of information is needed to identify it to the OMS. This additional piece of information is the Local Area Identifier (LAI). The mobile device transmits both the TMSI and the LAI to the base station. The base station then asks the Visitor Location Register (VLR) identified by the LAI for the specific mobile device’s authentication information, the RAND, SRES and Kc needed to conduct communications with the specific device.

7. Changing the Temporary Mobile Subscriber Identity
This is a relatively simple task since the mobile device is transmitting to the base station using an encrypted channel. The TMSI change request is sent from the OMS to the mobile device using the device’s Kc and encryption algorithm A5. The device receives this request, decrypts it, and sends an acknowledgement back to the base station using the Kc value and the encryption algorithm A5. Now the mobile device has changed it’s TMSI without broadcasting its IMSI, Ki or current/old TMSI in the clear. This prevents an attacker from associating the old TMSI with the new TMSI making it impossible for the user to be tracked through the system.

Those are the basics of how the GSM system works. The remainder of the paper will explore security issues with specific components of the system. For the rest of the paper, it is important to keep in mind the values listed in the following table.

Table 1 – Brute-force key seach times for various key sizes
Key length in bits 32 40 56 64 128
Time required to test
all possible keys
1.19 hours 12.7 days 2,291 years 584,542 years 10.8*1024 years
(source: GSM Security and Encryption, David Musgrave)

8. No Network Authentication
After reading the above discussion, you may be asking yourself “But why does the network not have to prove to the device that it is a legitimate network?” This question has much merit. Since the network does not have to authenticate itself to the mobile device, it can easily be compromised by a man-in-the-middle attack. In this type of attack, the attacker sets up a base station with the same Mobile Network Code as the subscriber’s network. This false network does not need to authenticate the user nor does it need to initiate ciphering, it simply must send to the mobile user the RAND value. Once a device receives a RAND value, it can begin to transmit information in the clear. Since the device does not receive the ciphering mode request from the base station, it never starts ciphering messages. To make sure the calls and messages that are sent are delivered, the spoofed network simply routes the calls and messages back to the regular phone network.

9. Security in the A8 and A3 Algorithms
One of the features of a GSM system is that it allows users to choose from up to seven different algorithms available for A8 and A3. All seven of the algorithms are stored on the base station. The SIM card tells the base station which version of these algorithms it possesses at the beginning of each authentication. Most SIM cards in the United States, United Kingdom and Australia use the combined A3/A8 algorithm developed by the GSM association called COMP128. This algorithm takes as input RAND and Ki to return SRES and Kc, combining the tasks of A3 and A8 into one algorithm.

COMP128 was developed in secret by the GSM association and was closely guarded for many years until attempts at reverse engineering and leaked documents exposed the algorithm to the public. This allowed researchers and attackers alike to uncover that the COMP128 algorithm had a narrow pipe at certain points in the computation. It takes input from a 128-bit RAND and a 128-bit Ki but produces only a 32-bit SRES and a 64-bit Kc. Researchers used this knowledge to choose values of RAND and Ki that would produce the same output as other pairs. This makes the cracking time of a SIM card much lower requiring between 2^13 and 2^15 RANDs.

Another major flaw with these algorithms is that the A8 algorithm sets the ten leftmost digits of the ciphering key (Kc) to zeros. This deliberately reduces the strength of the key from 64-bits (584,542 years at most) to 54-bits (2,291 years at most). It is also rumored that Kc is only effective to 40-bits (12.7 days at most). The GSM association accepts these weaknesses because of the belief that the information transmitted on these network has a confidential lifespan of about a week. This means that the information in an SMS or in a conversation is no longer relevant after seven days’ time.

10. Flaws in Device Identity Confidentiality
When a device comes online for the very first time, the network does not know its identity, so it makes an identity request. This request causes the phone to transmit its IMSI in the clear to the base station. This same procedure takes place if a VLR cannot determine the identity of a certain device by querying previous VLRs. This request and response cannot be encrypted since the base station does not know who the device is, and thus does not know which Kc and RAND to use to encrypt the message.

11. Cracking the SIM Card’s Information Over the Air
The three flaws discussed above, when exploited together, can lead to a complete compromising of a mobile device’s SIM card without physical access to the card. This process begins with an attacker imitating a legitimate GSM network. After listening to the in the clear traffic for a while, the attacker can pick out a TMSI to attack since the TMSIs are transmitted in the clear. Once the attacker has chosen a victim, he then pages that particular TMSI to establish a radio link with the user.

Once the connection is established, the attacker sends an identity request to the mobile device. This request requires the device to return its IMSI in the clear to the attacker. After compromising the IMSI, the attacker sends multiple RAND values accompanied by authentication requests to the phone in order to exploit the COMP128 flaws. The mobile device simply returns the SRES, as it is required to do. The attacker then uses all of the RAND and SRES values to determine Ki. This can all be done with no more than 2^17 RAND values.

Once the Ki and IMSI values have been discovered, an attacker can then impersonate the mobile device and send calls and messages in the user’s name. They can also eavesdrop on conversations. This is possible because the paging done with the TMSI as well as transmission of the RAND value are done in the clear, without encryption.

12. Conclusions
A few simple implementations can solve the above problems, or at least make them less severe.

  1. Network Authentication: To remedy the first problem, a simple network authentication scheme could be devised. After the mobile device has authenticated itself to the network, the network should be required to authenticate itself to the device. This can be done in a similar fashion as the mobile device authentication. Each GSM network should have a Network Identification Key (Kn). This way, the mobile phone can send a randomly generated number (RN) to the network. The network would then use a Network Identification Algorithm that takes the RN value and the Kn value as input and produces a signed response similar to the one the phone produces and sends it back to the phone. The phone would need to have the same algorithm so it can perform the same computation and verify that the network is a valid network. This way the Kn is never transmitted in the clear from network to device or device to network. The ciphering algorithm then needs to be modified so that the Kn and RN are required in conjunction with RAND and Kc to encrypt a message.
  2. Securing the A3 and A8 Algorithms: These algorithms need to pass the full 128-bits of RAND and Ki from stage to stage in the computing process. Currently, the values are truncated to smaller (2-bits at some places) values while generating SRES and Kc. If these full 128-bits are used, the generated values for SRES and Kc would be much more difficult to crack as well as not producing any anomalies such as the ones that can be exploited to discover the Ki value.
  3. Not transmitting the IMSI in the clear, ever: This is a more difficult problem to solve. The obvious answer is to have the OMS (base station) and the mobile device perform some sort of Diffie-Hellman Key Exchange to encrypt this information. This is not possible because it is a very computationally intensive algorithm and the mobile device does not have the processing power to perform this operation in a reasonable amount of time. Since the network would be required to have a network key (Kn), it should also be required to have a default encryption algorithm (DEA) that can be used by the handset to encrypt it’s IMSI for initial transmission and for transmission when it receives an identity request challenge. This would allow the IMSI to be transmitted to the network without being transmitted in the plaintext. This would also allow the base station to transmit to the mobile device the initial TMSI without it being able to be intercepted.

The current GSM network is much more secure than the old analog networks (AMPS and TACS) but it is still not as secure as users and service providers would like. Newer networks are being developed using different algorithms to encrypt information; however, most American, British and Australian customers still are using the GSM system described above. With a few modifications to algorithms and protocols, the current system could be more secure for both customers and service providers.

References

  1. Hudson, R.L. The GSM Radio Interface. British Telecom Technology Journal, Vol. 8, No. 1, January 1990, pp. 31-43.
  2. Goldberg & Briceno. GSM Cloning. http://www.isaac.cs.berkeley.edu/isaac/gsm-faq.html.
  3. Musgrave, David. GSM Security and Encryption. George Mason University. 1999.
  4. Quirke, Jeremy. Security in the GSM System. Ausmobile. 5/2004.
  5. www.gsmworld.com.