[Infowarrior] - GSM crypto cracked

[Richard Forno]

Secret code protecting cellphone calls set loose

http://www.theregister.co.uk/2009/12/28/gsm_eavesdropping_breakthrough/
Universal phone snooping moves forward

By Dan Goodin in San Francisco • Get more from this author

Posted in Security, 28th December 2009 18:57 GMT

Cryptographers have moved closer to their goal of eavesdropping on  
cellphone conversations after cracking the secret code used to prevent  
the interception of radio signals as they travel between handsets and  
mobile operators' base stations.

The code is designed to prevent the interception of phone calls by  
forcing mobile phones and base stations to rapidly change radio  
frequencies over a spectrum of 80 channels. Without knowing the  
precise sequence, would-be eavesdroppers can assemble only tiny  
fragments of a conversation.

At a hacker conference in Berlin that runs through Wednesday, the  
cryptographers said they've cracked the algorithm that determines the  
random channel hopping and have devised a practical means to capture  
entire calls using equipment that costs about $4,000. At the heart of  
the crack is open-source software for computer-controlled radios that  
makes the frequency changes at precisely the same time, and in the  
same order, that the cellphone and base station do.

"We now know this is possible," said Karsten Nohl, a 28-year-old  
cryptographer and one of the members of an open-source project out to  
prove that GSM, the technical standard used by about 80 percent of the  
mobile market, can't be counted on to keep calls private. The attack  
"is practical, and there are real vulnerabilities that people are  
exploiting."

A spokeswoman for the GSM Association, which represents 800 operators  
in 219 countries, said officials hadn't yet seen the research.

"GSM networks use encryption technology to make it difficult for  
criminals to intercept and eavesdrop on calls," she wrote in an email.  
"Reports of an imminent GSM eavesdropping capability are common."

The channel-hopping crack comes as the collective is completing the  
compilation of a rainbow table that allows them to decrypt calls as  
they happen. The table works because GSM encryption uses A5/1, a  
decades-old algorithm with known weaknesses. The table - a 2-terabyte  
list of known results that allows cryptographers to deduce the unique  
key that encrypts a given conversation - was developed by volunteers  
around the globe using giant clusters of computers and gaming consoles.

Within days of the project announcement in August, the GSMA pooh- 
poohed it as a "theoretical compromise" that would have little  
practical effect on the security of phone calls. In addition to the  
massive rainbow table needed, the GSMA said it doubted researchers had  
the means to process the vast amounts of raw radio data involved.

"Initially, we didn't consider channel-hopping a big security  
feature," Nohl told The Register. "If the GSM Association's excuse for  
bad crypto is there is another security feature we rely on much more,  
then of course, we'll break that, too."

A bare-bones attack can be pulled off with a PC with a medium-end  
graphics card, a large hard drive, two USRP2 receivers and the channel- 
hopping software. Under normal conditions, it will take a few minutes  
of conversation before eavesdroppers have collected enough data to  
break the encryption. Because the calls are recorded and played back  
later, the entire contents of a conversation can still be captured.

More elaborate setups that use a network of computers or Field  
Programmable Gate Array devices, will be able to unlock calls almost  
instantaneously, Nohl said.

To capture both ends of a conversation, an attacker would have to  
place one of the radios in close proximity to the person making the  
call, while the second would be used to capture downlink transmissions  
coming from a carrier's base station. That requires a fair amount of  
effort because attackers must target a specific individual.

But in many cases - such as phone menus used by banks and airline  
companies - it's sufficient for an attacker to intercept only the  
downlink, said David Burgess, a signal processing engineer who helped  
to identify weaknesses used to break A5/1.

"Even if I only see the downlink, that's still very useful," he said.  
"The base station is acknowledging back every button press."

After weaknesses in A5/1 became common knowledge, mobile operators  
devised A5/3, an algorithm that requires about a quintillion times  
more mathematical operations to break. Despite estimates that some 40  
percent of cellphones are capable of using the newer cipher, it has  
yet to be adopted, largely, Nohl says, because of the cost of  
upgrading and fears older handsets will be left behind.

"A5/3 is a better encryption algorithm and there has been a long- 
standing proposal to make this the preferred cipher in GSM," he said.  
"But no network operator with one exception that I'm aware of has  
started adopting A5/3 so far."

The GSMA has said it plans to transition to the new technology, but  
has yet to provide a timetable.

Nohl described the channel-hopping techniques at the 26th Chaos  
Communication Congress, an annual hacker conference in Berlin, along  
with fellow reverse engineer Chris Paget. Their presentation is here. ®