New project uses distributed computing to break GSM cryptoby Steve Ragan - Aug 29 2009, 02:12
The Tech Herald talks with Karsten Nohl about Creating A5/1 Rainbow Tables.
Do you use a GSM phone? If so, then a new project recently launched by Karsten Nohl might interest you. That or it will completely freak you out. We spoke to Karsten to learn more about his project, which if successful, will allow anyone with some RF equipment, patience, and a $500 USD laptop, the ability to decode GSM-based conversations and data transmissions.
Nohl’s project targets the A5/1 vulnerability in GSM (Global System for Mobile communications). The A5/1 algorithm is one of the ciphers used on GSM networks. The purpose for A5/1 is to encrypt both voice and signaling data, and it is applied in both the handset and the Base Transceiver Station (BTS). The problem is that A5/1 is outdated and broken.
Update: The GSM Alliance has responded to the project in a statement. You can read about that aspect of the story here.
The security offered by A5/1 has been proven exploitable since 2000, but in 2008, The Hackers Choice set out to develop a more practical attack on the A5/1 vulnerability. Nohl’s project is a variation of the one started by The Hackers Choice, as it differs in the choice of hardware used to crack A5/1. Namely, his project uses graphics cards with GPU capability, and seeks to build a distributed infrastructure of nodes.
Each node will donate small portions of disk space, which will house part of the Rainbow Table that will be created and used to crack A5/1, and the fast GPUs will be used for the generation of, and lookup of, the nodes own table. After the work is complete, the code book produced will be given out freely, and can be used to listen in on GSM-based phone conversations, capture SMS messages sent over the GSM network, or both at the same time.
Nohl told The Tech Herald in an interview that the project expects to have a working proof-of-concept attack on A5/1, “…by the end of the year.”
He estimates that the project will need 80 people dedicating their hardware and processing resources for about three months before the PoC is ready. However, with 160 people, the time can drop to about six weeks.
The project is anonymous, and the hope is that as users finish their part of the process, they will upload their completed tables to anonymous repositories and share them with BitTorrent. The process will be organic, Nohl explained, “…these tables will just popup in random places.”
Since there is no hard usage data being kept, Nohl was unable to tell us how many people have downloaded the software needed, because the project doesn't keep those records by design. “We’re still confident that the initial estimate of involving 80 people for next three months can be held,” he said.
So the project is likely to be successful, but what about the risks? Wouldn’t this mean the criminals could get access to GSM networks and compromise subscriber privacy and security? Why would Nohl even consider this? As expected, there is nothing malicious whatsoever about his intentions.
“We thought that everyone that is using cell phones should be aware of the security risks,” Nohl explained to us. “Our most sincere and primary goal was to raise awareness about this problem.”
Adding to this he said that the projects aim is to raise awareness about the widespread use of GSM, and by proxy A5/1, which amounts for just over 80-percent of the mobile phone market, used in 200 countries the world over by almost 3 billion people, by starting a public debate over the present insecurity and how to make GSM more secure to a “…level where people are comfortable using cellular phones.”
What about the risks? Full Disclosure, which is exactly what he has done with the project's announcement, means that end users are being placed in the line of fire. Assuming the project is a rousing success, isn’t he worried that the criminals will take advantage of the proof-of-concept?
“Some criminals already have this ability,” he explained. He gave is an example of code books available now for about $100,000 to $250,000 USD. “If you’re in the business of industrial espionage, then a quarter of a million dollars doesn’t sound like too high of a price,” he added.
As for users who might or might not be at risk, “That is the cost of Full Disclosure,” Nohl said. Whenever there is Full Disclosure, the information disclosed will usually, “…put some users at risk, but make things better for everybody in the long run.”
We asked about AT&T, who currently holds the rights to the iPhone, and uses both GSM and UMTS, better known as 3G on their network. Can AT&T do anything to secure the millions of iPhone users?
“AT&T has the ability to switch the iPhone to 3G on voice and data,” Nohl explained, but only for the iPhone 3G handsets. As things stand now, the iPhone 3G uses A5/3 (3G) for data transmission and A5/1 (GSM or 2G) for voice.
The problem is that, before AT&T moves customers over to 3G to avoid the weakness in A5/1, they would need to admit that there is a problem on their 2G voice network, something Nohl notes is highly unlikely.
“The proposal has been around for a long time to include the 3G cipher in the 2G standard,” Nohl said. Yet, despite the proposal, nothing has changed.
“Hopefully the discussion over GSM’s current insecurity will prompt the debate of adopting the better 3G security for GSM,” he added.
So what’s next? The project is official, active, and likely to succeed. According to Nohl, the next step is the main reason the project was started to begin with, he hopes all of the attention will “…start a discussion on how to make GSM security better, as it hasn’t improved over the last 15 years.”
If you want to take part in the project, you’ll need the ability to compile or download and install pre-compiled binaries on Linux. There is no Windows version of the project code. (Yet..but it is coming soon Karsten said.) You can get more information here.