Cracking PGP In the Cloud 167
pariax writes "So you wanna build your own massively distributed password cracking infrastructure? Electric Alchemy has published a writeup detailing their experiences cracking PGP ZIP archives using brute force computing power provided by Amazon EC2 and a distributed password cracker from Elcomsoft."
Re:And tons of carbon enter the air (Score:3, Interesting)
I was under the impression that crypto like PGP was based on stuff which would (in theory) take millions of years to crack even with every machine on earth dedicated to it?
Pointless (Score:3, Interesting)
Yes obviously cracking passwords scales linearly, we've known that for a long time. Oh, you could get 100 machines brute forcing instead of one, but what good is that? Either the password is crap and you crack is easily, or it's helluva complex and scaling it up 100x won't do a damn thing. In this case it looks like they just picked some random range and said "Hey, this is unfeasible on a single machine and doable on a cloud, let's do that" but they haven't produced any credible evidence it is in this range. Not unless semi-complex password possibility matches their corporate password policy or whatever.
Re:Pointless (Score:3, Interesting)
Yes obviously cracking passwords scales linearly, we've known that for a long time. Oh, you could get 100 machines brute forcing instead of one, but what good is that? Either the password is crap and you crack is easily, or it's helluva complex and scaling it up 100x won't do a damn thing. In this case it looks like they just picked some random range and said "Hey, this is unfeasible on a single machine and doable on a cloud, let's do that" but they haven't produced any credible evidence it is in this range. Not unless semi-complex password possibility matches their corporate password policy or whatever.
It is significant because the lone hacker in his basement or the IT department of your unethical competitor might not have a spare server farm with 200 CPUs lying around. They show just how effortless it has become to do brute-force if you have a couple of minutes to set it up and a few spare bucks for the computing power... (And I bet that very few corporations have a password policy that mandates anything exceeding 8-char alphanumeric - which can be cracked for 45 bucks, as they show...)
All communications securely encrypted (Score:3, Interesting)
One of the adversized features of ElcomSoft Distributed Password Recovery is that all network communications between password recovery clients and the server are securely encrypted. How is that possible, I wonder.
Re:And tons of carbon enter the air (Score:3, Interesting)
Schneier had an interesting piece on deriving a limit of the necessary key length from thermodynamics. ... assuming your password is only bruteforce-able ... otherwise http://xkcd.com/538/ [xkcd.com]
http://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html [schneier.com]
Re:And tons of carbon enter the air (Score:2, Interesting)
I'm also a bit confused. I've never used PGP to make an encrypted zip file, but I use GnuPG to encrypt emails all the time and I, too, was under the impression that it was infeasible in practice to brute force the encryption.
Is the difference that with PGP/GnuPG email encryption, our passwords are merely decrypting our keys which are themselves fully 128 or 256 bits long or whatever? Whereas in this situation with the ZIP file there was no separate key - the password was the key? (I haven't read all of TFA)
Re:Bottom Line: Use Long, Unusual Passwords (Score:2, Interesting)
Passwords are protected in the US by the fifth amendment, for now...
The UK is a different story, though you can always claim to have forgotten your password.
Perhaps an interesting set up would be having 2 computers on separate power supplies running full disk encryption. Each can only boot by requesting a keyfile from the other.
Hence you can shut one down, but when both go down, the two systems become unbootable.
In a police seizure, they will likely disconnect both computers, and unbeknownst to them, completely destroy their chances of recovering the data.
Now no one can compel you to surrender the decryption keys, which can be a good thing or a bad thing. I leave you to think about the de facto punishment courts can issue for contempt.
Re:And tons of carbon enter the air (Score:3, Interesting)
I thought the problem was that there was an infinite number of matching passphrases producing invalid results. Like, only a very simple hash or CRC - 1 or 2 bytes checks the validity of the passphrase to protect from common typos, but if you try even semi-hard, you will get a hash collision, the data decrypts, but it decrypts to garbage - a standard GIGO filter with a very weak anti-garbage protection on input.
This way, on top of one correct result you should get an infinite number of incorrect results and unless you have a clue how the correct result should look like and use some heuristics to distinguish it from garbage, you'll be no wiser than before... (and if it was additionally encrypted with anything that makes it look like white noise, there is simply no way to tell it apart from pure garbage.)
Re:Hmm (Score:5, Interesting)
The best solution (if you are dealing with a desktop system) is to have the pass-phrase and keys but also have a small GPS module. If the usb key is not close to where it should be (with a fairly big margin for the fact that cheap GPS modules arent exactly accurate) it would erase the pass-phrase
If they try to force you to hand over your password (e.g. UK RIP act), you just hand it over (to the guys who seized your computer and are now trying to use it somewhere else other than the required GPS location) and boom, the data is gone forever.
If you need to move house, just log in from the old house and reset the GPS then when you get to the new house, log in and put in the new coordinates.
Re:And tons of carbon enter the air (Score:4, Interesting)
To pick a trivial example.
Your password is 'password'.
Cracking algorithm attempts to open your encrypted archive using a list of, say, 20,000 english words. 'password' is 5th on the list. After 5 iterations, you notice that your decryption attempt has yielded data that looks like a valid zip archive, or contains english words. Result. You win the internets.
You can refine this.
1. Attempt a password list crack.
2. Attempt a Markov-chain based crack, looking for english-like words generated by your Markov Chain algorithm. Like, say. 'bibble' or 'foglet'. Tr
3. Repeat the above for all letter case combinations, and number/letter replacements - like B1bb7e, or f0Glet.
Et cetera,
The edge you have is that people often choose known words as passwords, or easy-to-remember nonsense words.
This reduces your password search space *hugely*.
For example, say your pgp doodad accepts up to 10 character passwords formed from any combination of letter case or number. 26 lowercase letter, 26 uppercase letters, 10 numbers. Your maximum search space would be the sum of all (26+26+10)^n, where n iterates from 1 to 10, or 853,058,371,866,181,866, or 8.5x10^17. This is the size of the set of all possible mixed case alphanumeric passwords up to a maximum length of 10. You would have to try each of these combinations to fully search this space. This is called 'brute forcing'.
It is a *much* larger number of passwords than the 20,000 in your dictionary list....
So, you use the search space limiting techniques *first*, which will yield a result in 95% of all cases. Then, you try brute force, or give up.
Re:Hmm (Score:3, Interesting)
The best answer of all is "physical seganography" i.e. 802.11 NAS built into something that the cops are unlikely to seize (yet which has a legitimate need to be plugged in and doing what it does)
Re:Pointless (Score:3, Interesting)
Actually salting does not help against brute-force. It only helps against dictionary attacks.
However other things help, for example instead of running your password/phrase through a crypto-hash once, do it a million times or, say, for 100ms (store the number or iterations). This increases effort proportionally.
Example: SHA-256 does around 100MB/sec on a single modern CPU. That is roughly 3 million hashes/sec. Doing this for 0.1s gives no noticeable interactive delay, but increases the effort 300'000 fold, compared to a single hash iteration. With a 8 char a-z password (4.7 bits/char of entropy, i.e. a total of 37.6 bits), you will need on average 104*10^9 attempts. Each takes 0.1 sec and the EC2 cloud gives something like 8 modern cores for $0.3/h. That would be $7.8 Billion for brute-forcing the password.
See, 8 char a-z passwords are not so bad. The problem here is that the basic PGP design is rather old and these tricks were not used then.
Re:And tons of carbon enter the air (Score:5, Interesting)
It wasn't carbon, but the fuel consumed that was my first thought. Back when distributed.net was busy burning energy to win these pointless challenges, I did some rough calculations on the electricity required to solve it.
Turns out that the energy spent breaking RC5-64 used somewhere between 2 and 50 *trains* full of coal.
And that was only the energy directly consumed by the computers involved, and not any of the heating or cooling costs associated with it. And sure, more modern CPUs are more energy efficient, and I extrapolated the figures from a lot of published sources and made a lot of assumptions. But regardless of CO2 or greenhouse gasses or dirty coal or any of that environmental stuff, that's a lot of irreplaceable fossil fuel that's now gone.
I don't think it's sad or tainted to consider the overall impact of what you do. Saying "oh, I want to help search for E.T." is one thing. It may cost you an extra 1440 kWh/day, but you have the money, no big deal. But understanding that SETI@HOME is causing tens of thousands of people around the globe to collectively burn tons of fuel every day might make some of the volunteers rethink their decision. Ignoring that is the kind of perspective that thoughtlessly sucks up our finite resources.
And no, I don't consider alien hunting a valuable use of energy, at least not at this time in our history. Once we have fusion reactors or some other form of "free energy", all that will change.
Go ahead and crack keys, search for Extra Terrestrials, or fold proteins, or whatever you want to do with your box. Leave your lights on 24x7. Run the furnace and the air conditioner together. Just understand that what you do today has an impact, and consider the value of the outcome.
But did it work (Score:2, Interesting)
FTA, they mention that Amazon didn't allow them to create more than 9 instances, so they couldn't crack the passwords in less than 122 days. (a request to get suitable amounts of computing power was made, but takes time, is not enabled by default, and wasn't available at the time of writing?)
Dear Sir,Thank you for submitting your request to increase your Amazon EC2 limit. It is our intention to meet your needs. We will review your case and contact you within 3 - 5 business days.
Re:Not the way of doing it (Score:4, Interesting)
Indeed. EC2 is rather expensive for most applications. It really only pays off if you may need a lot of power on short notice (but usually need none). The article describes one of the very few general applications. There is also the problem that even EC2 only scales so far. You would probably not get the cores to do a 12 char password in parallel. In addition, EC2 has problems like confidentiality and data transfer also costs money. And you have no control over how reliable and available the resources are.
Having done a (small) bit of high-performance computing myself, I believe the most cost effective way is to get some bright people that do understand current computer hardware and your problem, and then have them get the hardware they think does the job best, preferably of the white box variant. I went so far to get components, because having a student assemble them got me something like 20% more cores for the same money and exactly the hardware I wanted. Never had serious issues in several years with the resulting infrastructure.
Re:Not the way of doing it (Score:4, Interesting)
EC2 is rather expensive for most applications. It really only pays off if you may need a lot of power on short notice (but usually need none). The article describes one of the very few general applications.
I think most people don't realize just how often they need a lot (or even a little) computing power on short notice. Once you get used to that way of thinking, it's a little addictive. By way of example:
I host one of my company's websites on Dreamhost. Am I insane? Dreamhost experiences an outage every few months or so. Incompatible with a business application, right?
Wrong. I have an EC2 bundle with a startup script that automatically configures the instance and fails the IP address over. If my company's website is ever down for more than 2 minutes, a failover is triggered. The website on EC2 takes about 2 minutes to come up, so my maximum downtime is 5 minutes or so. That's an acceptable amount of downtime for my application, a brochureware site that displays vacant apartments and accepts rental applications (several hours, naturally, would be unacceptable).
EC2 as a cold spare saves me money. If I had to use a reliable webhost, it would cost me, what, $50/mo? Dreamhost costs $5, and I probably use about $5-$10/yr in EC2 charges for the cost spare. Based on the above assumptions (I have no idea what a reliable webhost costs these days), EC2 saves me roughly $530/yr.
What another example? A client of mine has a deployment process where they first deploy to a staging environment before production. Because the production environment has a clustered DB and clustered app server, their staging environment has 2 DB nodes and 2 web nodes. That's 4 machines that see roughly 50 hours of use per year. Not efficient at all.
We considered VMware, but they didn't have the admin expertise in-house, and I forget what the license cost was, but that was an issue, too. In addition, they could not do load testing because they didn't have enough boxes to replicate the production system architecture. Enter EC2.
Now, they spin up as many EC2 instances as they need for whatever testing scenario they need. 4 instances for application staging, and 15 for load testing, at a cost of a fraction of one of their staging boxes that sat idle 99.9% of the time.
Like I said, the concept that you can have a virtual box whenever you need it and then throw it away when you're done is very addicting. I find it to be extremely convenient.
Re:Not the way of doing it (Score:3, Interesting)
Re:Bottom Line: Use Long, Unusual Passwords (Score:3, Interesting)
If one is going to crack passwords, one may need to (eventually) test the key space. If your passphrase is in the "easy" part of the key space (such as if you don't use special characters), it will be found very early on. So, yes -- you must use special characters (and not in a prescribed pattern) in order to put your key in the larger portion of the key space.
( (easy to crack) ........... hard to crack ...... )
One can think of the key space as a Venn diagram. If your key falls in the "easy" to crack space, it's much more vulnerable than if it's in the hard to crack space. As someone mentioned above, though, you really needto ensure the passphrase was random: if you're just replacing some letters in words with numbers, that will be crackable by a Markov chaining attack.
We can also look at our key space in terms of what tactic can be used to crack it:
( ( (easy: dictionary attack) ... medium: Markov chaining attack ) .... hard: brute force attack )