Hello? Can you hear me now?

December 28, 2009 2:14 PM

Karsten Nohl and a team of fellow researchers has cracked the 64-bit encryption used in 80% of the world's GSM phones. Nohl had previously cracked the encryption in the MIFARE smartcard system, demonstrating that the encryption on that device can be cracked in approximately no time whatsoever. These, of course, aren't the first gaping holes in cellphone security to come to light; indeed, lack of security seems to be part of the design spec. Perhaps all new cellphones should be just be distributed with a deck of cards.
posted by kaibutsu (51 comments total)

With each passing day, the future looks more and more like something from a William Gibson novel.

Good times... good times.

See you in the sprawl.
posted by PROD_TPSL at 2:33 PM on December 28, 2009 [2 favorites]

You mean to tell me it could be risky to send sensitive information whizzing through the air?
posted by Sys Rq at 2:38 PM on December 28, 2009 [3 favorites]

"The association noted that hackers intent on illegal eavesdropping would need a radio receiver system and signal processing software to process raw radio data, much of which is copyrighted."

So a hacker would be willing to break numerous laws to listen in on an encrypted coversations but wouldn't dare break copyright on the signal processing software?

Did they manage to say that with a straight face?
posted by Static Vagabond at 2:38 PM on December 28, 2009 [6 favorites]

They didn't "crack" it. What they did was reverse-engineer the algorithm.

This makes a brute-force attack possible, but 64-bit key strength still isn't all that easy to break.
posted by Chocolate Pickle at 2:39 PM on December 28, 2009

This makes a brute-force attack possible, but 64-bit key strength still isn't all that easy to break.

Are you sure about that? I'm not sure how much the keys parallel one another or what kind of brute force options this makes available, but I know that it's possible to go through a 64bit WEP key in minutes.
posted by quin at 2:59 PM on December 28, 2009

kaibutsu: “Karsten Nohl and a team of fellow researchers has cracked the 64-bit encryption used in 80% of the world's GSM phones.”

Sorry that I haven't read the links yet, but: is this simply a misstatement, or do 20% of GSM phones really not use 64-bit encryption? I was under the impression that all of them did.
posted by koeselitz at 2:59 PM on December 28, 2009

The GSM Association, the industry group based in London that devised the algorithm and represents wireless operators, called Mr. Nohl’s efforts illegal and said they overstated the security threat to wireless calls.

“This is theoretically possible but practically unlikely,” said Claire Cranton, a GSM spokeswoman, noting that no one else had broken the code since its adoption. “What he is doing would be illegal in Britain and the United States. To do this while supposedly being concerned about privacy is beyond me.”

Are these people for real? That’s the best they can come up with? “Yes, they broke our algorithm but nobody would actually do this because it’s against the law”? Great. I was hoping for something more like “Well, that sucks. Guess we should go get a real encryption algorithm for the next version of the standard.”

This is the same kind of security theatre performed by DHS and TSA, and it annoys the hell out of me.
posted by spitefulcrow at 3:03 PM on December 28, 2009 [11 favorites]

interesting though somewhat dated news on the gsm front -- these guys have been selling turnkey gsm encryption breakers and eavesdroppers for years --> http://www.endoacustica.com/gsm_interceptor.htm .
posted by 3mendo at 3:07 PM on December 28, 2009

these guys have been selling turnkey gsm encryption breakers and eavesdroppers for years

They mention that in the paper. Half the purpose of this is to show, without any doubt, that it is possible to crack A5/1. Part of this is to create an entire open source toolset that will also Joe Hacker on the street to do so.
posted by zabuni at 3:19 PM on December 28, 2009

But the A5/1 algorithm is a 64-bit binary code, the modern standard at the time it was developed, but simpler than the 128-bit codes used today to encrypt calls on third-generation networks. The new codes have twice as many 0’s and 1’s.

So the 3G networks are 128-bit?
posted by birdherder at 3:24 PM on December 28, 2009

With each passing day, the future looks more and more like something from a William Gibson novel

Nah, this future's got cellphones...
posted by pompomtom at 3:33 PM on December 28, 2009 [5 favorites]

This is why I only use point-to-point laser communication.
posted by Artw at 3:37 PM on December 28, 2009 [2 favorites]

So the 3G networks are 128-bit?

Most 3g networks use the Kasumi cipher to encrypt communications. It is 128 bits, but if you look at the paper I linked, it shares some of the same bit level-independent weaknesses of the a5/1 cipher, and has already been attacked theoretically.

