Introduction to Mobile Networks - 3G (UMTS) Authentication

In my last post Security in 2G (GSM) Networks we examined how the SIM and the Authentication Center (AuC) are involved in the authentication process. We were introduced to the COMP128 algorithms used to derive a response value RES and a ciphering key Kc from the subscriber secret key Ki and a random challenge RAND.

source: original illustration for Steemit

This introduction to GSM security concluded with a list of weaknesses that had been identified by the time work was underway to realize the specifications for the next generation of mobile networks: 3G.
Here is a summary of those weaknesses:

Authentication / ciphering is optional. The network can provide full service without ever authenticating the subscriber and send all traffic in the clear over the radio interface.
With GSM authentication, the network authenticates the subscriber but the subscriber does not authenticate the network.
The GSM authentication is vulnerable to replay attacks.
The traffic is only secured on the radio interface, between the UE and the BTS.

UMTS (3G) Security Improvements

3G brings in the following security improvements:

The new SIM, referred to as USIM (Universal SIM), and the network now authenticate each other, preventing an attacker from faking the home network.
The 3G authentication mechanism prevents authentication replay attack by introducing a new authentication sequence number SQN in the USIM and the AuC.
The key generation algorithms produce a RES and an encryption key like in 2G, but also a new integrity key.
Signalling messages exchanged over the radio interface must be marked with a hash derived from the the message itself and the integrity key mentioned above. This prevents message tampering during a man-in-the-middle attack. The only exception to this rule is for emergency calls.

One key aspects of 3G authentication is that it can also be used over 2G (GSM) networks. All that is required is for the subscriber to replace his/her SIM with a USIM. In fact nowadays few 2G SIMs are in circulation in Western countries while the USIM is widely used across 2G, 3G and 4G networks.

UMTS Authentication and Keys Generation

Given a subscriber secret K (referred as Ki in GSM authentication but essentially the same thing), an authentication sequence number SQN, a random challenge RAND (same as 2G), 3gPP defines a set of algorithms which produce the following authentication and keying materials:

MAC: a network authentication code which can be verified by the USIM. Checked by the UE
XRES: an expected value returned by the SIM in response of the challenge. Checked by the network.
CK: a session key used for ciphering (encrypting) traffic
IK: a session key used for marking all traffic packets with a hash signature.
AK: an anonymity key used to obfuscate the SQN on its way to the UE

Each one of the above values are generated by a set of five cryptographic functions referred in 3gPP as f1, f2, f3, f4 and f5.
The role of each function is as follows:

f1: Generates MAC from K, SQN and RAND. An algorithm variant named AMF can also be used as a salt of the algorithm.
f2: Generates XRES from K and RAND.
f3: Generates CK from K and RAND.
f4: Generates IK from K and RAND.
f5: Generates AK from K and RAND.

All of the above is illustrated in the diagram below.

source: 3gPP 33.102

Using the generated values above the network sends an AUTN (authentication) string to the UE which consists of the SQN obfuscated with the anonymity key AK, the algorithm variant AMF and the MAC. The challenge RAND is also sent with the AUTN.

The UE then supplies the received RAND and AMF to the USIM authentication application which executes the same f1, f2, f3, f4 and f5 algorithms and returns the resulting MAC, RES, CK, IK and AK to the UE.
The UE can now check that the MAC received from the network is the same as the MAC calculated by the USIM.
The CK and IK values are stored in the UE for later use and the RES is sent back to the network which must check that RES = XRES.

There is a lot of information in the above so it is probably easier to understand the procedure through a sequence diagram. Note that the 3G authentication is shown over a 2G network but most of the sequence shown is actually identical when the procedure takes place over a 3G network.

source: original illustration for Steemit

