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!!

November 3, 2009 7:04 AM

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

November 3, 2009 7:21 AM 

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: http://reusablesec.blogspot.com/2009/10/analysis-of-10k-hotmail-passwords-even.html

November 4, 2009 1:07 PM 

See http://tools.ietf.org/html/rfc4880 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.

November 3, 2009 3:46 AM 

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.

November 3, 2009 3:48 AM 

Agree.  This is a point that Haroon at Sensepost raised, and the sentiment was echoed by The Register and also Rsnake at ha.ckers.org.  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.

November 3, 2009 9:33 AM 

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 :)

Cracking Passwords in the Cloud: Breaking PGP on EC2 with EDPR

UPDATE 15 Nov 2010: Amazon announces "Cluster GPU Instances", again radically changing the economics of using EC2 for password cracking.  

We've had some questions about whether or not we are going to re-run our analysis using the EC2 GPU Instances.  We may do so, but in the meantime have a look at stacksmashing.net. The have already got some numbers posted for cracking SHA1 on EC2/GPU.

UPDATE 21 Dec 2009: Amazon announces "spot instances", radically changing the economics of using EC2 for password cracking.  

Cloud Computing has enabled some interesting projects:  undertakings that wouldn't have been attempted without the cheap, flexible, easy to provision and simple to release computing power that "cloud" delivers.

The New York Times used Amazon EC2 and S3 to create PDF's of 15M scanned news articles.  NASDAQ  uses Amazon S3 to deliver historical stock information.  We recently tapped into the power of the cloud to perform brute force password cracking attacks which simply aren't feasible using traditional IT infrastructure.

We at EA are "pro-cloud" and have been assessing the security of various incarnations of cloud for some time now.  However, until recently we had not had an opportunity to leverage the massive scalability that cloud promises.  That changed a few months ago when we were approached by a client who needed several PGP ZIP archives decrypted through brute force.

When faced with the task of brute forcing PGP passphrases, we immediately thought of Elcomsoft.  We had witnessed the drama at Infosec 2009 in London when PGP had banners removed from Elcomsoft's booth, and that made a lasting impression.  We downloaded the trial version of Elcomsoft's Distributed Password Recovery software,  but found that unfortunately it was not able to properly parse the old PGP ZIP files.

Luckily, Andrey Belenko, the Elcomsoft wizard who gave the world GPU accelerated password cracking was able to get us a patch for the EDPR dll which handles PGP ZIP's. We were in business!  Unfortunately,  on a fast dual core Windows7 box we were looking at something like 2100 days to brute force a reasonably long complex passphrase for these PGP ZIPs.

This was clearly unacceptable, so we looked to the cloud for salvation.

This post goes into significant detail about how to get the Elcomsoft EDPR solution working on Amazon EC2, so if you are interested in the process and want to build your own personal NSA style distributed cracker keep reading.

During the course of this project, we had some interesting insights regarding the relative strengths of password length versus complexity.  Feel free to skip over the implementation details and get straight to the analysis.

If you're still with us, thanks for tuning in.  Let's continue.

Per NIST's cloud presentation, the definition of cloud is as follows:

"Cloud computing is a model for enabling convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction. "

Using a cloud provider was ideal for a project such as this, as the client really had no residual use for a massive physical cluster of Windows machines once the passwords were recovered.  Thus we moved forward with Amazon EC2, but in order to capitalize on the "rapid provisioning" promised by cloud we wanted to be sure that we could rapidly deploy a large number of EDPR cracking agents without manually configuring each one.

Elcom's EDPR runs only on Windows, so our first chore was picking an EC2 AMI which was fit for the purpose of creating a template instance to clone (or bundle, in EC2 speak).  EDPR is a 32 bit Windows app, so there was no need to use a 64bit Windows AMI.  We selected

ami-df20c3b6-g and then started an instance from a Linux shell using the EC2 API Tools as follows:

ec2-run-instances -k ssh-keypair ami-df20c3b6-g default

Once the instance was up and running, we enumerated the instance ID and public IP address of the running instance with the command

ec2-describe-instances

Once the instance status has changed from "pending" to "running" we can extract the administrator password for the instance, using the command

ec2-get-password -k ssh-keypair.pem $instanceID

AWS Windows AMI's output the (generated) encrypted administrator password for the instance to the system console.  This API Tool works by grabbing this encrypted console output, and decrypting it with the private key specified on the command line.  This private key must match the public key which was used when the instance was spawned.

