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.