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.
[T]he 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, 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.
If breaking 80%+ of the worlds GSM networks wasn’t enough for last week, I guess they’re breaking the rest this week.