GSM Security

1. Authenticate the subscriber, so that calls are billed to whoever really made them and a cloned identity does not work.
2. Encrypt the radio path, so that casual interception fails.
3. Hide the subscriber's identity on the air, so that a listener cannot track a person.

The goals are all about the operator's interests on the radio link: fraud, casual eavesdropping, and traffic analysis. Protecting the subscriber from the network, or the call once it is inside the network, was not among them, and that omission explains every weakness below.

The triplet, and why it exists

The clever part of the design is that a visited network authenticates a subscriber it knows nothing about, without ever learning the subscriber's secret.

The AuC, sitting with the HLR, holds Ki. On request it computes a batch of triplets, each one a random challenge, the response that the SIM will give, and the ciphering key that both will derive, and sends them to the VLR. The VLR can then authenticate the subscriber repeatedly, and start ciphering, without another word to the home network, and without ever holding Ki.

The exchange on the air is two messages: RAND down, SRES up. Both travel in clear, which is safe because knowing RAND and SRES does not give Ki, and because the next challenge is different.

Ciphering

Once authenticated, the network orders ciphering, naming which A5 variant to use, and both ends load Kc. A5 is a stream cipher: it produces a keystream from Kc and the frame number, and the keystream is added to the bits. Using the frame number means the keystream changes every 4.615 ms and does not repeat until the hyperframe does, about three and a half hours later ([GSM Logical Channels and the Frame Hierarchy] computed it, and this is the reason it is so long).

Ciphering runs between the MS and the BTS, as the standard says. Beyond the BTS, the call travels over Abis and into the core in clear, unless the operator has separately protected those links.

Anonymity

The IMSI is the permanent identity, and sending it on the air would let anyone track a subscriber. GSM therefore allocates a TMSI, sends it ciphered, and changes it, as [Localization and Calling in GSM] described. It is a real improvement, and it is not a guarantee: a network can always demand the IMSI, and a mobile that has just entered a network with no usable TMSI must send it.

Where the design falls short

One-way authentication. The subscriber proves itself to the network; the network proves nothing. A false base station can therefore broadcast a stronger signal claiming to be the operator, attract nearby mobiles, decline to authenticate them (nothing requires it to), order A5/0, no ciphering, and relay the calls onward while listening. The program lists the steps. This is the weakness UMTS was designed to close, by having the network prove knowledge of the key too.

Encryption stops at the BTS. Everything in the core is in clear to anyone with access to it, which includes microwave links between a BTS and its BSC.

No integrity protection. A GSM message is encrypted but not authenticated, so an attacker who can modify bits changes the message, and the receiver has no way to notice. Integrity protection of signalling is again a UMTS addition.

Weak algorithms. A5/1 was deliberately weakened for export, A5/2 more so, and both have been broken by published cryptanalysis; A5/0 is no encryption at all. A5/3 (based on KASUMI) and later A5/4 were added, and the standard's clauses on negotiation exist because a network and a mobile must agree which variant to use, which is itself an attack surface: an attacker who can force the choice downward gets a weaker cipher.

And one more, worth knowing. Some networks reduced the effective length of Kc, fixing part of it to zero, so that the 64-bit key carried fewer than 64 bits of entropy.

GSM security, computed

The program computes triplets with stand-in algorithms; tabulates what crosses the air and what never does; lists the properties the design provides and those it does not; explains the frame number's role in the keystream; and walks a false base station attack.

# GSM security: the triplet, where each secret lives, and what the design does
# and does not protect against.
import hashlib
import random

# 1. The triplet, with stand-in algorithms. The real A3 and A8 are operator
#    secrets; here SHA-256 stands in for both, which is enough to show the flow.
def a3a8(ki, rand):
    h = hashlib.sha256(ki + rand).digest()
    return h[:4], h[4:12]                      # SRES (32 bits), Kc (64 bits)