With the administrator password in hand, we now must configure the EC2 firewall to permit inbound RDP traffic to the instance.

ec2-authorize default -p 3389 -s $trusted_ip_address/32

Now we can RDP into the instance and configure EDPR.

As mentioned previously, the ec2-describe-instances command will provide the public IP address of the running instance.

Use the administrator password obtained from the ec2-get-password command to login to the instance.

Start IE and download http://www.elcomsoft.com/download/agent_setup.exe to somewhere convenient.  Note that we made the architectural decision to use EC2 for EDPR agents, but not the manager.  This was for two reasons.  One is that the encrypted files we were setting out to crack were client confidential, and thus there was no desire to upload them to systems outside our ultimate control.  Secondly, EC2 instances have a limited concept of state, and we didn't want to mess around with EBS volumes to persist the target files across instance generations.

We also configured the firewall in front of the EDPR manager system to permit TCP/12121 from anywhere, as it was difficult to pin down a sane range of public source addresses for EC2 instances.

Now launch the EDPR agent installer, and accept the license and all the default options.

Once the installation is complete, the EDPR agent will start.  Go to the General tab, and configure the public IP address or hostname of the EDPR manager you have configured.

On the Interface tab set the Start-up Mode to "At Windows Start-up".

EDPR creates a pair of registry values which are used to uniquely identify the agent when checking in to the manager.  We need to scrub these values before cloning this instance, otherwise every single instance we spawn will appear to be the same agent to the manager, and the job handling will be totally corrupted.

To clear these out, Start, Run, regedt32 and then navigate to the following key:

HKEY_LOCAL_MACHINE\Software\ElcomSoft\Distributed Agent\UID

Set the value of the UID key to null, but DO NOT DELETE THE KEY.

With the EDPR agent installed and configured, we can now bundle the EC2 instance.  This action is akin to creating a 'template' in VMware land.  To do this, we first need to install and configure the EC2 AMI Tools.

The syntax for the ec2-bundle-instance command is as follows:

ec2-bundle-instance $instance_id -b $bucket_name -p $bundle_name  -o $access_key_id -w $secret_access_key

Bucket name and bundle name can be whatever you like, just remember them because we will need to those values again when we register the bundled AMI in the next step.

The bundling process basically runs sysprep on the Windows instance, and then compresses and copies the instance to S3.

ec2-describe-bundle-tasks

Can be used to check on the progress of the task.  It will take several minutes.  Once the bundle task is complete, the following command will register the bundled AMI, which allows it to be used to run instances.

ec2-register $bucket_name/$bundle_name.manifest.xml

The registration command will return an AMI ID, which we will use to spawn instances of the EDPR agent.

IMAGE   ami-54f3103d

Now start the EDPR manager, and configure a task.  For the purposes of this example, we configure a task to brute an password composed of uppercase letters, lowercase letters, and the numbers 0-9, with a length of between 1 to 8 characters (heretofore represented as ([A-Za-z0-9] ^ 8) against one of our client's PGPZIP files.

To start working on this job, we start a single instance of our EDPR agent with the following command:

ec2-run-instances -k $ssh-keypair ami-54f3103d -g default

Shortly after the instance status changes from 'pending' to 'running', we see the agent check in with the EDPR manager.

This instance was started with the default parameters, and so is an EC2 "small" instance.  Sure it costs only $0.10 USD per hour, but as we see here it is only trying about ~500K keys per second.  How long will it take to brute force the key space?

What?  ~3600 days?  Ten years?  Unacceptable!

We now use the following command to deploy ten additional instances:

ec2-run-instances -n 10 -k ssh-keypair ami-54f3103d -g default -t c1.medium

The -n 10 parameter tells EC2 to launch 10 instances.  We also specify the c1.medium instance type, which is a "High CPU" instance, and raises the price from $0.10 per hour to $0.30 per hour.  According to Amazon's documentation, these instances provide "5 EC2 Compute Units (2 virtual cores with 2.5 EC2 Compute Units each)", compared to the "1 EC2 Compute Unit (1 virtual core with 1 EC2 Compute Unit)" provided by the small instance we initially spawned.

We now see that we have now invited many more cracking agents to the party.  We also note that these instances report two CPU's, and are benchmarking in at 2+M keys/second.  Sounds like the high cpu instances are in fact delivering on their promised additional horsepower.

What has this done to the time required to brute force the keyspace?

Down to ~122 days.  Still unacceptable, but we're moving in the right direction.  We kick off another 89 instances (to bring our total to 100, which is presently the upper limit of our Elcomsoft EDPR license), but run into a snag:

ec2-run-instances -n 89 -k ssh-keypair ami-54f3103d -g default -t c1.medium

Client.InstanceLimitExceeded: Your quota allows for 9 more instance(s). You requested at least 89

It appears that Amazon isn't keen to have folks DOS'ing EC2 by spawning arbitrarily large numbers of instances.  A quick visit here and a reasonable justification should have us cracking away at top speed in short order.

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.

[UPDATE 3 NOV 09: Amazon responded with a request for 'more information'.  However, our friends at Sensepost demonstrated a creative way to bypass this limit using Python scripts at Blackhat 2009.]

From what we have seen to date, Elcomsoft EDPR appears to scale linearly as additional cracking agents are deployed.  We are confident that as long as the EDPR manager system is properly equipped that you could easily deploy the maximum number of agents permitted by your EDPR license and cracking performance will scale linearly.

After running this cloud based distributed cracking system for a number of weeks against various types of encrypted target files, we have put together a rudimentary analysis of the EC2 cost required to brute force the various keyspaces.  This analysis may be insightful as you develop your enterprise password policies, or choose your personal passwords.

Next Page: Results & Analysis

Cracking Passwords in the Cloud: Insights on Password Policies

Previous Post: Breaking PGP on EC2 with EDPR

UPDATE 15 Nov 2010: Amazon announces "Cluster GPU Instances", again radically changing the economics of using EC2 for password cracking.  

We've had some questions about whether or not we are going to re-run our analysis using the EC2 GPU Instances.  We may do so, but in the meantime have a look at stacksmashing.net. The have already got some numbers posted for cracking SHA1 on EC2/GPU.

UPDATE 21 Dec 2009: Amazon announces "spot instances", radically changing the economics of using EC2 for password cracking.  

For years we have been preaching the virtues of long, complex passwords.  Putting dictionary attacks aside for a moment, one of the most interesting revelations of this project was the high cost of brute forcing simple passwords.

By simple here we mean a password only containing lowercase letters a through z.  And by optimistic cost to brute force we mean the EC2 usage charges we would incur to cover 50% of the keyspace.  If we're unlucky, we double the optimistic cost to calculate our "max cost" to exhaust the keyspace.

Clearly each additional character of password length adds a significant amount of cost to the brute forcing effort.  One might speculate that an average corporate adversary could quite easily come up with ~$50K USD to brute an 11 character simple password, but struggle to find the $1.5M USD to brute a 12 character simple password.

Next let's look at the case of a slightly more complex password, containing upper and lowercase a-z, plus the numerals 0-9:

In this case the hypothetical threshold between doable and not worth it falls at the 11 character password boundary.

Finally let's examine the cost to crack a truly complex password, consisting of upper and lowercase a-z, plus the numerals 0-9, the space character, as well as 32 special characters (think !@#$%^&*() etc):

In this case the "not worth it" threshold is at 9 character passwords.

So, looking at this data simultaneously, it's easy to make some recommendations about password length.  Assuming we are dealing with an adversary who is unwilling to spend more than $1M USD to brute your password, where are the length versus complexity sweet spots?


Referring to the chart above, we decide that simple passwords (a-z) are OK, provided they are at least 12 characters long.  Add numbers to your simple password, and again you're OK at 12 characters.  Introduce uppercase and special characters into the mix and 10 character passwords are acceptable.

Now let's consider a slightly different scenario.  Let's look at an 8 character password of variable complexity.  The complexity will start at 26 [a-z] and rise to 95 [a-zA-z0-9@#$ etc.].

Here we see that the cost to crack the 8 character password increases steadily with complexity, and that even fiercely complex 8 character passwords are still fair game for our adversary with <$1M to spend on a brute force attack.

Now let's look at fixing the complexity at a low value of just [a-z] and looking at the effect of increasing the length of the password on the cost to brute force.

Here we see that the cost to crack the simple password consisting of a variable number of just lowercase alpha characters jumps dramatically between 13 and 14 characters.

Remember, dictionary attacks are different than brute force attacks.  So if your 12 character simple password is composed of dictionary words, all bets are off.  Finally, remember that while a determined attacker may not have $10M USD to spend on EC2 cycles to crack your 10 character super complex password, a simple client side exploit may make that a moot point.

Q&A from Cloud Security Summit Presentation

Rob Randell from VMware and David Campbell from EA did a presentation at Brighttalk's Cloud Security Summit on Wed 30 Sept.

The session was fun, well attended, and received good ratings.  However, our time management left something to be desired and we ran out of time before we could take audience questions.  As promised, we'll answer them here.

Q: How in a VM deployment model, do you manage binding the "right" VM image to a "known" hypervisor? In other words, how do you lock a VM image to a specific H/W server via the hypervisor so a VM image cannot be abducted and re-used outside an enterprise or hosting provider?

A: Interesting question.  We see two options here.

1. You could 'sign' the VM, and configure the hypervisor to only boot a VM after first validating the signature.  This helps you keep unauthorized VM's from running in your infrastructure, but would do little to stop an attacker with access to your VM from booting it on a hypervisor they control.
2. You could encrypt your VM to a public key presented by a hypervisor, cluster, etc.  At boot time the hypervisor would use the private key to decrypt the VM just before boot.  Either of these scenarios introduce key management issues.  Also, at this time we are not aware of any commercial or open source solutions which incorporates any of these strategies out of the box.

After demonstrating the SSL MITM attack on the vCenter admin, we received this question:

 Q: It appears that multi-factor authentication would help with these issues. Can we implement multi-factor authentication to resolve using default certificates? Can we use "user-level" authentication to prevent these issues... going beyond PKI certs for the host but actually authenticating to the VMware Vcenter?

A: In short, no.  See http://www.schneier.com/essay-083.html for info about how multi factor authentication systems are still vulnerable to man in the middle attacks.  For example: a Windows enterprise using smartcard based two factor authentication for domain logon, and using Windows auth for vCenter login would *still* be vulnerable to man in the middle attacks for as long as the vSphere client continues to negotiate TLS (SSL) with an untrusted third party.  Multi factor authentication is great, but in this case replacing the self signed certificates presented by vCenter by default is the proper mitigation to SSL MITM threats.


After demonstrating the browser exploit leading to an attacker compromising an EC2 admin's EC2 ApiTools keypair, we received the following question:

Q: If the manager accesses EC2 management using multi-factor authentication, is it not the case that this attack is mitigated?

 A: In our demonstration the attacker used a browser exploit to run arbitrary code on the victim's workstation.  This code allowed the attacker to download credentials from the victim (an X.509 certificate and private key in .PEM format) which were used to nefariously administer the victim's EC2 infrastructure in the cloud using the EC2 API Tools.


Amazon recently began offering a multi factor authentication system  based on a Gemalto Ezio token which is used to provide two factor auth for login to the EC2 management console (web interface).  We doubt that this new 2FA service extends to the EC2 API Tools, which is what we exploited in the demo.  However, this piqued our interest, and we will find out!   UPDATE: Our hunch was correct.  AWS MFA provides two factor auth ONLY for the web management console, not the API Tools.  


Another method for protecting the private key used with the EC2 API Tools is to encrypt the private key, using a command such as "openssl rsa -des -in pk.pem -out pk_encr.pem".  It appears that the EC2 API Tools do *not* presently support encrypted private keys though, as instead of prompting for the passphrase when the key was needed, the API Tools bombed out.

EA presenting with VMware at Cloud Security Summit

We are pleased to announce that EA Principal Consultant David Campbell will be presenting with security expert Rob Randell from VMware at Brighttalk's Cloud Security Summit on 30 Sept 09.

The talk is titled "Securing Virtual Infrastructure", and though we may use VMware for certain examples, the principles we discuss will apply to most hypervisors.  We will be discussing, and demonstrating (to the extent that Brighttalk's webex platform will allow) a couple of practical attacks against virtualization management infrastructure that may be eye opening.

The webex goes live at 4pm PDT, 7pm EDT on 30 Sept 09.  The link to the registration page is here.  If you aren't able to attend the live session the event will be archived and available for streaming afterwards also.

Note that we have received feedback from folks who attended our last Brighttalk preso that the registration process was a bit over the top and required a lot of personal info for a "security session".  We encourage anyone who wants to attend the session but is put off by the level of personal information requested by the registration form to just put placeholder data in any fields they deem too invasive.