Shostack + Friends Blog Archive

Another Week, Another GSM Cipher Bites the Dust

Orr Dunkelman, Nathan Keller, and Adi Shamir have released a paper showing that they’ve broken KASUMI, the cipher used in encrypting 3G GSM communications. KASUMI is also known as A5/3, which is confusing because it’s only been a week since breaks on A5/1, a completely different cipher, were publicized. So if you’re wondering if this is last week’s news, it isn’t. It’s next week’s news.

The paper isn’t up on IACR’s Eprint archive yet, but copies of it are circulating around privately. I’m writing about it with Adi Shamir’s permission.

KASUMI is a modified version of the MISTY cipher. The KASUMI designers made MISTY faster and more hardware friendly by changing the key schedule and modifying some internal parameters. However, they also made it vulnerable to related key attacks.

Of all the weaknesses that a cipher can have, related key attacks are the ones to worry about least. Operationally, crypto engineers know that they should never reuse keys and when in doubt just pull another one off of the random number generator. Consequently, this doesn’t mean that the guys at Weizmann Institute of Science are listening to 3G calls.

Nonetheless, related key attacks are bad to have because implementers do screw up, and related key attacks indicate that the cipher designers didn’t have as tight a handle on things as they thought they did. It is no cause for panic, but it is no cause for either warmness or fuzziness (particularly since the DKS team point out that the KASUMI designers wrote that they’d taken care of related-key issues when they simplified MISTY into KASUMI).

Moreover, the attack here is completely practical. Here is a quote from the abstract:

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, 2²⁶ data, 2³⁰ bytes of memory, and 2³² 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 2¹²⁸ 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.

It will be interesting to see the response from the GSM Association. They have the opportunity to show leadership. If they recognize that this is a real problem, reassure us that it’s not a catastrophe, and show that they’re taking it seriously, then this can be an all-around good thing for them and us.

We’re all adults (well, okay, most of us are adults and act like adults some of the time), and if we know that there will be an upgrade in a few years, then that’s great. We lived through the WEP issues. We are living through the SSL evil proxy issues. This is less acute than either of those. But we need to have some assurance that in a few years, we’ll just get wireless devices with a safety net. Their challenge is to have a response before this news metastasizes into a common perception that 3G crypto is worthless.

Photo “bag_contents” courtesy of openfly. Selected because it looked good and it was the only photo that came back on a search of “3g crypto.”

Originally published by cwalsh on 11 Jan 2010
Last modified on 11 Jan 2010
Categories:   emergent chaos   privacy   Risk   Security   Uncategorized