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.'"
Related-Key and Original Paper (Score:5, Informative)
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 [wikipedia.org] since the paper [iacr.org] 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.
MOD PARENT UP! (Score:2)
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
Re:Related-Key and Original Paper (Score:4, Interesting)
Re: Related-Key and Original Paper (Score:2)
Doesn't explain how you can have a probability of 214, though. And a probability of 2^14 would just be worse.
Re: Related-Key and Original Paper (Score:5, Informative)
That makes a lot more sense. Doesn't explain how you can have a probability of 214, though. And a probability of 2^14 would just be worse.
Uh yeah, that's the funniest error of them all. If you read the summary on the paper that I linked it's two raised to the power of negative fourteen which copy pastes to 214 but should be something like 2^(-14).
Re: (Score:2, Informative)
Re: (Score:2)
It should be (expt 2 -14).
Re:Related-Key and Original Paper (Score:5, Funny)
Mr. eldavojohn, you're under arrest for violating the Slashdot Anti-Proofreading Act.
3G GSM ? (Score:4, Informative)
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.
Re: (Score:3, Informative)
Hm, technically EDGE falls under 3G speeds, just. But generally 3G networks built on top of existing GSM infrastructure are still often taken under "GSM" umbrella.
Re: (Score:2)
Re: (Score:1)
Really ? I've never seen anyone use it like that, is this a US thing ?
Re: (Score:3, Informative)
Re: (Score:1)
Re:3G GSM ? (Score:4, Interesting)
All 3G cards I've seen have used rijndael (AES).
Re: (Score:3, Informative)
This isn't necessarily true. Operators can use ciphers of their choice for functions that occur within the SIM card (such as authentication and key derivation), but data sent over the air can only be encrypted with Kasumi or (since UMTS Rel-7) Snow 3G. http://www.3gpp.org/ftp/Specs/html-info/33102.htm [3gpp.org]
Re: (Score:2)
Again, Failing ... (Score:2)
O.K., the abstract from TFA says 1/2^14, but I still fail to see how this is 'amazingly high'.
CC.
Re: (Score:1)
Hint: it takes on the order of milliseconds for a computer to do something 2^14 = 16384 times.
Coping, pasting and typesetting (Score:1)
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.)
And the first decryption yielded this.... (Score:2, Funny)
Re: (Score:2)
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}",
Re: (Score:2)
Generally correct, though in British English, collective nouns can take plural verbs.
http://en.wikipedia.org/wiki/American_and_British_English_differences [wikipedia.org]
Re: (Score:2)
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...)
Re: (Score:1)
Re: (Score:2, Interesting)
That's okay, it works as a review. People like me learn all our grammar from Slashdot.
Re: (Score:2, Offtopic)
EN_UK and EN_US (Score:2, Offtopic)
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.
Re: (Score:1)
The point about "has" intended for "Group of cryptographers" does makes sense, but I like the British vs US English possibility as well, because I learnt British English.
Though this is the first time I am running into UK vs US difference other than the likes of "colour vs color". I'll have to research more into it.
Re: (Score:1, Offtopic)
Yes you're right.
Collective nouns generally are plural. Some nouns are treated as singular, even when you could consider them as groupings. Where the line lies is somewhat subjective. Wrt group, it's very emphatically a collective noun and there should be very little reason to want to consider it a singular, distinct entity from its constituents.
Another example are companies. It is acceptable to consider these too as plural collectives, e.g. "My company have developed", or "ACMEs' products" (note the placi
The probability is not 214 (Score:1)
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.
Re: (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).
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.
Ha, correction (Score:3, Interesting)
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...
Re: (Score:1, Informative)
Both Orr and Nathan are post-docs. That said, I am sure they spent lots of time working hard on this one.
Re: (Score:2)
This is the danger with cutting and pasting mathematics.
Actually it's a danger with getting your tech news from a site with no editorial oversight, or at best editors who have so little clue about the subject that they let nonsense like this get through (I know zip about cryptography, but knew enough that the values in the summary made no sense, although not enough to infer the correct values. That's how low the bar is that the /. editors fail to reach.)
Re: (Score:1)
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.
Related key attacks are very feasible if a block cipher is used as a building block for a hash function. FYI XBOX was broken [xbox-linux.org] with a related key attack.
(credit goes to Orr Dunkelman for finding this out)
Gotta crack 'em all! (Score:2)
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
Re: (Score:1)
Freaking ninja cryptographers! (Score:1)
Re: (Score:1)
Like it was private to begin with (Score:2)
Re: (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
Ahem. (Score:2)
Just as I was saying [slashdot.org], just use AES, and never roll your own cryptography.
Re: (Score:2)
AES became a standard on November 26, 2001. The GSM standard was published in 1990, over 10 years earlier. The fact AES is NSA approved means security agencies can probably crack it in reasonable time, but it should certainly be strong enough for most uses.
Phillip.