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