GSM 3G encryption much weaker than thought

[phongn]

Remember this thread on GSM crypto? Well, Orr Dunkelman, Nathan Keller and Adi Shamir have just shown serious weaknesses in the A5/3 cipher designed to replace the old A5/1 cipher in widespread use.

Abstract: The privacy of most GSM phone conversations is currently protected by the 20+ years old A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They will soon be replaced in third generation networks by a new A5/3 block cipher called KASUMI, which is a modified version of the MISTY cryptosystem. In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of 2-14. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, 226 data, 230 bytes of memory, and 232 time. These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity. Interestingly, neither our technique nor any other published attack can break MISTY in less than the 2128 complexity of exhaustive search, which indicates that the changes made by the GSM Association in moving from MISTY to KASUMI resulted in a much weaker cryptosystem.

...

Summary: In this paper we develop a new sandwich attack on iterated block ciphers, and use it to reduce the time complexity of the best known attack on the full KASUMI from an impractical 276 to the very practical 232. However, the new attack uses both related keys and chosen messages, and thus it might not be applicable to the specific way in which KASUMI is used as the A5/3 encryption algorithm in third generation GSM telephony. Our main point was to show that contrary to the assurances of its designers, the transition from MISTY to KASUMI led to a much weaker cryptosystem, which should be avoided in any application in which related key attacks can be mounted.

[Edi]

My superiors are just going to fucking love this. The company just got done with a thorough review of the A5/1 crypto problems and then this comes out.

The Register article that puts it in a little bit easier to read form. In any case, here we are again, and those are problems with the algorithm itself, not the implementation.

[sketerpot]

What's stopping them from using something mainstream like AES, instead of a now-broken algorithm named after a Pokemon character? Do they have special requirements that AES doesn't meet?

[phongn]

What's stopping them from using something mainstream like AES, instead of a now-broken algorithm named after a Pokemon character? Do they have special requirements that AES doesn't meet?

Did you even read the abstract and summary? MISTY is not the problem, KASUMI is. Also, did you consider when the ciphers might've been selected and developed? AES was not available at the time the cipher for UMTS was being developed.

[sketerpot]

What's stopping them from using something mainstream like AES, instead of a now-broken algorithm named after a Pokemon character? Do they have special requirements that AES doesn't meet?

Did you even read the abstract and summary? MISTY is not the problem, KASUMI is. Also, did you consider when the ciphers might've been selected and developed? AES was not available at the time the cipher for UMTS was being developed.

Of course I read it. First, Misty and Kasumi are the English and Japanese names of the same Pokemon character, although in this case it looks like the people who came up with the name did it as an unrelated pun. Second, I was talking about replacing the algorithm in the future. Of course they're not going to suddenly recall all the existing phones. I just want the next standard that comes along to have better encryption, and I'm curious how that would happen.

For example, does their protocol support negotiating alternate encryption methods? If so, then newer phones could co-exist peacefully with older, easier-to-tap ones, and we could migrate to a more secure encryption method smoothly.

[Skgoa]

AES might be to complicated to encrypt calls on the fly. But yes, a better crypto system is exactly what has to implemented ASAP. Legacy phones, base stations, routers etc. will be a major problem though.* I think for now the entire GSM infrastructure can be assumed to be wide open, since more and more information of how it all works has been found out lately. Damn, it used to be that you just couldn't trust the phone itself - which could be mostly dealt with by installing your own firmware/OS. Well, I guess we have to and another layer of encryption before the data leaves the phone. (I.e. end to end encryption between the two communicating phones.)


* Let me clarify what I mean by that:
Your shiny new Android phone won't do you any good if the cell you log into does not yet support the newer encryption - and it won't get that capability until enough people have phones that would benefit from replacing it.

[Edi]

* Let me clarify what I mean by that:
Your shiny new Android phone won't do you any good if the cell you log into does not yet support the newer encryption - and it won't get that capability until enough people have phones that would benefit from replacing it.

Which is going to take YEARS at the very least. A lot of operators are only partially capable of switching from A5/1 to A5/3 even now, and you actually have to be able to switch your entire network at once or things will get really fucked up really, really fast.

All of that will cost a significant amount of money.

[sketerpot]

AES might be to complicated to encrypt calls on the fly.

I did some research, and it turns out that AES hardware accelerators are dirt cheap in terms of silicon real-estate and can easily handle the throughput needed for 3G or 4G telephony, with very small latency. And the keys are only 128-256 bits. And it's a very sturdy, well-tested algorithm, with no signs of being practically broken anytime in the foreseeable future. It should be technically feasible to use AES encryption on telephones. Of course, as Edi points out, technical feasibility isn't the whole story.

[phongn]

First, Misty and Kasumi are the English and Japanese names of the same Pokemon character, although in this case it looks like the people who came up with the name did it as an unrelated pun.

So ... why would you think they named it after Pokemon characters without any evidence?

I did some research, and it turns out that AES hardware accelerators are dirt cheap in terms of silicon real-estate and can easily handle the throughput needed for 3G or 4G telephony, with very small latency. And the keys are only 128-256 bits. And it's a very sturdy, well-tested algorithm, with no signs of being practically broken anytime in the foreseeable future. It should be technically feasible to use AES encryption on telephones. Of course, as Edi points out, technical feasibility isn't the whole story.

AES' safety margin is becoming rather thin so there's some concern over it. It's pretty cheap to do now, especially as every Wifi device made in years has had it embedded in.