GSM Cracking: Coming Soon to a Computer Near You via a Web Service

A web service that will make it easy and inexpensive to crack the GSM A5/1 encryption protocol, quickly enough for a call that is still in progress, is slated to launch at the end of April. Living right at the intersection of open hardware, open source software, software as a service, and cryptography, the service will reduce the cost and effort of cracking GSM call encryption by at least an order of magnitude.

The service is being developed by members of the GSM Software Project and demonstrates just how much things have changed in the world since the GSM system was designed. Various approaches to cracking both A5/1 (the European standard) and A5/2 (the weaker US standard) have been available for some time but this one is unique in that it should be available to researchers and hackers at the end of April in hosted api form instead of pdf.

Back in 1997 this overview of the GSM system declared that "Enciphering is an option for the fairly paranoid, since the signal is already coded, interleaved, and transmitted in a TDMA manner, thus providing protection from all but the most persistent and dedicated eavesdroppers." After all, such a radio encoding scheme made the signals invisible to typical radio band scanners.

Today, however, the availability of the Universal Software Radio Peripheral (USRP), an open hardware software defined radio that sells for about $700, combined with work being done at GNU Radio project to codify the GSM waveform (also targeted for the end of this month), makes this once reasonable point of view seem quaint. Good encryption is now a must and it appears that A5 no longer qualifies.

With USRP and GNU Radio making the waveform and encrypted frames cheaply accessible and the A5 Hacking Project's service easily breaking A5/1, anyone will be able to make a cheap GSM scanner. Today neither the complexity of the waveform or the encryption in use is adequate to keep a GSM call private.

I first became aware of the effort to create a service for breaking A5/1 encrypted GSM frames at Blackhat DC in February. David Hulton and Steve (no last name given) described an approach to cracking the A5/1 protocol that requires the one time development of a large (~ 2.2 TB) rainbow table that is then later used to quickly decrypt a GSM call. At the time they were in the process of building a machine with a bunch of disk and 68 Field Programmable Gate Arrays (FPGA) to parallelize the table build. Using FPGA's short circuits Moore's law without resorting to the use of specially forged Application Specific Integrated Circuits (ASIC) and reduces the time to build the table from about 33,000 years with a single PC to only three months with the specialized hardware.

Curious about their progress, I followed up with Steve and David this week. After a brief hardware hiccup that added a few weeks, they report they now have over 70% of the table calculated and already have greater than 80% coverage for the A5/1 cipher. When the table is completed towards the end of this month A5/1 coverage should be about 97%.

At that point, using the same 68 FPGA machine, they plan to host a service on the Internet that will let you break GSM A5/1 encryption and then, using your own equipment, begin replaying most voice calls in about 30 seconds. All you will need is a PC and a USRP to capture the encrypted GSM frames (from your own phone, it is illegal to intercept someone else's communication) and the software to play back recorded or streaming decrypted frames. If you wish to experiment without the expense of a USRP, sample encrypted GSM frames will be available.

Because they are deploying this as a web service, you won't need to obtain and host the large rainbow table yourself or buy a bunch of FPGA's to build your speedy GSM scanner. However, if you do want to decrypt GSM frames locally you'll have to get a copy of the table. Because of its size it isn't clear how it will be distributed (which was at least one motivation for offering a web service). You'll also have to build a PC with one or more FPGA's and a lot of disk space. The time to complete the calculations on your local setup will scale roughly linearly with the number of FPGA's you have (e.g. ~ 45 minutes if you have just one).

I think it is interesting to consider what this means to systems like GSM that are expected to be around for a long time. Is it possible to adequately decouple the encryption from the rest of the architecture so that it can evolve more rapidly than the rest of the system?

The practical reality is that encryption in systems like GSM always lives at some uneasy equilibrium between citizen's privacy expectations and government's desire to be able to wiretap. In a sense the question is "what is the target cost for decryption?" Or put another way, who should be able to afford to wiretap? The cost should be high enough to provide reasonable security, but governments generally don't want it to be absolute. The design of GSM was certainly an example of these forces at work.

The problem is that the moment GSM was deployed, forces like Moore's law and the availability of open hardware conspired to start shifting that cost point. Since the encryption isn't shifting with it, what once looked as expensive to defeat as a bank vault is now looking quite a bit flimsier.