Researchers Crack Code in Cell Phones
By SARA ROBINSON
AN FRANCISCO -- Two Israeli researchers say they have found an efficient way to crack the encryption scheme that protects the privacy of conversations and data transmissions over a type of wireless phone used by more than 215 million people worldwide.
The encryption method, known as A5/1, is part of the G.S.M. wireless phone standard. Although not dominant in the United States, G.S.M. (Groupe Speciale Mobile) is the world's most widely used cellular technology. It is employed in more than 215 million digital phones worldwide, including about 5 million in the United States and more than 100 million in Europe. Analog cellular phones do not encrypt conversations.
--------------------------------------------------------------------------------
An eavesdropper with just a PC could break into a conversation in less than a second, its developers said.
--------------------------------------------------------------------------------
Most of the cell phones in the United States are based on a variety of other wireless technologies, but a number of American cellular phone companies, including Pacific Bell, a unit of SBC Communications Inc., and the Omnipoint Corporation, use the G.S.M. standard.
Although the finding was not formally announced, it was confirmed today by one of the researchers after word spread quickly among encryption experts on Internet mailing lists.
A spokesman for Omnipoint today called the researchers' claims "ridiculous."
"What they're describing is an academic exercise that would never work in the real world," said the spokesman, Terry Phillips. "What's more, it doesn't take into account the fact that G.S.M. calls shift frequency continually, so even if they broke into a call, a second later it would shift to another frequency, and they'd lose it."
But David Wagner, a computer security researcher at the University of California at Berkeley, insisted the discovery was significant. "This is a big deal," he said. "I don't think that the frequency hopping will be a major barrier." He added that it put the interception of G.S.M. calls "within the reach of corporate espionage."
Computer security researchers continually attempt to break cryptographic codes because the measure of an encryption scheme is how much time and computing power are needed to crack it.
While cell phone encryption has been cracked before, the new method is significant because it requires very little computer power; an eavesdropper with just a PC could break into a conversation in less than a second, its developers said.
Several schemes for attacking the G.S.M. algorithms have been announced before, but most were impractical, requiring several hours and a network of computers to intercept a single conversation.
In 1998, Wagner and Ian Goldberg, also at U.C.-Berkeley, and Marc Briceno, of the Smart Card Developers Association, demonstrated that they could crack an authentication method associated with G.S.M. in a matter of hours on a single PC. That technology prevents detecting a phone's number and "cloning" it in another phone to bill calls fraudulently.
As part of their research, they discovered that the A5/1 algorithm used keys that were much shorter than advertised, prompting speculation that the algorithm had been deliberately weakened to allow for government eavesdropping.
The underlying algorithms in G.S.M.'s encryption design are thought to have originated from the German or French military, industry cryptographic experts said.
In August, Wagner, Goldberg and Briceno developed a method for breaking into calls protected by weak versions of the A5/1 algorithm used in parts of Asia and Australia.
Their method could break into a conversation in a fraction of a second.
The researchers who discovered the latest method are Alex Biryukov and Adi Shamir of The Weizmann Institute in Rehovot, Israel. The men said they were able to break the code on a PC with 128 megabytes of RAM and two 73 gigabyte hard disks. The PC is used to analyze the output of the A5/1 algorithm in the first two minutes of the conversation. Once that data is gathered, the eavesdropper can listen to the rest of the conversation, they said.
For now, the new cracking method requires resources not available to most individuals. Before intercepting telephone conversations, the eavesdropper must perform a one-time data preparation stage that demands significant computing power, but after the data is prepared once, all GSM-protected conversations are accessible, they said.
The eavesdropper must also have access to a digital scanner, a device that can intercept wireless calls within a radius of several miles.
Such devices cost thousands of dollars and are illegal in the United States. |
