GSM is publicly cracked

[RevDisk]

http://www.nytimes.com/2009/12/29/technology/29hack.html?_r=1

Cellphone Encryption Code Is Divulged

By KEVIN J. O’BRIEN
Published: December 28, 2009

BERLIN — A German computer engineer said Monday that he had deciphered and published the secret code used to encrypt most of the world’s digital mobile phone calls, saying it was his attempt to expose weaknesses in the security of global wireless systems.

The action by the encryption expert, Karsten Nohl, aimed to question the effectiveness of the 21-year-old G.S.M. algorithm, a code developed in 1988 and still used to protect the privacy of 80 percent of mobile calls worldwide. (The abbreviation stands for global system for mobile communication.)

“This shows that existing G.S.M. security is inadequate,” Mr. Nohl, 28, told about 600 people attending the Chaos Communication Congress, a four-day conference of computer hackers that runs through Wednesday in Berlin. “We are trying to push operators to adopt better security measures for mobile phone calls.”

The G.S.M. Association, the industry group based in London that devised the algorithm and represents wireless companies, 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, an association spokeswoman. She said 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.”

Some security experts disagreed. While the disclosure does not by itself threaten the security of voice data, one analyst said companies and governmental organizations should take the same steps to ensure the security of their wireless conversations as they do with antivirus software for computer files.

“Organizations must now take this threat seriously and assume that within six months their organizations will be at risk unless they have adequate measures in place to secure their mobile phone calls,” said Stan Schatt, a vice president for health care and security at the technology market researcher ABI Research in New York.

Mr. Nohl, who has a doctorate in computer engineering from the University of Virginia, is a widely consulted encryption expert who waged a similar campaign this year that prodded the DECT Forum, a standards group based in Bern, to upgrade the security algorithm for 800 million cordless home phones.

Mr. Nohl has now set his sights on G.S.M., whose second-generation digital technology is still the most widely used wireless-communications standard in the world. About 3.5 billion of the world’s 4.3 billion wireless connections use G.S.M.; it is used by about 299 million consumers in North America.

In August, at a hackers’ forum in Amsterdam, Mr. Nohl challenged other computer hackers to help him crack the G.S.M. code. He said about 24 people, some members of the Chaos Computer Club, which is based in Berlin, worked independently to generate the necessary volume of random combinations until they reproduced the G.S.M. algorithm’s code book — a vast log of binary codes that could theoretically be used to decipher G.S.M. phone calls.

(snip)

Rest of article at the above link.   GSM has been broken for some time, but most researchers have been threatened into keeping their results private.  If said researchers were American, they'd be in jail.  Reverse engineering any security (no matter how retard simple) is technically illegal under the DMCA.  Which only applies to consumers, hackers and researchers.  Criminals could care less and are much more likely to have funds for legal defense.  There isn't exactly an overwhelming lobby or slush fund to defend security researchers.

Thankfully, the CCC had the guts to do the right thing and publish.  Folks have been aware for a long time that GSM was vulnerable, badly so, but legally unable to prove it.  If you proved it, you went to jail.  If you couldn't prove it, you were ignored or threatened with a libel suit.  Heh, gotta love US law, eh?

[Harold Tuttle]

Exposing that the Ministry of Love can hear your GSM is not approved

[roo_ster]

I thought all digital phone systems were weak tea, encryption-wise and meant to be so that the gov't could crack real-time.

[AZRedhawk44]

I thought all digital phone systems were weak tea, encryption-wise and meant to be so that the gov't could crack real-time.

They don't need to brute-crack.  They have the encryption keys.  Doesn't matter how strong the encryption is/isn't.

Kinda like your computer.  If you use a commercial OS and/or a commercial disk encryption system, or something like WinZip to attempt security... it can be cracked with a simple warrant and the right govt tech geek software provided by the software manufacturer.

A resounding argument for open source software.

[RevDisk]

