The Last Days of A5/1

I have been following the long-predicted public demise of A5/1 for a few years now, first in The Long Tail of Vulnerability for A5/1, and more recently in Another crack at open Rainbow Tables for A5/1, where the task of producing public rainbow tables for A5/1 was taken up in a project led by Karsten Nohl last August. Nohl and his team are leveraging previous work done by The Hacker’s Choice (THC) and using the parallel computing architecture of CUDA graphics chips to rapidly compute the rainbow tables. They were asking for people to donate computing power and hoping for some results by last Christmas.

Nohl and colleague Chris Paget gave a project update at the 26th Chaos Communication Congress (CCC), held in Berlin last December, and indeed they completed the computations by year end. The project recovered from a major bug announced last October, which indicated a fundamental coding error in the linear feedback shift register (LFSR) components of A5/1 (it has three). In any case, it seems that the error was corrected, and the required table computations were completed in 3 months using 40 CUDA nodes – considerably less than the 80-node initial estimate, and the 100,000 year effort required on a single-threaded PC. You can read more about the parameters of the rainbow tables on this project page, with some additional background on time-memory trade-off (TMTO) collected here. The tables can be downloaded from a collection of torrents.

On the project page the official status is given as “A full GSM interceptor to collect GSM data could hypothetically be built from open source components. We have not done so as it may be illegal in some countries”. So it seems that the project may have hit legal complications, in the same manner as previous efforts. The last part of the CCC update describes how to intercept GSM traffic from open source components to be used as input to the table look-up process, but a few important issues remain to be resolved before GSM traffic interception can be automated. And as reported in the Tech Herald, the GSM Alliance believes that the channel hopping features of GSM will make the remaining stage difficult to complete, if not a practical impossibility – and illegal in Britain and the US to boot. Nonetheless, updates indicate that the project is continuing, and A5/1 must surely be entering the last days of its more than 20 year operational life.

MasterCard bets on A5/1

MasterCard recently announced (see here and here for example) that it will introduce out-of-band GSM authentication into its Chip Authentication Program. Consumers will be able to authenticate banking and other online transactions using their mobile phones, either by entering a password sent to the phone by SMS or generating the password directly on their smart phone via a java application.

MSN Money states that

This new development leverages the ubiquitous nature of mobile phones. According to latest research from Forrester, the number of individual mobile users in Europe will increase to 344 million users by the end of 2014, representing 84% of the Western European population. Coupled with growing online banking fraud activity (the UK Card Association reports that online banking fraud has jumped 132% in 2008 to stand at a record £52.5m.) the possibility to harness the mobile phone for authentication purposes is considerable.

This strategic decision makes the A5/1 rainbow table generation project, led by Karsten Knol, all the more timely. The project was announced at the Hacking At Random conference in August,and described in the paper Subverting the security base of GSM. Knol has stated that one of the reasons for the project to highlight the weaknesses of A5/1 encryption is the increased usage of GSM as an additional out-of-band authentication mechanism for online protocols, and the MasterCard announcement may well prove his point. The stronger A5/3 algorithm is being phased in during upgrades to 3G networks, providing secure 128-bit encryption, and this key size is effectively beyond the reach of rainbow attacks.

However Knol’s project appears to have hit a snag about 3 weeks ago. On October 29th it was announced that a critical bug was found

All versions prior to the one released on 25 of October 2009 use a buggy LFSR to generate round function values. Instead of producing 2^{64}-1 distinct values there are in fact only 32. This means that tables that ought to not produce chain merges in the event of a collision because of different round functions do produce merges.

The message is a bit cryptic but it points to a fundamental coding error in the linear feedback shift register (LFSR) components of A5/1 (it has three).  Its appears that the period (the number of clock cycles before the sequence produced by the LFSRs repeats) is only 32 as opposed to the much much larger 2^{64}-1. This bug reminds me of the problem with Debian’s random number generator for OpenSSL, where a programming error was causing keys to be generated from at most 15-bits of entropy.

The A5/1 bug has been fixed and let’s hope it does not delay the project too much. Meanwhile, keep your phone handy for future MasterCard transactions.

Another crack at open Rainbow Tables for A5/1

About a year ago I posted on The Long Tail of Vulnerability for A5/1, the stream cipher for GSM data encryption, after earlier in the year David Hulton, director of applications for the high-performance computing company Pico, and Steve Muller, a researcher for mobile security firm CellCrypt, announced new results which claimed that A5/1 keys can be recovered in 30 minutes for $1000. I concluded that

A5/1 has operated unchanged for the last 21 years but it has now reached its cryptographic end-of-life, engulfed by the march of Moore's Law. However, the operational end-of-life of A5/1 may still be decades away as there are approximately 2 billion GSM subscribers, commanding about 80% of the global mobile market. This would be a tough product recall indeed. A5/1 is well-positioned to become the NT of the mobile crypto world, and I see the makings of a long tail of GSM vulnerability.

