Source: "Crypto-Gram" by Bruce Schneier, December 15, 1999
http://www.counterpane.com

There's been a lot of bad information about what kinds of encryption are out there, what's been broken, and how bad the situation really is. Here's a summary of what's really going on.

GSM is the world's most widely used mobile telephony system (51% market share of all cellular phones, both analog and digital), with over 215 million subscribers in America, Europe, Asia, Africa, and Australia. In the US, GSM is employed in the "Digital PCS" networks of such telecommunications giants as Pacific Bell, Bell South, and Omnipoint.

There are four cryptographic algorithms in the GSM standard, although not all the algorithms are necessarily implemented in very GSM system. They are:

A3, the authentication algorithm to prevent phone cloning
A5/1, the stronger of the two voice-encryption algorithms A5/2, the weaker of the two voice-encryption algorithms
A8, the voice-privacy key-generation algorithm

(Remember, these voice-encryption algorithms only encrypt voice between the cellphone and the base station. It does not encrypt voice within the phone network. It does not encrypt end to end. It only encrypts the over-the-air portion of the transmission.)

These algorithms were developed in secret, and were never published. "Marc Briceno" (with the Smartcard Developer Association) reverse-engineered the algorithms, and then Ian Goldberg and David Wagner at U.C. Berkeley cryptanalyzed them.

Most GSM providers use an algorithm called COMP128 for both A3 and A8. This algorithm is cryptographically weak, and it is not difficult to break the algorithm and clone GSM digital phones.

The attack takes just 2^19 queries to the GSM smart-card chip, which takes roughly 8 hours over the air. This attack can be performed on as many simultaneous phones in radio range as your rogue base station has channels.

The Berkeley group published their COMP128 analysis in April 1998. They also demonstrated that all A8 implementations they looked at, including the few that did not use COMP128, were deliberately weakened. The algorithm takes a 64-bit key, but ten key bits were set to zero. This means that the keys that secure the voice-privacy algorithms are weaker than the documentation indicates.

They published and analyzed A5/2 in August 1999. As the weaker of the two voice-encryption algorithms, it proved to be very weak. It can be broken in real-time without any trouble; the work factor is around 2^16. Supposedly this algorithm was developed with "help" from the NSA, so these weaknesses are not surprising.

The Berkeley group published A5/1 in May 1999. The first attack was by Jovan Golic, which gives the algorithm a work factor of 2^40. This means that it can be broken in nearly real-time using specialized hardware. Currently the best attack is by Biryukov and Shamir. Earlier this month they showed that they can find the A5/1 key in less than a second on a single PC with 128 MB RAM and two 73 GB hard disks, by analyzing the output of the A5/1 algorithm in the first two minutes of the conversation.

All GSM providers and equipment vendors are part of the GSM Association. The algorithms were designed and analyzed by the secretive "SAGE" group (which is really part of ETSI). We don't know who the people are or what their resumes look like. What we do know is that the SAGE security analyses of the ciphers are online at ETSI's homepage in PDF format. Read it; it's entertaining. A5/1 is purported to be a modified French naval cipher. This is mentioned in the leaked Racal document.

What's most interesting about these algorithms is how robustly lousy they are. Both voice-encryption algorithms are flawed, but not obviously. The attacks on both A5/1 and A5/2 make use of subtle structures of the algorithm, and result in the ability to decrypt voice traffic in real time on average computer equipment. At the same time, the output of the A8 algorithm that provides key material for A5/1 and A5/2 has been artificially weakened by setting ten key bits to zero. And also, the COMP128 algorithm that provides the keying material that is eventually weakened and fed into the weakened algorithms is, itself, weak.

And remember, this encryption only encrypts the over-the-air portion of the transmission. Any legal access required by law enforcement is unaffected; they can always get a warrant and listen at the base station. The only reason to weaken this system is for *illegal* access. Only wiretaps lacking a court authorization need over-the-air intercepts.

The industry reaction to this has been predictably clueless. One GSM spokesman claimed that it is impossible to intercept GSM signals off the air, so the encryption breaks are irrelevant. Notwithstanding the fact that GSM interception equipment was once sold openly -- now it's illegal -- certainly the *phone* can receive signals off the air. Estimated cost for a high-quality interception station is well under $10K.

GSM analysis:
http://www.scard.org/gsm/
http://www.jya.com/crack-a5.htm

GSM Association Web site:
http://www.gsmworld.com

News reports:
http://wired.lycos.com/news/politics/0,1283,32900,00.html
http://www.nytimes.com/library/tech/99/12/biztech/articles/07code.html