ki = bytes(range(16))                          # the SIM's secret key, 128 bits
print("Authentication, as the AuC and the SIM each compute it:")
rnd = random.Random(94)
for i in range(3):
    rand = bytes(rnd.randrange(256) for _ in range(16))
    sres, kc = a3a8(ki, rand)
    print("  RAND %s -> SRES %s, Kc %s" % (rand[:6].hex(), sres.hex(), kc.hex()))
print("  the AuC computes triplets in advance and sends them to the VLR; the SIM computes")
print("  the same values when challenged, and Ki never leaves either place.")

# 2. What is sent and what is not.
print("\nWhat crosses the air, and what does not:")
for item, crosses in (("RAND, the challenge", "yes, in clear"),
                      ("SRES, the response", "yes, in clear"),
                      ("Ki, the subscriber key", "never"),
                      ("Kc, the ciphering key", "never: both ends derive it"),
                      ("IMSI", "only when no TMSI can be used"),
                      ("TMSI", "yes, but it is temporary and local")):
    print("  %-26s %s" % (item, crosses))

# 3. Where GSM's security stops. Each row is a property and whether GSM has it.
print("\nWhat the design provides, and what it does not:")
for prop, verdict, why in (
        ("the network authenticates the subscriber", "yes", "A3 with a challenge and response"),
        ("the subscriber authenticates the network", "NO", "nothing stops a false base station"),
        ("confidentiality on the air", "yes", "A5 between the MS and the BTS"),
        ("confidentiality beyond the BTS", "NO", "Abis and the core are in clear unless separately protected"),
        ("subscriber anonymity", "partly", "the TMSI hides the IMSI, but the IMSI can be demanded"),
        ("integrity of signalling", "NO", "no message authentication: messages can be altered"),
        ("strong ciphers", "NO", "A5/1 and A5/2 are broken; A5/3 and A5/4 came later")):
    print("  %-42s %-7s %s" % (prop, verdict, why))

# 4. Why a 64-bit key and a 22-bit frame number matter: the keystream must not
#    repeat, and the hyperframe is what guarantees it.
FRAME_MS = 4.615384615
print("\nThe keystream and the frame number:")
print("  A5 takes Kc and the frame number, so the keystream repeats when the frame number does")
print("  the hyperframe is 2,715,648 frames, %.2f hours: longer than any call" % (2715648 * FRAME_MS / 3600000))
print("  Kc is 64 bits, but some networks fixed 10 of them to zero, leaving %d bits of real key" % 54)

# 5. A false base station, in one exchange.
print("\nWhy a false base station works against GSM:")
for step in ("the attacker broadcasts a stronger BCCH claiming to be the network",
             "the mobile camps on it and offers its identity; the attacker may demand the IMSI",
             "the attacker never asks for authentication, because nothing requires it to",
             "the attacker orders A5/0, that is no ciphering, and the mobile complies",
             "the attacker relays the call onward, listening to everything"):
    print("  - %s" % step)
print("  the fix is mutual authentication, which UMTS introduced.")

The triplet. Three challenges give three different responses and three different ciphering keys, all computed from the same Ki. Two things follow: the VLR can authenticate as often as it likes from a batch, and an attacker who records one exchange learns nothing usable, because the next RAND will be different.

What crosses. RAND and SRES cross in clear; Ki never crosses at all, and Kc never crosses either, since both ends compute it. That is the strength of the design, and it is genuinely strong: cloning a SIM by listening to the air does not work.

What is missing. The table is the examination answer: subscriber authenticated yes, network authenticated no, air encrypted yes, core encrypted no, anonymity partly, integrity no, strong ciphers no in the original algorithms. Four of seven are absent, and every one of the four is a consequence of the same decision, that security was designed to protect the operator from the subscriber and from the casual listener, not the subscriber from anyone.

The false base station. Five steps, none of which requires breaking any cipher. That is the difference between a cryptographic weakness and a protocol weakness: the ciphers can be replaced, but a protocol that never authenticates the network cannot be patched from the handset.

Distinctions

What it does not mean

Encrypted does not mean end to end. The call is in clear from the BTS onward.

Authentication is not mutual. The network never proves who it is, which is what a false base station exploits.

