Password Security Revisited

In my article, “Why Password Rotation is Bad,” I made the case that rotating passwords offers no security benefits, while making them harder for people to use. I stand by my assertion that passwords are hard to use, and rotation only diminishes usability, but I can now say that on a system that implements a password hashing algorithm like bcrypt or PBKDF2, in some cases, password rotation can effectively defeat brute-force attacks, but little protection against dictionary attacks.

bcrypt and PBKDF2 (Password-Based Key Derivation Function 2) work in essentially the same way – instead of salting and hashing the password once, the process is done repeatedly, an arbitrary number of times. (scrypt is a newer alternative that is specifically designed to further resist brute-force attacks) Although adding iterations doesn’t add to the cryptographic strength, it does increase the computing time required to calculate the hash. By increasing the calculation time, we can make password cracking more difficult. Instead of being able to test hundreds of millions of passwords per second, we can slow the attacker to ten per second (at least on one machine with no specialized hardware). The defender can choose a target time for how long it takes to calculate a single hash, and adjust the number of iterations accordingly. The beauty of this approach is that, failing a major breakthrough in mathematics, the number of iterations can be increased over time as computing power increases to keep the calculation time constant. Users’ password hashes can be silently upgraded when the number of iterations increases, so that calc times stay constant for legacy hashes.

Practically speaking, this means figuring out how long to make your passwords becomes an exercise in comparing relative computing power of attacker and defender.

Analysis

For my analysis, I assumed a password has time of 100 ms; this is a reasonable target, as a tenth of a second isn’t going to have much of a negative impact on user experience when logging in. An attacker calculating hashes at the same rate can perform 10 attempts per second, although they could apply additional horsepower to increase the cracking rate. Below are a couple of tables showing the number of days to brute-force a password at a given rate.

Lowercase Letters Only

Number of days to brute-force crack a password of a given length.

Uppercase, Lowercase, and Numbers

Number of days to brute-force crack a password of a given length.

Realistically, hashes only have to withstand attack long enough for the defender to detect that the hash database has been compromised, after which the passwords are all changed or invalidated. If passwords are set to rotate once per year, or if you assume the majority of attacks will be detected within a year, that leads to some interesting conclusions:

Password length required to resist an attack for 1 year (365 days or more).

Three types of attackers are considered, an Average attacker who can check 100x as many passwords per second as the defender, a Strong attacker with 100,000 times capacity, and a Massive attacker with 100 million times capacity. For reference, the largest Botnet on record, Bredolab, had an estimated 30 million systems.

For an Average attacker, any 8-character password will resist a brute-force attack for a year. A “PCI-compliant” 8-character strong password will resist even a Strong attacker for a year. Extending the length to 10 will pretty much prevent any non-government sponsored attack; even a Massive attacker would take 26 years to exhaust the password space (note that some passwords would be found more quickly).

This simple analysis aligns with work done by the developers of scrypt: by their estimates, (p. 14) it would take $130K worth of custom-fabricated 2002 hardware to crack an 8-character bcrypt password and $4.8 million worth to crack an 8-character scrypt password. (Keep in mind these are educated guesses for building ASICs tailored to cracking)

Putting this all together, adding bcrypt (or better yet, scrypt) to contemporary password policies that are already in place at most large companies (8 character, complex password) will protect password hashes against most attackers. Password rotation does improve security, since it puts an upper limit on how long a stolen hash is valid for, but if you assume that password database breaches will be detected in a reasonable time period (12-24 months), then rotation is probably unnecessary. When complexity is not mandatory, even an 8-character all-lowercase password will hold up against an Average attacker.

Unfortunately, bcrypt/scrypt provides little protection against dictionary attacks. Even at 10 attempts per second, an attacker can try 1 million passwords per day; bad passwords will still be guessed very quickly. To defend against this, the only practical approach is to run a dictionary attack against your password database. Some systems allow this to be done at the time the password is set – even a relatively small dictionary, along with good guidance on how to select an acceptable password should provide reasonable protection.

Recommendations

So, to sum up:

• Use scrypt, or a similar password hashing algorithm.
• Set the number of iterations so that hashes take approximately 100 ms, and adjust this value over time as computing power increases.
• Use the same password policy you have today (8 character complex passwords).
• Run dictionary checks against passwords as they are selected.

If you follow all this advice, your passwords will be able to withstand an offline attack long enough for you to discover the breach, removing the need to rotate passwords, and keep you safe against all but the strongest adversaries.

Note however, it doesn’t change my advice for creating passwords for sites you visit, since it’s safe to assume most sites still use relatively weak MD5-crypt or SHA-1 hashes.