The Hulton & Muller attack was based on pre-computing rainbow tables that enable the direct "lookup" of A5/1 keys when indexed by a small amount of observed traffic (3 to 4 GSM frames). However these tables have not been materialized, apparently due to potential legal issues.

But a new project announced in August could deliver these tables in 6 months - or by Christmas if we are lucky. Karsten Knol, best known for his work on reverse engineering the Mifare chip, announced, at the Hacking At Random conference in August, a new project to produce A5/1 rainbow tables that would be open and available to the public. Knol described the project details in his conference paper with the somewhat sinister title of Subverting the security base of GSM. In subsequent interviews Knol has gone to some lengths to emphasize that his intentions are not to destabilize GSM, but rather to highlight through public demonstration the weaknesses GSM encryption, and hopefully initiate a migration towards a more secure solution for mobile telephony.

What are these Rainbow Tables?

Several recent articles paint quite a bleak picture for GSM, such as this one from the Tech Herald, which says of Knol’s project, “if successful, will allow anyone with some RF equipment, patience, and a $500 USD laptop, the ability to decode GSM-based conversations and data transmissions”. We need a little technical background to decode this statement.

Imagine that an attacker is given (or intercepts) a plaintext-ciphertext pair P, C encrypted under an unknown key. In a brute force attack the attacker arranges all possible keys in some order, and then starts searching the keys until the right one is found – that is, the key K that encrypts P to C. In this case the attacker is facing a needle-in-a-haystack search problem since there is only one point in the key space (the target key K) that provides information on when the search can stop.

The idea of rainbow tables is to pre-compute a compressed form of the key space that contains a collection of “checkpoint” keys. When searching the compressed key space, hitting a checkpoint identifies a relatively small collection of keys (say several billion) that is known to contain the target key. So key search with rainbow tables has two steps; first, start the search to find a checkpoint, and then second, search the keys defined by the checkpoint to find the target key.

The advantage over brute force search is that many checkpoints can be created, and the search process will therefore hit one of these checkpoints much faster than waiting to stumble across the lone target key. Of course the disadvantage is that the checkpoints points must be pre-computed and stored. So there is a time-memory trade-off (TMTO) to be considered – the search time is reduced with more checkpoints but at a cost of more pre-computation and storage.

On the Shoulders of Giants

We have glossed over many important ideas in an effort to give the gist of how rainbow tables offer improvements over brute force search. In practice generating the required set of a tables to allow key recovery with high probability is quite tricky. Conveniently for Nohl and his team, the appropriate parameters for generating an effective set of tables was done previously by The Hacker’s Choice (THC), including the special optimisations that give rise to the name rainbow tables.

The THC project failed to produce a set of public A5/1 tables (apparently for legal reasons), and Knol’s project is to use the THC base to re-compute the tables in an open and distributed fashion. One innovation is to compute the tables using CUDA chips, which is a parallel computing architecture developed by the graphics co-processor company NVIDIA. Knol estimates that computing the tables on a single-threading Intel-like processor would require 100,000 years but only a matter months on 80 CUDA nodes. So Knol’s project (homepage here) is to find volunteers who will download optimized A5/1 code for the construction of the tables. It is estimated that the total computational effort to produce the tables is 2^{57}.

Tables in the Cloud

Knol emphasizes that the tables are computed through a volunteer distributed computation and then made available to all and sundry through BitTorrent for example. The point is not to centrally reconstitute the tables – in fact he wants to avoid that. He does not want to have a central point or legal entity where the project can be potentially shut down, and this also helps to provide anonymity for the volunteers if they seek it. In any case, this sounds a little bit like the defence that Pirate Bay unsuccessfully used in their recent prosecution – we don’t distribute illegal music, only the index for where you can find it.

Impact and Responses

Public rainbow tables for A5/1 will provide a definite and public demonstration of the shortcomings of GSM encryption - currently relied on by 3 billion subscribers in over 200 countries, representing about 80% of the mobile telephony market. While it has been known for sometime that A5/1 is weak, there is nothing like an actual demonstration to drive the point home, as was the case in the breaking of 56-bit DES or more recently with the Cold Boot attack.

Potentially all GSM communication, including voice and SMS, as well as newer security services that rely on GSM as an out-of-band mechanism for authentication and authorization, will be under threat. Knol’s advice, and the main reason for undertaking the project, is to raise awareness on the need to upgrade to more secure encryption. The stronger A5/3 algorithm is being phased in during upgrades to 3G networks, providing 128-bit encryption. However A5/3 may only be used to encrypt data traffic, and voice traffic will remain with A5/1 until a full upgrade is made.

The GSM Association (GSMA) has politely scoffed at the project, claiming that the practical complexities of carrying out actual attacks, in particular intercepting the required GSM traffic, are being underestimated. However I think the project team will rise to the challenge.

Knol hopes to have proof-of-concept tables by the end of 2009, and you can see some graphs on the main project page showing current computational results. In risk terms the project promises to show that what is perceived as a high-impact/low-probability event is actually medium- to high-probability. We should have more news by Christmas.

You can find additional information on this topic from the FreeMind map I created for this post, rendered into Flash here.