A TMSI is not anonymity. It hides the IMSI from a casual listener; the network can always ask for the IMSI.

Breaking A5 is not the only attack. The protocol weaknesses need no cryptanalysis at all.

A secret algorithm is not a strong one. A3 and A8 are operator choices, and the early common example, COMP128, was itself broken.

Quick revision

• Ki: 128-bit key, only in the SIM and the AuC.
• A3: computes SRES from RAND and Ki, to "allow authentication of a mobile subscriber's identity". A8: computes Kc from RAND and Ki, in the SIM, co-located with A3 in the network. A5: protects "both user data and signalling information elements at the physical layer on the dedicated channels (TCH or DCCH)", in the MS and the BSS, keyed by Kc and the frame number.
• Triplet (RAND, SRES, Kc): computed by the AuC, used by the VLR, so the visited network never sees Ki. RAND and SRES cross in clear; Ki and Kc never cross.
• Anonymity: the TMSI, temporary and local.
• Weaknesses: no network authentication (false base station, can force A5/0), encryption only to the BTS, no integrity protection, A5/1 and A5/2 broken (A5/3, A5/4 later), and Kc sometimes effectively shortened.
• UMTS answers with mutual authentication and integrity protection.

Test yourself

1. Describe GSM's authentication procedure. The authentication centre, which shares the subscriber key Ki with the SIM, computes triplets consisting of a random challenge RAND, the expected response SRES that the SIM will produce from RAND and Ki using algorithm A3, and the ciphering key Kc that both will derive from RAND and Ki using algorithm A8. These triplets are sent to the visitor location register. To authenticate, the network sends RAND to the mobile; the SIM computes SRES and returns it; the network compares it with the value in the triplet. The key Ki never leaves the SIM or the authentication centre, and Kc is never transmitted.

2. What are A3, A5 and A8, and where does each run? A3 authenticates the subscriber's identity by computing an expected response SRES from a random challenge RAND using the secret key Ki; it runs in the SIM and in the authentication centre. A8 computes the ciphering key Kc from RAND and Ki; it is contained in the SIM and, on the network side, is co-located with A3. A5 protects both user data and signalling at the physical layer on the dedicated channels; it is implemented in the mobile station and in the base station subsystem, and is keyed by Kc together with the frame number.

3. Why does the authentication centre send triplets rather than the key? So that a visited network can authenticate a subscriber and encrypt the radio link without ever learning the subscriber's secret key. The triplets contain only a challenge, the expected answer and the derived session key, so a compromised or untrusted visited network cannot impersonate the subscriber in the future or derive keys for other challenges; and because triplets are sent in batches, the visited network can authenticate repeatedly without further traffic to the home network.

4. How does a false base station attack GSM, and why does it work? The attacker transmits a stronger broadcast channel claiming to be the operator's network, so nearby mobiles camp on it. Because GSM authenticates only the subscriber to the network, and never the network to the subscriber, the false base station is not obliged to authenticate the mobile at all, and it can order the null cipher A5/0 or a weak variant, which the mobile accepts. It can then relay the traffic to the real network while reading it. No cipher has to be broken; the weakness is in the protocol, and the answer is mutual authentication, which UMTS introduced.

5. What does GSM's encryption not cover? It covers only the radio path between the mobile station and the base transceiver station. The Abis link from the BTS to the BSC, the A interface, and everything in the core network carry the call unencrypted unless the operator protects them separately, so anyone with access to those links, including microwave hops between sites, can listen. GSM also provides no integrity protection at all, so a message can be altered without detection.

6. Summarise GSM's security weaknesses and how UMTS answers them. GSM authenticates the subscriber but not the network, so false base stations work; it encrypts only to the base transceiver station; it provides no integrity protection of signalling; and its original ciphers, A5/1 and A5/2, have been broken, with A5/0 providing none at all. UMTS introduces mutual authentication, so the network must prove knowledge of the key; it adds integrity protection of signalling messages; it extends the encryption to the radio network controller; and it uses a published, stronger algorithm from the start.