Second 3G GSM Cipher Cracked 57
Trailrunner7 writes "A group of cryptographers has developed a new attack that has broken Kasumi, the encryption algorithm used to secure traffic on 3G GSM wireless networks. The technique enables them to recover a full key by using a tactic known as a related-key attack, but experts say it is not the end of the world for Kasumi. Kasumi, also known as A5/3, is the standard cipher used to encrypt communications on 3G GSM networks, and it's a modified version of an older algorithm called Misty. In the abstract of their paper, the cryptographers say the attack can be implemented easily on one standard PC. '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 214. 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.'"
Shamir and his techniques (Score:5, Insightful)
First of all, the amazingly high probability should be 2^14 (or 1/2^14 = 1 / 16,384), not "214". This is the danger with cutting and pasting mathematics. In a slightly simplified explanation, distinguishing attacks work by looking at encrypted data and trying to distinguish it from random bits. This means that the distinguisher succeeds with the probability above, which may not seem very high, but believe me --- it's much higher than what it should be for a cipher like this. And as they show, efficient distinguishing attacks can lead to nastier things like key recovery.
I saw Adi Shamir stand up in front of a crowd at Crypto 2008 and introduce a new set of techniques he and his colleagues had developed for simplifying complex algebraic equations. People jokingly asked him if he thought it might work against AES (yes, it did [pgp.com]). I haven't seen this paper, but my guess is that they're running around applying their techniques to everything they can find. And so Kasumi bites the dust. (Meaning that I must update my course slides, agh.)
More to the point, this is unlikely to be a practical issue right now because it's a related key attack. You have to encrypt something with multiple keys that are closely related (similar in many respects) before the attack applies. This usually doesn't happen unless the implementers are idiots. But the point is that it's bad news --- related key attacks are the camel's nose under the tent for much worse things to come. I'd say they should upgrade to AES, but I'm not even sure if that's a great idea :)
Oh, and I'm doing the thing I hate the most: giving the senior person all the credit. No doubt an equal or greater share of the credit goes to Orr Dunkelman and Nathan Keller, his hungry PhD student and post-doc who probably spent the last zillion hours of their lives working this out in their lab only to see people like me attribute all of their work to Shamir. Good job, guys.
Re:The probability is not 214 (Score:3, Insightful)
a p value of 214 would be an amazingly impossible probability. Probability goes from 0 to 1, and 1 is the highest (most likely). 2^-14 = (1 in 16384) is "low" by human standards but amazingly high by crypto standards (most importantly, because computers can try something 16384 times in a split second).
Re:Like it was private to begin with (Score:3, Insightful)
First you are missing the point. If you have access to the exchange of course you can listen. This either requires a warrant, or some good social engineering skills. However intercepting between mobile and base station is untraceable and can be done by anybody. By tabloid journalists, criminals, jealous spouses, or somebody that just wants to cause mischief.
Second it is A5/3 which has been broken. A5/1 is used in Europe and A5/2 outside (the US probably uses a modified A5/1 with reduced key length to allow real-time NSA intercepts) for standard GSM voice calls. A5/1 is still secure as far as we know.
Phillip.