Cybernetic Entomology – GSM Encryption

Okay, this article is going to be a bit technical, so if you’re not a cryptography geek and not interested in exactly how people are listening in on your phone calls, you can move along now.

Most of the articles about this capability are about people using it – about reporters tapping the calls of celebrities or politicians, about hackers using this capability among others to ‘dox’ big companies like Sony, etc. This article is about what flaws in the protocols and  devices make it possible and how those flaws are exploited.

The first thing you need to understand is the GSM protocol. This was deployed with the second generation of cellular phones, and it was advertised as protecting your privacy when making calls. In fact it’s laughably insecure. Here is how it works.

Your phone wants to know the location of the nearest cell tower. If it hasn’t very recently found a cell tower, it continually searches for one by broadcasting authentication requests, which any tower that can receive the requests will respond to. Usually several towers respond to the authentication request; your phone picks the response with the best connection and authenticates to that one, so that the tower can tell the phone company’s network to route any calls to you through that tower. Incidentally, this is why, with some phones, your battery charge is used up within an hour or two if you venture into an area that doesn’t have cellular coverage; your phone is using all its power on its broadcasts hunting for a cell tower every few seconds, because it didn’t find one in the previous few seconds.

So, how are these authentication requests made? Your SIM card (Subscriber Identity Module) contains, along with all your phone configuration and other subscriber information, an identification number and a key, which never change. It broadcasts its identification number as an authentication request.

The tower contains a computer called a Gateway MSC (Mobile Switching Center) which connects through a network (originally a dedicated network maintained by the provider; these days, in practical terms almost always the Internet) to a database server called the HLR (Home Location Register) to get the key associated with that SIM card. It then uses that key to issue a challenge to your phone. Essentially it’s saying, “If you’re really the SIM card you claim to be, then prove it by using the key that SIM card has.” It makes up a random number, picks a cipher to use for further communication, then encrypts the random number and cipher choice using a cipher named A3 and the phone’s key, and sends it to the phone. The phone decrypts it using A3 and its own key to derive an authentication token, and sends the authentication token back in the clear. The Gateway MSC checks to see whether the phone got it right.

If the phone gets it right, the Gateway MSC then encrypts the same number using a different cipher named A8, and will use the result as a key with the cipher it chose for communicating with the phone. On the other end, your phone got the random number by decrypting with A3, then got the key by encrypting with A8, so there is agreement on a key to use.

Now, let’s list some of the problems with the protocol.

