Cloud Computing Crypto: GSM is dead. Long live GSM!

GSM, at least in its current form, is dead and the GSMA‘s attempts to downplay serious vulnerabilities in claiming otherwise reminds me of this rather famous Monty Python sketch about a dead parrot:

Fortunately consumers these days are savvy and have access to information with which to verify (or not) vendors’ claims about security. So when they get together and say things like “the researchers still would need to build a complex radio receiver to process the raw radio data” the more cynical of us are able to dig up 18 month old threads like this one which concludes:

So it appears you might be able to construct a GSM sniffer from a USRP board and a bunch of free software, including a Wireshark patch. (It appears that one of the pieces of free software required is called “Linux” or “GNU/Linux”, depending on which side of that particular debate you’re on🙂, i.e. it works by using Linux’s tunnel device to stuff packets into a fake network interface on which Wireshark can capture.

Ok so extracting the 1’s and 0’s from the airwaves and getting them into the most convenient (open source) framework we have for the dissection of live protocols is a problem long since solved. Not only are the schematics publicly available, but devices are commercially available online for around $1,000. One would have assumed that the GSMA should have known this, and presumably they did but found it preferable to turn a blind eye to the inconvenient truth for the purposes of their release.

The real news though is in the cracking of the A5/1 encryption which purports to protect most of us users by keeping the voice channels “secure”. Conversely the control information which keeps bad guys from stealing airtime is believed to remain safe for the time being. That is to say that our conversations are exposed while the carriers’ billing is secure – an “externalisation” of risk in that the costs are borne by the end users. You can bet that were the billing channels affected then there would have been a scramble to widely deploy a fix overnight rather than this poor attempt at a cover-up.

The attack works by creating a 2Tb rainbow table in advance which allows one to simply look up a secret key rather than having to brute force it. This should be infeasible even for A5/1’s 64-bit key but “the network operators decided to pad the key with ten zeros to make processing faster, so it’s really a 54-bit key” and there are other weaknesses that combine to make this possible. A fair bit of work goes into creating the table initially, but this only needs to be done once and you can buy access to the tables as a service as well as the tables themselves for many common hashes (such as those used to protect Windows and Unix passwords – and no doubt GSM soon too!). The calculations themselves can be quite expensive but advances like OpenCL in the recently released Mac OS X (Snow Leopard) can make things a lot better/faster/cheaper by taking advantage of extremely performant graphics processing units (GPUs).

Of course thanks to cloud computing you don’t even need to do the work yourself – you can just spin up a handful of instances on a service like Amazon EC2 and save the results onto Amazon S3/Amazon EBS. You can then either leave it there (at a cost of around $300/month for 2Tb storage) and use instances to interrogate the tables via a web service, or download it to a local 2Tb drive (conveniently just hitting the market at ~$300 once off).

Cloud storage providers could make the task even easier with services like public data sets which bring multi-tenancy in the form of de-duplication benefits to common data sets. For example, if Amazon found two or more customers storing the same file they could link the two together and share the costs between all of them (they may well do this today, only if they do they keep the benefit for themselves). In the best case such benefits would be exposed to all users in which case the cost of such “public domain” data would be rapidly driven down towards zero.

Ignoring A5/2 (which gives deliberately weakened protection for countries where encryption is restricted), there’s also a downgrade attack possible thanks to A5/0 (which gives no protection) and the tendency for handsets to happily transmit in the clear rather than refusing to transmit at all or at least giving a warning as suggested by the specifications. A man in the middle just needs to be the strongest signal in the area and they can negotiate an unencrypted connection while the user is none the wiser. This is something like how analog phones used to work in that there was no encryption at all and anyone with a radio scanner could trivially eavesdrop on [at least one side of] the conversation. This vulnerability apparently doesn’t apply where a 3G signal is available, in which case the man in the middle also needs to block it.

Fortunately there’s already a solution in the form of A5/3, only it’s apparently not being deployed:

A5/3 is indeed much more secure; not only is it based on the well known (and trusted) Kasumi algorithm, but it was also developed to encrypt more of the communication (including the phone numbers of those connecting together), making it much harder for ne’er-do-wells to work out which call to intercept. A5/3 was developed, at public expense, by the European Telecommunications Standards Institute (ETSI) and is mandated by the 3G standard, though can also be applied to 2.5G technologies including GPRS and EDGE.

That GSMA consider a 2Tb data set in any way a barrier to these attacks is telling about their attitude to security, and to go as far as to compare this to a “20 kilometre high pile of books” is offensively appalling for anyone who knows anything about security. Rainbow tables, cloud computing and advances in PC hardware put this attack well within the budget of individuals (~$1,000), let alone determined business and government funded attackers. Furthermore groups like the GSM Software Project, having realised that “GSM analyzer[s] cost a sh*tload of money for no good reason” are working to “build a GSM analyzer for less than $1000” so as to, among other things, “crack A5 and proof[sic] to the public that GSM is insecure”. Then there’s the GNU Radio guys who have been funded to produce the software to drive it.

Let’s not forget too that, as Steve Gibson observes in his recent Cracking GSM Cellphones podcast with Leo Laporte: “every single cellphone user has a handset which is able to decrypt GSM“. It’s no wonder then that Apple claim jailbreaking the iPhone supports terrorists and drug dealers, but at about the same price as an iPhone ($700 for the first generation USRP board) it’s a wonder why anyone would bother messing with proprietary hardware when they can deal with open hardware AND software in the same price range. What’s most distressing though is that this is not news – according to Steve an attack was published some 6 years ago:

There’s a precomputation attack. And it was published thoroughly, completely, in 2003. A bunch of researchers laid it all out. They said, here’s how we cracked GSM. We can either have – I think they had, like, a time-complexity tradeoff. You’d have to listen to two minutes of GSM cellphone traffic, and then you could crack the key that was used to encrypt this. After two minutes you could crack it in one second. Or if you listen to two seconds of GSM cellphone traffic, then you can crack it in two minutes. So if you have more input data, takes less time; less input data, more time. And they use then tables exactly like we were talking about, basically precomputation tables, the so-called two terabytes that the GSM Alliance was pooh-poohing and saying, well, you know, no one’s ever going to be able to produce this.

Fortunately us users can now take matters into our own hands by handling our own encryption given those entrusted with doing it for us have been long since asleep at the wheel. I’ve got Skype on my MacBook and iPhone for example (tools like 3G Unrestrictor on a jailbroken iPhone allow you to break the digital shackles and use it as a real GSM alternative) and while this has built in encryption (already proving a headache for the authorities) it is, like GSM, proprietary:

Everything about this is worrisome. I mean, from day one, the fact that they were keeping this algorithm, their cipher, a secret, rather than allowing it to be exposed publicly, tells you, I mean, it was like the first thing to worry about. We’ve talked often about the dangers of relying on security through obscurity. It’s not that some obscurity can’t also be useful. But relying on the obscurity is something you never want because nothing remains obscure forever.

We all know that open systems are more secure – for example, while SSL/TLS has had its fair share of flaws it can be configured securely and is far better than most proprietary alternatives. That’s why I’m most supportive of solutions like (but not necessarily) Phil Zimmerman‘s Zfone – an open source implementation of the open ZRTP specification (submitted for IETF standardisation). This could do the same for voice as what his ironically named Pretty Good Privacy did for email many years ago (that is – those who do care about their privacy can have it). Unfortunately draft-zimmermann-avt-zrtp expired last week but let’s hope it’s not the end of the road as something urgently needs to be done about this. Here you can see it successfully encrypting a Google Talk connection (with video!):

Sure there may be some performance and efficiency advantages to be had by adding encryption to compression codecs but I rather like the separation of duties as it’s unlikely a team of encryption experts will be good at audio and video compression and vice versa.

Widespread adoption of such standards would also bring us one big step closer to data-only carriers that I predict will destroy the telco industry as we know it some time soon.