Have the A3 and A8 algorithms been broken?

Most GSM providers use a version of COMP128 for both the A3 authentication algorithm and the A8 key generation algorithm.

Ian Goldberg and David Wagner of the University of California at Berkeley demonstrated that all A8 implementations they looked at, including the few that did not use COMP128, were deliberately weakened. The A8 algorithm takes a 64-bit key, but ten key bits were set to zero. The attack on the A8 algorithm demonstrated by Goldberg and Wagner takes just 2^19 queries to the GSM SIM *Subscriber Identity Module), which takes roughly 8 hours.

Josyula R. Rao, Pankaj Rohatgi and Helmut Scherzer of IBM and Stephane Tinguely of the Swiss Federal Institute of Technology have published Partitioning Attacks: Or How to Rapidly Clone Some GSM Cards which shows a method by which COMP128 can be broken in less than a minute.

The COMP128-2 and COMP128-3 algorithms have been developed to address the security issues of COMP128-1. COMP128-2 and COMP128-3 are secret algorithms which have not been subject to cryptanalysis. COMP128-3 fixes the issue where 10 bits of the Session Key (Kc) were set to zero.

GSM network operators are slowly migrating from COMP128 (also known as COMP128-1) to COMP28-2 or COMP128-3. Because the A3 and A8 algorithms are stored in the Subscriber Identity Module, this requires changing the GSM subscribers SIM cards.

How do Authentication and Key generation work in a GSM network?

Encryption in the GSM network utilizes a Challenge/Response mechanism.

1. The Mobile Station (MS) signs into the network.
2. The Mobile Services Switching Center (MSC) requests 5 triples from the Home Location Register (HLR).
3. The Home Location Register creates five triples utilizing the A8 algorithm. These five triples each contain:
   • A 128-bit random challenge (RAND)
   • A 32-bit matching Signed Response (SRES)
   • A 64-bit ciphering key used as a Session Key (Kc).
4. The Home Location Register sends the Mobile Services Switching Center the five triples.
5. The Mobile Services Switching Center sends the random challenge from the first triple to the Base Transceiver Station (BTS).
6. The Base Transceiver Station sends the random challenge from the first triple to the Mobile Station.
7. The Mobile Station receives the random challenge from the Base Transceiver Station and encrypts it with the Individual Subscriber Authentication Key (Ki) assigned to the Mobile Station utilizing the A3 algorithm.
8. The Mobile Station sends the Signed Response to the Base Transceiver Station.
9. The Base Transceiver Station sends the Signed Response to the Mobile Services Switching Center.
10. The Mobile Services Switching Center verifies the Signed Response.
11. The Mobile Station generates a Session Key (Kc) utilizing the A8 algorithm, the Individual Subscriber Authentication Key (Ki) assigned to the Mobile Station, and the random challenge received from the Base Transceiver Station.
12. The Mobile Station sends the Session Key (Kc) to the Base Transceiver Station.
13. The Mobile Services Switching Center sends the Session Key (Kc) to the Base Transceiver Station.
14. The Base Transceiver Station receives the Session Key (Kc) from the Mobile Services Switching Center.
15. The Base Transceiver Station receives the Session Key (Kc) from the Mobile Station.
16. The Base Transceiver Station verifies the Session Keys from the Mobile Station and the Mobile Services switching Center.
17. The A5 algorithm is initialized with the Session Key (Kc) and the number of the frame to be encrypted.
18. Over-the-air communication channel between the Mobile Station and Base Transceiver Station can now be encrypted utilizing the A5 algorithm.

This process authenticates the GSM Mobile Station (MS) to the GSM network. One known security limitation of GSM networks is that the GSM network is never authenticated by the GSM Mobile Station (MS).

This one-way authentication makes it possible for an attacker to pretend to be a GSM network provider.

How do Authentication and Key generation work in a GSM network?

Encryption in the GSM network utilizes a Challenge/Response mechanism.

1. The Mobile Station (MS) signs into the network.
2. The Mobile Services Switching Center (MSC) requests 5 triples from the Home Location Register (HLR).
3. The Home Location Register creates five triples utilizing the A8 algorithm. These five triples each contain:
   • A 128-bit random challenge (RAND)
   • A 32-bit matching Signed Response (SRES)
   • A 64-bit ciphering key used as a Session Key (Kc).
4. The Home Location Register sends the Mobile Services Switching Center the five triples.
5. The Mobile Services Switching Center sends the random challenge from the first triple to the Base Transceiver Station (BTS).
6. The Base Transceiver Station sends the random challenge from the first triple to the Mobile Station.
7. The Mobile Station receives the random challenge from the Base Transceiver Station and encrypts it with the Individual Subscriber Authentication Key (Ki) assigned to the Mobile Station utilizing the A3 algorithm.
8. The Mobile Station sends the Signed Response to the Base Transceiver Station.
9. The Base Transceiver Station sends the Signed Response to the Mobile Services Switching Center.
10. The Mobile Services Switching Center verifies the Signed Response.
11. The Mobile Station generates a Session Key (Kc) utilizing the A8 algorithm, the Individual Subscriber Authentication Key (Ki) assigned to the Mobile Station, and the random challenge received from the Base Transceiver Station.
12. The Mobile Station sends the Session Key (Kc) to the Base Transceiver Station.
13. The Mobile Services Switching Center sends the Session Key (Kc) to the Base Transceiver Station.
14. The Base Transceiver Station receives the Session Key (Kc) from the Mobile Services Switching Center.
15. The Base Transceiver Station receives the Session Key (Kc) from the Mobile Station.
16. The Base Transceiver Station verifies the Session Keys from the Mobile Station and the Mobile Services switching Center.
17. The A5 algorithm is initialized with the Session Key (Kc) and the number of the frame to be encrypted.
18. Over-the-air communication channel between the Mobile Station and Base Transceiver Station can now be encrypted utilizing the A5 algorithm.

This process authenticates the GSM Mobile Station (MS) to the GSM network. One known security limitation of GSM networks is that the GSM network is never authenticated by the GSM Mobile Station (MS).

This one-way authentication makes it possible for an attacker to pretend to be a GSM network provider.