I adhere to a ‘one post, one topic’ rule on this blog, which means that this weekend I actually have to choose which bad-crypto news I’m going to blog about.

It’s a tough call, but the most interesting story comes via Erik Tews, who recently attended a talk on satellite phone security at Ruhr Universität Bochum. It seems that researchers Benedikt Driessen, Ralf Hund, Carsten Willems, Christof Paar, and Thorsten Holz have reverse-engineered and cryptanalyzed the proprietary ciphers used in the GMR-1 and GMR-2 satellite telephone standards.* If you’ve never heard of these standards, what you need to know is that they power the networks of satphone providers Thuraya and Inmarsat.

The verdict? Encrypting with these ciphers is better than using no encryption. But not necessarily by much.

I guess this shouldn’t come as a big shock — link privacy in mobile telephony has always been kind of a mess. And the GMR ciphers come from the same folks (ETSI) who brought us the A5-series GSM ciphers. If you pay attention to this sort of thing, you probably know that those ciphers have also had some problems. In fact, today it’s possible to download rainbow tables that permit (efficient) decryption of A5/1-encrypted GSM phone calls.

A5/1 is actually the strong member of the GSM family. For export purposes there’s A5/2 — a weakened version with a much shorter key. You don’t hear about people downloading huge A5/2 rainbow tables, mostly because you don’t need them. A5/2 is vulnerable to ciphertext-only attacks that run in a few minutes on a standard PC.

A5/2 GSM cipher. Image: Barkan, Biham, Keller.

ETSI seems to have had A5/2 in mind when developing the GMR-1 and GMR-2 ciphers. Both are custom designs, use short keys, and depend heavily on obscurity of design to make up for any shortcomings (the ciphers are only given to manufacturers who sign an NDA). This secrecy hardly inspires confidence, and worse yet, it doesn’t even do a good job of keeping things secret. The R.U.B. researchers didn’t have to break into Thuraya’s hardware lab; they simply reversed the ciphers from handset firmware updates.**

GMR-1 uses an LFSR-based cipher quite similar to A5/2 (pictured above), which means that it’s vulnerable to a similar class of attacks. Since the underlying plaintext has correctness checks built into it, it’s possible to recover the key using only ciphertext and about 30 minutes on a standard PC. The GMR-2 cipher is a bit more sophisticated (and weirder to boot), but it also appears to have weaknesses.

So why is this a big deal? The obvious answer is that satellite telephone security matters. In many underdeveloped rural areas it’s the primary means of communicating with the outside world. Satphone coverage is also important in war zones, where signal privacy is of more than academic interest.

Moreover, eavesdropping on satellite communications is (in principle) easier than eavesdropping on cellular signals. That’s because satellite ‘spot beams’ cover relatively broad geographic territories (Thuraya’s are 600km on average). So you don’t just have to worry about eavesdropping by your neighbor, you have to worry about eavesdropping by neighboring countries.

The really sad thing is that, unlike cellular networks — which are fundamentally vulnerable to government eavesdropping at the infrastructure level — satellite networks like Thuraya/Inmarsat don’t need local infrastructure. That means their systems really could have provided privacy for individuals persecuted by oppressive regimes. You can argue about whether the manufacturers even had the option to use strong ciphers; it’s quite possible they didn’t. Still, I suspect this will be cold comfort to those who suffer as a direct result of ETSI’s design choices.

Those who are really in the know (news organizations, for example) claim to use additional security measures beyond the built-in link encryption found in GMR-1 and GMR-2. Presumably these days the best way to do that is to run your own voice protocol via the packet data extensions. This practice ought to become more common going forward; now that the GMR-1 code is public, it looks like the barriers to eavesdropping are going to go down quite a bit.

The slides above come from this presentation.

Notes:

* Update 2/16/2012: I had some initial confusion about the authorship on this work, but the research paper clears it all up: see here.

** And by ‘simply’, I mean ‘with great expertise and difficulty’ — don’t read this as trivializing the effort involved. Obtaining the ciphers meant disassembling code written in a proprietary DSP instruction set, and then searching for a cipher without knowing exactly what it looks like. All in all a pretty significant accomplishment. The point here is that it could have been a lot harder. If you’re going to keep a cipher secret, you shouldn’t release it as software in the first place.