Yin Wang, Jonathan Kleiner

12/13/04

GSM SIM Card Cloning

Introduction:

GSM stands for Global System for Mobile Communication. It is the most widely used mobile phone system in the world. GSM was the first digital design to follow the analog era. It was supposed to make mobile communication more secure than analog counterparts. However, at the start of GSM, there were big security flaws. Many have been fixed, while others may still exist. This report will discuss one such security flaw that allows an adversary to retrieve the secret key. This has been fixed. The GSM Consortium designed the GSM specification in secrecy. They thought that “security through obscurity” would give their network an edge over malicious users. This allowed for the algorithms to be weak. Despite strict distribution only to manufacturers who needed this information, the GSM algorithms were leaked to the public. Most, if not all the vulnerabilities found since GSM was deployed could have been prevented had the Consortium allowed the public to scrutinize the specification.

Definitions:

A3The authentication algorithm used in the GSM system. Currently the COMP128 algorithm is used as the A3/A8 implementation in most GSM networks.

A5The encryption algorithm used in the GSM system. There are various implementations named A5/1, A5/2, ... The A5/1 is known as the strong over-the-air voice-privacy algorithm. A5/x (A5/2 ...) are weaker implementations targeted at foreign markets out side of Europe. There is also an A5/0 algorithm, which encloses no encryption at all.

A8The key generation algorithm used in the GSM system. Currently COMP128 algorithm is used as the A3/A8 implementation in most GSM networks.

AuCAuthenticationCenter. The AuC register is used for security purposes. It provides the parameters needed for authentication and encryption functions (RAND, SRES and Kc). The RAND is a random challenge generated randomly. The other two parameters are generated from the RAND and the subscriber's Ki using the A3 and A8 algorithms. These parameters help to verify the user's identity (SRES) and provide the session key (Kc).

BSCBase Station Controller. The BSC acts as a common node between multiple BTSs that together form one BSS and the backbone network.

BTSBase Transceiver Station, a base station the MS communicates with.

COMP128A one-way function that is currently used in most GSM networks for A3 and A8. Unfortunately the COMP128 algorithm is broken so that it gives away information about its arguments when queried appropriately. This is an undesired and unacceptable side effect in a one-way function.

GSMGlobal System for Mobile communications, a mobile phone system based on multiple radio cells (cellular mobile phone network).

HLRHome Location Register. The HLR is part of the AuC. The HLR provides the MSC with triples specifying a random challenge and a SRES and a Kc based on the Ki of a specific subscriber and the random challenge. The HLR is also responsible for knowing the location of the MS at all times.

KcThe secret session key used to encrypt over-the-air traffic between the BTS and the MS. The Kc is generated after every authentication initialized by the MSC. The Kc is calculated from the Ki and from the random challenge sent by the MSC with the A8 algorithm. The MS and the HLR both calculate the Kc independently of each other. The Kc is never transmitted over-the-air.

KiKi is the secret key shared between the SIM and the HLR of the subscriber's home network.

MSMobile Station, the mobile phone.

MSCMobile services SwitchingCenter, the central component of the NSS. The MSC performs the switching functions of the network. It also provides a connection to other networks.

NSSNetwork and Switching Subsystem, its main role is to manage the communications between the mobile users and other users, such as mobile users, ISDN users, fixed telephony users, etc. It also includes data bases needed in order to store information about the subscribers and to manage their mobility.

SIMSubscriber Identity Module. The SIM identifies a subscriber. The subscriber can use multiple GSM phones with one SIM. All calls are charged on the same account and the subscriber's phone number stays the same. The SIM card contains IMSI, Ki and the A3 and A8 algorithms. The SIM is supposed to be tamper-proof, so that the Ki cannot be retrieved from it.

SRESSigned RESponse. This is the response the MS returns to a challenge made by the MSC during the MS authentication thus authenticating itself to the MSC (or SGSN in the case of GPRS).

VLRVisitor Location Register. The VLR stores triples generated by the HLR when the subscriber is not in his home network. The VLR then provides the MSCs with these triples when necessary.

GSM Authentication:

When a user wants to connect to the network she sends her identification (IMSI) to a local base station. This request is relayed to the MSC which contacts the HLR. The HLR creates a triple containing a random number, a signature response, and a session (RAND, XRES, Kc) based on the secret key of the connecting user and sends it back the MSC. RAND is sent to the user. The user calculates SRES and Kc using RAND and her secret key stored on her SIM. She sends SRES to the MSC who then verifies that XRES and SRES are equal. Now the user is connected to the network with Kc as the session key.

SRES is computed using the authentication algorithm A3. Given a 128-bit random number and the 128-bit secret key, A3 outputs a 32-bit value which is called the SRES.

Kc is computed using the Voice-Priovacy Key Generation Algorithm A8. Given a 128-bit random number and a 128-bit secret key, A* outputs a 64-bit session key Kc.

Today, both A3 and A8 are combined into one algorithms COMP128 which given the 128-bit random number and the 128-bit secret key, outputs a 32-bit SRES and a 64-bit session key. Note that the last 10 bits of the session key are set to 0.

GSM system uses the secret key in the SIM card to authenticate subscribers. By checking the implementation of COMP128, we have discovered that the authentication and session key generation of GSM system is not strong enough to resist an attack. Once the key is compromised, it is possible to make fraudulent calls which will be billed to the victim.

The vulnerability can be attributed to the serious failing of the GSM security design process. The GSM committee kept all security specification secret. Experts have learned over the years that the only way to assure security is to follow an open design process, encouraging public review to identify flaws. On the April 13, 1998 Ian Goldberg and Marc Briceno published an article which described a method to recover the secret key by querying SIM card about 150,000 times. On May 2002 a group from IBMWatsonResearchCenter released a partitioning attack on COMP128. It is based on the side channels and could retrieve the key in several minutes.

Ian Goldberg, Marc Briceno’s method:

There's a narrow “pipe” inside COMP128. Bytes i,i+8,i+16,i+24 at the output of the second level depend only on bytes i,i+8,i+16,i+24 of the input to COMP128. Vary bytes i+16,i+24 of the COMP128 input which are the rand challenge and keep the rest of the COMP128 input same. Since the second level has only 7 valid bits per byte the birthday paradox guarantees that collisions will occur pretty rapidly. As long as we find a collision, we just have to exhaust the whole key space in byte i and i+8 to find the right key which can generate the same collision.

Algorithm in the Random Oracle Model

FINDCOLLISION

Choose
For each
do
If for some
then return
else return (failure)

The birthday paradox tells us if let our , we have probability at least 1/2 to get a collision. The expected of the number of queries is. By vary i+16 and i+24 we have different inputs.The total expected queries to recover the entire 128 bit Ki is. If the computational ability of IC is 6.25 queries/s, the totally recovery period will be7.3 hours.

Suggestion on B. and G.

Pre-compute eight tables. Each havingentries each.Every time we find a collision, just look up the corresponding tables to find the key. Space requirements areGB. However the bottle-neck of recovery time is dominated by computational time of IC. This technique could decrease computational requirement of PC, but the total time won’t decrease so much.

Evaluation of B. G.’s Method

•Pros:

- Easily to implement.

- High accuracy.

- Doesn’t have to physical access to the SIM card.

•Cons:

Slow: 7.3 hours

Sources: