NYT on GSM Hack

[John Young <jya@pipeline.com>]

   The New York Times, April 14, 1998, pp. D1, D5.

   Researchers Crack Code In Cell Phones 

      Weakened Encryption Raises Security Concern 

   By John Markoff

   San Francisco, April 13 -- 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 G.S.M., for the
   Groupe Speciale Mobile standard. The world's most widely
   used encryption system for cellular phones, G.S.M. is
   employed in about 80 million of the devices worldwide and
   by as many as two 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 the Omnipoint
   Corporation, use the G.S.M. standard.

   Two researchers at the University of California at Berkeley
   announced today that they had successfully broken the
   G.S.M. method by using a computer to determine a secret
   identity number stored in the Subscriber Identity Module,
   or S.I.M., a credit card-like device inside the phone.

   If criminals were to crack the method, they could "clone"
   phones protected by G.S.M. 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 today that the cloning
   threat was extremely remote compared with the vulnerability
   of analog cellular phones.

   For one thing, they said, cracking G.S.M. 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 G.S.M. 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
   G.S.M. system. Industry cryptographic experts said that the
   underlying mathematical formulas, or algorithms, in
   G.S.M.'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 today'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 N.S.A.

   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," Mr. 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
   G.S.M. "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 the University
   of California at Berkeley's Internet Security Applications,
   Authentication and Cryptography Group, with the aid of Mr.
   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 G.S.M. 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," Mr. Briceno said. "These companies pride
   themselves on their security, but now the chickens are
   coming home to roost."

   [End]