They don't need to brute-crack.  They have the encryption keys.  Doesn't matter how strong the encryption is/isn't.

Kinda like your computer.  If you use a commercial OS and/or a commercial disk encryption system, or something like WinZip to attempt security... it can be cracked with a simple warrant and the right govt tech geek software provided by the software manufacturer.

A resounding argument for open source software.

BWAHAHAHAHAHA.   Hehehe....

Ah.  By law, all communication services must have a backdoor installed for law enforcement and intelligence purposes.   This is mandated by Communications Assistance for Law Enforcement Act (CALEA).  Naturally, carriers leaped to go above and beyond the legal requirements and actually illegally hand over information on a regular basis.  They were essentially granted immunity from the law, permission to destroy evidence, and immunity from obstruction.   Interestingly, FISA Amendments Act of 2008 was the first case of Obama (as a presidential candidate) breaking his word and stabbing his own supporters in the back.

If you do not donate to the EFF, you really should.  They are probably the best folks fighting for your freedom.   They are very decent folks.   I can sum them up from one quote made by one of their lawyers at Defcon, relating to attempts to suppress IT security information being presented in a spoken form.   "So we won the case because of the placement of a comma in a sentence in the law.  A win is a win, but I was upset because I wanted to win on Constitutional grounds."  They sue the NSA and FBI on a regular basis.  You're not gonna find lawyers with more guts anywhere on the planet.

Without their priceless work, things like Stellar Wind or DCSNet would not come to light.  DCSNet is the FBI's survaillance system that allows real time interception from basically any US communication system.


http://www.wired.com/politics/security/news/2007/08/wiretap
http://www.eff.org/deeplinks/2007/08/eff-documents-shed-light-fbi-electronic-surveillance-technology

[AZRedhawk44]

By law, all communication services must have a backdoor installed for law enforcement and intelligence purposes.

So... a theoretical SSH tunnel through which I shovel VoIP has a back door?

Does goobermint have the ability to crack open source SSH by means other than brute force?

[RevDisk]

So... a theoretical SSH tunnel through which I shovel VoIP has a back door?

Does goobermint have the ability to crack open source SSH by means other than brute force?

If you are using a commercial VoIP service, then yes.  If you are running your own VoIP application that does not employ a service, then likely no.  


FYI and to be a lil more specific, GSM is not a code, it's a protocol.  But it does specify usage of A5/1 and A5/2 streaming ciphers.   This is the attack tables for A5/1. The tables were generated by compression techniques, rainbow tables and distinguished point chains.  They are now available via BitTorrent.  They were computed in three months using 80 distributed NVIDIA CUDA nodes.  A moderate server farm could do the same job in a few days.  A rented botnet, in a few hours.

This isn't about "decoding GSM signal was previously impossible".  It was intentionally designed to only have moderate security to allow ease of government surveillance.  It's "decoding GSM signal is now within reach of the average person".   That's a valid problem.  Another problem for consumers wishing to secure their cells is that doing so is illegal.  Over the air crypto is highly regulated.  For the average person, it is generally illegal.  It's by certifying an industry protocol for a specific usage can you get an exemption from the FCC to make it legal for broad application.  (IANAL and this is oversimplification of US law.   Contact your lawyer for specific legal guidance.)

The article leaves out a lot of information.   This is the first step of allowing casual eavesdropping.  The rest is just hardware or software implementations.   Now someone just has to make an applicable field-programmable gate array and wire it to an antenna, some DSP's, desired form of output and voila, relatively casual eavesdropping.

To make a realistic threat scenario.  The average organized crime group could probably get it commissioned within six months.  Police officers don't ever use cell phones, right?  Even to tell their wives or husband when they're coming home for dinner, and if they're stopping at any point to pick up groceries?

[Hawkmoon]

"Excuse me, Mr. Minister Plenipotentiary, but am I the only one to have noticed that His Royal Smugness does not appear to be wearing any ... ahem ... CLOTHES?"

