Cracking PGP In the Cloud

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."

Comments

Re:Hmm

[jonwil]

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

[VoidCrow]

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:And tons of carbon enter the air

[plover]

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.

Re:Not the way of doing it

[gweihir]

I looked at EC2 for raw processing power earlier this year (my company needs to train a lot of neural nets) and it just isn't worth it, unless you only need the power short term. A high-performance EC2 node gives you 8 cores running at (very roughly) the equivalent of a 2GHz P4, and costs $0.68/hr == about $460 per month, which is only a little less than what an equivalent box (probably a 2.83GHz Core 2 Quad or similar) would cost you. Put power to run that box down at about $0.05 per hour and you can build your own local cluster of equivalent performance for around the same amount of money as you'll save in your first month and a half of operation.

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

[Slashdot Parent]

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.