Stratfor Breach: A (Better) Password Analysis

TL; DR: It seems that well over three-quarters of all the breached accounts were created but never used.

By now it's been widely reported that around Christmas time 2011, Stratfor suffered a significant breach.  The company provides "an audience of decision-makers and sophisticated news consumers in the U.S. and around the world with unique insights into political, economic, and military developments."  Disclosed data includes over 800K records, containing usernames, e-mail addresses, password hashes, physical addresses, and in numerous cases credit card account numbers, shockingly including CVV data.

A hash is the result of  processing data (like a password) with a specific type of algorithm, called a one way function.  These functions are designed such that output cannot be used to derive the input.  Some hashing functions are more effective at this than others, but that isn't the point of this article.  Several articles analyzing the password hashes have been published already, complaining about the collectively poor password practices of end users.  Generally speaking, they are correct.  The Tech Herald article in particular discusses using hashCat and CPU based cracking to recover roughly 80,000 plaintext passwords after about 4 hours of tinkering on account of these weak passwords.

Top 10 Passwords

Using GPU technology, we can just as easily crack those 80,000 passwords in just a few seconds.  We have been working on the disclosed hashes for a few days now and have managed to crack 713,984 (or 86%) of the ~822,000 unique hashes that have been released (roughly 40k of them are duplicates).

The resulting data is interesting, as it's not very often that we get the chance to look at over 700K passwords from a single source.

Probably the surprising and under-reported insight we found is that a majority (about 630K) of the passwords we recovered appear to be randomly generated by the Stratfor site at registration time.  These passwords all have a very specific set of characteristics.  They are eight characters long. They consist of uppercase and lowercase letters, and digits ('mixedalphanum').  With a mid-range dual GPU machine, we were able to test and recover all passwords for that entire character set and length in just over 24 hours.

So what does this tell us?  It's likely that during enrollment, the system generates a password automatically, and e-mails it to the user.  Normally users are required to change the randomly generated password on subsequent logins.  So it seems that well over three-quarters of all the breached accounts were created but never used. It's possible that Stratfor auto-generated a password and didn't require a change on next login, but based on our discussions with users exposed by the breach it appears that this was not the case

Password analysis tools  identify other patterns as well, such as the most common 'base word', or common digit patterns.  Many passwords start or end with digits to pad them out to meet password length requirements.  In the context of all of the random generated passwords, the numbers are very insignificant.  Patterns found have less than .25% commonality among the whole set.

So this begs the question: When there are GPU's at our disposal which make intelligent password guessing and checking easy to do, at a very rapid pace, what is a good password?

A very long one.  How long? As long as the storage mechanism supports.  If you have to look it up everytime, what does it matter, how long it is? It should be randomly generated, and contain as many unique characters as feasible (again, per the constraints of the password policy). Most importantly, it should be unique for that one application.  Should it become compromised, it won't put your other accounts at risk.  Open source password utilities (like KeePass or PasswordSafe) can be used to generate and securely store passwords.  Using strong passwords and securely storing them doesn't protect against keylogging, and if an attacker has deployed a keylogger to your system, they probably have  access to your filesystem as well.

For the curious, we ran the resulting Stratfor dictionary through a password analysis tool called Pipal.

Total entries = 750940

Total unique entries = 713984

Top 10 passwords
stratfor = 12023 (1.6%)
123456 = 625 (0.08%)
0000 = 519 (0.07%)
password = 517 (0.07%)
stratfor1 = 426 (0.06%)
changeme = 265 (0.04%)
strat4 = 265 (0.04%)
1qaz2wsx = 232 (0.03%)
1234 = 228 (0.03%)
wright = 179 (0.02%)

Top 10 base words
stratfor = 13562 (1.81%)
password = 775 (0.1%)
strat = 498 (0.07%)
changeme = 273 (0.04%)
qaz2wsx = 254 (0.03%)
wright = 188 (0.03%)
qwerty = 182 (0.02%)
usmcportal = 148 (0.02%)
intel = 133 (0.02%)
ranger = 127 (0.02%)

Password length (length ordered)
1 = 47 (0.01%)
2 = 41 (0.01%)
3 = 266 (0.04%)
4 = 3735 (0.5%)
5 = 4198 (0.56%)
6 = 32676 (4.35%)
7 = 28599 (3.81%)
8 = 648267 (86.33%)
9 = 16592 (2.21%)
10 = 9819 (1.31%)
11 = 3568 (0.48%)
12 = 2016 (0.27%)
13 = 609 (0.08%)
14 = 359 (0.05%)
15 = 163 (0.02%)

