GSM Security is getting more important. There are many
successful attacks on GSM communication reported recently. And the list keeps growing. Today is extremely easy to get access to a technology which allows you to record GSM session and possible decrypt it.In this article I will mention some of the early attempts to decypher the GSM communication. However, there are projects explaining in more details about the GSM attack itself (like
https://srlabs.de/decrypting_gsm/) and providing more information.
Many GSM users rely on the GSM cryptographic system to transfer information securely. Since the late 80's, when GSM network become popular, its cryptographic system is a subject of many attacks. The first attacks on A5 algorithm are purely theoretical but recently there are reports for some successful practical attacks too. The rainbow table attack is one of the most successful attacks on A5 algorithm. Using this approach breaking the cipher is possible within a minute if few packets of cipher text are available. The rainbow tables size is few terabytes, but that is not a problem those days. Furthermore, this method allows using different size of the rainbow tables, which lead to different calculation time breaking the cipher.The new 3G mobile network uses more advanced KASUMI cipher. Even the KASUMI is better than the old A5 cipher, its implementation makes it weaker than MISTY1. There are also a few attacks on KASUMI which are not applicable on the original MISTY1 cypher.
There are many attacks and cryptanalysis of the A3/A8, COMP128 and A5 algorithms.
A5/1 is developed in 1987, and A5/2 - in 1989. Both protocols are kept secret. However the algorithms ware entirely reverse engineered in 1999 by Marc Briceno from GSM telephone and A5/2 was broken at the same time.
A5/1 was broken on academic level in 1997, but the firs attack on the real cipher is in 2000 by Alex Biryukov, Adi Shamir and David Wagner.
In 2003, Barkan et al. published several attacks on GSM encryption. The first is an active attack. GSM phones can be convinced to use the much weaker A5/2 cipher briefly. A5/2 can be broken easily, and the phone uses the same key as for the stronger A5/1 algorithm. A second attack on A5/1 is outlined, a ciphertext-only time-memory tradeoff attack which requires a large amount of pre computation.
In 2006, Elad Barkan, Eli Biham, Nathan Keller published the full version of their 2003 paper, with attacks against A5/X Ciphers. A precomputed table is used to attack A5/2 and the key can be found in less than a second on a personal computer using one packet of encrypted information.
In 2007 Universities of Bochum and Kiel started a research project to create a massively parallel FPGA based crypto accelerator COPACOBANA. COPACOBANA was the first commercially available solution using fast time-memory trade-off techniques that could be used to attack the popular A5/1 and A5/2 algorithms, used in GSM voice encryption, as well as the Data Encryption Standard (DES). It also enables brute force attacks against GSM eliminating the need of large precomputed look-up tables.
In 2008, the group The Hackers Choice launched a project to develop a practical attack on A5/1. The attack requires the construction of a large look-up table of approximately 3 terabytes. Together with the scanning capabilities developed as part of the sister project, the group expected to be able to record any GSM call or SMS encrypted with A5/1, and within about 3–5 minutes derive the encryption key and hence listen to the call and read the SMS in clear. But the tables weren't released.
A similar effort, the A5/1 Cracking Project, was announced at the 2009 Black Hat security conference by cryptographers Karsten Nohl and Sascha Krißler. It created the look-up tables using Nvidia GPGPUs via a peer-to-peer distributed computing architecture. Starting in the middle of September 2009, the project ran the equivalent of 12 Nvidia GeForce GTX 260. According to the authors, the approach can be used on any cipher with key size up to 64-bits.
In December 2009, the A5/1 Cracking Project attack tables for A5/1 were announced by Chris Paget and Karsten Nohl[8]. The tables use a combination of compression techniques, including rainbow tables and distinguished point chains. These tables constituted only parts of the 2TB completed table, and had been computed during three months using 40 distributed CUDA nodes, and then published over BitTorrent. More recently the project has announced a switch to faster ATI Evergreen (GPU family) code, together with a change in the format of the tables and Frank A. Stevenson announced breaks of A5/1 using the ATI generated tables.
There are some theoretical attacks on KASUMI. In 2001, an impossible differential attack on six rounds of KASUMI was presented by Kühn (2001).
In 2005, Israeli researchers Eli Biham, Orr Dunkelman and Nathan Keller published a related-key rectangle (boomerang) attack on KASUMI that can break all 8 rounds faster than exhaustive search. The attack requires 254.6 chosen plain texts, each of which has been encrypted under one of four related keys, and has a time complexity equivalent to 276.1 KASUMI encryptions. While this is not a practical attack, it invalidates some proofs about the security of the 3GPP protocols that had relied on the presumed strength of KASUMI.
In 2010, Dunkleman, Keller and Shamir published a new attack that allows to recover a full A5/3 key by related-key attack. The time and space complexities of the attack are low enough that the authors carried out the attack in two hours on a modest desktop computer even using the unoptimised reference KASUMI implementation. The authors note that this attack may not be applicable to the way A5/3 is used in 3G systems; their main purpose was to discredit 3GPP's assurances that their changes to MISTY wouldn't significantly impact the security of the algorithm.
Some time ago I created an article about GSM communication protocol and the attempts to be compromised.
Subscribe to the security newsletter and get the file.