If you look at the paper, you also see that they use the same damn encryption key for both the A5/1 (current encryption) and Kasumo/A5/3 (3g encryption), if you tell it to. So if you can get the phone to connect to a fake cell tower (rather trivial if you have the hardware), you can get the encryption key that way.
posted by zabuni at 3:49 PM on December 28, 2009

Static Vagabond: ""The association noted that hackers intent on illegal eavesdropping would need a radio receiver system and signal processing software to process raw radio data, much of which is copyrighted.""

Ladies and gentlemen of the jury, I introduce Exhibit A:openBTS, implementing the base station side. It's based on GNUradio, which itself has a long history. There have been multiple successful field test of the hardware, and plenty of recorded evidence that these do indeed work.

But what good is software if you need an expensive FPGA to run it? I present to you Exhibit B: USRP. Currently a bit pricey at $1400. But not copyrighted and the schematics are available.

It seems simple to do what's needed without violating copyright at least.
posted by pwnguin at 3:51 PM on December 28, 2009 [4 favorites]

actually the crack has been around for years. it's commonly known as court order. you need to be seriously screwed up to understand that system though.
posted by krautland at 3:55 PM on December 28, 2009 [2 favorites]

I thought it was common knowledge that all stream ciphers sucked.
posted by ryanrs at 4:28 PM on December 28, 2009

This is why I use two tin cans connected with string.
posted by Rangeboy at 4:32 PM on December 28, 2009

Sorry that I haven't read the links yet, but: is this simply a misstatement, or do 20% of GSM phones really not use 64-bit encryption? I was under the impression that all of them did.

I think that what they're saying is that this cipher is used by GSM 2G but not by GSM 3G. Most of the world hasn't transitioned yet.
posted by Chocolate Pickle at 4:34 PM on December 28, 2009

Nah, this future's got cellphones...

When I first started getting seriously serious about computers, in no small thanks to Mr. Gibson, I always thought the most unrealistic part was being able to jack into cyberspace on your deck from basically anywhere. No modem, no ethernet connection, no fiber-optics, just jack-in and your deck's already connected? Utterly unrealistic...

...says I, typing on a pocket-sized computer that has always-on 3G wireless data.

Neuromancer doesn't have cellphones because they're boring transitional tech.
posted by Slap*Happy at 4:45 PM on December 28, 2009 [5 favorites]

Hmm. There have been several attempts at building the cyberspace of Gibson/the metaverse of , all the time taking thinsg very literally and non-metaphorically, and basically it's given us Second Life and PS3 home.
posted by Artw at 4:52 PM on December 28, 2009 [2 favorites]

With each passing day, the future looks more and more like something from a William Gibson novel.

Stephenson, more like.

And the number of things from Snow Crash that have become actual products frightens me.
posted by ChurchHatesTucker at 5:00 PM on December 28, 2009 [3 favorites]

Chocolate Pickle: “This makes a brute-force attack possible, but 64-bit key strength still isn't all that easy to break.”

They're also apparently distributing a multi-terabyte "codebook." I haven't downloaded it yet, but it sounded to me like they've worked out some sort of Rainbow Tables type precomputation attack. If that's the case, it indicates that the algorithm has some serious fundamental flaws, and that there might be faster routes than brute keyspace exhaustion.

Also, I'm pretty sure that the GSM encryption algorithm (there are actually several, but I'm talking about A5/1) is fairly well-known. There's a description on Wikipedia; it doesn't look that complex, just a bunch of registers that get initialized using a 64-bit key and 22-bit salt (frame number). It's only implemented with a 54-bit key in practice though. So what I expect is happening is people are precomputing the various salt/key combinations, and then you'll be able to crack a transmission by just pattern-matching, without actually performing the hard calculations. There must be a little more to it, because 2^(54+22) is 2^76, which is an impractically large lookup table even by modern standards, so something else must be reducing the complexity, but I think that's the general idea.

Apparently previous attacks on GSM have relied on tricking a handset into falling back on A5/2, which is a weaker algorithm designed for use outside the US and Europe, and can be trivially broken.

There is already a new algorithm, A5/3, which is superior to A5/2, so the solution to all this is just for the operators to start offering it, and then new handsets can use it when it's available. Within a few years as handsets get upgraded, the old algorithm fades away.
posted by Kadin2048 at 5:11 PM on December 28, 2009 [1 favorite]

Don't people generally assume the U.S. government has broken all these years ago?
posted by smackfu at 5:55 PM on December 28, 2009

