Forgot your password?
typodupeerror
Encryption Wireless Networking

Second 3G GSM Cipher Cracked 57

Posted by Soulskill
from the dropping-like-encrypted-flies dept.
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.'"
This discussion has been archived. No new comments can be posted.

Second 3G GSM Cipher Cracked

Comments Filter:
  • by eldavojohn (898314) * <eldavojohn AT gmail DOT com> on Tuesday January 12, 2010 @08:48AM (#30736266) Journal

    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.

  • 3G GSM ? (Score:4, Informative)

    by BorgDrone (64343) on Tuesday January 12, 2010 @08:53AM (#30736312) Homepage

    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: (Score:3, Informative)

      by sznupi (719324)

      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.

    • by Verdatum (1257828)
      3G GSM is frequently used interchangeably to refer to 3GPP implementation of 3G, which is UMTS.
      • by BorgDrone (64343)

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

        • Re: (Score:3, Informative)

          by Verdatum (1257828)
          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.
    • by genik76 (1193359)
      3G GSM is shorthand for "3G and GSM".
    • Re:3G GSM ? (Score:4, Interesting)

      by LucidBeast (601749) on Tuesday January 12, 2010 @10:29AM (#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).

  • 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.
    • Hint: it takes on the order of milliseconds for a computer to do something 2^14 = 16384 times.

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

      by marcansoft (727665)

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

  • by dachshund (300733) on Tuesday January 12, 2010 @09:55AM (#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 (Score:3, Interesting)

      by dachshund (300733)

      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)

      by Anonymous Coward

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

    • by radtea (464814)

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

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

  • 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 [wikipedia.org]!
  • 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: (Score:3, Insightful)

      by horza (87255)

      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

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

    • by horza (87255)

      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.

The reason that every major university maintains a department of mathematics is that it's cheaper than institutionalizing all those people.

Working...