Estimate the time to crack passwords using bcrypt

Question

I am reading on the Ashley Madison password exposure case. Dean Pierce was able to output about 4000 cracked passwords within 5 days given his system. I'm assuming that he generated a table of hashes to compare 1 to 1. My question is, how long does it take to crack or fully test a bcrypted password given any cost [n]?

Answer 1

In June 2015, using eight GTX TitanX video cards, they were able to get hashcat to perform:

• 14,455 hashes/second (cost factor 5, i.e. 32 iterations)

With a rig of 8 video cards, they got:

• 155,642 hashes/seconds (cost factor 5, i.e. 32 iterations)

Of course nobody actually ever used bcrypt with a cost factor of 5.

At the time of publication of BCrypt (1999) the default costs were:

• Normal User: 6
• Superuser: 8

And also:

"Of course, whatever cost people choose should be reevaluated from time to time."

The question is how long should a hash take to compute. At the time of deployment in 1976, crypt could hash fewer than 4 passwords per second. (250 ms per password)

In 1977, on a VAX-11/780, crypt (MD5) could be evaluated about 3.6 times per second. (277 ms per password)

You should be adjusting your bcrypt work factor so it takes 250-500 ms to compute.

Our implementation uses the cost factor 11 as a lower bound. And it then benchmarks the system, increasing the cost if it's being computed too fast.

And the function to check a password forces you to deal with the consequences of that:

Boolean passwordRehashNeeded;
BCrypt.CheckPassword(rawPassword, savedHash, out passwordRehashNeeded);

Sometimes a re-hash is needed:

• because we're going from 2 -> 2a -> 2x -> 2y -> 2b -> ...
• hardware is too fast these days, and is calculating your saved hash in 230 ms

Hashing speeds

Back to the question of time to crack. For different bcrypt cost factors, the CPU a the eight video card monster, the hashing speeds are:

| Cost |             Hashes/sec         |
|      | i7-2700K@3.5GHz | 8xGTX TitanX |
|------|-----------------|--------------|
|  5   |        384.04   |  115,642.00  |
|  6   |        192.02   |   57,821.00  |
|  7   |         96.01   |   28,910.50  |
|  8   |         48.00   |   14,455.25  |
|  9   |         24.00   |    7,227.63  |
| 10   |         12.00   |    3,613.81  |
| 11   |          6.00   |    1,806.91  |
| 12   |          3.00   |      903.45  |
| 13   |          1.50   |      451.73  |
| 14   |          0.75   |      225.86  |
| 15   |          0.38   |      112.93  |
| 16   |          0.19   |       56.47  |

Time to crack

The time to crack a password depends on the password. We all know that corporate password policies forbid strong passwords.

• If it's a password being enforced by a corporate policy of complexity and expiration, then it will by definition be a weak password, and be broken much more easily.
• If it's a password that follows best practices (e.g. no complexity requirements, no forced expiration), then it will be much stronger.

For example:

• Weak: Tr0ub4dour&3 (e.g. 10¹¹ bits)
• Strong: correct horse battery staple (e.g. π^40.89316, aka 10^20.33003 bits)

The passwords demanded by security auditors are intended to weaken the security of your system:

| Cost |   Time to crack - 8 way GTX TitanX       |
|      | PCI-compliant password | Good password   |
|------|------------------------|-----------------|
|  5   |                 5 days |       29M years |
|  6   |                10 days |       59M years |
|  7   |                20 days |      117M years |
|  8   |                40 days |      234M years |
|  9   |                80 days |      469M years |
| 10   |               160 days |      937M years |
| 11   |               320 days |    1,875M years |
| 12   |               641 days |    3,750M years |
| 13   |             1,281 days |    7,499M years |
| 14   |             2,562 days |   14,999M years |
| 15   |             5,124 days |   29,998M years |
| 16   |            10,249 days |   59,996M years |

NIST says your password policy is terrible

In 2017 NIST even reminded auditors how dumb their password polices are. The better password rules are:

• no complexity requirements
• no forced expiration
• allow any character (e.g. correct horse battery )
• check passwords against corpus of previous breaches
• minimum of 8 characters
• no SMS 2FA
• no What is the eye color of your first pet's favorite maiden name?
• no password hints

Personally, I believe that a password policy should be:

• password is estimated to take 50 years to break

Getting a password to take an estimated 50 years to break is ridiculously easy (once you teach people that everything IT told them about passwords was wrong.) And as a bonus:

• it exceeds most statue of limitations
• and hopefully i'll be dead in 50 years

tl;dr: Don't be one of those people who caves when HIPPA, or PCI, or other regulators who come in demanding password complexity and regular expiration requirements. You're just encouraging the idiots, and making the world less secure.

Diatribe about correct horse battery staple

It may be a well known password, but it is not a commonly used one.

For example, Intel's World Password Day 2014 gives the example password:

• Compl3xity < Length!

Nobody is arguing that zxcvbn should recognize this as a commonly used password.

And rightly so: it's not a commonly used password!

zxcvbn is intentionally limited to the top 30,000 passwords:

     1: 123456          55893
     2: password        20785
     3: 12345678        13582
     4: qwerty          13230
     5: 123456789       11696
     6: 12345           10938
     7: 1234            6432
     8: 111111          5682
     9: 1234567         4796
    10: dragon          4191
         ...
 11577: hunter2         44
        ...
 28871: hunter22        17
       ...
 29998: scoubidou2      17
 29999: benelli         17
 30000: vasilina        17
        ...
 47022: dimazarya       11
 47023: xpcrew          11

The fact is: correct horse battery staple does not belong in the list of top 30,000 passwords: because it simply is not in the list of the top 30,000 known passwords.

In fact, i would be willing to go far as you say that's it's not used by anyone.

It is no more common that the other extraordinarily well-known password:

• 173467321476C32789777643T732V73117888732476789764376Lock

Answer 2

Bcrypt has an adjustable work factor. Standard benchmark uses weak work factor, but we can extrapolate. Take number for strong GPU [1].

13Kh/s with work factor 5 means 200H/s with strong work factor. 8 GPUs, so 1600H/s for the entire machine. 8 character mixed case with digits (62 options) is 62 raised to the 8th power: 218340105584896 combinations. Divided by 1600 per second is: 136462565990 seconds. 4300 years to try every combination. But of course, first common passwords and dictionary words would be checked. Those are cracked first. At 10 minutes per account, you can try the top 1 million popular passwords.

Note that weakly stored passwords can be more than 1 billion times faster to crack.

1 - https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a270c40