Slashdot Mirror
Second 3G GSM Cipher Cracked
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.'"
The technique enables them to recover a full key by using a tactic known as a related-hey attack ...
Certainly you meant related-key attack since the paper by and large discusses related key attacks before explaining their sandwich attack.
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.
To give you more specific numbers from the conclusion of the paper:
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.
Er, I believe you meant to say 4 related keys, 2^26 data, 2^30 bytes of memory and 2^32 time. As you will see in the conclusion of the paper:
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 2^76 to the very practical 2^32.
After all a time complexity of 232 should take any computer at most a few seconds while 2^32 approaches the two hour-ish mark.
My work here is dung.
Yes, those are powers of 2. Yes, those conclusions are correct. Poppa Poster is correct. Original poster is a dolt.
Editors that approved dolt are bigger dolts.
Cheers and all that.
E
What is 3G GSM ? As far as I know GSM is a 2G standard.
This encryption is also used in UMTS, which is the successor of GSM and a 3G standard.
with an amazingly high probability of 214
O.K., the abstract from TFA says 1/2^14, but I still fail to see how this is 'amazingly high'.
CC.
TaijiQuan (Huang, 5 loosenings)
with an amazingly high probability of 214.
Yep that is amazing. Not the same thing as 2^(-14). Not at all.
(And just to preempt some wise ass C programmer, I do not mean -16.)
"I'm on the train..."
The phrase "a group" is singular. So it's "a group of cryptographers has developed". Without the phrase "a group" making it singular, it would be "cryptographers have developed".
(Really, niggling about the grammar when there are so many other errors in the summary...)
GCHQ Quantum Insert installed. If only our tongues were made of glass, how much more careful we would be when we speak
The probability should be p=2^-14. A p value of 214 would be an amazingly low probability.
This is why we computer scientists need to study more math.
In British English, 'have' is indeed correct. US English is a bit different in this regard IIRC.
"Arsenal have defeated ..." vs. "Arsenal has defeated ..."
At least that's how I remember it from over a decade ago.
________
Entranced by anime since late summer 2001 and loving it ^_^
Thanks for clarifying that. My bad for acting like a debugger and stopping at the first wrongly identified mistake.
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). 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.
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.
That is, it should be 2^{-14} -- this is the danger with posting in the morning before finishing my coffee...
That's okay, it works as a review. People like me learn all our grammar from Slashdot.
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.
OK, who's the dork who named these?
Rob
For a nanosecond I was worried that Mugen Tenshin ninja cryptographers had attacked Kasumi!
To try to elaborate on what the parent is trying to say, US English has the concept that when you take many things and lump them into a single 'compound' item, the item is singular, so a "Galaxy" is a singular noun, a "Solar System" is a singular noun, and a "group" is a singular noun. It does make a certain sort of sense, if you think about it, though I can also see the argument for treating a 'group' as a plural.
The most confusing thing is that when people see a phrase like "a group of scientists {verb}", since scientists (which is plural) is the very last thing before the verb, people tend to think the object of the sentence is "scientists", when it's actually "group".
If you think your phone calls were secure to begin with (at least in the US), man I have a couple bridges for sale. Everything you say on a phone, anything you do online can be intercepted by the Feds. Here's just one example of methods implemented in carrier-level equipment that specifically allows ease-dropping. http://en.wikipedia.org/wiki/Lawful_interception
Just as I was saying, just use AES, and never roll your own cryptography.
Generally correct, though in British English, collective nouns can take plural verbs.
http://en.wikipedia.org/wiki/American_and_British_English_differences
Check out my sci-fi/humor trilogy at PatriotsBooks.
The British might say "A group of cryptographers have developed". To an American, it sounds more natural as written above. A lot of students of English outside of America are likely to have been taught more British patterns of usage.
It is pitch black. You are likely to be eaten by a grue.