Time to throw away our GSM phones?

The mobile phone industry is in full PR battle mode this week with the news that a computer scientist has successfully cracked the A5/1 encryption code that secures GSM mobile phone calls. In theory this means that anyone having access to appropriate snooping hardware and software, estimated by the researcher to cost under $30,000, can listen in on GSM phone calls by intercepting and decoding radio signals.

Last week at the Chaos Communication Congress in Berlin, Dr. Karsten Nohl announced that his team, a group of hackers working collaboratively to create a distributed computing cluster, had cracked the encryption code by creating an enormous, 2-terabyte “rainbow table” of hash values. In simplistic terms, the rainbow table provides a cracking program with a reverse-lookup scheme that can quickly decrypt the wireless voice data.

I’ll leave aside any prediction of who might want to use this kind of cracking technology, and where they might want to do it. In the United States GSM is used for only a fraction of communications, most notably by AT&T and T-Mobile.

GSM dominates worldwide, however, carrying the overwhelming majority of phone calls. (And if you are an iPhone user like I am, you should know that AT&T most probably sends your voice via the 2G GSM standard using A5/1 encryption, even though you are paying for presumably more secure 3G service. And if you think your iPhone data is secure… read this.)

From a computing perspective, what’s interesting about this project is that it required two types of computational acceleration. The first computing problem was the creation of the rainbow tables. This only needed to be done one time, but represented a massive computing problem. Nohl estimated that to generate these tables using a single traditional PC or server would have required many years to complete. To make this problem practical, Nohl and his collaborators set up a distributed computing system similar to the SETI@Home project in which the spare computing cycles from many different computers on the Internet were harnessed to calculate the needed tables. In some of the computers GPUs were also used to accelerate the problem, which was completed in three months of calendar time.

The second computing problem occurs at the point of decryption, in whatever server or laptop PC is being used to snoop and crack the wireless signal. That problem is also computationally intensive, but with ready access to the 2-Terabyte rainbow tables the crack can be performed in minutes, or seconds if GPU and/or FPGA accelerators are added into the mix.

During his talk, Nohl stated that a person (or agency?) wanting to eavesdrop on GSM calls would currently need to spend around $100,000 on hardware in order to crack an A5/1 encrypted call in one second or less. And the hardware to use? A cluster of 64 or more FPGAs. For less money and slower cracking times (still under a minute, and under $30,000) a smaller number of FPGAs or GPUs would do the job just fine.

Slides from Nohl’s talk are here.


1 Comment

Filed under Uncategorized

One response to “Time to throw away our GSM phones?

  1. Karsten Nohl is the same researcher who discovered the Mifare Classic RFID vulnerability by etching away the card and determining the cipher’s random number generator was broken so the ciphercould be broken using the same “rainbow table” method. I seem to remember them using 64 Virtex-2 chips to steal your RFID data under a minute.

    Some of my friends at MIT implemented the same RFID hack on the Boston T “Charlie Cards” by converting the cipher crack to a SAT problem and using FPGAs to brute force it. This resulted in a cease-and-desist order blocking their presentation at Defcon.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s