• The authentication requests aren’t encrypted. Anybody can set up a radio station to listen to the authentication requests (the SIM card’s ID number) and as a result know roughly where each phone in the area of its radio coverage is at any moment by keeping track of which tower it’s assigned to.
• The authentication token which the phone derives is sent back in the clear, so any eavesdropper can record the challenge and the response and then take all the time they want to try different SIM keys until they find the one that makes the response to the same challenge.
• The ID numbers from the authentication requests aren’t encrypted on the network when the Gateway MSC queries the HLR, so anybody who can tap the HLR’s network doesn’t need to set up a radio station to keep track of where all the phones served by the network are.
• A3 and A8 in their original versions are subject to an adaptive known-plaintext attack which a bogus tower can use to learn the phone’s SIM key. Instead of a ‘real’ A3 authentication challenge, a bogus tower can send specially crafted packets for your phone to decrypt, and from the decryptions of those specially crafted packets, it can learn your SIM key. Each decryption from the phone provides information that the attacker can use to craft the next packet, and after eight to ten such packets it knows enough to figure out your key. These authentication attempts will fail, as seen from your cell phone. But when they fail, your phone just hunts for another tower, and the bogus tower can respond again. The ninth or tenth authentication attempt will succeed. A8 is subject to the same attack, although it’s ‘better’ insofar as it takes a lot more than eight queries to break. Now there are updated versions of A3 and A8 for which this attack won’t work. Unfortunately, phones still understand the original version of these ciphers and will respond to them, so a bogus tower can just pretend it doesn’t know the updates and the attack will proceed as usual. As of 2015 most cellular manufacturers are promising that by fourth quarter they will quit selling phones that have the original A3 baked in. Call me skeptical.
• Bogus towers are easy to set up. All an attacker needs to do is put a radio near a real tower to relay your traffic back and forth from the bogus tower, then set up a bogus tower to relay traffic back and forth from all the cell phones in the area. They can use the known-plaintext crack to extract SIM keys from phones. If that doesn’t work, they can download huge lists of cracked SIM card keys from ‘dark markets’ used by crackers around the Internet.
• Your SIM card’s key never changes. And as if the adaptive known plaintext attack on A3 weren’t bad enough, cellular providers, cellular provider’s networks, the radio communications between phone and tower, and the manufacturers of SIM cards have all been repeatedly cracked to reveal huge numbers of SIM keys to unknown attackers. That includes the company that manufactures essentially all the SIM cards used in Europe and about half of those in the USA. Some of these crackers sold the lists, and this is how those ‘dark markets’ I just mentioned get them. Anybody can sell a list of SIM keys, no matter how they got it. If a law enforcement officer or intelligence agent obtained it legally with a warrant, they can sometimes double their income by selling it along to crooks. If a cracker obtained it by breaking into the manufacturer’s database illegally, s/he can make the same money. And in neither case does anyone usually learn who the seller is.
• The tower, whether real or bogus, uses some version of A3 for authentication responses, but gets to choose what cipher to use for actual calls. They’re supposed to use A5/1, which is bad, but they can choose A5/2, which is worse, or A5/0, which is no encryption whatsoever. If they pick A5/2 or A5/0, you generally won’t know it. A5/2 is deliberately weakened encryption made for export purposes. It can be broken in the time it takes before the phone even stops ringing. Your phone contains software to alert you to the use of A5/0, but cell service carriers can and often do turn that function off.
• An attacker who has recorded previous calls from you can decrypt them later. A5/1 still requires significant compute time and rainbow tables, but an attacker with a bogus tower doesn’t need to attack A5/1. If the attacker’s bogus tower responds to your authentication request by retransmitting the authentication challenge it recorded a real tower giving your phone for the recorded call, your phone will authenticate deriving the same session key. Then the bogus tower can drop to A5/2, crack the session key instantly, and switch back to A5/1. At that point whatever previous call the attacker has recorded can be decrypted without going through the trouble of attacking A5/1.

That was the state of the art for G2 networks. Some protocol improvements were made for G3, G4, and G5 networks. But they don’t matter, because almost all phones will silently fall back on the unimproved GSM protocol if the tower doesn’t (or claims it doesn’t) support the new protocols. Almost all towers will silently fall back on the unimproved GSM protocol if the phone doesn’t (or claims it doesn’t) support the new protocols. So the job of the attacker is still as simple as attacking GSM; all s/he has to do is ignore the new protocols, and the phones/towers will automatically do the wrong thing.

That said, some improvements to the protocol were made starting with G3.

• Calls are now supposed to be encrypted with KASUMI, which is a better cipher than A5/1. Unfortunately KASUMI is not actually a good cipher. It is based on a reasonably good cipher called MISTY1, but was “optimized” heavily to be fast on cell phones with limited computing power. Unfortunately these “optimizations” broke its security seriously and KASUMI is a lot weaker than MISTY1.
• There is now mutual authentication which is supposed to allow phones to figure out whether or not they’re talking to a real tower as well as letting towers figure out whether they’re talking to a real phone. Unfortunately, phones will still silently connect to towers that don’t use it.
• A3 and A8 are no longer supposed to be used to derive auth tokens and session keys respectively. Now there are a series of new ciphers called F1, F2, F3, F4, F5, and F5* which are used instead. These are supposed to be better ciphers. Unfortunately the carriers are refusing to support that claim by allowing them to be reviewed.

And that is the state of the art today.

The lesson is simple. Don’t use a cell phone for anything you need to keep private. Assume that whatever crooks are interested, already have your SIM card key. You probably won’t be wrong.