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.

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.

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.

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. But it's rare for a company to have a single mobile device as their flagship, so to speak. Apple is well known for being nuts about the iPhone. Most if not all of the employees carry one. The thing is, if GSM is as weak as it seems to be, then by standing behind a GSM device, Apple has effectively deployed thousands of completely insecure devices which they are using to handle and manage Apple's business and corporate secrets. Even their retail store payment devices run on iPhone.

They have put their corporate faith in GSM. Which is now full of holes like a swiss cheese. Do you see where this is going?

All a Microsoft or a Google or a Motorola needs to do is setup a van or rent an office near Apple HQ and run a very low key listening program. Probably do the whole thing from a briefcase or even a car in the parking lot. You'd never see it. They'd have probably most of Apple's secrets in a day or two, and a lot more after a few months or years. Legal? No. Is somebody going to do it? You betcha. If not Microsoft or Google, then any of the dozens of handset makers or laptop makers or software companies. Can you imagine just for Apple how many people would want all that inside info? Now expand to Boeing, Cisco, IBM, HP, Dell, you name the company, some subset of workers will be carrying GSM.

Apple shareholders ought to care about that. Steve Jobs ought to care about that. ANY CEO or IT person in any company with any GSM devices ought to be scared to death about this. If you are using GSM, you are dead. It's that simple.

And even if they cannot crack the encryption NOW, the data can still be recorded and stored away. Storage is cheap. Decrypting Apple's calls a year from now will still be valuable. I guarantee you someone is doing that right this second outside 1 Infinite Loop. The data can happily wait for the lookup table to be completed at which time the whole set of recorded data will be opened like Diet Coke with a Mentos dropped in. There are a LOT of people would want that info, and not just for Apple of course. They're just a notable example of the targets.

GSM is possibly the biggest threat to information security currently in play. Bigger than Chinese hackers. Bigger than Windows worms or Facebook hacks. Why? GSM devices are widely deployed around the world, totally trusted by their users, and relatively easy to crack thanks to a poor encryption implementation, and those who are doing the illegal (non-law enforcement) signal intercepts are able to do it from a distance without being detected or noticed. Somebody could be in the house or office or dorm next to you monitoring GSM right this second, and you would not know. You could not stop it even if you did know, except by not using the devices.

So, the fact that there is now an opensource effort will bring light to the scale of the problem (it's very bad) and hopefully get it fixed immediately, even if that means a whole lot of GSM handsets are going to have to go obsolete at once. In the worst case, it MAY change behavior so confidential stuff is no longer handled on GSM devices or encourage wholesale change in behavior for all wireless devices (please!), or at least get people to consider security as one vital aspect when they choose a provider of phone services or data or anything else.

DECT cordless home phones run on a variation of the GSM protocol, most likely with the same encryption issues. So that's yet another area worth looking at.

In most parts of the world the telco's tend to microwave all their cell towers back to the exchange. It's cheaper to do it this way.

With a small investment (a couple of hundred $USD) on Ebay for some receive gear, modems, and data capture cards, your average enthusiast has absolutely no need for decryption of GSM. The only point encryption takes place is between the phone and the tower. The microwave links are not encrypted and are virtually always conveyed using E1 / T1 transmissions - maybe sometimes replace the 1 with a bigger number in congested areas.

The only hard part is picking out your target, but this is hard anyway, even if you can manage decryption while the call is still in progress. (Frequency hopping and sheer number of users) Also at the trunk level, the out of band signaling (SS7) doesn't tell you where the phone call actually is (which timeslot), so you'll have to either record everything and go through it manually, or use some kind of fudged analysis to guess based on activity in the SS7 and what you see in the trunk. Or... You might just be voyeuristic, in it just for the gossip / phone sex / ambulance chasing / whatever, so none of the above matters.

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.

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 incentive exists. If anything you discuss might cost more than 50K usd in three months time, don't do it ether. Wideband recording of anything where you might be and filtering out your phone conversations later is practical. Costs about 3K usd in equipment (outlay) + whatever you want to throw at key search.
Three - as mentioned above in the comments - backbones are usually unencrypted. Not much can be done about it, and MITM or backlink eavesdropping is a project that would be practical (it still is) only for really determined subjects. Oh, and your local/office base station is probably on the roof of some semi-public building where gaining access again is not beyond practical attack. Or, if a tower with equipment container - trivial.
---
Good (ish) things:
GPRS and 3G security isn't broken (publicly, afaik) yet. OTOH - isn't peer reviewed ether (worked well for a5, didn't it?). Therefore what you browse around or talk via your _UMTS_ handset is perhaps still safe. Just make sure the handset is really in 3g mode. Don't have much know-how about pretending to be UMTS base station thou - still can be fully feasible. Perhaps a feasible attack will show up tomorrow, perhaps won't. Radio hopping pattern intercept and packet capture is feasible cheaply today thou.

All in all, okay, there might be a public attempt to generate open A5/1 rainbow table today, good. From what I recall target size for the table was rather laughable - 500gb or thereabouts? I can surely bet that there are fair few of them out there already. Perhaps inside usd300'000 equipment sold for law enforcement. Perhaps...