Wednesday, November 4, 2009

Cracking Passwords in the Cloud Q&A

Thanks to everybody who read the story and provided questions and comments.  El Reg picked up the story, and the Slashdot thread saw loads of activity also.  There were quite a few good questions raised by commenters here and elsewhere on the web.  We will try to answer as many of them as possible in this post.

Anonymous said...

So did you crack the password in the end? How long did it take? You've left us hanging here!!

So far we have run [a-z0-9] (length=8) on all of the target files with no luck.  We are in the process of running [a-zA-Z0-9 !@#$%^&*()] (length=8) on the targets, however the EC2 charges are significant and the client is interested in building out their own infrastructure to take over this work so that the OpEx can become CapEx and the equipment be used for multiple purposes.

Anonymous said...
first of all, thanks a lot for the interesting write-up!
Just being curious: decrypting a PGP encrypted file through bruteforce cracking the passphrase - does that mean you were in possession of the (passphrase protected) private key?
Or was the file encrypted using a symmetric key?
Decrypting a file using ONLY the passphrase contradicts my understanding on how PGP works...

The PGP ZIP archives we are trying to recover are encrypted to a passphrase, NOT to a key.  It is our understanding that if the files had been encrypted to a public key, we would not even be able to attempt recovery with EDPR unless we also had access to the (encrypted) private key.

Matt Weir said...

Great article. I'm curious if anyone could tell me what hashing/encryption algorithm PGP Zip uses. Aka, how many rounds of MD5/SHA1 ect does it use to convert the user's password into the encryption key. That way I could estimate the cost to crack other hash types, (such as NTLM or WPA). Also, are the graphs on the results page created by attacking PGP Zip files as well?

Finally, you almost never want to do a pure brute force attack. Using Markov models can drastically reduce the number of guesses you need to make even when performing a non-dictionary based attack. Some analysis that I did on the hotmail set, pure brute force vs. Markov models can be found here:

See for details on the OpenPGP message format, which is what I believe PGP uses to create PGP ZIP files.  You are also correct that pure brute force is inefficient, and were not the only one to point that out:

As Bruce mentions, there are far more efficient ways to crack passwords, and the article he links to discusses those options in detail.

In general, EDPR is designed to be FAST, not smart.  The creators of EDPR intend for it to be used as a 'last resort' sort of tool, to brute force passwords that can't be recovered using more intelligent methods.

Ariel said...

You are totally ignoring CUDA (high end NVidia graphics cards) when giving your password recommendations.

CUDA can crack passwords about 10 to 100 times faster than CPUs can, and costs less.

Between comments here and on Slashdot, probably the most frequently raised point was that GPU accelerated cracking is MUCH faster than what we were getting with our EC2 instances.  WE KNOW.  EDPR does NOT support GPU acceleration for cracking PGP ZIPs, and thus even if EC2 could offer us an instance with 10 GeForce GTX's it would do us no good for this particular application.  See the EDPR GPU Acceleration FAQ for a list of currently supported file and password types.

Joe Hacker said...

One problem with that analysis, which is interesting for sure. Botnets are free. People hacking passwords are very likely to have access to botnets. So I wouldn't base my password length just on assumed cost. Why do that, when I can add few more chars above 12 chars, and make it inviable to be hacked with all the computer power on the planet for the foreseeable future.

Agree.  This is a point that Haroon at Sensepost raised, and the sentiment was echoed by The Register and also Rsnake at  The Sensepost talk "Clobbering the Cloud" at Blackhat Vegas 09 specifically demonstrated how easy it is to create hundreds of EC2 accounts (using a single credit card), totally subverting the EC2 per account instance limit.  Even if Amazon cracks down on allowing a single credit card to be used to open multiple AWS accounts, I imagine that blackhats will still find it quick and easy to script up mass EC2 enrollment with stolen credit card numbers.  Such a methodology might give traditional botnets a run for their money.

Blrfl said...

Interesting analysis, but I think you're leaving out one detail:

With just about everything using digested passwords and anything really important using good algorithms, social engineering and ThugWare become awfully attractive options.

Yes.  We also had several commenters suggesting that precomputation attacks (such as rainbow tables) would be a better plan.  Again, WE KNOW.  However, when trying to recover salted hashes, rainbow tables are of limited utility, because an attacker needs to precompute tables for each possible salt value.

We did mention by way of disclaimer that a client side exploit could render your 34 character uber-complex passphrase completely useless.  Several of our readers mentioned the 'wrench attack' against such passwords, which is also a serious threat, and is best described by the following comic from xkcd :)