Password length (count ordered)
8 = 648267 (86.33%)
6 = 32676 (4.35%)
7 = 28599 (3.81%)
9 = 16592 (2.21%)
10 = 9819 (1.31%)
5 = 4198 (0.56%)
4 = 3735 (0.5%)
11 = 3568 (0.48%)
12 = 2016 (0.27%)
13 = 609 (0.08%)
14 = 359 (0.05%)
3 = 266 (0.04%)
15 = 163 (0.02%)
1 = 47 (0.01%)
2 = 41 (0.01%)

        |
        |
        |
        |
        |
        |
        |
        |
        |
        |
        |
        |
        |
        |
        |
||||||||||||||||
0000000000111111
0123456789012345

One to six characters = 40957 (5.45%)
One to eight characters = 717821 (95.59%)
More than eight characters = 33119 (4.41%)

Only lowercase alpha = 62342 (8.3%)
Only uppercase alpha = 1482 (0.2%)
Only alpha = 63824 (8.5%)
Only numeric = 9959 (1.33%)

First capital last symbol = 3333 (0.44%)
First capital last number = 50259 (6.69%)

Months
january = 18 (0.0%)
february = 4 (0.0%)
march = 40 (0.01%)
april = 42 (0.01%)
may = 309 (0.04%)
june = 71 (0.01%)
july = 57 (0.01%)
august = 39 (0.01%)
september = 14 (0.0%)
october = 30 (0.0%)
november = 13 (0.0%)
december = 14 (0.0%)

Daysmonday = 20 (0.0%)
tuesday = 7 (0.0%)
wednesday = 2 (0.0%)
thursday = 4 (0.0%)
friday = 34 (0.0%)
saturday = 2 (0.0%)
sunday = 8 (0.0%)

Months (Abreviated)
jan = 450 (0.06%)
feb = 169 (0.02%)
mar = 1794 (0.24%)
apr = 255 (0.03%)
may = 309 (0.04%)
jun = 360 (0.05%)
jul = 274 (0.04%)
aug = 249 (0.03%)
sept = 42 (0.01%)
oct = 208 (0.03%)
nov = 209 (0.03%)
dec = 240 (0.03%)

Days (Abreviated)mon = 958 (0.13%)
tues = 8 (0.0%)
wed = 199 (0.03%)
thurs = 9 (0.0%)
fri = 274 (0.04%)
sat = 319 (0.04%)
sun = 457 (0.06%)

Includes years
1975 = 76 (0.01%)
1976 = 63 (0.01%)
1977 = 61 (0.01%)
1978 = 66 (0.01%)
1979 = 63 (0.01%)
1980 = 68 (0.01%)
1981 = 78 (0.01%)
1982 = 88 (0.01%)
1983 = 67 (0.01%)
1984 = 96 (0.01%)
1985 = 79 (0.01%)
1986 = 68 (0.01%)
1987 = 56 (0.01%)
1988 = 68 (0.01%)
1989 = 47 (0.01%)
1990 = 52 (0.01%)
1991 = 50 (0.01%)
1992 = 40 (0.01%)
1993 = 36 (0.0%)
1994 = 24 (0.0%)
1995 = 46 (0.01%)
1996 = 40 (0.01%)
1997 = 42 (0.01%)
1998 = 40 (0.01%)
1999 = 53 (0.01%)
2000 = 240 (0.03%)
2001 = 137 (0.02%)
2002 = 107 (0.01%)
2003 = 97 (0.01%)
2004 = 115 (0.02%)
2005 = 138 (0.02%)
2006 = 141 (0.02%)
2007 = 150 (0.02%)
2008 = 157 (0.02%)
2009 = 252 (0.03%)
2010 = 365 (0.05%)
2011 = 290 (0.04%)
2012 = 46 (0.01%)
2013 = 13 (0.0%)
2014 = 15 (0.0%)
2015 = 9 (0.0%)
2016 = 14 (0.0%)
2017 = 10 (0.0%)
2018 = 5 (0.0%)
2019 = 14 (0.0%)
2020 = 56 (0.01%)

Years (Top 10)
2010 = 365 (0.05%)
2011 = 290 (0.04%)
2009 = 252 (0.03%)
2000 = 240 (0.03%)
2008 = 157 (0.02%)
2007 = 150 (0.02%)
2006 = 141 (0.02%)
2005 = 138 (0.02%)
2001 = 137 (0.02%)
2004 = 115 (0.02%)

Single digit on the end = 87780 (11.69%)
Two digits on the end = 28409 (3.78%)
Three digits on the end = 9033 (1.2%)

