Security Protocols with Conventional Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 148

MS VLR HLR

IMSI
−−−−−−−−−−−−−−→

IMSI
−−−−−−−−−−−−−−→

(Ki) (Ki)

)
←−−−−−−−−−−−−−−

n × ( RAND , SRES , KC

RAND
←−−−−−−−−−−−−−− store

SRES
−−−−−−−−−−−−−−→ check

)
←−−−−−−−−−−−−−−

C KC ( TMSI

TMSI
−−−−−−−−−−−−−−→
RAND
←−−−−−−−−−−−−−−
SRES
−−−−−−−−−−−−−−→

check

Figure 5.8. GSM authentication.

explained, the A3/8 algorithm itself is not standard: every GSM operator can use its
own algorithm. However, the A5 algorithm is standard but secret. 9

A mobile system (MS) is a combination of a terminal and a security module (the
SIM card). The terminal can be manufactured by any company, but the SIM card is
manufactured by the service provider who corresponds to a home network: the Home
Location Register (HLR). Each MS has an identifier called IMSI. When connecting to
a local network, the Visited Location Register (VLR), the IMSI is sent and forwarded
to the HLR (see Fig. 5.8). Then, the HLR sends many triplets, which are used in order
to authenticate the MS to the VLR. After the first authentication, the VLR gives a
temporary identity TMSI to the MS in a confidential way in order to protect its privacy.

For the authentication, the mobile and the network share a long-term 128-bit secret
key Ki (integrity key) which is stored in the security module. When a mobile identifies
itself, it sends a TMSI (a temporary identity) which protects the real identity. The
network sends a random 128-bit challenge RAND to the mobile. The mobile uses
A3/8 with inputs Ki and RAND in order to compute SRES and KC. SRES is sent to
the network. It is the response to the challenge. The network can perform the same
computation and compare the SRES values for authentication. At the end, the mobile
is authenticated and both parties have computed a common short-term 64-bit secret
key KC. KC is used for encryption. The three values RAND, SRES, and KC make a
triplet, which is used by the VLR.

We emphasize that Ki is protected by the security module and the HLR, but KC is
a short-term secret key between the device and the VLR. Encryption is performed by
the telephone, whereas authentication is performed by the security module. Therefore,
A5 must be standard for every VLR and telephone manufacturers, but A3/8 can be
specific to a service provider.

9

The version presented in Section 2.8.3 was disclosed, and then broken in Ref. [32]. Interestingly, another
secret algorithm—COMP128, which was an A3/8 proprietary algorithm—was disclosed and broken. See
http://www.isaac.cs.berkeley.edu/isaac/gsm.html .