GSM (Group Standard for Mobile communications) is the current standard for digital mobile communications in Europe, Asia and most of the USA.

Upon its introduction, GSM replaced various aging analogue mobile systems in many countries. Analogue telephones were vulnerable to eavesdropping with a simple hand-held scanner, and could be ''cloned'' by anyone with the correct equipment. GSM added SIM cards and basic privacy to telephone conversations.

The sale of scanners that could listen in to analogue mobile phone conversations was made illegal throughout Europe and America some years after many thousands had been sold.

GSM was pushed as a mobile standard on an EU-wide basis. It uses TDMA for communication between handsets and base-stations, and TDMA is getting old. By contrast, most phone networks in the USA use the newer and better CDMA, which will mean less pain when upgrading to 3G, which uses the backwards-compatible CDMA2000.

TDMA is incompatible with CDMA, so european mobile operators are facing a hefty bill for new infrastructure when (or if) they upgrade to 3G.

System Architecture

The GSM system architecture has six basic components.

  1. The SIM card or ''Subscriber Identity Module'' stores personal information such as phone numbers, as well as information such as the network you're subscribed to. It also contains the international mobile subscriber identification (IMSI), a globally unique identifier that can be matched against the telephone number of the mobile.

    It also contains a subscriber authentication key, which never leaves the SIM card, and is known only by the HLR (see below).

  2. The Mobile phone is the hardware - the aerial, the transmitter and the receiver, the sexy plastic - the commodity item. The mobile phone attempts to authenticate itself to the base station with the strongest signal - by implication, the nearest one.

  3. The base station is the 'cell' in 'cell phone'. These are the short range transmitters/receivers that communicate with your phone (via radio) and the rest of the phone network (via cable or microwave links). They communicate with your phone at various frequencies, depending on the kind of phone, and the kind of base station.

    There are two kinds of base station controllers - fixed and mobile. Fixed controllers can be seen on top of tall buildings, water towers, etcetera. These are the bricks and mortar of a mobile phone network.

    Mobile base stations are generally set up at events such as Glastonbury (in the UK), where temporary demand can overwhelm the capacity of the local network.

    There are three main frequency pairs in use by the current GSM system. For each pair of frequencies, the lower is used by mobile base stations, and the higher is used for the fixed base stations.

    The older phones use ''GSM400'', which is two pairs of lower frequencies - 450.4 - 457.6 MHz paired with 460.4 - 467.6 MHz, and 478.8 - 486 MHz paired with 488.8 - 496 MHz

    Newer phones use ''GSM900'' 880 - 915 MHz paired with 925 - 960 MHz, or ''GSM1800'' 1710 - 1785 MHz paired with 1805 - 1880 MHz.

    Mobile base stations are also used by law enforcement to listen in on GSM communications in real time. Compact base station circuitry can fit in the trunk of a police car, whose drivers can then position themselves within a few hundred meters of a target - for example, a flat or a car on a motorway. Any mobile phones in the vicinity latch on to the police base station, as it has the strongest signal. The police base station then relays traffic normally to the nearest fixed base station.

  4. The base station controller (BSC) normally maintains microwave or cable links with large numbers of base stations - up to several hundred. Base stations can be connected to a controller via other stations - in other words, base stations can act as routers.

    Base station controllers are also responsible for hand-over procedures - when an active phone moves from the range of one base station to another, or from the domain of one controller to another.

    Base station controllers report to a visitor location register, or the home location register.

  5. The visitor location register (VLR) is a database run by the owner of the network segment currently being used by the mobile. It serves as an intermediate to the HLR (see below). It is normally the case that one network will have a couple of location registers on it's network, one for each large geographic area. Each VLR is also the HLR for it's local subscribers. This is also for roaming - it allows you to take your GSM phone and use it with a different network - for example, in a different country.

  6. The home location register (HLR). This is a subscriber database that is run by the provider of your mobile service. It is used mainly for billing purposes, and holds the information that allows you to authenticate to a phone network.

Authentication and privacy

A GSM phone connects to a network via the base station with the strongest signal. It carries out some basic steps to authenticate itself. These are explained below in first in plain English, and then in crypto-speak.

The protocol in plain English

Both the SIM card and it's home location registry know a secret A.

When a base station claims to have an incoming connection from the phone and the SIM card, the home location registry sends out a pseudo-random number B, and the same number encrypted using the secret A as a key, C1.

The base station then sends the pseudo-random number B to the mobile.

If the mobile has the SIM card it says it does, then it will be able to compute the pseudo-random number B encrypted using the secret A. So it encrypts the random number B using the secret A as a key, just like the home location registry. It sends part of this number C2 to the base station, to prove that it has the full number, and the secret A.

The base station compares the number C2 it receives from the mobile to the start of the number C1 it received from the home location registry. If they match, then the mobile does have the SIM card that it says it does.

As the identity of the card is now confirmed, the base station will now allow the mobile to communicate, using the other part of the C2 as the session key for further encryption.

The protocol, laid out formally

The actors in the authentication

  • SIM - The SIM card (using the mobile as a transmitter and receiver).
  • BS - The base station that SIM is connecting to.
  • BSC - The base station controller that connects BS to.
  • VLR - The visitor location register, that connects to.
  • HLR - The home location register that holds your information.

