The ultimate attack against the A5/1 GSM protocol

This end of the year was marked by a major piece of news in the world of mobile telephony and beyond, believing the media coverage. Indeed, at the 26th edition of the “Chaos Computer Club” conference (26C3), which was held in Berlin from December 27th to 30th, 2009, a German cryptologist Karsten Nohl, publicly disclosed his research allowing the cracking of the famous A5/1 cipher algorithm which is used to protect GSM traffic against eavesdropping.

Tossed around for more than twenty years, the GSM protocol has undergone the ultimate attack of its so-called encryption algorithm A5/1 version. This version, used in more than 80% of the worldwide mobile market (nearly 3billion telephones), has just been broken.

Without moving into the controversy regarding the public disclosure of such a weakness, and without diving into technical and complex details, this controversial protocol aroused pirates for a long time.

 

A protocol tossed around for more than twenty years!

Created in the eighties, GSM networks democratized in the nineties. The deployments of the networks thrive year after year in various wavebands (GSM-850, GSM-1800, GSM-1900, etc) around the world. Today more than 200 countries use it. At the time of its beginnings, security was not on the agenda. It had only be considered in 1987, and cryptography was then considered as optional and, even more, declared in certain recommendation papers to be used by “paranoiacs”:

 “Enciphering is year option for the fairly paranoid, since the signal is already coded, interleaved, and transmitted in has TDMA manner…”

Persuaded of the protocol weaknesses, back in 1985, many experts already spoke about there exploitation.

As of 1994, the A5/1 algorithm is claimed by certain experts to be unreliable, but no papers were publicly disclosed.

In 1999, it is “retro-analyzed” by reverse-engineering techniques. Then, many studies, reports and various initiatives were published to uncover the last secrets of this algorithm.

In 2006, the data-processing department of the Institute of Technology of Haïfa in Israel already published a very complete study on the possible attacks of the encryption algorithms of the GSM protocol. Attacks against A5/1 algorithms (deployed in Europe), but also against its equivalent A5/2 (used in the US and described as weaker in terms of security because of export restrictions), were in particular extremely documented. Their successor, the A5/3 algorithm, based on a more advanced block ciphering (KASUMI), was already addressed in the study, although not deployed in the GSM networks.

In 2007 and 2008, other initiatives also try to uncover other aspects of the cipher algorithm. It is in particular the case of a group of hackers called “The Hacker's Choice”, whose non-revealed work has inspired Karsten Nohl.

 

Karsten Nohl’s Initiatives

This researcher is not at his first attempt in cryptographic “reverse-engineering”. In July 2008, he defies with his counterpart Jacobs Radboud, the giant of electronics “NXP Semiconductors” (formerly Philips), at the Dutch court of justice in order to disclose his work on the cracking of an algorithm used in “Mifare Classic” wireless radio chips. The court finally authorizes them to publish their research.

At the “Hacking At Random” conference last August in the Netherlands, the German cryptologist gave himself the challenge to break the GSM A5/1 algorithm in 6 months (see Cracking A5 GSM Encryption). He then created the “A5/1 Cracking Project” open-source project, based on distributed calculations in order to break the encryption algorithm of GSM communications. Beyond the pedagogical aspect (more or less questionable) aiming at (according to the author) “increasing public awareness” of telecom operators regarding the weaknesses of this protocol and at protecting consumers, Nohl succeeded in showing by the practice what security experts theoretically demonstrated twenty years earlier.

 

The vulnerability of the protocol

The A5/1 GSM algorithm uses an extremely weak encryption key (64 bits). The short length of this key makes it vulnerable to rudimentary attacks such as “brute force” ones (dictionaries, iterations, etc). However these attacks are expensive in terms of computation time and disk space. Nohl estimates that more than 100 000 years would be necessary for a single computer (without task parallelisation) to decrypt the key. In terms of disk space, he also estimates that the attack would require a storage capacity of about 128 peta-bytes (128 million Go)!

In order to increase the probability to break the key, Nohl used clever techniques such as distributed calculations, but he also managed to take advantage of computation powers at hand, that is to say, one can buy in any computer shops.

 

The attack of the A5/1 algorithm

The attack of the A5/1 algorithm led by Nohl is a passive attack, that is to say, a nonintrusive (no traffic injection). Based on the capture of communication flows, it thus does not spoil targeted GSM network, which makes it more furtive in a sense. The technique consists in using the calculation capacities of modern graphics cards. Their computing powers make it possible to carry out several million operations in a second. By distributing calculations through a grid of several machines (about forty nodes), it was possible to distribute the construction of the tables (known as rainbow tables).

 

