Open Source Attempt To Crack GSM Encryption 78
Lexta writes with an interesting tidbit from IEEE Spectrum: "'Karsten Nohl, chief research scientist with H4RDW4RE, a Sunnyvale, Calif.-based security research firm, is mounting what could be the most ambitious attempt yet to compromise the GSM phone system.' The intended approach is to create an open source project to spread the computation of a giant look-up table across more than 80 machines. Interestingly, they've openly stated that nVidia's CUDA technology will be used to execute parallel elements of the problem on GPUs as well."
Wheew (Score:2, Funny)
Makes me glad I use CDMA ;)
Hackers Sell Out (Score:2, Funny)
Interestingly, they've openly stated that nVidia's CUDA technology will be used to execute parallel elements of the problem on GPUs as well.
Wow, even hacking is branded these days.
I look forward to the Pepsi Challenge being revised to an RSA cracking contest.
Re:Hackers Sell Out (Score:4, Insightful)
Saying they are anti-opensource is a bit much don't you think? They are a corporation who just haven't figured out how being open source would be more beneficial to them and their share-holders than remaining closed.
I believe if they were "anti-opensopurce" most people wouldn't have that nice nvidia wrapper for the driver on linux systems. Why waste time making it at all if they are "anti-opensource"?
Just because they haven't opened their code to the universe doesn't mean they are against open-source; just that they haven't found a means to leverage it to their advantage which companies like to do.
Businesses are about the bottom line, money, and how to make more and keep what they got. Opensource is about sharing and giving up control; it is a hard thing for a lot of companies to fit into their business plan and sell to investors.
Re: (Score:2)
If they're not with us, they're against us!
Re: (Score:2)
Didn't Reagan originate that (feel free to tell me to get off your lawn)?
Re: (Score:1, Interesting)
It appears a couple of times in the gospels as something Jesus said.
Bush said after 9/11 "Either you are with us, or you are with the terrorists." The definition of "with us" changed according to convenience but included things as diverse as an import ban on Canadian Lipitor, not criticizing the director of FEMA, and not asking what reason we had for occupying Iraq.
It's usually a clear sign that the person talking should be slowly backed away from until it's safe to break into a run.
Re: (Score:2)
Jesus said that because evil is a pervasive influence that will not rest until it succeeds in getting as many people damned as possible.
Apparently all the devil needs is just one loophole.
Personally I think misappropriating it to apply it to terrorism is just plain wrong.
1. Forces people into a false dichotomy, which sorta becomes true when everyone else goes lemming and takes offense (or worse) if you don't fall in line.
2. Who are they to judge what is or is not equal to evil?
Re: (Score:1)
Re: (Score:2)
Re: (Score:1)
It's very anti-competitive you mean.
Take a good hard look at what they do and have done and that is an inescapable conclusion.
Re: (Score:2)
Wow, even hacking is branded these days.
I look forward to the Pepsi Challenge being revised to an RSA cracking contest.
I prefer algorithm "B"
Mmmm, algorithm... {drool sound}
So sad, that humor is not with us... (Score:2)
I'm really not sure how this was branded "Troll" as I meant the whole thing in jest. Lighten up, fellow hackers!
Big deal (Score:4, Funny)
Big deal. No one still uses their cellphone to make calls anyway.
Re: (Score:2)
He was talking about voice calls.
The thing about GSM is that it's easy for authorities to access, so anybody with more knowledge and something to hide is going to use more secure options which have become possible with mobile internet access.
Re: (Score:2)
Re: (Score:3, Insightful)
Re: (Score:2)
Re: (Score:2)
I still use a Zach Morris phone, you insensitive clod!
The only way I can receive texts is through Morris code.
Re: (Score:2)
Oh my gosh (Score:2, Informative)
Re:Oh my gosh (Score:4, Insightful)
Re: (Score:3, Funny)
A pity ... (Score:2)
.. You've got to call yourself each two minutes to skip the voicemail during sex!
Re: (Score:2)
Hey, if it helps us poor nerds out, let's have at it.
Better than staring at a screen all day.
Re: (Score:2)
Re: (Score:2)
Whoosh
A big book (Score:2)
TFA:
Any crypto experts want to take a stab at explaining, in lay geek terms, how this is even remotely possible? That's a ~50,000:1 compression ratio.
Re: (Score:2)
Lookup table?
Re: (Score:3, Interesting)
Any crypto experts want to take a stab at explaining, in lay geek terms, how this is even remotely possible? That's a ~50,000:1 compression ratio.
I think what they're saying is that instead of building a table which will allow you to simply look up the relevant key from some known encrypted data, they'd build a smaller table which would allow you to substantially reduce decryption time.
Re:A big book (Score:5, Informative)
TFA:
Any crypto experts want to take a stab at explaining, in lay geek terms, how this is even remotely possible? That's a ~50,000:1 compression ratio.
Trading space for time.
128 petabytes would enable instant lookup of collisions. Cutting size in half, and you'd need 2 operations to find a collision. Cut size in half again would need to double the time again. Repeat until you reach the desired space/time trade-off.
P.C. van Oorschot, M.J. Wiener. Improving meet-in-the-middle attacks by orders of magnitude, Crypto'96, Springer LNCS vol.1109, pp.229-236, 1996. ps, pdf. A more complete treatment is given in the 1999 Journal of Cryptology paper.
P.C. van Oorschot, M.J. Wiener. Parallel collision search with applications to hash functions and discrete logarithms. pp.210-218, proceedings, 2nd ACM Conference on Computer and Communications Security, Nov. 1994, Fairfax, Virginia. ps, pdf. The Crypto'96 paper builds on this, and a more complete treatment is in the 1999 Journal of Cryptology paper.
P.C. van Oorschot, M.J. Wiener. Parallel collision search with cryptanalytic applications. Journal of Cryptology, vol.12 no.1 (Jan. 1999) pp.1-28. pdf.
Re: (Score:3, Funny)
Re: (Score:2)
TFA:
Any crypto experts want to take a stab at explaining, in lay geek terms, how this is even remotely possible? That's a ~50,000:1 compression ratio.
IIRC it was found some years ago that while GSM security in principle was OK, most of the bits of the encryption key are always set to zero.
I don't think this is true of 3G GSM though...
Re: (Score:1, Interesting)
As far as I can remember, the original GSM spec included a reference implementation of the A5 algorithm where the last 10 bits of the key were nulled.
I don't think the reference made it into any production systems though and this problem was rectified in later revisions.
A5 itself is sound afik.
Re: (Score:2)
Wasn't. It is what is running out there.
Re:A big book (Score:5, Insightful)
The key phrases you are looking for are "rainbow tables"; "time / memory trade-off"; "distributed computing"; "embarrassingly parallel"; "GPGPU Computing" and probably "More's Law".
So now computers are faster than when they cooked that "100,000 years" phrase. They are employing many different computers with multiple cores. GPUs are much faster at this calculation that X86 processors. Rainbow tables are ingenious methods to store precomputed results, so the actual cracking is simple comparisons between encrypted text with known values and the data you are attacking.
Re:A big book (Score:5, Informative)
The article doesn't contain enough information about A5/1 or the details of the attack for a crypto expert to explain exactly what he plan to do. However it does mention that he intend to create a rainbow table, so I can at least explain what a rainbow table is, and what the 128PB might mean. The article say it is a 64 bit encryption, but 128PB doesn't sound like the right size given a 64 bit encryption, the 128PB sounds more like a 54 bit encryption. And though it doesn't sound like a huge difference those 10 bits does mean a factor of 1024 times less work to brute force, and these days the difference between 54 and 64 bits may very well be the difference between feasible and not feasible to break. Of course in a few years 64 bits may be feasible to brute force as well.
Compressing 128PB down to 2-3TB doesn't sound realistic at first, but then consider that those 128PB are not just 128PB of random data, they are generated by a very simple algorithm. The entire code to generate those 128PB would probably fit in less than 1MB. But the time it would take to actually run the code for long enough to generate the 128PB is prohibitive. Also notice, that what is going to happen is not really a compression of the 128PB of data. The output of the algorithm is going to be a few TB of data, but that data can't actually be used to reproduce the original 128PB of data, which wouldn't be very interesting anyway. What you really want is a function that given some input can output the encryption key, and that can happen through a very simple table lookup, which would be very fast, but infeasible since very few people have the resources to store the complete 128PB lookup table. Instead you use a more complicated algorithm, which use 50.000 times less stored data, but OTOH may run 100.000 times (or even more) slower than the simple table lookup. But 100.000 table lookups would still only take a fraction of a second on a modern CPU.
Back to the rainbow tables. It is a tool to speed up the task of reversing a one way function. A one way function is a function that maps from one set of values to another set of values. The function is fast to compute in one direction, but there is no simple way to compute in the other direction. One example of a one way function is a hash function, which maps from strings of arbitrary lengths to the much smaller set of strings of one fixed length.
Let's assume our one way function is called f and maps from the set S to the set T. Then we can define a different function g, which maps from T to some interesting subset of S. For example it has been used in the past with a function that maps from 128 bit strings (outputs from MD5) to the set of passwords consisting of 7 alphanumeric characters (which is a subset of the possible inputs to MD5). If you combine g and f, you get a function mapping from T to T. If you start with a value in T and keep applying this combination, you will keep getting values in T.
Now you decide how many times in a row you will apply this combination, let's call that number n. A small n will produce very large rainbow tables, that may be faster to use. OTOH a large n will produce smaller rainbow tables that will be slower to use. This choice is the compromise mentioned in the article. He is probably going to use a value of n around 65536 or so.
Now you start producing chains (this is the large amount of work that this project will aim to distribute). You take some input in T, then you apply the combination of the two functions n times and get an output in T. You repeat that with a few hundred billion different values in T. The output will be a lot of pairs of values, from those pairs you create a lookup table.
Now assume you have a value x, which is the output of the one way function f, and you want to find out what the input may have been. Then you can apply the combination of functions n times and get n different values in T, look
Re:A big book (Score:4, Informative)
From Wikipedia [wikipedia.org]:
Way to make an already weak cipher even weaker.
Two points.. (Score:5, Informative)
2) This has been known pretty much from the beginning, and updating has been started years ago. As said in TFA, only news of this is the plan to make it publicly available.
Re: (Score:2)
Most importantly, handsets use less power when on GSM.
I don't see GSM being killed for a long, long time. It's like DVD, an example of "good enough" for majority of population, especially those who basically just call and text. 3G benefits are either not used or manifest themselves in very specific scenarios, "modem" function mostly.
Security also is good enough. As this attempt shows, it's non-trivial to crack. And "lawful wiretapping" bypasses it anyway also for UMTS.
Re: (Score:1, Redundant)
Most importantly, handsets use less power when on GSM.
I don't see GSM being killed for a long, long time. It's like DVD, an example of "good enough" for majority of population, especially those who basically just call and text. 3G benefits are either not used or manifest themselves in very specific scenarios, "modem" function mostly.
Security also is good enough. As this attempt shows, it's non-trivial to crack. And "lawful wiretapping" bypasses it anyway also for UMTS.
Precisely, my iPhone battery lasts days on GSM, hours on 3G. What I don't understand is why phones can't do some sort of hybrid: GSM for standby and voice, and 3G for data? Best of both worlds!
Incorrect time estimate? BOINC? (Score:2)
TFA:
Wouldn't they need about 100,000 computers for it to take one year? And why don't they just use BOINC and enlist random computers and attempt to get more computing power?
Re: (Score:3, Interesting)
Wouldn't they need about 100,000 computers for it to take one year? And why don't they just use BOINC and enlist random computers and attempt to get more computing power?
Not if they're using CUDA. I did some fairly simple experiments in college and cut compute time on large datasets by 95% using a GeForce (don't remember which one) instead of a Core2 Duo. That was over almost two years ago, so I imagine the modern graphics boards are even better.
Re: (Score:3, Funny)
Re: (Score:2)
it isn't 128PB to start with. Actual key length is 2^48 if I remember correctly - there are some rather huge issues with the A5/1.
Good thing they're going to use open source (Score:3, Insightful)
Nobody wants GSM Encryption broken if it's done using proprietary code. And if the general public is told this is illegal, just think of the free publicity for open source!
Re:Good thing they're going to use open source (Score:4, Insightful)
Who wants it cracked in the first place? The only interests served are those of crooks and spys.
Re: (Score:2, Interesting)
Who wants it cracked?
I do, because people I bank with and trust with my data are even now happily using GSM devices to shuffle my data around, and your data, and everybody's data, and as of now, it's wide open and vulnerable.
Then there's the corporate IT security side of it. Let's take Apple as an example: Apple's mandated iPhones as their corporate device much the way some companies have gone to BlackBerries. Ok fine. This is not about OS wars or which device is better. There are GSM Blackberries too.
Re: (Score:2)
First, "And even if they cannot crack the encryption NOW..." Then, "... and relatively easy to crack thanks to a poor encryption implementation..."
So which is it? Cracked or not?
And if not, a successful open-source method to do so simply let's EVERYONE into the playpen.
Re: (Score:3, Insightful)
So which is it? Cracked or not?
I dunno - maybe if we interrogated everybody with a supercomputer we might find out. For that matter, if we interrogated everybody we might figure out who has supercomputers.
If these guys are talking about this being something that a bunch of people can do with donated CPU/GPU time, then there is a good chance that somebody has a bunch of ASICs and a rainbow table already. They probably have had it for a number of years.
Keep in mind that the cracking of Enigma wasn't publicl
Re: (Score:3, Interesting)
Well, I haven't done it myself, but have researched the topic quite a lot (with a background on mobile applications and security):
One - if you have anything that is actually sensitive to discuss, don't do it over your phone. Ever. It is trivial to pretend to be your base station (van in the alley scenario) and you'll be none the wiser. But phone will be talking via A5/0 (no encryption) and you'll be experiencing very nice and good battery life.
Two - brute force attack on A5/1 is feasible, if enough incentiv
Re: (Score:2)
Oh, forgot to mention - the above applies to gsm. CDMA security is nonexistent + tower coverage is larger (less geo targeting required).
Re: (Score:3, Interesting)
Re: (Score:1)
It's not so much that he only runs a browser, but that a browser is the only program he needs to run.
donate (Score:1)
http://wiki.thc.org/gsm [thc.org]
If you're IT admin of school with 5000 idle computers, consider donating some GPU time
Re:donate (Score:5, Funny)
Link to the project web-site: http://wiki.thc.org/gsm [thc.org]
Inexplicably, that link makes me think of weed and sex. I expect a high turnout of volunteers at the college level.
again? (Score:1)
Sp3ll1ng (Score:4, Insightful)
H4RDW4RE?
Are we really supposed to take a company seriously, when its own name substitutes numerals for letters?
Re: (Score:2, Informative)
Re: (Score:2)
he's a leading innovator in the grey-hat cracking scene.
Nobody's taking that seriously, either. Perhaps in your little world of w4nk3rs it's a big deal, but nobody else cares.
comments from TFA (Score:2)
I hope I am not the first to say: "giggity."
GSM@Home? (Score:1)