[Antibubba]

So how (relatively) secure is CDMA?

[Headless Thompson Gunner]

What?  People actually thought broadcasting their communications over the airwaves was secure?

Weird.

[ilbob]

I thought all digital phone systems were weak tea, encryption-wise and meant to be so that the gov't could crack real-time.

It is widely believed (and probably true) that national governments have back doors into all communications systems including landlines, cell phones, and the Internet.

The thing is that even with computers doing most of the listening in there is no way to sift through the huge amount of data in any practical way unless they can zero in on a particular person.

I wonder how long it will be before some one recodes a droid style phone with some kind of PGP like encryption system for texting. Something that is encrypted before it hits the network and decrypted afterward would be pretty close to secure.

Even without PGP one time pads are very secure, but can be breached by other means. Even PGP has ways to break it, although generally the way to break it is to steal the keys.

[AZRedhawk44]

droid style phone with some kind of PGP like encryption system for texting talking

Fixed that for you.

[RevDisk]

It is widely believed (and probably true) that national governments have back doors into all communications systems including landlines, cell phones, and the Internet.

It's not widely believed.  It's the law.  Any telecom provider that does not provide an easy to use back door is committing a felony.  Most telecom providers go well beyond the minimum requirements and hand over information in violation of US law.  Very simple reason.  If they don't, they are denied government contracts which are very lucrative.  Oh, and they'll FIND a reason to send the CEO to jail.  Look up Qwest and the consequences of following the law when the NSA wants you to break it. 

