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.