Tue 16-03-2004 07:30 PM
On GSM Security
Nowadays, the typical example to illustrate the inconveniences of the “security through obscurity” method should be the worrisome insecurities of the GSM standard. Designed in 1989, its different security procedures were given the following names:
- A3: authentication algorithm
- A8: key generation algorithm
- COMP128: authentication algorithm widely used for A3 and A8
- A5/1: "strong" over-the-air voice-privacy algorithm
- A5/2: "weak" over-the-air voice-privacy algorithm
- A5/3: add-on stronger over-the-air voice-privacy algorithm .
Since the beginning, there were problems: the closed design process, the unpublished descriptions of A5/1, A5/2 and COMP128 and the deliberate weakening of the algorithms were a clear indication of the poor quality of the standard.
A leaked GSM document specifying COMP128 in 1998 started it all, and a corrected implementation of the algorithm came out: a chosen-challenge attack was announced, requiring physical access to the target SIM, although an over-the-air attack could also be carried out. With the SIM internal key and the intercepted random challenge sent by the base station, the attacker can derive the session key used by A5 and successfully decrypt the voice communications.
With COMP128 broken, A5/1 was the next target: the first cryptanalysis, "Cryptanalysis of alleged A5 stream cipher" based on partial design appeared. But the publication of “A pedagogical implementation of A5/1”, containing an alleged implementation, allowed the first significant cryptanalysis: "Real-time cryptanalysis of A5/1 on a PC". Later, some other efficient attacks have been published:
- "BDD-based cryptanalysis of keystream generators"
- “Cryptanalysis of the A5/1 GSM stream cipher”
- "Another attack on A5/1"
Bad publicity pressured to release the stronger cipher A5/3, KASUMI, based on MISTY1, which featured an academic design. A number of attacks have been test on both, without noticeable success:
- “On MISTY1 higher order differential cryptanalysis”
- "Strength of MISTY1 without FL Function for Higher Order Differential Attack"
- "Integral cryptanalysis (extended abstract)"
- "Cryptanalysis of reduced-round MISTY"
- “Improved cryptanalysis of MISTY1”
- "Related key attacks on reduced round KASUMI"
- "On the Strength of KASUMI without FL Functions against Higher Order Differential Attack"
With KASUMI, it would seem that the GSM Association has learned from its mistakes: au contraire!. The second version of COMP128, COMP128-2, is unpublished. And even if KASUMI is secure, the protocols haven’t been fixed: the last attack, "Instant Ciphertext-only cryptanalysis of GSM encrypted communication", requests the secret key under the weak A5/2 to later decrypt voice under KASUMI.
Some of these attacks have been implemented by the following companies (really expensive products!):
