GSM encryption crack made public

The schemes commonly used to encrypt GSM telephone calls, SMS messages, and data transmissions have been theoretically broken for years at both the protocol and cipher levels, but results presented in Berlin at the 26th Chaos Communication Congress (26C3) on December 27 demonstrate that a practical attack can be easily implemented. Researchers unveiled cracking tables requiring just two terabytes of disk space that can be used to look up a GSM encryption key and decrypt a transmission. The tables were computed on 40 commodity hardware PC nodes in just a few months' time, and are shared through Bittorrent. Furthermore, the presentation explains that the more difficult practical task of intercepting and capturing GSM calls can already be done with inexpensive radio equipment and open source software.

Background

The cipher under attack is known as A5/1; it was invented by the GSM Association in 1987. Due to the Cold War, A5/1 was deployed only in Western Europe and the United States, and was accompanied by a significantly weaker cipher called A5/2 for export to other regions. The GSM protocol supported both A5/1 and A5/2, plus A5/0, or unencrypted connections, a choice that left the protocol itself vulnerable to attack.

A5/1 was not published, but researchers began to reverse-engineer it almost immediately, work that was completed and publicized in 1999. Theoretical attacks based on weaknesses in the cipher date back to at least 1997, but real-world attacks on the system as implemented in the global GSM network only began to appear in 2003, when the team of Elad Barkan, Eli Biham, and Nathan Keller reported that phones use the same set of keys regardless of whether A5/1 or A5/2 encryption was enabled. [PULL QUOTE: Thus, by momentarily tricking a phone into using A5/2 (which can be cracked in seconds), a man-in-the-middle attacker can retrieve the session key for a call and continue to decrypt it even if it subsequently switches to A5/1 at the network's request. END QUOTE] Thus, by momentarily tricking a phone into using A5/2 (which can be cracked in seconds), a man-in-the-middle attacker can retrieve the session key for a call and continue to decrypt it even if it subsequently switches to A5/1 at the network's request. Shortly thereafter, networks were advised to discontinue use of A5/2.

Barkan, Biham, and Keller also published a ciphertext-only attack on A5/1 itself that relied on a time-memory tradeoff: building a lookup table of partially-precomputed hash values. A5/1 uses a 64-bit key (although, interestingly enough, 10 bits are fixed at 0 in all known deployments, making the practical strength 54-bits), which would require around 128 petabytes for a complete code book (a complete plaintext:ciphertext table for each key).

In 2008, a group called The Hackers Choice (THC) announced that it had computed the complete code book, in a more space-efficient format that required just three terabytes, running on a cluster of 70 field-programmable gate array (FPGA) boards. THC did not publish its tables, however.

A5/1 Security Project, technique and results

At the Hacking at Random conference in July of 2009, researchers Karsten Nohl and Sascha Krißler announced yet another effort to compute the code book, dubbed the A5/1 Security Project, utilizing distributed computing with publicly available source code. The A5/1 Security Project code was designed to run on NVIDIA and ATI graphics cards using the CUDA parallelization architecture; a participating node would claim a unique chunk of the code book from the project, then report its results back to the centralized server.

Nohl and Chris Paget announced in their 26C3 presentation that the project had completed computation of the tables, and that the complete result was available on Bittorrent. Around 40 nodes participated in the effort over three months; some false starts caused by bugs in the code slowed down the computation initially, but the results as presented at 26C3 are final. The format chosen by the project uses a combination of rainbow tables and distinguished point tables as a space-saving measure.

Rather than storing the entire code book as a plaintext:ciphertext lookup table, rainbow tables compute chains of encrypted values, and store only the first and last values in the chain. Decrypting a given value then involves generating a chain from the value, and looking at each step for a match in the rainbow table. Thus, using longer chains in the rainbow table requires less storage space, but demands more time in the decryption step by requiring more computation steps looking for a match. But once a match has been found, the key can then be determined allowing further decryption using the algorithm directly.

Distinguished point tables save space by selectively storing only those chains in the table that have an endpoint matching some helpful property — such as a long string of zero-bits. Chains that don't have that property are not stored saving a great deal of space, but turn the key extraction into a probabilistic search. Given enough ciphertext, though, key extraction should be possible.

The team eventually settled on a combined table approach that used 380 tables, each of which consists of 32 distinguished-point segments of length 2^15 merged into one rainbow table. In addition, they discovered ways to locate known plaintext in a GSM transmission (such as predictable ACK packets) that would save time and space by requiring a smaller subset of the code book to be computed. If those details do not communicate much to non-cryptographers, the practical results should: the final tables take up just 2 terabytes of storage space, and can be used to perform near-real-time decryption.

Reaction and better security

Nohl and Paget are quick to point out that the completion of the A5/1 tables itself does not constitute a measure for intercepting and listening in on GSM telephone calls. Shortly after news of the work went public, the GSM Association issued a press release playing down the result, based in large part on what it called the "practical complexity" of capturing and recording a GSM call.

Nohl and Paget dealt with that assertion in their talk, describing the components that would be required to receive, process, and record GSM calls, all of which are easy to obtain. At the hardware level, the Universal Software Radio Peripheral (USRP) developed for the GNU Radio project can tune and capture GSM spectrum. The OpenBTS software stack implements GSM and is designed for use with USRP, allowing the user to process and decode the data in a GSM channel, as well as to perform other feats in active attacks, such as faking a legitimate GSM base station. Other software packages, such as OpenBSC and Airprobe, can also be used for specific GSM-related tasks.

The GSM Association press release also implies that any real-world risk inherent in a broken A5/1 is moot because the stronger A5/3 is also available, and is not subject to the same algorithmic attacks. Nohl and Paget point out, however, that theoretical attacks on A5/3 have already been published, and that, despite its availability for over a decade, no carriers use it.

Moreover, the GSM protocol itself is still highly insecure; in fact the same technique Barkan, Biham, and Keller used in 2003 to trick a phone into downgrading from A5/1 to A5/2 can also be used to attack A5/3 — since A5/3 uses the same encryption keys as A5/1 and A5/2. In addition, lack of network authentication and the fact that GSM phones automatically attach to the strongest available base station make interception and man-in-the-middle attacks possible, that are independent of the encryption method deployed.

Securing mobile phone communications is vital in today's world. As Nohl and Paget's presentation noted, GSM is not only used for voice calls, but for SMS (which increasingly includes financial transactions) and EDGE data connections as well. Consumers have no control over the GSM network, and although most have little to worry about in the realm of criminal attackers intercepting their voice calls, business and government users do. 40 off-the-shelf graphics cards computed the A5/1 code book in less than three months; the estimated hardware needed to built a USRP-based GSM interceptor is less than US$3000. That is a trivial investment to anyone with a financial interest in eavesdropping. On top of that, as the weakness of WEP encryption demonstrated to WiFi router owners, a broken security system leaves the network open to mischief, bandwidth-theft, and other security problems beyond call interception. Hopefully, as the A5/1 Security Project suggests, the telecommunications sector will now take positive steps to correct the flaws in GSM and implement better security.

For the open source software community, however, there is another benefit to the project's success: the basic idea is reusable. The team built the distributed pre-computation framework to be generic; it can work on any cipher, with different table layouts, and on multiple hardware back-ends. In other words, if you have a cipher that needs a code book and you have access to 40 modern graphics cards, your job may have just gotten a lot easier.