The UE initiates a procedure by sending an initial message to the network, for example a Location Updating Request to initiate CS attachment (see GSM CS Attachment). All traffic transmitted over the radio interface is currently sent in the clear.
The MSC receives the UE message and initiates the appropriate procedure with the VLR (e.g. Update Location Area)
The VLR decides to authenticate the subscriber. It sends a Send Authentication Info Request to the HLR along with the IMSI of the subscriber.
The HLR requests the AuC for one or more authentication vectors (AVs), supplying the IMSI.
The AuC retrieves the secret key K and authentication sequence number SQN associated with the IMSI. For each requested AV it generates a random challenge RAND and executes f1, f2, f3, f4 and f5 resulting in as many [MAC, XRES, CK, IK, AK] result values. The SQN value is obfuscated with the anonymity key AK through an XOR operation. The AMF and the MAC are concatenated to this obfuscated to form an Authentication token named AUTN.
The AuC returns a list of [RAND, AUTN, CK, IK, XRES] AVs to the HLR.
The HLR returns the first authentication vector AV to the VLR in a Send Authentication Info Response message.
The VLR stores the XRES, CK and IK for later use.
The VLR requests the MSC to authenticate the subscriber. It supplies the RAND and the AUTN.
The MSC an Authentication Request to the UE, supplying the RAND and AUTN.
The UE invokes the AUTHENTICATE program on the SIM, supplying the RAND and AUTN.
The SIM executes f1, f2, f3, f4, f5 supplying the RAND, AMF (extracted from AUTN), its stored SQN and secret key K. This returns [MAC, RES, CK, IK, AK]. It then calculate SQN XOR AK and verifies that the value matches the value in the AUTN. It also checks that the calculated MAC matches the MAC extracted from the AUTN token.
The SIM returns to the UE the generated CK, IK and RES values.
The UE stores the CK and IK and, because the procedure is over GSM, derives a Kc from these two values.
The UE sends back an Authentication Response to the MSC with the calculated RES.
The MSC responds to the VLR authentication response, supplying the RES returned by the UE.
The VLR verifies that RES = SRES. If this check is verified, then the SIM is storing the same Ki as in the AuC and therefore the subscriber is authenticated. It derives a Kc from the stored CK and IK.
The VLR now can use the stored Kc to request the BTS/UE to start encrypting all traffic exchanged over the radio interface. It does so by sending a Set Ciphering Mode message to the MSC, supplying the Kc and a chosen encryption algorithms supported by the BTS and the UE.
The MSC requests the BTS and UE to start ciphering by sending a Ciphering Mode Command. The Kc and encryption algorithm is supplied.
The BTS stores the Kc for later use.
The BTS sends the Ciphering Mode Command to the UE with the selected encryption algorithm.
The UE activate encryption on the logical channel using the stored Kc as ciphering key.
the UE sends a Ciphering Mode Complete back to the BTS.
The BTS starts encryption on the logical channel using the stored Kc.
The BTS forwards the Ciphering Mode Complete to the MSC.
All traffic sent in both directions over the radio link is now encrypted.

Choice of f1, f2, f3, f4, f5 Algorithms

As we have learned, 3gPP describes five key generation function to derive authentication vectors: f1, f2, f3, f4, f5.
The specifications describes the input, the output and the cryptographic requirements of each function but the exact implementation is left as a choice to the SIM/AuC provider.

In practice 3gPP gave so far two examples of confidentiality functions that meet all these requirements: MILENAGE and TUAK.

MILENAGE has been widely adopted in the mobile industry since the advent of 3G networks and is more or less guaranteed to be present on all USIMs currently in circulation.

TUAK is more recent and quite different than MILENAGE in design so that if MILENAGE was compromised a backup algorithm set would be available to mobile operators.

In practice Milenage is still considered secure today and TUAK hasn't been significantly deployed yet.

Preventing Replay Attacks with SQN

As we have seen in the previous sections the UMTS authentication uses an authentication sequence number SQN which is used along with the RAND and secret K as input arguments to the MILENAGE algorithm set.

This value SQN is stored securely in the AuC and the USIM and must be incremented on both sides upon each authentication vector AV generation.

When the USIM receives the SQN value received from the network (remember, it is obfuscated with the anonymity key AK), it checks that the received SQN corresponds to the SIM SQN.
If this is not the case it triggers a procedure with the network to re-synchronize the SQN value in the AuC with the value stored in the USIM.

Before we look at how this re-synchronization procedure works, let's examine how the network and the USIM could store different values of SQN.

How SQN Synchronization Errors Happen

Consider that a mobile network operator is made of many VLRs (and other network elements) which can authenticate subscribers. Each one of these network elements can request several authentication vectors (AVs) from the HLR but may not use all received AVs.

Consider now that UEs can move between network elements, we can now foresee the following scenario.

source: original illustration for Steemit

A UE initiates a procedure such as a Location Update.
The VLR requests the HLR to return 2 authentication vectors.
The HLR returns 2 AVs: AV1 (for SQN1) and AV2 (for SQN2)
The VLR uses AV1 for authenticating the subscriber and keeps AV2 for later use.
The UE now moves to another cell served by another VLR.
The UE initiates a new Location Update procedure
The new VLR requests an authentication vector from the HLR.
The HLR returns AV3. Note that AV3 will have SQN3 = SQN2 + 1
The VLR authenticate the subscriber with AV3. Note that the USIM will accept an authentication with SQN3 following SQN1 as a small SQN delta is allowed.
The UE now returns the the first cell.
The UE initiates a Location Update
The VLR still AV2 for this subcriber corresponding to SQN2. The VLR initiates the authentication procedure with AV2.
The SIM detects that SQN2 < SQN3 and rejects the authentication with a synchronization failure.

Note that the specifications allow for a new VLR to retrieve a subscriber details, including stored AVs, from an old VLR so in principle the above scenario doesn't occur under normal circumstances. However the subscriber information retrieval from a previous VLR may fail and therefore the scenario described may happen.

Recovering from a Synchronization Failure

When the USIM detects a synchronization failure it generate a new Authentication Synchronization token AUTS which contains an obfuscated value of the correct SQN and a hash MAC-S which proves to the network that it is the originator of the re-synchronization procedure.

