Jaap-Henk Hoepman – on security, privacy and…

Today the New York Times reported that Karsten Nohl had finally broken the A5/1 encryption algorithm used to protect GSM voice (and data) communication. He presented the details of his attack at the Chaos Communication Congress (which he pre-announced at Hacking At Random earlier this year).

Is this any news?

It is already well known that A5/1 contains serious weaknesses. Back in 1997 the first attacks appeared in the academic literature. These attacks were impractical, because they needed to much known plaintext. Later on, hardware based attacks were described that required less known plaintext but instead relied on expensive hardware to compute large lookup tables.

The full lookup table would be 128 petabyte (= 1.000 terabytes = 1.000.0000 gigabyte) large. That would be impractically large, so instead a smaller rainbow table is computed and stored. The total size of that table is 2 terabyte, which results in a 50% chance of recovering the key if you have 64 bits of ciphertext for which you know the corresponding plaintext. GSM actually produces a lot of such known plainttext/ciphertext pairs when a call is set up, so this is feasible.

Karsten Nohl’s basically uses the same approach (it is in fact a reimplementation of the THC work, which was done in early 2008 but never released), but uses graphics cards to perform the computations. In fact he is distributing the effort over nodes all over the internet, and collecting the results through BitTorrent. This process is still continuing actually, and the current status can be checked here. Currently (December 29, 16:38) there are 23 sorted torrents containing 100 gigabyte of data, i.e. 5% of the total.

So back to the question: is this any news. So far, not all table data is computed yet. But it will, in due time. To use that data, however, you also need the equipment to intercept an actual call. This is in principle possible, using software defined radio equipment, and an open-source implementation of the GSM protocols. However, the equipment comes at a cost (the USRP2 sells at $1400), and the software is incomplete. Especially following a call while the signals hop from one channel to the other appears to be difficult.

So for the average attacker, this is still quite costly and (still) to difficult. For a determined attacker (criminals, or government agencies) the attack will become cheaper, but the previous attacks already were within their budget and powers anyway. And let’s not forget: A5/1 only encrypts the signal between the handset and the base station. Beyond that, the protection depends on the network security of the particular telecom carrier… For determined attackers, the connection beyond the base station (or, better yet, set up a fake base station) may still be the easiest attack vector. Simply because to eavesdrop a call, you have to be in the vicinity of the victim.

In other words: for ordinary conversation, A5/1 provides adequate protection. For sensitive conversations, A5/1 should have been abandoned years ago. For
electronic banking systems that use SMS as a separate channel to exchange one time transaction authorisation codes, the fact that you need to be in the vicinity of the victim makes the attack impractical as well.