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. ®