3gPP defined two more key generation functions to provide this functionality:

f1* (f1 star): Generates MAC-S from the received RAND, AMF, K and the correct SQN
f5* (f5 star): Generates the anonymity key from K and the received RAND
The USIM then obfuscates the correct SQN with the generated AK and constructs the AUTS token.
All of this is illustrated in the diagram below.

source: 3gPP 33.102

The AUTS token is then returned to the network in an Authentication Failure message with cause Synchronization Failure.

The network now requests the AuC to return new authentication vectors but this time it supplies the AUTS token as well as the IMSI of the subscriber.

The AuC invokes the f5* function to calculate the anonymity key AK. It can now retrieved the SQN value from the AUTS token, since (SQN xor AK) xor AK = SQN

Now that the USIM SQN has been retrieved, the AuC also executes f1* to calculate MAC-S and check that the computed value is the same as the received value in the AUTS token.

If all of the above operations succeed, the AuC updates the SQN in its database and calculate new authentication vectors AVs.
These are then used to initiate a new authentication procedure with the UE.

Let's summarize all this with the sequence diagram below.

source: original illustration for Steemit

The UE has initiated an initial procedure, such as location update, as before. Authentication vectors have been requested from the HLR.
The VLR initiates authentication
The MSC sends an Authenticate Request with an AUTN token and a RAND.
The UE invokes the USIM Authenticate program.
The USIM executes the key generation functions and finds out that the SQN used by the network is invalid.
The USIM executes f1* and f5* to generate the AUTS token.
The USIM returns a failure to the UE indicating Synchronization failure and supplies the AUTS token.
The UE sends back an Authentication Failure to the MSC with the AUTS token.
The MSC forwards the result to the VLR.
The VLR requests new authentication vectors AVs from the HLR. It supplies the IMSI, the previously used RAND, and the received AUTS token.
The HLR forwards the request to the AuC.
The AuC executes f1* and f5* to verify the MAC-S value in the AUTS and extracts the correct SQN value. It updates its database with the correct SQN and calculates new AVs
AVs are returned to the HLR
The HLR sends back the AVs to the VLR.
The VLR initiates a new authentication procedure with the UE, which should succeed.

Conclusions

As you can see the 3G authentication procedure is reasonably complex. In returns it addresses all the weaknesses identified with 2G authentication.

The new authentication required a new type of SIM when initial 3G networks were deployed, and the AuCs had to undergo software updates.

3G authentication has been used all over the world since the dawn of the new millennium and is still in use in current 4G networks, proof that the mechanisms described in this post have withstood the test of time.

Another key advantage of the updated authentication procedure is that it could be easily back ported to legacy 2G networks.

What Next?

Armed with a good understanding of 2G network architecture, CS attachment and security procedures, it is now time to examine the first useful feature of the network provided to subscribers: voice calls.
This will be the subject of my next post in this series.

Acronyms and Concepts

Acronym	Meaning	Description
AK	Anonymity Key	Key value used to authenticate the SQN
AMF	Access and Mobility Function	A number used as a salt in the key generation functions
AuC	Authentication Center	The network element, usually located with the HLR, storing all subscribers secret keys and in charge of calculating authentication vectors
AUTN	Authentication Token	Authentication token generated by the AuC consisting of the obfuscated SQN, AMF and MAC
AUTS	Authentication Synchronization Token	Authentication token generated by the USIM which carries SQN re-synchronization information
HLR	Home Location Register	Stores all subscriber information such as IMSI, access and service rights, location information, etc.
IMSI	International Mobile Subscriber Identity	15 digits number uniquely identifying a mobile network subscriber across all providers
Kc	Key Ciphering	64bit ciphering key used for encrypting traffic transmitted over the radio interface
K	Key Individual	A 128bit shared key stored in the SIM and the AuC for authenticating the subscriber to the GSM network
MAC	Message Authentication Code	A hash value proving to an end party that the generating party was in possession of the secret key K
MAC-S	Message Authentication Code - Synchronization	A MAC generated by the USIM for the purpose of SQN re-synchronization
PLMN	Public Land Mobile Network	An operator providing mobile telecommunication services
RAND	Random Value	128bit value randomly generated by the AuC and used as a challenge to authenticate the subscriber
RES	Result	32bit value resulting from executing COMP128 with the supplied RAND value and secret key Ki
SIM	Subscriber Identity Module	A type of UICC fitted within mobile network terminals (e.g. handsets). Responsible for storing important and sensitive information and capable of processing instructions, including authentication algorithms
SRES	Signed Response	32bit value calculated by the AuC using COMP128 on a RAND value and secret Ki
UE	User Equipment	Terminal used by the subscriber to access the mobile network, such as smartphone, modem, IoT device, etc.

References

Previous Posts in this Series

Introduction to Mobile Networks
The GSM CS Architecture
GSM CS Attachment
Security in 2G (GSM) Networks

As always do not hesitate to leave comments with your questions and I will make sure to reply with the best possible answers.