Implemented techniques

The cryptologist indeed used three techniques:

• the construction of “rainbow” tables,
• distributed calculations,
• computing power of the graphics processors.

The “rainbow tables” technique is known and used in cryptanalysis in order to reduce the computing times. By using calculations known as “time-memory trade-off”, it allows using precompiled tables to limit the number of possible collisions when decrypting.

For the distribution of calculation tasks, Nohl developed tools making it possible to distribute the load between computers (nodes) connected to the network. Each computer had dedicated tasks of calculation. The results were then compressed and returned towards a centralized system, which could redistribute new tasks to the crack the key.

In order to reduce the very time consuming computing tasks, Nohl used the capabilities that GPU (Graphics Processing Unit) processors offer in modern graphics cards such as Nvidia or ATI, those supporting in particular the CUDA (Compute Unified Device Architecture) technology. This technology makes it possible to program these overpowered graphics cards, in order to dedicate them calculations generally assigned to the motherboard CPU.

Finally, it “only” needed one IMSI (International Mobile Subscriber Identity) capture system, made of open-source pieces of software (OpenBTS, Asterix, wireshark, airprobe, etc.) and of some hardware components bought electronic shops, and “only” forty computers for decrypting communications, and only four months to manage to break the A5/1 GSM key. Nohl initially planned to make it in 6 months.

 

Is this an innovation?

Nohl declares, that the cracking the A5/1 GSM algorithm is not an innovation. Many papers on the subject showed the theory. Moreover, as he points it out, various commercial products used by government organizations already exist. On the other hand, their implementation and their cost (several hundreds of thousands of Euros) are not good bargain, even more that the law regulates their use.

The innovation here mainly lies in the following points:

• the hardware requirement is not as expensive as that,
• the equipments used are simple PC,
• a collaborative effort can allow such an attempt.

 

Should we worry?

The GSMA  (GSM Association), gathering the actors of the GSM world, denounces obviously this irresponsible disclosure, and adds that the GSM protocol uses other complex mechanisms to self-protect. The task of deciphering under real conditions is more difficult than what the cryptologist shows. Recognizing however in its official statement of December 30, 2009, that the existence of many other initiatives of deciphering of GSM algorithms, the GSMA stresses that they always remained vain until now. Even if A5/1 algorithm was cracked, the exploitation of the weakness is made difficult by various factors inherent to the networks of GSM operators.

According to certain operators, the users should not fear anything. According to them, the weakness of the protocol does not lie in the robustness of the key but rather in the method used to change transmission channels. Moreover, other difficulties can rise, particularly in the when dealing with radio signal isolation. Nohl probably did not meet these difficulties in his lab, when testing is own GSM test network. The configuration of the necessary equipments would be thus far from being within reach for everyone. According to Nohl, it is underestimated the capacities of the Internet and of the open-source world, and that powerful configurations can be purchased at low cost.

Beyond these declarations, one should not underestimate the technical skill of Nohl’s project. Still in the GSMA official statement aiming at minimizing Nohl’s discovery, GSMA recalls that listening or capturing radio frequencies is prohibited in many countries. It would be however illusory to believe that it confers any protection to GSM users. Indeed, it is obvious that this disclosure will have the serious consequences and that media coverage will arouse the interest of malicious groups, which will hasten to grab this work.

To reassure the GSM world, the GSMA recalls that it kept on improving protection mechanisms of GSM communications. The implementation of A5/3 algorithm, which uses a 128-bit encryption key, is a response to the increasing need to protect private life. Underlining that many countries lessened exportation laws regarding cryptographic means, the GSMA proposes this version of the protocol, still very little implemented. It is worth mentioning that this new version is also subject to the same cracking contests as its sibling, the A5/1algorithm, it wants to replace.

 

Conclusion

To finish and beyond this academic case and the technical prowess realized here, it is obvious that the technological changes make it possible to reduce the limit of well-established known security facts. The evolutions in the microprocessors realm (graphics or others), and low cost powerful computers (the price of a PC has been divided by 5 in few years) allow such attempts.

Can the security and IT worlds be summarized as a never lasting competition? Protections get broken one day. It is thus necessary to renew ourselves. This cracking, predicted for years, has been made possible here by ingeniousness and by means that we did not imagine twenty years ago. Other barriers may fall quickly as well. Until when will the AES algorithm resist?