Slashdot Mirror

← Back to Stories (view on slashdot.org)

Second 3G GSM Cipher Cracked

Posted by Soulskill on 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.'"

8 of 57 comments (clear)

  1. Related-Key and Original Paper by eldavojohn · · 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 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.
    1. Re: Related-Key and Original Paper by eldavojohn · · 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).

      --
      My work here is dung.
    2. Re: Related-Key and Original Paper by error_frey · · Score: 2, Informative

      It should be 2^(-14)

  2. 3G GSM ? by BorgDrone · · Score: 4, Informative

    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.

    1. Re:3G GSM ? by sznupi · · Score: 2, 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.

      --
      One that hath name thou can not otter
    2. Re:3G GSM ? by lobsterturd · · 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

    3. Re:3G GSM ? by Verdatum · · Score: 2, Informative

      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.

  3. Re:Shamir and his techniques by Anonymous Coward · · 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.