×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Second 3G GSM Cipher Cracked

Soulskill posted more than 4 years ago | from the dropping-like-encrypted-flies dept.

Encryption 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.'"

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

57 comments

Related-Key and Original Paper (5, Informative)

eldavojohn (898314) | more than 4 years ago | (#30736266)

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! (1)

gavron (1300111) | more than 4 years ago | (#30736300)

If only I had mod points.

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 (1)

gidds (56397) | more than 4 years ago | (#30736448)

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.

Re: Related-Key and Original Paper (5, Informative)

eldavojohn (898314) | more than 4 years ago | (#30736486)

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:Related-Key and Original Paper (-1, Flamebait)

Anonymous Coward | more than 4 years ago | (#30736502)

Even worse than the fact that they typoed a 3 letter word is that they didn't fatfinger it, they instead somehow confused their index finger with their middle finger.
Oh Slashdot contributors, how do your brains operate on anything higher than a limbic level, I'll never know.

Re:Related-Key and Original Paper (5, Funny)

Jurily (900488) | more than 4 years ago | (#30736758)

Mr. eldavojohn, you're under arrest for violating the Slashdot Anti-Proofreading Act.

Re:Related-Key and Original Paper (0)

Anonymous Coward | more than 4 years ago | (#30737048)

poop

3G GSM ? (4, Informative)

BorgDrone (64343) | more than 4 years ago | (#30736312)

Kasumi, also known as A5/3, is the standard cipher used to encrypt communications on 3G GSM networks

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:3G GSM ? (2, Informative)

sznupi (719324) | more than 4 years ago | (#30736414)

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:3G GSM ? (0)

Anonymous Coward | more than 4 years ago | (#30736904)

The generation is not determined by the speed. EDGE is 2G technology, since it's based on GSM, eventhough it's the latest advancement. The generation is determined by the underlying architechture, and since EDGE is a strap-on on a GSM network, it belongs to the second generation, just as HSDPA belongs to the third generation, since it's strapped on top of a UMTS architecture

Re:3G GSM ? (1)

Verdatum (1257828) | more than 4 years ago | (#30737054)

3G GSM is frequently used interchangeably to refer to 3GPP implementation of 3G, which is UMTS.

Re:3G GSM ? (1)

BorgDrone (64343) | more than 4 years ago | (#30742314)

Really ? I've never seen anyone use it like that, is this a US thing ?

Re:3G GSM ? (2, Informative)

Verdatum (1257828) | more than 4 years ago | (#30742724)

I think it's more of a common innacuracy than anything. The GSM standard is now maintained by 3GPP, and 3GPP developed the UMTS standard, based to some extent on the GSM architecture. So people presume 3G GSM is a valid way to distinguish the technology as separate from the CDMA2000 3G technology. I don't know about other countries, but in the US, "UMTS" and "3GPP" are not well known terms to consumers, but "GSM" and "3G" are.

Re:3G GSM ? (3, Interesting)

LucidBeast (601749) | more than 4 years ago | (#30737592)

UMTS allows operator to choose chiphers as long as it confirms to the 3GPP specification see: http://www.3gpp.org/ftp/Specs/html-info/33105.htm [3gpp.org] .

All 3G cards I've seen have used rijndael (AES).

Re:3G GSM ? (3, Informative)

lobsterturd (620980) | more than 4 years ago | (#30740284)

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:3G GSM ? (0)

Anonymous Coward | more than 4 years ago | (#30739600)

UMTS is still a specification from the GSMA.

Re:3G GSM ? (0)

Anonymous Coward | more than 4 years ago | (#30739892)

No it isn't. It's from the 3GPP.

Again, Failing ... (1)

foobsr (693224) | more than 4 years ago | (#30736530)

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.

Re:Again, Failing ... (0)

Anonymous Coward | more than 4 years ago | (#30736808)

O.K., the abstract from TFA says 1/2^14, but I still fail to see how this is 'amazingly high'./quote

Then you don't know crypto. That's a very high probability to get in cryptanalysis, and constitutes a severe certificational weakness in a cipher.

Re:Again, Failing ... (0)

marcansoft (727665) | more than 4 years ago | (#30737502)

Hint: it takes on the order of milliseconds for a computer to do something 2^14 = 16384 times.

Coping, pasting and typesetting (1)

sakonofie (979872) | more than 4 years ago | (#30736598)

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.)

Actually (0, Redundant)

Rikiji7 (1182159) | more than 4 years ago | (#30736638)

Source says:

...by using only 4 related keys, 2^26 data, 2^30 bytes of memory, and 2^32 time.

Copy-paste lost some exponentials...

Language lesson first... (0, Offtopic)

Asadullah Ahmad (1608869) | more than 4 years ago | (#30736844)

"A group of cryptographers has developed...."

Shouldn't this be "have"?. I admit English is not my first language, but I think I remember those 3rd grade chapters.

Re:Language lesson first... (0)

Anonymous Coward | more than 4 years ago | (#30736986)

Nope, "has" is correct here. "Group" is a collective noun.

Re:Language lesson first... (1)

JSBiff (87824) | more than 4 years ago | (#30737962)

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".

Re:Language lesson first... (1)

metamatic (202216) | more than 4 years ago | (#30736990)

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:Language lesson first... (1)

Asadullah Ahmad (1608869) | more than 4 years ago | (#30737088)

Thanks for clarifying that. My bad for acting like a debugger and stopping at the first wrongly identified mistake.

Re:Language lesson first... (2, Interesting)

Anonymous Coward | more than 4 years ago | (#30737314)

That's okay, it works as a review. People like me learn all our grammar from Slashdot.

Re:Language lesson first... (1, Offtopic)

khellendros1984 (792761) | more than 4 years ago | (#30741390)

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.

EN_UK and EN_US (1, Offtopic)

Inf0phreak (627499) | more than 4 years ago | (#30737056)

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:EN_UK and EN_US (1)

Asadullah Ahmad (1608869) | more than 4 years ago | (#30740012)

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:EN_UK and EN_US (0)

Anonymous Coward | more than 4 years ago | (#30740140)

I would like to agree with lnf0phreak, and point out the reason for the difference:

British English, "A group" is considered plural, because it is made of numerous individuals.

American English, "A group" is singular, because there is only one group.

Both can be considered correct, just different conventions, really.

Re:Language lesson first... (0, Offtopic)

Paul Jakma (2677) | more than 4 years ago | (#30740538)

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 placing of the possessive '), indeed it was the normal usage once upon a time. However, the tendency to treat companies as singular, distinct things is becoming (has become) the norm in British english too. It seems nicer to use the plural to me, as it reinforces the idea that companies are not single-minded entities.

Related hey attack? (0)

Anonymous Coward | more than 4 years ago | (#30736950)

Would that be a 'needle in a hey-stack' attack?

The probability is not 214 (1)

RandCraw (1047302) | more than 4 years ago | (#30736996)

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:The probability is not 214 (2, Insightful)

marcansoft (727665) | more than 4 years ago | (#30737552)

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 (5, Insightful)

dachshund (300733) | more than 4 years ago | (#30737096)

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 (2, Interesting)

dachshund (300733) | more than 4 years ago | (#30737146)

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:Shamir and his techniques (1, Informative)

Anonymous Coward | more than 4 years ago | (#30737742)

Both Orr and Nathan are post-docs. That said, I am sure they spent lots of time working hard on this one.

Re:Shamir and his techniques (0)

Anonymous Coward | more than 4 years ago | (#30738194)

Then someone needs to get in touch with Nathan and tell him to update his web page!

Re:Shamir and his techniques (1)

radtea (464814) | more than 4 years ago | (#30737828)

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:Shamir and his techniques (1)

HonestButCurious (1306021) | more than 4 years ago | (#30744314)

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)

Like it was private to begin with (1)

papasui (567265) | more than 4 years ago | (#30738142)

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 [wikipedia.org]

Re:Like it was private to begin with (2, Insightful)

horza (87255) | more than 4 years ago | (#30742346)

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.

Ahem. (1)

QuoteMstr (55051) | more than 4 years ago | (#30738620)

Just as I was saying [slashdot.org] , just use AES, and never roll your own cryptography.

Re:Ahem. (1)

horza (87255) | more than 4 years ago | (#30741792)

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.

Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...