The variables

  • IMSI - The international mobile subscriber identification, explained above.
  • RAND - A pseudo-random challenge.
  • SRES - The response.
  • KI - The subscriber authentication key of the SIM, explained above.
  • KC - A ciphering key.

The algorithms

  • Comp128 - A family of hash functions, namely Comp128 and Comp128-2. Comp128 is itself a member of a family officially known as A3/A8.
  • A5 - A family of ciphers, A5/1 and A5/2, and A5/3. Referred to as A5 below.

The protocol

  1. One time setup

    SIM and HLR both share KI

  2. Protocol messages

    (1) SIM --> BS --> BSC --> VLR --> HLR : IMSI
    (2)         BS <-- BSC <-- VLR <-- HLR : RAND, SRES, KC
    (3) SIM <-- BS                         : RAND
    (4) SIM --> BS                         : SRES
    (5) SIM --> BS ... to callee           : A5(traffic)KC
  3. Protocol actions

    1. SIM passes IMSI to HLR via BS, BSC, and maybe VLR.
    2. VLR sends a challenge RAND, a ciphering key KC and the expected response to the challenge SRES, to BS
    3. BS sends RAND to SIM
    4. SIM calculates Comp128(RAND)KI, the result of which is SRES concatenated with KC
    5. SIM sends the response SRES to BS, who checks it against the SRES received from HLR.
    6. SIM sends all further traffic to BS as A5(traffic)KC

Problems

There are several problems with this authentication protocol.

Implementation

In the protocol laid out above, the base station and the HLR often communicate using unsecured microwave links. Microwave links are used for their ease of installation, and in preference to land-lines because the local phone company is normally a competitor to the mobile company.

The triplet (RAND, SRES, Kc) passes between the base station and the HLR unencrypted, in the clear. So anyone with the necessary equipment could eaves-drop on a microwave connection, send an IMSI to a base station, and use the results to make phone calls that would appear to originate from someone else's phone - identity theft.

In addition to this, triplets can be re-used for billing. One triplet is used over the lifetime of its connection to a network, and is discarded when the phone is disconnected. Therefore, one triplet can be used for multiple calls. A network operator can use one triplet to repeatedly bill your account.

Algorithms

Comp128 is the A3/A8 hash function used by the vast majority of GSM providers, because it was the default in the reference implementation for the GSM protocol. It has an output length of 96 bits, and is used in the generation of Kc, which is 54 bits long, and SRES, which is 32 bits long.

On April 13, 1998, two students published the discovery of a flaw on the algorithm. Within a couple of days, source code surfaced on the Cypherpunks list that exploited the flaw, and made it possible to obtain Ki with a couple of hours access to the SIM card. GSM phones were no longer uncloneable.

A5 is the family of ciphers used for ensuring privacy between the base station and the mobile. There is generally no security from the base station to the rest of the phone network. This is where law enforcement taps take place. End-to-end privacy (encryption between one phone and another) was not implemented at the system level.

There are two versions of the A5 cipher. When the GSM standard was being created, there were worries from law enforcement and national security interests that the encryption would be too strong. Countries such as France wanted a weak cipher that was easy to break; countries with strong privacy laws such as Germany wanted a strong cipher that was difficult to break. NATO was worried about countries like Iraq gaining access to strong cryptography.

The end result was that two versions were created: A5/1 and A5/2. A5/1 was the full version, and was used within Europe and the USA. A5/2 was export strength - i.e. it was a weak cipher. There was a minor scuffle when it was discovered that Australia had been sold A5/2.

On April 10, 2000, Alex Biryukov, Adi Shamir, and David Wagner published a paper entitled "Real Time Cryptanalysis of A5/1 on a PC". In it, they detailed weaknesses in the algorithm and in it's implementation that allowed the retrieval of a key for an A5/1-encrypted conversation within one second, using a normal personal computer. A5/1 has been exposed as being totally pathetic.

Furthermore, it was revealed that the cipher was fairly simple - it only used three linear feedback shift registers (basic cipher components), and the last ten bits of the key were always zero.

The inescapable conclusion was that all versions of A5 - including A5/1 - had been deliberately weakened.

Justifications

GSM is a very successful standard, having become the worldwide standard for mobile communications (with the exception of the USA). The protocols involved are correct, and are improved upon in 3G. However, the design flaws in the authentication protocol outlined above were the result of bureaucratic squabbling, security through obscurity, and a closed standards process. Typically, the flaws in Comp128 were of a type that had been known and discussed in the cryptographic community for years.

Starting in 2000 and 2001, providers began to replace A5/1, and Comp128 with new, stronger components (A5/3 and Comp128-2, respectively), to prevent the GSM system from being unintentionally compromised.

GSM serves as the base protocol for SMS (Short Message Service) and WAP. It will all soon be replaced by the 3G protocol, the ''third generation'' mobile protocol, which solves all of the problems mentioned above, with the exception of end-to-end security.

Sources:
Security Engineering - Ross Anderson
http://www.willassen.no/msl/diplom.html
http://www.gsmworld.com/technology/spectrum_gsm.html
http://cryptome.org/cryptout.htm#GSM
http://www.brookson.com/index.htm