As I said when I heard about this, I used to listen in on cell calls on the old 1G analog network using a modified police scanner from Radio Shack. So, it's still better than it was for most of the time cell phones have existed even if the algorithm has been reverse-engineered.
posted by DecemberBoy at 6:10 PM on December 28, 2009

There is already a new algorithm, A5/3

Huh. They're moving to a public, fairly well-studied block cipher. They're not as stupid as I thought they've been in the past.
posted by ryanrs at 6:10 PM on December 28, 2009

Don't people generally assume the U.S. government has broken all these years ago?

Pretty much, yes, though sometimes they also do things that strengthen codes. DES was reviewed by the NSA and some values were "magically" changed without explanation. Those changes strengthened the algorithm against attack techniques that were then unknown in public.
posted by lowlife at 6:11 PM on December 28, 2009 [1 favorite]

And if that sounds like it might have been interesting, it wasn't. I just did it because it was possible and quickly found that people's phone conversations are invariably boring as hell. I got bored with it pretty quick.
posted by DecemberBoy at 6:11 PM on December 28, 2009

OT:

Neuromancer doesn't have cellphones because they're boring transitional tech.

I like this rationalisation, but it's still a rationalisation.

I can presently get a phone up the road that costs about the same as a decent case of beer, which my seven year old niece will have no trouble operating, and which gives me the same global reach as your Ono-Sendai VII. As I see it, this easily trumps the cyberdeck/saline gel/electrodes etc arrangement seen in Neuromancer, Burning Chrome etc as a mass-market communications product. (also, IIRC, according to the text a deck is a modem - it's just that the local end of the connection is a human brain).

Let's see Case call a cab at the last second using his deck (standing in the rain, fiddling with saline paste), compared to someone with even an old mobile phone.
posted by pompomtom at 6:24 PM on December 28, 2009

pompomtom - I'm not going to pick nits*, because yes, it is a rationalization - remember, science fiction isn't about tomorrow, it's about society and culture today, and Neuromancer was written in the early '80s. It's not prophecy, it's observation. The reason why it sometimes seems like prophecy is that Gibson really, really understood the world around him as it was, not as it was going to be.

And, besides, phones are boring transitional tech. Skype and Google Phone on a 3G device that costs about as much as a case of beer at the local 7-11, available at the local 7-11, with all-you-can-eat data for a buck a day on a pre-pay plan, will be reality in five years.

(*Actually, yes I am. The pedantry won't let me be! The deck was an obvious extrapolation of a personal computer, not a "modem into the mind." Most of the stuff in cyberspace, or at least the parts that interested a criminal like Case, was large corporate data installations. The 'trodes were custom, cowboy gear, Headbands were mass-market tech, for recreational and educational access to cyberspace. (Count Zero went into this.))
posted by Slap*Happy at 7:10 PM on December 28, 2009

Apparently previous attacks on GSM have relied on tricking a handset into falling back on A5/2, which is a weaker algorithm designed for use outside the US and Europe, and can be trivially broken.

Actually, previous attacks on GSM relied on setting up your own GSM base station, and intercepting the calls through pure MITM.

In the presentation they talk about how there are numerous indicators to detect that this is happening, but no phones actually try to detect this. Most likely because that's how law enforcement agencies usually wiretap GSM phones.
posted by ymgve at 7:20 PM on December 28, 2009

> I used to listen in on cell calls on the old 1G analog network using a modified police scanner from Radio Shack.
> And if that sounds like it might have been interesting, it wasn't. I just did it because it was possible and quickly found that people's phone conversations are invariably boring as hell. I got bored with it pretty quick.

Scanner's been able to make interesting things from it. And if he hasn't been the subject of an FPP yet, he should be some day (here's a documentary uploaded in two six-minute parts: one and two).
posted by ardgedee at 7:25 PM on December 28, 2009 [1 favorite]

Skype and Google Phone on a 3G device that costs about as much as a case of beer at the local 7-11, available at the local 7-11, with all-you-can-eat data for a buck a day on a pre-pay plan, will be reality in five years.

Not if AT&T has any say in the matter.
posted by Sys Rq at 7:26 PM on December 28, 2009

They don't. Not in the long term, anyway.
posted by ryanrs at 7:40 PM on December 28, 2009

And the number of things from Snow Crash that have become actual products frightens me.

Me too.

*goes to secret vault under house*

*feeds rat-thing*

*hugs Reason*

And now I feel better.
posted by quin at 7:42 PM on December 28, 2009 [2 favorites]

ymgve: any cite for that? intelligence agencies i can imagine, but law enforcement setting up their own towers? what happens when the subject moves out of range, to another tower? do they have their own parallel networks?

I would imagine law enforcement uses warrants and the cooperation of carriers. law enforcement is often keen to have evidence hold up in court as well, hence using warrants. Intelligence agencies have different needs and may be doing this fun stuff.

So now what? If you saw that you had roamed to a place whose tower only supported weaker (broken) crypto, would it impact what you discussed? If you had large business deals at stake would you change your behaviors?
posted by el io at 7:54 PM on December 28, 2009

This makes a brute-force attack possible, but 64-bit key strength still isn't all that easy to break.

64 bit key strength means, on average, you need 2³² tries to brute force the key. The EFF built a box that could brute force a 56 bit DES key (average tries, 2²⁸, so 64 bits is 8 times harder) in about two days.

Oh, and they built that box eleven years ago. Eleven years ago, the EFF could run 90 billion keys (or about 2²⁶ keys) *every second*, and it cost them $250K.

Let's apply Moore's Law -- double the CPU, or halve the cost, every 18 months. There has been just about 8 18-month periods in that time. So, eight doublings or halving. So, either you can spend $250K and run 2³⁴ keys per second (or, if you will, a bit over 17 trillion keys per second) or spend $970 and get Deep Crack Performance.

The real bad guys can spend far more than $250K. Hell, to use that fancy lingo the kids use, imagine a beowulf cluster of those things.

64-bit keys are far too weak. This is why the minimum AES key length is 128 bits, which is 64 doublings of a 64 bit key. If it took a second to brute force a 64 bit key, it would take 2⁶⁴ seconds to brute force a 128 bit key.

That's 1.84x10¹⁹ seconds, or 1.28x10¹⁶days, or 35 trillion millennia to brute force.

Or, if you will - when it doubt, double the problem space a few times.
posted by eriko at 9:01 PM on December 28, 2009 [1 favorite]

Sorry that I haven't read the links yet, but: is this simply a misstatement, or do 20% of GSM phones really not use 64-bit encryption? I was under the impression that all of them did.

Many countries use A5/2 which is weaker because the French & Americans wouldn't export the stronger crypto. Also, some North African countries use A5/0 (no encryption) because they want to be able to use cheap surveillance tech.
posted by atrazine at 9:12 PM on December 28, 2009 [1 favorite]

I'm not going to pick nits*

*Mick Dundee voice*

That's not nitpicking.

The deck was an obvious extrapolation ...

To you, perhaps, but that's not at all what the text says (along with a ton of networking stuff that Gibson didn't get at the time.) Again, I like your justification, but the text says it's a modem to the mind, and that the important part of the system that went beyond solid-state processing was exactly that.

(I don't expect Jules Verne knew too much about pressure seals, either...)
posted by pompomtom at 9:22 PM on December 28, 2009

The real bad guys can spend far more than $250K. Hell, to use that fancy lingo the kids use, imagine a beowulf cluster of those things.

Dude, no bad guy worth his control throne and white Persian cat is going to spend $250K on this! Instead you send out a billion or so e-mails from "uh Mike, in shipping" with a hilarious video that everyone needs to see attached. Four hours later the most time consuming part of your bot net's trying to factor a 30 digit prime number is the crappy ping most of your nodes have rather than the computation.

Now repeat after me. "No Mr. Bond, I expect you to Die!"

Good, but try to do it more from the diaphragm.
posted by Kid Charlemagne at 9:52 PM on December 28, 2009 [4 favorites]

ymgve: “Actually, previous attacks on GSM relied on setting up your own GSM base station, and intercepting the calls through pure MITM.”

We might be talking about the same thing. There are at least three ways of intercepting GSM calls that I was aware of, not counting the recent annoucement.

The most foolproof way of intercepting GSM is probably to just set up a base station (e.g. picocell or microcell) and then tap the IP or PSTN backhaul. It gets around the problem of encryption completely. I wouldn't call this MITM, although some people do, because you're not really in the "middle" of anything — you actually are providing call termination and acting as the cell tower.

Then there's an active MITM attack, which takes advantage of the poorly-designed encryption fallback mechanism. It's described in this paper (PDF). Basically you MITM between the victim handset and the network, and pretend (to the victim) that you're an A5/2-only network, grab the key, and then (to the network) pretend to be a normal A5/1 handset. Supposedly it creates less than a 1s delay during initial call setup (and this was on 2004 hardware) and is transparent once it gets going, provided the phone isn't set to display a warning when A5/2 is in use.

But the other thing that I've always thought is even better is only mentioned peripherally in that same paper:

Many networks initiate the authentication procedure rarely, and use the key created in the last authentication. An attacker can discover this key by impersonating the network to the victim mobile phone. Then the attacker initiates a radio-session with the victim, and asks the victim mobile phone to start encrypting using A5/2. The attacker performs the attack, recovers the key, and ends the radio session. The owner of the mobile phone and the network have no indication of the attack.

It's a MITM attack, but it's very brief, and it's asynchronous. You could record a bunch of traffic, and then once the call terminates get the key, as long as the authentication procedure hasn't happened again. So even someone with a phone that displays an A5/2 warning could potentially be vulnerable, because the key leakage happens after they've said whatever they're going to say (into a handset that wasn't displaying any warnings, because it was using the "good" A5/1 encryption).

It seems like a gaping security hole to reuse keys like that, but the more I read about GSM, the more I realize it's basically riddled with gaping security holes. Whether they exist as intentional choices (obviously this is the case of A5/2's insecurity) or design tradeoffs, it definitely hasn't been secure in a while.

Of course, the active attacks basically become academic the moment someone comes out with a workable, efficient passive attack — the exact same thing happened a few years ago with WEP. But it's probably a lesson for the future: once you start to see known-plaintext and elegant active attacks (ones that actually go after the cryptosystem or its implementation, not just bypass attacks like picocells) start to crop up, true breakage may not be far off.
posted by Kadin2048 at 9:59 PM on December 28, 2009 [5 favorites]

I know that it's possible to go through a 64bit WEP key in minutes.

That's not really saying anything about the strength of a 64 bit key because when you see airsnort/aircrack break WEP in minutes it's because of a weakness in the way that initialization vectors are chosen that allows deriving the key from a limited amount of traffic. It's not brute-forcing the keyspace at all.
posted by Rhomboid at 6:55 AM on December 29, 2009

(And also "64 bit WEP" means a 40 bit RC4 key, so even if it was brute forcing it, the keyspace is only 40 bits.)
posted by Rhomboid at 6:56 AM on December 29, 2009

What Rhomboid said. After I posted the link to the talk Drew Endy gave about hacking the genome I watched some of the other talks from the conference. A couple were really interesting, including one that opened up the play station 2 (maybe, maybe another counsole) by doing a timing attack on a 128 bit key. The punch line was that they implemented it so that instead of a 128 bit key, they had a 32 bit key and then three more just like it, which is not the same thing.

I've not gone diving into this case, but I dare say that it's a similar situation - you don't break the encryption - you break the broken implementation.
posted by Kid Charlemagne at 11:44 AM on December 29, 2009

My phone has a little camera.
posted by Skot at 12:23 PM on December 29, 2009 [3 favorites]

eriko: 64 bit key strength means, on average, you need 2³² tries to brute force the key.

I think you have the math wrong. Brute forcing a 64-bit key would take on average 2⁶⁴/2 = 2⁶³ trials. That's two billion times more than 2³².
posted by mhum at 12:55 PM on December 29, 2009 [1 favorite]

that's how law enforcement agencies usually wiretap GSM phones.

No, they go straight to the server. I used to work for a cell phone company, and while we weren't supposed to know when there was a tap, I hung out with the engineers, and it was pretty obvious that we got a court order roughly once a week...and we had less than 5% of the local market.
posted by Jimmy Havok at 1:38 PM on December 29, 2009

mhum: I think eriko has the math right but is describing the wrong problem (using the birthday paradox to get a collision, rather than brute-forcing a specific key you've been given).

Regarding law enforcement, I assume they just use CALEA-mandated taps that are built in to the switches.
posted by hattifattener at 6:45 PM on December 29, 2009

I think eriko has the math right but is describing the wrong problem

Nuh-uh. Bad math.
posted by ryanrs at 7:48 PM on December 29, 2009

Jimmy Havok: I think eriko has the math right but is describing the wrong problem

Possibly. The math would be correct if he were talking about a birthday paradox collision result. However, he specifically used the term "brute force the key" and referenced the EFF's Deep Crack which is definitely a brute force cracker. In any case, I'm not sure how a brute-force collision result would be applicable in this context.
posted by mhum at 7:52 PM on December 29, 2009

This is why kids should be forced to use slide rules in school.
posted by ryanrs at 12:36 AM on December 30, 2009

I think you have the math wrong. Brute forcing a 64-bit key would take on average 2⁶⁴/2 = 2⁶³ trials.

mhum's right, and I'm wrong -- this isn't a birthday paradox problem.
posted by eriko at 9:18 PM on January 5, 2010