Last number
0 = 6778 (0.9%)
1 = 16724 (2.23%)
2 = 17527 (2.33%)
3 = 18068 (2.41%)
4 = 15993 (2.13%)
5 = 15746 (2.1%)
6 = 15759 (2.1%)
7 = 15946 (2.12%)
8 = 15143 (2.02%)
9 = 16036 (2.14%)

  ||
 ||||  | |
 |||||||||
 |||||||||
 |||||||||
 |||||||||
 |||||||||
 |||||||||
 |||||||||
||||||||||
||||||||||
||||||||||
||||||||||
||||||||||
||||||||||
||||||||||
0123456789

Last digit
3 = 18068 (2.41%)
2 = 17527 (2.33%)
1 = 16724 (2.23%)
9 = 16036 (2.14%)
4 = 15993 (2.13%)
7 = 15946 (2.12%)
6 = 15759 (2.1%)
5 = 15746 (2.1%)
8 = 15143 (2.02%)
0 = 6778 (0.9%)

Last 2 digits (Top 10)
23 = 2888 (0.38%)
11 = 2143 (0.29%)
00 = 2023 (0.27%)
01 = 1999 (0.27%)
12 = 1582 (0.21%)
10 = 1347 (0.18%)
34 = 1335 (0.18%)
56 = 1276 (0.17%)
99 = 1200 (0.16%)
77 = 1076 (0.14%)

Last 3 digits (Top 10)
123 = 2113 (0.28%)
000 = 995 (0.13%)
234 = 838 (0.11%)
456 = 746 (0.1%)
111 = 448 (0.06%)
007 = 432 (0.06%)
010 = 357 (0.05%)
001 = 322 (0.04%)
777 = 292 (0.04%)
011 = 284 (0.04%)

Last 4 digits (Top 10)
1234 = 791 (0.11%)
3456 = 687 (0.09%)
0000 = 606 (0.08%)
2010 = 283 (0.04%)
2011 = 240 (0.03%)
2009 = 220 (0.03%)
2000 = 210 (0.03%)
2345 = 191 (0.03%)
1111 = 146 (0.02%)
2007 = 130 (0.02%)

Last 5 digits (Top 10)
23456 = 682 (0.09%)
12345 = 181 (0.02%)
45678 = 84 (0.01%)
11111 = 69 (0.01%)
54321 = 52 (0.01%)
77777 = 47 (0.01%)
34567 = 38 (0.01%)
00000 = 34 (0.0%)
56789 = 34 (0.0%)
31313 = 29 (0.0%)

Character sets
mixedalphanum: 415810 (55.37%)
mixedalpha: 179778 (23.94%)
loweralpha: 62342 (8.3%)
loweralphanum: 61633 (8.21%)
upperalphanum: 10973 (1.46%)
numeric: 9959 (1.33%)
mixedalphaspecialnum: 6507 (0.87%)
upperalpha: 1482 (0.2%)
loweralphaspecialnum: 1343 (0.18%)
loweralphaspecial: 709 (0.09%)
mixedalphaspecial: 188 (0.03%)
upperalphaspecialnum: 65 (0.01%)
specialnum: 64 (0.01%)
upperalphaspecial: 12 (0.0%)
special: 12 (0.0%)

Character set ordering
allstring: 243602 (32.44%)
stringdigitstring: 207513 (27.63%)
othermask: 150645 (20.06%)
stringdigit: 88585 (11.8%)
digitstring: 39717 (5.29%)
alldigit: 9959 (1.33%)
digitstringdigit: 8209 (1.09%)
stringspecialdigit: 2042 (0.27%)
stringspecial: 296 (0.04%)
stringspecialstring: 277 (0.04%)
specialstring: 52 (0.01%)
specialstringspecial: 31 (0.0%)
allspecial: 12 (0.0%)

Hashcat masks (Top 10)
?l?l?l?l?l?l?l?l: 24525 (3.27%)
?l?l?l?l?l?l: 14922 (1.99%)
?l?l?l?l?l?l?l: 9925 (1.32%)
?l?l?l?l?l?l?d?d: 5381 (0.72%)
?l?l?l?l?l?l?l?l?l: 4312 (0.57%)
?d?d?d?d?d?d: 4180 (0.56%)
?u?u?d?d?d?d?d: 4018 (0.54%)
?l?l?l?l?l?l?l?d: 3207 (0.43%)
?l?l?l?l?d?d?d?d: 3074 (0.41%)
?l?l?l?l?l: 2917 (0.39%)

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.