April 14, 1998
Researchers Crack Code in Cell Phones
By JOHN MARKOFF
AN FRANCISCO -- In successfully cracking a widely used encryption method designed to prevent the cloning of digital cellular phones, a group of University of California computer researchers believe they have stumbled across evidence that the system was deliberately weakened to permit government surveillance.
The method that was cracked is known as GSM, for the Groupe Speciale Mobile standard. The world's most widely used encryption system for cellular phones, GSM is employed in about 80 million of the devices worldwide and by as many as 2 million phones in the United States.
Most of the 58 million American analog and digital cell phones are based on a variety of other methods, but 20 American cellular phone companies, including Pacific Bell, a unit of SBC Communications Inc., and Omnipoint Corp., use the GSM standard.
Two researchers at the University of California at Berkeley announced Monday that they had successfully broken the GSM method by using a computer to determine a secret identity number stored in the Subscriber Identity Module, or SIM, a credit cardlike device inside the phone.
If criminals were to crack the method, they could "clone" phones protected by GSM encryption -- that is, detect a phone's number and use it in another phone to fraudulently bill calls. However, both the researchers and cellular telephone company officials said Monday that the cloning threat was extremely remote compared with the vulnerability of analog cellular phones.
Illustration: Christine M. Thompson
For one thing, they said, cracking GSM had required almost 10 hours of electronic probing and high-powered computing.
What was even more intriguing than the security threat, however, was that cracking the code yielded a tantalizing hint that a digital key used by GSM may have been intentionally weakened during the design process to permit government agencies to eavesdrop on cellular telephone conversations.
Although the key, known as A5, is a 64-bit encryption system -- generally an extremely difficult code to crack -- the researchers determined that the last 10 digits were actually zeros. That means that with the powerful computers available to national intelligence agencies, it would be possible to decode a voice conversation relatively quickly, said Marc Briceno, director of the Smartcard Developers Association, a small programmers organization.
"It appears the key was intentionally weakened," he said. "I can't think of any other reason for what they did."
For years, the computer industry has been rife with rumors about encryption designers having been persuaded or forced by government spy agencies to mathematically weaken communications security systems or to install secret backdoors. Some of the rumors even have the National Security Agency or the Central Intelligence Agency posing as cryptographers, designing the encryption programs themselves and then releasing them -- all to insure that they could decode data or phone conversations.
Such rumors are fed, in part, by the hazy origins of the GSM system. Industry cryptographic experts said that the underlying mathematical formulas, or algorithms, in GSM's encryption design were thought to have originated in either Germany or France as part of the creation of the standard in 1986 and 1987.
But other than Monday's hint of an intentionally weakened system, little evidence has ever emerged to support speculation, and the researchers' suspicions were not universally endorsed.
"It's possible there are other reasons for doing this," Stewart Baker, a Washington lawyer who was formerly a lawyer for the National Security Agency, said. The NSA is one of the agencies most often suspected of such schemes because a major part of its mission is to intercept telephone calls.
"Speculation is easy, and it never dies," Baker said.
Even so, most industry experts could think of no good reason why an encryption algorithm key would be intentionally shortened, other than to facilitate surveillance.
"This was deliberately weakened," said Phil Karn, an engineer at Qualcomm Inc., a cellular telephone manufacturer that has developed an alternative standard to GSM. "Who do you think would be interested in doing something like this?"
The weakened key was discovered by two researchers, Ian Goldberg and David Wagner, both members of University of California at Berkeley's Internet Security Applications, Authentication and Cryptography Group, with the aid of Briceno. They stressed that they had easily detected the security flaw that could make digital cellular phones vulnerable to cloning.
Cloning has been a costly fraud problem for many years. But digital phones are widely believed to be immune from cloning. In San Francisco, Pacific Bell's billboard advertisements depict a sheep and a cell phone and boast that of the two only the cell phone cannot be cloned.
Cellular telephone industry executives acknowledged the flaw in GSM but said it actually reinforced their claims about the security of digital telephones.
"My hat goes off to these guys, they did some great work," said George Schmitt, president of Omnipoint. "I'll give them credit, but we're not at any risk of fraud."
The researchers and the Smartcard Developers Association said that the successful attack was new evidence of the shortcomings of a widespread industry practice of keeping security techniques hidden from public review. Real security, they argue, requires publication of the algorithms so that independent experts can verify the strength of the systems.
"This shows yet again a failure of a closed design process," Briceno said. "These companies pride themselves on their security, but now the chickens are coming home to roost."