Cryptanalysis of Satellite Phone Encryption Algorithms

In this paper, we analyze the encryption systems used in the two existing (and competing) satphone standards, GMR-1 and GMR-2. The first main contribution is that we were able to completely reverse engineer the encryption algorithms employed. Both ciphers had not been publicly known previously. We describe the details of the recovery of the two algorithms from freely available DSP-firmware updates for satphones, which included the development of a custom disassembler and tools to analyze the code, and extending prior work on binary analysis to efficiently identify cryptographic code. We note that these steps had to be repeated for both systems, because the available binaries were from two entirely different DSP processors. Perhaps somewhat surprisingly, we found that the GMR-1 cipher can be considered a proprietary variant of the GSM A5/2 algorithm, whereas the GMR-2 cipher is an entirely new design. The second main contribution lies in the cryptanalysis of the two proprietary stream ciphers. We were able to adopt known A5/2 ciphertext-only attacks to the GMR-1 algorithm with an average case complexity of 2³² steps. With respect to the GMR-2 cipher, we developed a new attack which is powerful in a known-plaintext setting. In this situation, the encryption key for one session, i.e., one phone call, can be recovered with approximately 5065 bytes of key stream and a moderate computational complexity. A major finding of our work is that the stream ciphers of the two existing satellite phone systems are considerably weaker than what is state-oft-he-art in symmetric cryptography.

Press release. And news stories.

Tags: academic papers, cryptanalysis, cryptography, encryption, phones

Posted on February 16, 2012 at 12:22 PM • 10 Comments

Comments

Sam Jones • February 16, 2012 1:17 PM

News of this result has been circulating for some time, but it’s great to actually see the details. Here are two recent blog posts for those who don’t plan to read the paper:

http://cryptanalysis.eu/blog/2012/02/02/dont-trust-satellite-phones-the-gmr-1-and-gmr-2-ciphers-have-been-broken/

http://blog.cryptographyengineering.com/2012/02/sattelite-phone-encryption-is-terrible.html

Bob • February 16, 2012 9:42 PM

Why don’t they just use AES? Picking the algorithm should be the easy part in all of this. Can someone explain to me the temptation that exists in so many of these cases for people to use a proprietary algorithm???

Karellen • February 17, 2012 3:23 AM

“an average case complexity of 232 steps.”

should be:

“an average case complexity of 2³² steps.”

...--... • February 17, 2012 4:02 AM

All crypto can be broken do you really think the gov would let crypto go unbroken so whats the point of crypto–to keep the low level players guessing

vedaal • February 17, 2012 9:58 AM

What about using any ot the new (less-vulnerable than arc-4) eSTREAM ciphers?

Open Source, free for public use, vetted by EU ECRYPT,

ideal for mobile phone use …

(there might be a considerable market in i-phone, i-tab users willing to pay for encrypted ‘facetime’ that doesn’t have to go through wifi …)

vedaal

NobodySpecial • February 17, 2012 1:34 PM

@Bob – usual engineering compromises. It was developed from GSM and had to have some interoperation, it needed to be embedded in a cheap chip at the time the standard was set – usually years before it’s actually implemented.

It also needs to be suitable for a stream encryption where parts of the message might be lost/corrupted and you need to be able to recover by only re-sending very few blocks. This almost guarantees a the encryption is bad whatever algorithm you use!

Then the politics, it needs to be exportable to anywhere you want to use a sat phone – ie everywhere, but mostly the sort of underdeveloped places that we are friends with.

NobodySpecial • February 17, 2012 2:04 PM

… edit.. places we AREN’T friends with!

Nick P • February 18, 2012 12:59 PM

It should be no surprise. Most proprietary, secretive encryption schemes are weak. The only ones that might be an exception are the NSA’s Type 1 ciphers. They’re classified. I’d love to see an analysis of those.

ᴀnonymous • February 19, 2012 2:30 PM

@NobodySpecial:
Not unreasonable points, but …

” … It was developed from GSM and had to have some interoperation, …”

The described algorithm is sufficeintly different that it will not interoperate.

” … it needed to be embedded in a cheap chip at the time the standard was set”

Not cheap at all: sat phones are still quite expensive equipment (over a thousand dollars per unit for a new one, although 2nd hand ones are apparently widely available and much cheaper), but back in the mid-1990s when these standards were being developed, they were $3,000/unit (equivalent to about $4000 in today’s money) and $7/minute for air time. A couple of hundred bucks for a secure cipher chip would not have been a big deal. And by the late 1990s, high speed triple DES cipher chips were a lot cheaper than that.

” … It also needs to be suitable for a stream encryption where parts of the message might be lost/corrupted and you need to be able to recover by only re-sending very few blocks. This almost guarantees a the encryption is bad whatever algorithm you use!”

Actually, CFB mode on a block cipher does this, and yet is a secure method (if the underlying block cipher is secure). CFB mode does still cause some error expansion so you need to be sure that the BER (after and FEC is applied) is well below 1 uncorrected error per frame.

It’s true that if your corrected BER is on the order of 1 per frame or more, you can’t tolerate any error expansion at all so you must use a completely malleable system. (Even authenticators don’t help, if every 2nd frame fails authentication!) However at that point you are only a few dB away from the system becoming completely unusuable anyway.

“..Then the politics, it needs to be exportable to anywhere …”

I suspect this is the real reason. It is widely believed / suspected to be the reason A5 was crippled for GSM, and here we see an A5-like cipher developed by another European telephony association. I wouldn’t be suprised if it was developed by the exact same agency.

NobodySpecial • February 20, 2012 4:21 PM

From my experience, the final cost of the hardware has nothing to do with how manufacturing will try and save 10c on a component!

It’s not so much deliberately weakening the encryption to allow eavesdropping – the government just has to have a quite word with the operator, they have the unencrypted signal anyway.
The big problem is that governments (esp. the US) used to be paranoid about exporting crypto – even limiting the version of SSL allowed in browsers. So a sat phone which had AES but which you couldn’t legally use in Africa, Asia, S. America or at sea is a bit useless

Schneier on Security

Cryptanalysis of Satellite Phone Encryption Algorithms

Comments

Leave a comment Cancel reply