Didn't you ever wonder why RIM keeps all of their hardware in Canada when the majority of their customers are in the US?  If you want legal secure mobile data, use a Blackberry and your own server.  RIM can't dime you out even if they wanted (it's been tried by various govts), because the keys are generated on the BES.  The govt isn't going to shut down Blackberry, because they're addicted to their crackberries as well. 

The thing is that even with computers doing most of the listening in there is no way to sift through the huge amount of data in any practical way unless they can zero in on a particular person.

I wonder how long it will be before some one recodes a droid style phone with some kind of PGP like encryption system for texting. Something that is encrypted before it hits the network and decrypted afterward would be pretty close to secure.

Even without PGP one time pads are very secure, but can be breached by other means. Even PGP has ways to break it, although generally the way to break it is to steal the keys.

Re moble PGP, it already exists.  You want to use GPG, not repeat NOT PGP.   GPG is open source, and does not use patented algorithms.  That's important.  NAI used to own PGP and took it closed source.  Anyone with half a brain ditched it.   PGP Corp open sourced PGP when they bought it from NAI, and trust is slowly being rebuilt.  But, make it easier for yourself (and same a couple bucks), and use GPG if you can.

One time pads are the only secure and unbreakable "code" if correctly implemented (not reused and a good source of randomness).  Because they are not a code.  "The swan flies at dawn" is an quasi example of a one time pad.  (Sorta, crypto geeks gimme a break here.)   There is no cryptanalysis on the planet that can mathematically break "The swan flies at dawn".  You can still potentially use signal analysis, which is a completely different ball of wax. 

[AJ Dual]

Above and beyond encryption, you need to think long and hard about what your signal to noise ratio, communication frequency and recipients tells someone listening about you. 

If you want a truly secure communications path you need to decide if it's going to be one-time throw-away channels, or a constant stream of communication that won't raise suspicion once it's activated.

[RevDisk]

Rather than start a new thread...

Another GSM cypher has been cracked.  A5/3.

http://www.emergentchaos.com/archives/2010/01/another_week_another_gsm.html


Shamir (the S in RSA) published a new cryptoanalytic technique relating to related-key attacks at Crypto 2008, basically simplifying complex equations.  Among other things, it was more recently used to attack AES block cipher.  A previous example was WEP.   Related-key attacks are when you can observe the operation of a code under multiple keys, and you can figure out how the keys interact in a mathematical sense.  The details can be found here:  http://eprint.iacr.org/2010/013.pdf

Now you might be saying, well that doesn't sound like a practical approach.   Surely it's processor intensive.   Sorta.  If you consider two hours on a consumer grade PC to be "processor intensive".  Basically, why it was broken is simple.  The broken cypher (KASUMI) is based off MISTY.  MISTY is unbroken.  3GPP modified MISTY to make it faster to implement on mobile hardware and some other concerns.  Well...   They didn't do a good job in the port.

Even more entertaining, KASUMI is used in the GSM A5/3 key stream generator, the GPRS GEA3 key stream generator and the UMTS security system.

[Jimmy Dean]

Is anyone else as lost as I am?

[CNYCacher]

Is anyone else as lost as I am?

I have a BS in Computer Science, studied everything from compiler construction to encryption to advanced number theory.  I implemented various public-key cryptosystems in hand-made code in the past, designed an OS from scratch, hand-made a compiler for an invented language, and can pretty much bend the will of a computer into anything I want.

The Rev loses me on a regular basis, unless he is talking about improvised explosives.

[RevDisk]

Is anyone else as lost as I am?

It's getting to the point where it'd be trivial for non-government entities to intercept cell phones on the fly.  Not just voice, but also data, text messages, etc.  Even location.   That's really bad.

I have a BS in Computer Science, studied everything from compiler construction to encryption to advanced number theory.  I implemented various public-key cryptosystems in hand-made code in the past, designed an OS from scratch, hand-made a compiler for an invented language, and can pretty much bend the will of a computer into anything I want.

The Rev loses me on a regular basis, unless he is talking about improvised explosives.

Am I wording it badly?   Sometimes I type when I'm thinking and it comes out...  less than optimally clear.

Do wish I would have finished my BS in CompSci...   But I had to go blow up parts of Europe.   

[CNYCacher]

It's getting to the point where it'd be trivial for non-government entities to intercept cell phones on the fly.  Not just voice, but also data, text messages, etc.  Even location.   That's really bad.


Am I wording it badly?   Sometimes I type when I'm thinking and it comes out...  less than optimally clear.

Do wish I would have finished my BS in CompSci...   But I had to go blow up parts of Europe.   

Your wording is fine, it's your knowledge of various subjects that is the problem, it's too vast! :)

[Gewehr98]

Indian code talkers.

Or Morse Code, since fewer and fewer people know it?   

[Nick1911]

It's getting to the point where it'd be trivial for non-government entities to intercept cell phones on the fly.  Not just voice, but also data, text messages, etc.  Even location.   That's really bad.


Am I wording it badly?   Sometimes I type when I'm thinking and it comes out...  less than optimally clear.

Do wish I would have finished my BS in CompSci...   But I had to go blow up parts of Europe.    

Grammatically I'm able to follow along, you're fine.  I did have to wiki some of the algorithms you mentioned due to lack of familiarity, though.  I consider this a good thing, as it expands my knowledge.   

[Matthew Carberry]

So this thread is about electronic stuff right? 

[RocketMan]

Indian code talkers.

Or Morse Code, since fewer and fewer people know it?  

Are you sure you want to go there?  Some of us that do know Morse Code are kind of...whacked...if you know what I mean.  The fun we could have, damage we could do... 

[Matthew Carberry]

I can wax rhetorical on subjects phantasmagorical,
I can even cuss you out in Klingon.

I can cite from memory events from ancient history,
as long as it's from Niven, Feist, or Tolkien.

But my big ol' brain starts knocking, when RevDisk gets to talking,
about subjects of binaric origin.

So let's go back to mindless drivel, lest my brain should shrivel,
or I'm forced to learn of useful things again.

[HankB]

. . . I had to go blow up parts of Europe.     

Some job you did - according to Google Earth, Europe is still there.