29 December 2009. GSM A5 Files Published on Cryptome
9 December 1999: Link to final paper: http://cryptome.org/a5.ps
7 December 1999: Add news report.
6 December 1999
To: cryptography@c2.net Subject: Forthcoming Biryukov/Shamir result against A5/1 GSM privacy algorithm Date: Sun, 05 Dec 1999 22:36:28 -0500 From: Matt Blaze <mab@research.att.com> ------- Forwarded Message Date: Sun, 5 Dec 1999 15:31:21 +0200 (IST) From: Adi Shamir <shamir@wisdom.weizmann.ac.il> To: mab@research.att.com Subject: FYI Dear Matt, You may be interested in the following new result: Real-Time Cryptanalysis of GSM's A5/1 on a PC Alex Biryukov and Adi Shamir Computer Science Department The Weizmann Institute Rehovot 76100, Israel Abstract: A5/1 is the strong version of the encryption algorithm used by about 100 million GSM customers in Europe to protect the over-the-air privacy of their cellular voice and data communication. The best published attacks against it require between 2^40 and 2^45 steps. This level of security makes it vulnerable to hardware-based attacks by large organizations, but not to software-based attacks on multiple targets by hackers. In this paper we describe a new attack on A5/1, which is based on subtle flaws in the tap structure of the registers, their noninvertible clocking mechanism, and their frequent resets. The attack can find the key in less than a second on a single PC with 128 MB RAM and two 73 GB hard disks, by analysing the output of the A5/1 algorithm in the first two minutes of the conversation. The attack requires a one time parallelizable data preparation stage whose complexity can be traded-off between 2^37 and 2^48 steps. The attack was verified with an actual implementation, except for the preprocessing stage which was extensively sampled rather than completely executed. Remark: The attack is based on the unofficial description of the A5/1 algorithm at http://www.scard.org. Discrepancies between this description and the real algorithm may affect the validity or performance of our attack. I'll email you the paper in a few days, when its ready. Best wishes, Adi. ------- End of Forwarded Message
Date: Sun, 05 Dec 1999 23:29:18 -0800 From: Lucky Green <shamrock@cypherpunks.to> To: "cypherpunks@Algebra. COM" <cypherpunks@Algebra.COM> Subject: FW: cracking GSM A5/1 Executive summary: sub-second attack against A5/1. I am in communications with Shamir. The actual paper has not yet been released. -----Original Message----- From: Lucky Green [mailto:shamrock@cypherpunks.to] Sent: Sunday, December 05, 1999 20:49 To: John Gilmore Cc: cryptography@c2.net Subject: RE: cracking GSM A5/1 > Real-Time Cryptanalysis of GSM's A5/1 on a PC > > Alex Biryukov and Adi Shamir At last! Congratulations are in order. Way to go, Alex and Adi! Between the COMP128 and A5/2 work of our group and Alex and Adi's break of A5/1, my motivation for finishing that software radio-based GSM interception station has just increased greatly. Not that I wasn't motivated to begin with. :-) Even counting the almost 200 GB of drive space that seem to be required by this new attack, we still should come in well under the USD 10,000 target figure. We tested the code the came out of my reverse engineering against official test vectors, so I am confident that Alex and Adi's caveat that the attack will only work if the A5/1 code is correct won't be an issue. It will be interesting to see the actual attack. Our 15 milliseconds attack against A5/2 only works because several properties of the cipher come together just right. I wonder if the same holds true for the new attack against A5/1... We live in interesting times, --Lucky Green <shamrock@cypherpunks.to> "Among the many misdeeds of British rule in India, history will look upon the Act depriving a whole nation of arms as the blackest." - Mohandas K. Gandhi, An Autobiography, pg 446 http://www.citizensofamerica.org/missing.ram
Date: Sat, 04 Dec 1999 19:10:11 -0800 From: Lucky Green <shamrock@cypherpunks.to> Subject: RE: New Yorker article on NSA surveillance, crypto regs To: "Steven M. Bellovin" <smb@research.att.com> Cc: cryptography@c2.net Dave Emery wrote: > And much of the worlds wireless phone plant is GSM, which is > almost always encrypted, which must add significantly to NSAs burden > intercepting it, even if they can break keys very quickly... Being rather familiar with GSM crypto, allow me to say this: most GSM voice traffic globally is encrypted using A5/2. We know how to break A5/2 in five clock cycles on an ASIC. For an agency that operates interception satellites costing USD 1.5 billion each featuring antennas over twice the size of a football field, adding 5 lousy clock cycles for the cryptanalysis to the many clock cycles required to demodulate a GSM call can not be considered to be significant. Immaterial would be a better term. A5/1 likely requires more clock cycles. How many clock cycles we don't know and won't know until the cryptographic community takes a serious look at A5/1. But I from what I know about A5/1, it won't be a showstopper by any standard. I know how to build a GSM interception station using off-the-shelf hardware and a PII running Linux for a total cost of well below USD 10k. Give me a couple of billions of dollars, peanuts for the NSA, and I hereby guarantee you that I can take that system down to a single chip and some RF hardware. --Lucky Green <shamrock@cypherpunks.to> "Among the many misdeeds of British rule in India, history will look upon the Act depriving a whole nation of arms as the blackest." - Mohandas K. Gandhi, An Autobiography, pg 446 http://www.citizensofamerica.org/missing.ram
Date: Sun, 05 Dec 1999 23:03:25 -0800 From: Lucky Green <shamrock@cypherpunks.to> Subject: RE: New Yorker article on NSA surveillance, crypto regs To: die@die.com Cc: cryptography@c2.net Dave Emery wrote: > I certainly humbly defer to your expertise on the subject. I was > aware that A5/2 was very weak, though not aware that a 5 cycle result > had been found, and fully expect that (as indicated by the Shamir > announcement) that there probably is a similar very fast solution > to a5/1. And one supposes NSA has long ago derived these results in house > though some talented outsiders have yet to find a really cheap > A5/1 crack that would trivialize the required compute, meaning that > finding such is not totally trivial. Your observation that you didn't know about the 5 clock cycle attack on A5/2 is noted. Our group really needs to sit down and write our long overdue GSM crypto paper. Other than better funding, the NSA has the advantage over us "outsiders" in that the NSA or their European counterparts designed A5/1 and A5/2. They didn't have to find a compromise. They had the luxury of being able to engineer it in. Our 5 clock cycles attack against A5/2 only works because several properties of the cipher come together just right. Chance? Many doubt it. We can only wait and see if similar "fortunate coincidences" play a role in the new attack against A5/1. > As you say, we shall simply have to wait and see what kind of > crack is most effective and how low the cracking cost goes. Shamir's > recent letter hints at cracking time and resources comparable with those > required to demodulate the call and follow the protocol - or less... I am delighted that Biryukov and Shamir found a sub-second attack on A5/1. Our group had an attack of just a tad under 2^40 based on Golic's paper, but I just knew there had to be a much better attack. It didn't appear that we would find that attack. I had tried to get others interested in cryptanalyzing A5/1, but most cryptanalysts are busy working on the AES candidates. For a while there, I thought that we might have to wait until AES is chosen before A5/1 would receive some serious attention. I am glad that it didn't take that long, since some 250 million GSM users worldwide currently rely on the supposed voice privacy features of GSM. Other than perhaps DES, GSM's COMP128, A5/1, and A5/2 are by far the most widely used cryptographic algorithms in the world. [On the GSM interception station project]. > Have you actually written the code and tried it ? How well did > it work ? And in particular have you actually cracked real A5/1 even > with a 2^45 or so workfactor ? The project is still underway. It is a complex project and I don't expect it to be fully completed before 2Q2000. I am confident that the project will succeed, but I'd rather not go into more detail at this time. Watch this space. ;-) --Lucky
The New York Times, December 7, 1999
By SARA ROBINSON
SAN 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.
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.
Copyright 1999 The New York Times Company