Slashdot Mirror
Cracking GSM
RobertM writes "Professor Eli Biham, one of the worlds most famous crypto analysts, together with two of his students presented an interesting paper on flaws in GSM at the IACR Crypto conference. The GSM association is not happy. Read more on theReg." There's also a Reuters article about the situation.
The International Journal of Digital Evidencehas a current article about GSM forensics.
the UK M5 is a road. perhaps you mean MI5?
Elad, Nathan, Eli Biham and Orr Dunkelman (which was not listed for some reason) are friends of mine at the Technion Israeli Institute of Technology. Their previous attack on A5/1 required a few hundred GB of HD space and dedicated telephony equipment to pull. A5/2 is a peace of cake in comparison. This new attack makes it ciphertext only. That means that you don't have to initiate a short call (for example) to the evesdropee or knowing some part of the call (like with voicemail) before breaking the encryption. It uses the signal correction mechanism to initialize itself.
In general, this is no big news, because this equipment is hard to aquire and the benefits are not that great. In comparison, CDMA and TDMA don't (effectively) encrypt calls at all.
Make even shorter URLs - 8LN.org
From theReg...
Both parties agree that the issue does not affect 3G phones, which use different protocols and security mechanisms than legacy GSM handsets.
Nathan, Elad, and Eli Biham are not US citizens as far as I know...
Make even shorter URLs - 8LN.org
The novelety of this attack is that it is instantanous. The cryptanalysis is done one when the call is being established (when the phone just rings) even before any any real conversation is being done.
The exact details are still secret but the attack exploits a misuse of Error Correcting Codes (ECC - are used in communication protocols to correct random noise errors).
It seems that instead of encrypting the conversation and then employing ECC, the GSM does it the other way thus leaking enough data for the cryptanalysis to be performed
At least they point out that the equipment required costs about $250k.
"I'd rather be a lightning rod than a seismometer." -Ken Kesey
Finally one reason for people to upgrade to 3G.
Just saying it like it are.
From http://israelemb.org/sanfran/News&Media/full/03/se p/02#c
"Elad found that the GSM network does not work in proper order: First, it inflates the information passing through it in order to correct for interference and noise and only then encrypts it," Biham told The Jerusalem Post. "At first, I didn't believe it. We checked it, and it was true."
That probably means higher predictability for the encrypted data.
my other sig is a 500 page novel
From the Reg article:
I don't have the sales figures to hand, but I don't think GSM can really be called a "legacy" technology yet. IIRC Britain only has one provider 3G service provider, which has had a fraction of the expected number of subscribers.
"The Milliard Gargantubrain? A mere abacus - mention it not."
They are all infact at the Technion, Israel's high Tech-engineering school in Haifa. The DMCA is a US law, which applies to people in the USA. It has absolutly no effect on people outside the USA.
Now in theory if they travel to the USA they could have a problem, and many Israelis do travel to the USA for one reason or another, but I don't think the US goverment will arrest an Israeli professor for publishing a paper.
Erlang Developer and podcaster
Um they already presented their work. I was there I should know. In fact their attack is hardly "news" I was chatting with certain people at the conference and they already knew the details of the attack way before the presentation took place.
Santa Barbara is an awesome btw! I can't wait for CRYPTO'04
Tom
Someday, I'll have a real sig.
"The question is can somebody deploy a off-the-shelf (or homebuilt) scanner and grab the conversations on-the-air? I know that a PR (pseudo random) number is used with the ESN and A-key to generate some keys for encrypting some of the communications, and that the voice channel is "scrambled", but is there a source where the security implications of this is discussed?"
In theory, anything is possible.
Off-the-shelf scanner - Definately not. Unless you're talking about high-end five-figure and even six-figure sums. A Rohde and Schwartz FSIQ would probably be 90% of the hardware needed to crack a CDMA signal, but FSIQs run $75k used ($120k or so new). An Agilent E4406A VSA starts at $32000 and cdmaOne and CDMA2000 options are extra $$$. And these might not even be sufficient for realtime monitoring and demodulation. It would be possible to build custom equipment for much less, but only a M.S. or Ph. D. in EE would be able to design a system to do adequate realtime demodulation of CDMA.
Non-realtime (capture the signals and post-process them) - Much easier. The hardware is $1000-2000 off-the-shelf (see GNU Radio), and the software is $99 if you're a student (Matlab), although you'll still need thorough knowledge of CDMA and some communications systems background to write the demodulation algorithms.
I don't know about the datastream-level encryption, but CDMA is much tougher to demodulate than the TDMA scheme used by GSM. (Given a captured baseband signal, I could probably tweak my old ECE 467 projects to demodulate GSM down to its datastreamin not too long, while CDMA would be a LOT harder.
retrorocket.o not found, launch anyway?
Wrong! The encryption algorithm is not in the SIM, it's in the phone. The (broken a long time ago) authentication algorithm is in the SIM and can be changed by issuing new SIM cards. The encryption is in the phone, so the phone needs to be upgraded. Also, see the Crypto03-paper by Biham et al. for ways in which you can break the system even if the default is to use a strong encryption algorithm.
A: No.
The hash function (A3/A8) used in the default implementation of the GSM protocol for the challenge-response authentication had a vulnerability of a type known about in the cryptographic community for years.
This wasn't a deliberate weakening, because this flaw had no real impact on the ability of law enforcement to intercept, and allowed cloning of GSM handsets: something that was definitely not supposed to be possible.
They've learnt from their mistakes though: the 3G protocol has undergone extensive public review , as has the ciphers they chose.
I'd guess (without any stats) that more people are killed by legal guns than illegal guns.
You would be guessing wrong at least in Canada.
Guns that end up killing people tend to be stolen, illegally stored, or owned by people who shouldn't have a gun.
Few deaths result from responsible gun owners.
Myself I don't have a gun, I think most city dwellers need a gun like they need their SUV.
For USians, the roles equate as follows:
MI5 = FBI
MI6 = CIA
GCHQ = NSA
JIC = Senate Oversight Committee (*very* roughly)
UNIX? They're not even circumcised! Savages!
CDMA is indeed tougher to demodulate than GSM, the reason being that each GSM signal uses the same carrier (basically it encodes bits by modulating phase; the technical term is Gaussian Minimum Shift Keying, or GMSK). CDMA, on the other hand, has each user use a different "spreading code" in an attempt to make signals from different users orthogonal. The purpose of the spreading code is to take your nice orderly stream of bits, and turn it into a random-looking sequence. At the other end, the receiver knows what sequence you're using, and it can undo this transformation. As a side effect, your code is chosen to try to be orthogonal to other people's codes, so that at the same time demodulating your signal nulls out other people's signals, so your interference is reduced.
The reason there's some security in this process is that if a 3rd party doesn't know your spreading code, they won't be able to demodulate your signal -- you're going to sound like so much noise to their receiver, even if they have the proper CDMA decoding hardware. Having said that, this "encryption" supposedly isn't difficult to crack; Phil Karn from Qualcomm posted a discussion on CDMA security to a crypto list about this a while back. Here's a snippet:
I remember hearing a lecture on CDMA where the professor described a favorite tactic of hackers being to hang out with scanners over bridges, where people's connections would cut out, and grab their codes when the phones tried to resync with the base stations as cars exited the tunnel.
The bold print giveth, and the fine print taketh away
TDMA, which is used in the GSM standard, does represent the majority of US cellular networks. CDMA is used primarily by Verizon. AT&T, T-mobile, Cingular, etc. don't use CDMA.
At great risk of sounding like the Voice of Reason (and God knows how Slashdotters hate that!), could you please present some evidence to back up your assertion that the United States and United Kingdom are colluding to break the laws of both nations?
Look up the Federal laws: if it is illegal for a Federal agency to do $foo, then it is also illegal for a Federal agency to have a third party do $foo on their behalf.
If I break into a home and see a kilo of cocaine lying around, I can then go to the DEA and tell them. They can use my testimony to get a warrant to search the home and impound the drugs. Why? Because I didn't commit the crime on their behalf; I came in entirely of my own accord; there was no understanding between the DEA and myself that "if I see any drugs, I'm going to bring them to your attention".
But if the DEA asks me to break into a home, they'd better damn well have a warrant, otherwise they're breaking all manner of Federal laws.
So what you're positing is there is a tacit understanding between the US and UK that each will spy on the other's citizens and share with each other the fruits of those actions. Hmm. This sounds mind-bogglingly stupid.
Why?
Free hint: this is a Federal crime.
Free hint number two: the FBI and NSA do not get along.
Free hint number three: the FBI is the one with the charter to spy on American citizens--not the NSA.
Free hint number four: the FBI protects its jurisdictional turf very zealously.
Free hint number five: the FBI is one of the nation's intelligence agencies, co-equal with the CIA and NSA. The FBI has no charter to collect intelligence from foreign sources; the CIA and NSA have no charter to collect intelligence from domestic sources.
Free hint number six: if the NSA were to really be involved in this, the FBI would be doing a full-court-press investigation into the matter. (a), because it's a clear and massive violation of Federal law, and more importantly, (b) THE FBI DOES NOT SHARE ITS JURISDICTIONAL TURF.
Period.
So if you have any hard facts proving this tacit agreement, I'd love to hear it. If you have hard facts about it, then I'll talk to my FBI friends tomorrow and tell them about it.
I guarantee you they'll be pissed off.
Intercepting or receiving radio waves isn't illegal of course. Same as you are not breaking any law if you hear when your neighbours shout to each others over you property (hell, if they bother you with it, you can probably get them for disturbing your peace). Even descrambling probably isn't illegal, unless there's a specific law against that. But listening to certainly is. That's about same as using sensitive directional microphone from your house and listening what is said at your neighbour's house. Surely you don't think that's legal too, just because the sound waves travel through you and your property, and if you want to have a private conversation you should be in some special room or avoid sounds by using pen and paper...?
It's the same principle as with post. If you get somebody elses mail by mistake, you are not allowed to open it even if it came through your mailbox and lies on your floor in your house on your land.
I mean, if you want to get technical, then every telephone wire is actually a radio antenna. With sensitive enough equipment you can listen to what it transmits, just as with correct equipment you can (according to the article) mess with GSM. So what did you say about landlines being secure?
A civilized society has to protect privacy of it's citizens, both from the government and from other citizens. That's just common sense to me.
And you say "far fetched"... Hmm, tell me, are you by any chance an American...?
Yes, but that doesn't make eavesdropping legal.
"Simple fact is, there are technical ways to travel safely - and people who think walking on street is safe from getting killed are crazy."
That's true too, but it doesn't mean that intentionally driving over somebody walking on a street should be legal...
Bruce Schneier mentioned how weak the GSM algorithm was back in this Dec 99 issue of Crypto-Gram. Its lousy encrpytion and is secret, non-peer reviewed.