Cryptanalysis of the GSM Algorithms

www.oocities.org/eoinward

In Brief: The Project involved the investigation of the cryptographic strength of the algorithms used in GSM Mobile phones. This included investigating previous attacks simulating the GSM environment and generating attacks on this environment. I launched anattack on a SIM card after building a SMART card reader circuit and extracted it’s secret key by cracking the A3/A8 algorithms making it possible to clone that SIM card. As well as launching Attaches on A5 and showing that A5/2 is insecure.

The goal of the project was to investigate the cryptographic strength of the GSM encryption algorithms. The four core GSM algorithms are:

· A3 authentication algorithm

· A5/1   "strong" over-the-air voice-privacy algorithm
· A5/2   "weak" over-the-air voice-privacy algorithm
· A8   voice-privacy key generation algorithm

Basics
 
Firstly I look at the different types of Algorithms; Symmetric Algorithms, Stream Ciphers, Block Ciphers, Public-Key Algorithms, Multiple-Key
 Public–Key Cryptography, Message Broadcasting etc.. Next I looked at Cryptanalysis and Kerckhoff's Principle. Followed by the different
 types of attacks Ciphertext-only attack, Known plaintext, Chosen plaintext and Chosen Ciphertext. I took a good look at Work Factor for
 comparison of algorithms and Differential Cryptanalysis, Linear cryptanalysis and Weak keys.

DES Data Encryption Standard

DES has been a worldwide standard for 25 years. DES has been crypto-analysed since its release so it is regarded as an excellent starting place when studying cryptology. I looked at the structure of DES and what’s involved in a round. I looked at some of the attack on DES;

1. Biham and Shamir use of differential cryptanalysis requiring the encryption of 2⁴⁷ chosen plaintexts.
2. Matsui has developed an attack using linear cryptanalysis with this method a DES key can be recovered by the analysis of 2⁴³ known plaintexts

3. The Electronic Frontier Foundation DES Cracker and a worldwide network of nearly 100,000 PCs on the Internet, broke DES in 22 hours and 15 minutes.

I t became apparent that DES is not secure, simply because 56 bit keys are vulnerable to exhaustive search.

Advanced Encryption Standard Round 2 finalists

Rijndael - Joan Daemen, Vincent Rijmen

Mars - IBM

RC6^TM - RSA Laboratories

Serpent - Ross Anderson, Eli Biham, Lars Knudsen

Twofish - Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson

I explained the structure and workings of each cipher; it’s advantages and disadvantages. I compared them under the following categories;

Area, Throughput, Transistor Count, Input/Outputs (I/O) Required, Key Set-up Time, Algorithm Set-up Time, Time to Encrypt One Block, Time to Decrypt One Block.

It seemed that Both Rijndael and Serpent are both very strong applicants for the AES. I discussed why the NIST selected Rijndael to propose for the AES.

The GSM Encryption Algorithms A3 A5 and A8

I described both (A3/A8 are implement in the vast majority of networks as one algorithm COMP128) of the algorithms and their function in the GSM system. I took a detail look at their outputs. I looked at previous attacks on COMP128 specifically at Ian Goldberg and Marc Briceno attack, which takes advantage of a narrow pipe in the Algorithm.

For A5 I looked at the following attacks

_1. The Berkeley group published and analysed A5/2 in August 1999. They showed the work factor is only 2¹⁶ for a 64 bit key algorithm_.

2. Briceno found a “Flaw” in the A5/1 algorithm, reduces the complexity of exhaustive search from 2⁶⁴ to 2⁵⁴. 

3. Anderson and Roe proposed a divide-and-conquer attack that could have a time complexity from 2⁴⁰ to 2⁴⁵.

4. J. Golic has proposed another divide-and-conquer attack based on the same assumptions with the average complexity of 2^40.16.

5. Golic also proposed a Time-Memory Trade-Off Attack based on the Birthday Paradox in the same paper. He concludes that it is possible to find the A5/1 key in 2²² probes into random locations in a precomputed table with 2⁴² 128bit entries.

6. Biryukov, Shamir, Wagner detailed two attacks in a paper titled "Real Time Cryptanalysis of A5/1 on a PC" and several variants. They describe a Biased Birthday attack, which requires 2⁴² preprocessing steps and 292 GB of Hard drive space, yet with two minutes of data can extract the key in 2 second. A variant requires 2⁴⁸ Preprocessing steps and 146 GB of Disk space where the conversation need only be 2 second long and can generate the key in several minutes.

The Attacks I implemented

Computational Attack on COMP128

After reading extensively about the weakness of COMP128 I decided to attempt to break the Algorithm and compromise the Secret key Ki. I built a sim card reader and using a program called "Sim Scan" which was designed by Dejan Kajevic, I managed to deduce Ki in 13 hours. I also looked in to over the air cloning but the $10k price tag was just slightly out of my budget.

Brute Force attack on A5, known plaintext.

I developed a brute force attack on A5 using its frame structure as my plaintext. Initially the attack took 17H 56M but after refinements such as;

Generating one byte not a whole frame, Reducing the output from 228 to 164 bits, C- Optimisation and employing the most efficient compiler I managed to reduce the attack to 1 H 14m. The attack was still unrealistic but a hardware attack employing Xilinx chips using the same method would be very affective. As hardware attack are about 1000 times faster the software attacks.

Simulation of the GSM Environment

After implementing the attacks above I had all the information necessary to roughly simulate the GSM Environment. This has all the interaction of a really GSM environment but the interaction is through file rather the over the air. I used this environment in the demo of my FYP to show the weaknesses in the environment and where my attacks where launched.

Conclusion

In this paper I have shown many flaws in the GSM cryptographic algorithms. I was able to compromise COMP128 and showed numerous flaws in A5 including the fact that it is really only 2⁵⁴-bit encryption. I believe that these have come from the way that these algorithms where developed in secrecy. In time all were leaked or reverse engineered, versions of A3 A8 A5/1 and A5/2 are all freely available. These algorithms where developed in 1989 – 90 and are just over ten years old. In contrast DES was developed in total openness and released to the entire cryptographic community. It was designed in the mid 70’s and remained a government standard for over 20 years. When it was replaced it was replaced by triple DES simply because it’s key length was too short but everything else about the algorithm is still strong. The AES has been released in a similar fashion to DES, and is presently being investigated for weaknesses on many fronts.

Essentially the telecom companies need to understand that "security through obscurity" is not the way to develop cryptographic systems.

For more information see www.oocities.org/eoinward.