Schneier on Security
A blog covering security and security technology.
« Guard Towers at Walmart |
| Sony PS3 Security Broken »
January 5, 2011
Eavesdropping on GSM Calls
It's easy and cheap:
Speaking at the Chaos Computer Club (CCC) Congress in Berlin on Tuesday, a pair of researchers demonstrated a start-to-finish means of eavesdropping on encrypted GSM cellphone calls and text messages, using only four sub-$15 telephones as network "sniffers," a laptop computer, and a variety of open source software.
The encryption is lousy:
Several of the individual pieces of this GSM hack have been displayed before. The ability to decrypt GSM's 64-bit A5/1 encryption was demonstrated last year at this same event, for instance. However, network operators then responded that the difficulty of finding a specific phone, and of picking the correct encrypted radio signal out of the air, made the theoretical decryption danger minimal at best.
As part of this background communication, GSM networks send out strings of identifying information, as well as essentially empty "Are you there?" messages. Empty space in these messages is filled with buffer bytes. Although a new GSM standard was put in place several years ago to turn these buffers into random bytes, they in fact remain largely identical today, under a much older standard.
This allows the researchers to predict with a high degree of probability the plain-text content of these encrypted system messages. This, combined with a two-terabyte table of precomputed encryption keys (a so-called rainbow table), allows a cracking program to discover the secret key to the session's encryption in about 20 seconds.
Did you notice that? A two-terabyte rainbow table. A few years ago, that kind of storage was largely theoretical. Now it's both cheap and portable.
Posted on January 5, 2011 at 6:20 AM
• 39 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
Damn. A 2TB lookup table. And the processors (and bus) are fast enough to make that usable. Wasn't that long ago (j10 years?) that only governments and large businesses could do that.
Which sort of implies that some of them probably were.
Governments don't need a rainbow table approach, they just set up a fake tower if operation is clandestine or ask the telco to give them a copy of decrypted traffic in real time.
And the bad guys with money at hand can hire "consultants" with stolen GSM/3G analysis hardware, which contains the necessary decryption keys just like your local locksmith probably has masterkeys to get into your house...
While I echo the sentiments, "cheap" is a very subjective term...
What we really need to know is what the vague things are - what is a "variety of open source software," for example.
Now, time to start constructing some rainbow tables...
"Did you notice that? A two-terabyte rainbow table A few years ago, that kind of storage was largely theoretical. Now it's both cheap and portable Posted on"
About ten years ago it was possible for a few thousand dollars with a RAID array. The company I bought one of was about 1/10th the price of the then big names. About the same time as Redhat 7.3 came out you could buy PCI RAID cards for less than 150USD you could build 1.5TByte with the then drives.
The hard part is not the storage but the efficient building of the tables to work on such hardware for multiple access.
Google with "open source" and "decryption". You find www dot freerainbowtables dot com.
With the following statistics on their site:
Active machines 1180
Online machines 778
Current CPU power 4397 GIOPS
Last 24 hours 7759 million chains
Current speed 5.25 bil links/second
Data growth 130.07 GB
Cracked hashes 298148
Uncracked hashes 226241
Success rate 56.86%
Or onlinehashcrack dot com:
* Total unique hashes in databases : 5211540890
* Total unique password in tables : 377 606 890 543 261 236 174 594 486
Free online cracking service
* Hashes found today : 99 / 259 (38 %)
* Hashes found this month : 523 / 1387 (38 %)
* Hashes found last month : 3535 / 11113 (32 %)
* Hashes found ever : 56124 / 131349 (43 %)
VIP cracking service
* 89.5 % cracked.
Or hashcrack dot blogspot dotcom/p/md5ntlm-kracker.html which enlists the power of the mob:
How this works:
1. User upload uncracked MD5/NTLM hashes to the database.
2. Other users crash the hashes list, using a cracking program of their choice.
3. The crackers upload the lists of passwords, and based on each password cracked are awarded points. The person with the most points appears on the top of the Top 25 Crackers List.
Wouldn't it be simpler just to route all your calls through Google Voice and let the "bad guys" have all your info up front?
US Android users can try out the free RedPhone app from Whisper Systems for end-to-end encrypted phone calls:
Check out TextSecure whilst you're there if you want to protect your SMS storage and transmission with public key encryption.
Although the above sounds like an advert, I'm not affiliated, just a happy user.
@konrads, who said wiredog was talking about the US govt? I could imagine China sitting some people out by Google, Apple, and MSFT just sucking up corporate secrets.
Time for network operators to fix things.
Past time actually. But I'd like to know if the key deciders who resisted (and likely still resist) modifying their system are still employed. If so, why?
@ Ken Jackson,
"I could imagine China sitting some people out by Google, Apple, and MSFT just sucking up corporate secrets."
I think the Russians did it first many years ago when car phones where pre-celular (and obviously in the clear). They used the information to manipulatio grain prices on the US exchange one year when the Russian crop had failed.
A simple rule of thumb would be never say anything on the phone that you would not happily say in a room full of your competitors / enemies / friends...
But hey having people think you are paranoid is the easy bit to live with, going beetroot red with shame when something you have said is brought to the attention of your friends / enemies / competitors is the hard part unless you have sociopath tendencies.
The vagueness is to give the telco's another few years to look at finding and hopefully implementing some solutions. e.g. Disabling the current practice by more 3G operators of shunting voice and SMS traffic from the more secure 3G band to the now insecure GSM band, to have more bandwidth available for mobile broadband/smartphone users (€€€/$$$).
Read the pdf from the CCC event first http://events.ccc.de/congress/2010/Fahrplan/... and watch the videos of the event. I'm sure they are on youtube at this stage.
The code, well most of it, some bits are purposely missing, to prevent even more creditcard theft among other things.
For another broken thing read about "chip and pin broken". The banks are still thinking of rolling this broken system out to US consumers. http://events.ccc.de/congress/2010/Fahrplan/...
@Per: Locks are simple enough to understand that you can easily confirm that there are no master keys to your house. There certainly aren't any to mine.
However, lockpicks work really well. Standard house locks will not slow down a determined opponent.
Disclaimer: I was at 27c3.
While the phones (Motorola C123 is the reference one, others work, as well) have risen in price since that talk, you can still get them fro ~20-50 Euro at the moment. Add 100 Euro for a 2 TB drive and...
Anyway, the software can be found at osmocom.org and torrents for the rainbow tables are at http://opensource.srlabs.de/projects/a51-decrypt/...
As an aside, with only one of those phones, you basically have "an Ethernet card for GSM", allowing you to send arbitrary packets to the network. Or simply have a look at what is happening on the air while you are making a call, etc.
One of my rules of thumb is a working inverse of Hanlon's Razor: "Sufficient obstinate or convenient stupidity is indistinguishable from malice." Such basic "flaws" in GSM cannot have been accidents. For example, GSM goes to some effort to assure the identity of the terminals, but there is zero effort for the terminals to assure the identity of the tower, making the "false tower" attack trivial. The insistence on the weakness A5/1 for the "sake of law enforcement" is jaw droppingly mendacious on it's face, since law enforcement can get the datastream from the telco instead of over the air, which mean's that it's purpose is enabling tapping a call without the telco's knowledge or permission (e.g. illegally).
@Mark Atwood: GSM goes to some effort to assure the identity of the terminals, but there is zero effort for the terminals to assure the identity of the tower
Look where the money is. Telcos care only that users cannot steal service easily. Other issues like privacy and security of subsribers are nearly nonexistent for them.
@Konrads at January 5, 2011 6:53 AM
A regular citizen can do it that way (the fake tower approach) too these days with just a few thousand in equipment (really no worse than your average laptop if you think about it.)
USRPs are wonderfully fascinating devices.
People have even set one up large enough to service all of Burning Man. Fairly impressive stuff.
I have recently discovered
as my new favorite VoIP & Chat program. It has end2end (opportunistic) voice encryption with SRTP and ZRTP (and OTR for chat) build in, making it much easier to convince my family and friends to use end2end-encryption without the need to install/configure add-ons etc.
The problems behind the GSM are long and fairly understandable.
First of the US had this thing about "40bit" equivalent crypto key strength when it was first designed.
Then remember the French where involved and their attitude to "citizens using crypto" was "off with their heads" and they supposadly designed the algorithm in question.
There is a story that there where actually three algorithms originaly that where intended to be used and to keep various people happy. (French, other EU Nations, US/rest of the world others in the EU). In all cases they where not part of the published GSM documentation and only available under NDA to "approved persons".
And further this algorithm escaped out from under the NDA becuse a well known Telecoms company sent the documentation to a UK university without getting them to first sign the NDA...
@Richard Steven Hack
Interesting links, thanks for sharing. It was reassuring (although not that surprising, either) to see that Blowfish passwords (the default in OpenBSD) are not included in the sites listed. From the manual:
"For ``blowfish'' the value can be between 4 and 31. It specifies the base 2 logarithm of the number of rounds."
At 15 rounds, a fast P4 takes about 7 seconds to hash a single password. I wonder what computational power would be required to build a rainbow table of every
The impression one gets is that this is done 'on the cheap'. I'm not a big hardware guy, but that laptop is pretty high-end. Like, about 7K.
$15 phones make it sound cheap, but just stating them is misleading - you need a fairly serious bit of computing power to do this quickly.
@ Mike and vedaal
Applications like Redphone and zfone already allow one to easily protect communication between two endpoints, be it a mobile phone or laptop. That isn't secure communication, though. The reason is that the endpoint's aren't trustworthy: mobile OS's are notoriously insecure and telco operators are often in control of the firmware if you didn't replace it. Backdoors anyone?
The next issue is leaks at the application level. A KGB guy once said they could never break the encryption of our STU-III telephones, but they got plenty of info from the first few seconds (or 10) of a call. Many people got lazy and forgot to make it secure.
Assuming the user doesn't have this problem, traffic analysis is the next problem. Certain compression strategies on VOIP create patterns in the encrypted text that give away some of what's being said. I remember when zfone came out there were only two or three of about a dozen clients that used safe compression strategy. That's discomforting. The link must also send data at a fixed rate or the listener can tell when parties are talking and possibly infer information from the length of voice data.
Hence, it's best not to trust mobile phone security. Currently, the best approach is to use a microkernel or separation kernel to separate the security-related components from the user interface. The kernel must also ensure that user input, including voice, is forced through the encryption system during a secure call and plaintext or key material are wiped from registers during context switches. These phones are available on request from firms that custom-designed them for specific partners. The only one I know that's very public is being developed by Sirrix and OK Labs, but it's not ready yet. I'd use this approach on a tiny embedded PC with a microphone and ethernet, with the PC sourced from a trustworthy foreign country.
Sure, your locks might not have a master key designed in. But when it comes down to it, a bump key is pretty much the same thing... (and those weren't designed in either...)
@ Bruce Schneier
"A two-terabyte rainbow table. A few years ago, that kind of storage was largely theoretical. Now it's both cheap and portable."
Are you kidding? Aberdeen was selling 4TB raid servers to small businesses in 2005 for about $7,000. Far from theoretical, but not dirt cheap.
Aberdeen SAN brings iSCSI to SMB's
@ BF Skinner
I quoted the resistance from the GSM Association in my review.
In short, they have consistently called the attacks "theoretical" since 2007, but researchers have continuously demonstrated the attacks are real...but the GSM Association has shown no concern so there has probably been no accounting (yet).
"In 2007-8, a hacking group claimed to be building an attack on A5/1 by constructing a large look-up table1 of approximately 2 Terabytes — this is equivalent to the amount of data contained in a 20 kilometre high pile of books. [...] All in all, we consider this research, which appears to be motivated in part by commercial considerations, to be a long way from being a practical attack on GSM. More broadly, A5/1 has proven to be a very effective and resilient privacy mechanism."
Proven? What has been proven is that even the 128-bit A5/3 algorithm (aka KASUMI) is breakable in a few minutes using cheap hardware.
My guess is the A5/3 crack is what made Nohl switch from demanding it as an upgrade to a whole security wish list for GSM.
"Aberdeen was selling 4TB raid servers to small businesses in 2005 for about $7,000. Far from theoretical, but not dirt cheap."
Fair enough but 2TB is now under US$100
To put the 2TB into perspective, I build a 22 node Linux cluster for my PhD 8 years ago (the data processing for the PhD, not the cluster as subject of the PhD), with 120GB disks in each node (i.e. abut 2.2TB usable space), as 200GB disks were just becoming available and were too expensive. The whole cluster was about 25000 USD/EUR at that time. So out of the reach of amateurs, but not theoretical at all and this included 22 Athlon XP 1.8GHz CPUs and GbE Networking.
You get comparable power in a single machine at around 1000-1500 USD/EUR today, i.e. a factor of 16-25 cheaper in 8 years. The disk I/O bandwidth is not quite the same (around 1.5GB/s aggregated in my cluster, about 300MB/s for a dual disk RAID0 today), but that hardly matters for rainbow tables.
Go back another 8 years or so, and the amount of storage becomes really expensive, my guess would be another factor of 16-25 (Moore seems to fit well here).
Bottom line: For a cryptosystem to survice brute-forcing after time passes, you need to take into account at least a speed-up of two orders of magnitude per decade, possibly more.
"Bottom line: For a cryptosystem to survice brute forcing after time passes, you need to take into account at least a speed-up of two orders of magnitude per decade, possibly more"
I think "possibly more" is a little bit of an understatement ;)
The real bottom line on cracker boxes has been untill recently what goes on in the SOHO commodity PC component market. Because most "cracker boxes" are going to be COTS designs, though this might change with the availability of cheap cloud resources.
And it is getting very difficult to keep tabs on all the important changes that would make a real difference to a cracker box these days (which is why I've stopped keeping track). This is especialy true of some technologies like FireWire which can have a major impact on a motherboard by motherboard bases, but not show up in the published motherboard specs.
Thus you have to test... but the joke appears to be that by the time you have tested even a small set of bits they are becoming obsolescent. So real performance is pot luck.
However a few things can be said,
Mass storage (HD) has atleast doubled in size for the same price break every year fairly consistantly for the past several years, and may actually be improving. Part of this has been the move from PATA to SATA. However even with commodity RAID controlers I've yet to see bus transfer speeds on the PC motherboard being even close to being met except in short bursts. For some reason even though 10,000 RPM IDE drives are available commodity IDE has teneded to be 7,500 RPM. Cache sizes on IDE drives has however not doubled up at the same rate as drive storage capacity, which gives an indicator as to where the performance limitation is currently.
However with iX86 CPU's it appears these days to actually be slowing down with the double up on price break point moved back on the long side of 18 months.
However less than this on GPUs which was around 12months, which might account for the shift in that direction of some projects. But the two high end PC GPU manufacturesr appear to have not done overly much in raw performance terms in recent times (as quite a few gamers have been complaining about).
I've lost track on RAM because the actual improvment is more market driven (by motherboard & CPU), but did get down to a doubling every 11months at one point.
And the star at the moment appears to be flash memory, the price / performance ratio has untill recently been on the likes of USB thumb drives. However recent improvments in reliability in write cycles has made mechanical IDE drive replacment practical and the price has droped in recent times by as much as half in 9months whilst seeing the drive size more than double.
The slow part these days appears to be network comms the SOHO market has been on 1GHz Ethernet for a few years now and switches have not improved much in actual through put.
Then there is the OS issue, obviously you are not going to be looking in the MS direction for many reasons but tunning FOSS OS's is still a black art when it comes to raw performance on comodity hardware.
This is due in part to the hidden performance issue on COTS systems the PC motherboard IO switching, which does not overly effect "application specmanship" but does raw through put. Thus some boards are very good others are truly appalling, even from the same manufacturer on what appear to be very close specmanship figures. Worse you even get significant variation from batch to batch as the manufacturer makes small changes in the design to accomodate different component supply...
However shopping around and a bit of luck will get you quite a nice cracker box for 5,000USD these days. And if you are looking to do it I'd look at "behind the edge" gaming hardware that was getting reasonable reviews a few months ago.
'the researchers replaced the firmware of a simple Motorola GSM phone'
This still requires expertise... until someone packages it.
"This still requires expertise... until someone packages it."
For much of the functionality described you could infact use a "test sim" of which I have quite a few (I need to dig further to see what might actually need the firmware to be wiped).
Or for those that are just programers they can buy a little blue box from an Israeli company (Remember Motorola has very strong jewish and Israeli connections) which uses the Motorola radio modules for GSM and CDMA (G24, K24 etc).
These G24 moduals developed in Israel alow you to program them to do some very interesting things in Java or via an RS232 or USB 1 port and a very much updated set of the old modem AT commands. The little blue box also contains a GPS modual etc...
However if you do wish to replace the firmware in phones you can do it a number of ways which for older phones can usually befound on the web.
The simple fact is in Europe WEEE legislation has opened up an interesting market in second hand phones and bits for repairs etc and the phone manufactures are effectivly "commited" to handing over this otherwise proprietary information and it has a habit of leaking even when under NDA.
This has kind of upset the phone manufactures because it means that old phones stay in the marketplace not landfill which effects their bottom line. Worse it means for consumers in the more affluent west that the African and Indian markets in stolen phones are getting stronger by the day.
If you remember back a few months that Bomb in a printer via air freight had a suspect "set up" by the terrorists as they used her mobile phone details that where traced back to her.
Now imagine what happens when they trace the mobile phones actually used in bombs back to somebody in the US... It's going to be difficult to prove your inocent. And as we know from another terrorist incident wher a US TLA decided that a partial finger print on a bomb (that they incorectly matched) was a US citizen, clearing your name can be difficult and have quite long lasting repercussions...
@ Clive Robinson
Remember that we have more options for cracking crypto these days than moore's law on regular processors. You mentioned GPU's. These are significant because modern GPU's are really just massively parallel processing machines on a chip, which has been used by password crackers. FPGA's provide hardware acceleration at great price points and there's software that allows non-hardware guys to use them pretty effectively. Lastly, the Cell processor's design makes it good for both serial and parallel operation, demonstrated when a Cell cluster forged a MD5-signed certificate.
So, you and Gweihir are right on point about how dangerous it is to assume attackers lack computational resources to break a given cipher. GSM was just BSing so they didn't have to upgrade the phones. I've also heard they might have intentionally used a broken cipher for intelligence agencies, which had the budget to crack the calls. Would be much cheaper than the $50,000+ alternatives, even back then. And those agencies have a history of trying to subtly weaken crypto in widely used standards.
@ Clive Robinson
Good point about set ups. I wouldn't limit the misuse of these things to terrorists. In the observation business that's all covered in the Patriot Act, nobody has to tell the truth.
Contractors can set up targets when they overspend on observations too. If they are working for telcos for example. What's interesting about set ups like that is that its hard to trace back. For instance, today one of my observers said she could add to or drop my case at anytime and it wouldn't stick to her. She thought it was really funny. I wondered if she was part of the telco security group that identified itself to my dentist in a handwritten note that I happened to see?
Regarding ZRTP, I'd like to share a new project born today and open-sourced by PrivateWave Italia S.p.A, an italian company engaged in developing technologies for privacy protection and information security in voice telecommunications.
ZORG, a new open source ZRTP protocol implementation, is immediately available for download from http://www.zrtp.org.
@ Gianluca Varisco
Nice to have one of PrivateGSM's system administrators post their latest product. ;) Looks very useful, though. I seriously wish they released it under the BSD or at least LGPL license. I've found GPL discourages adoption by many development firms and for good reason. High assurance or integrity software development particularly requires a large upfront investment that GPL makes impossible (or really difficult) to recover. I won't be using it on any projects except perhaps extensions to or rewrites of GPL'ed applications. I'd rather use Crypto++, Cryptlib or Botan.
Another criticism I have is that it only does Diffie-Hellman up to 3,072 bits (rather than 4,096) and relies on the increasingly weak SHA-1. SHA-2 should at least be an option. Maybe this is a limitation of the ZRTP protocol, which I haven't analyzed yet. In comparison, Cryptophone uses a 4,096 bit DH key exchange, double encrypts the data with 256-bit AES/Twofish, and uses SHA-2. For those that care, they also use a hardened OS to reduce risk there. The PrivateGSM ZORG library seems weak in comparison.
My bigger gripe, though, is that a secure call can't happen on a phone with an insecure OS or firmware of unknown trustworthiness. iPhone, Android, Win Mobile and Blackberry hacking is way easier than it should be. Must also worry about EMSEC if it's wireless. Have to build a secure mobile platform from the ground up and eliminate all low-hanging fruit. There are a few companies working in that direction.
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.