The end of 2009 and the first couple of weeks of 2010 has seen the world of cryptography, and more specifically data encryption, thrust into the media spotlight.
News of "Secret codes being hacked" that "Rocked the mobile phone establishment" get splashed across the tabloids as mobile phone users are told their signals can now be hacked.
And more recently, but with less mainstream fanfare (well, in fact, none to be honest...) a group of academics have managed to factorise a 768-bit RSA public key resulting in some of the more technical media questioning the future of RSA.
So what is the importance of these announcements and are they something your boss needs to worry about?
This short article will explore the recent mobile phone encryption attack, and a follow up article, when I get a chance, will explore the issues behind the RSA key factoring.
Mobile Phone Encryption
Mobile phones are, of course, everywhere. GSM, Global System for Mobile communications (or Groupe Spécial Mobile as it was originally) is the leading mobile phone technical standard with over 80 percent of the market and in excess of 4 billion users across 200 countries. The chances are that if you travel with a GSM mobile phone then you will be able to make calls in most places you travel.
Eavesdropping telephone conversations has been of interest to a variety of people from nosey neighbours through to security services across the world. Early analogue mobile phones were basically simple radio systems that had no inbuilt security features and were subsequently open for anyone to listen into with simple radio equipment. As technology advanced, users quite rightly demanded better security and, in 1987, a stream cipher called A5/1 was developed for that purpose. A5/2 was developed in 1989 as a weakened version of the cipher for export to less trusted regions of the world.
The algorithm behind A5/1 was originally kept secret, an approach that modern cryptographers quite rightly deride as foolishness. It is only by opening up algorithms to analysis and in-depth review that the security community can gain confidence in the robustness of these tools. Security by obscurity, in the case of cryptographic algorithms, is a flawed approach. Suffice to say that by 1994 the algorithm had been more or less worked out and by 1999 it had been successfully reverse engineered. Academic hacks against A5/1 have in the past relied upon knowing some plain text—albeit a couple of seconds of a conversation—to get to the encryption key. In reality this won't happen as conversations would be encrypted from the start, so unless there was a flaw in the system that provided such a snapshot, this academic hack is dead in the water. Other hacks have relied on some pretty significant computing power, costing around $100,000, but even with such horsepower the system could only decrypt around 1 SMS text message a day, hardly productive unless you had something particular you wanted to get from a user.
This new hack is based on open source principles. In theory an off the shelf radio system such as USRP2 (Universal Software Radio Peripheral—a software defined radio system) could be linked with some signal processing software such as OpenBTS. This would enable a 25Mhz spectrum to be captured, which is enough for one operator.
A5/1 itself is vulnerable to generic pre-computation attacks in the form of a code book attack. For ciphers with small keys, code books allow decryption to take place—facilitated by the fact that a code book provides a mapping from a known plaintext output to a cipher text. If anyone is that interested I'd be happy to discuss these further in another article.
An A5/1 code book is 128 Petabytes and will take about 100,000 years to compute on a desktop PC. In a nutshell what these researchers have done is find a more efficient way of computing and storing an A5/1 codebook using a high speed A5/1 engine designed solely to crack away at that algorithm. The engine ran for 3 months across 40 CUDA nodes, which are essentially the computing engines on NVIDIA graphics processing units.
The output from this work was then consolidated into lookup tables, having used rainbow tables to mitigate collisions. Not all the lookup tables have been created, and the research team are requesting other developers to take part and help with table sorting and storage. The idea is that tables will be stored across multiple jurisdictions in an open source manner, with ownership shared across a community removing an obvious chain of ownership and hence individuals that could be targeted by the authorities.
So what of the most recent attack?
The good news is that we don't need to panic about GSM encryption. A5/1 is an old encryption algorithm that is in the process of being slowly phased out in favour of A5/3, which uses the Kasumi block cipher. Although this is academically broken and the same keys are used for A5/1 and A5/3, it is secure enough for everyday use.
GSM encryption is only used over the air. As soon as your conversation hits a local cellular base station the signal is decrypted into plain text and shunted across the standard telephone system. Security services throughout the world have been able to tap into mobile phone calls by simply waiting for the data to reach this point and then target it as they would any landline, obviating the need for tools to intercept the encrypted radio traffic. That said, some security services allegedly have access to equipment for such decryption.
Often there is no need to go to this extent. If you are interested in capturing mobile phone traffic then installing a fake cellular base station will do the trick as mobile phones will always go for the strongest signal. Set one of these up and you can capture all the local mobile phone signals.
So, panic over, more or less.
And as an afterthought probably the best way to "intercept" a mobile phone conversation is to simply sit next to your target as they take the train to work. So many people are oblivious to the secrets they divulge during their irritatingly loud mobile phone conversations a MK I human ear can probably do as good a job as any complex code breaking...
