5

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]?

  • 4
    The Bcrypt algo uses salts, so generating a table of pre-computed password hashes to compare won't work. I'm guessing the way he did it was to take a list of most common passwords, and test them one by one over the entire account list. This would yield results much faster than brute-forcing each password individually. – Numeron Oct 14 '16 at 1:32
3

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:

The passwords demanded by security auditors are intended to weaken the 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:

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 is 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:

  • 1
    Your terminology is incorrect for 10^x "bits". Bits are log2(# of possible passwords). Using zxcvbn to estimate entropy is useful for user-entered passwords, but if you already know the password distribution you're choosing from it's much better and more accurate to calculate it yourself. xkcd's "correct horse battery staple" has 44 bits of entropy, which is 10^13.25 possible passwords, not 10^20.33 (though of course at this point it's terrible, as it's in most password dictionaries). – AndrolGenhald Jan 22 at 16:00
  • The system trying to break the password doesn't know the distribution being chosen from; that's why it's stronger. Also, if we're being pedantic, there is no example of a good password anyone can give: because as soon as give one it is added to database dictionaries. – Ian Boyd Jan 22 at 19:28
  • Fair enough, saying that specific password is now terrible was more of an afterthought, and not really meant to criticize your use of it. Interestingly, I just noticed that zxcvbn gives 10^14.44 as the guesses for "correcthorsebatterystaple", but 10^20.33 if you add spaces between words. Seems it fails to split it correctly and recognizes " horse " as a pattern rather than a word surrounded by spaces. I'd prefer to go with Shannon's Maxim and calculate the actual 44 bits of entropy, rather than the 67.5 or 48 that zxcvbn gives. – AndrolGenhald Jan 22 at 19:35
1

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

  • 1
    I'm not confident in your extrapolation: what is a "strong work factor"? Can you specify the number please? Also, the latest performance data is 133 KH/s on bcrypt(05) – cottsak Oct 18 '16 at 6:18
  • @cottsak 16Kh/se per GPU instead of 13Kh/s is not a huge difference, but good to know. I don't know if it's cost effective to use the better GPUs. A "strong work factor" is high enough that you believe passwords your users will use will not be broken, or as strong as you are willing to do (your server will have to use CPU to compute those hashes...). My calculations above assumed 11 (64 times slower than 5). If you allow really weak passwords, nothing will help. – Z.T. Oct 18 '16 at 6:35
  • @cottsak What is the problem with my extrapolation? The benchmark shows speed for each GPU and then speed for all 8 GPUs together. Cost of bcrypt is power of 2 for number of rounds. So cost 5 is 2^5=32 rounds and cost 11 is 2^11=2048 rounds. Since (a^x)/(a^y)=a^(x-y) so 2^11 is 2^6 =64 times more than 2^5. But some people recommend cost 17 or even whole second of CPU time (too much I think). – Z.T. Oct 18 '16 at 8:35
  • you should be quoting the combined performance of this example rig 133.1 kH/s instead of the per-GPU number 16701 H/s. It's only the combined performance that matters when you're brute forcing with a dictionary - it's the speed at which you get through the list that's matters, not the speed of an individual hash computation. – cottsak Oct 19 '16 at 2:43
  • My concern re your extrapolation wasn't about the math as much as the 'point in space' for what you considered a "strong work factor". Now that you've said it's 11, I'm happy to agree that yes that is "relatively" strong, but like I think you've already alluded to, the absolute work factor is less important than the time on a given machine that the hash takes to compute. Also, I do side with the "whole second" party - it's not a poor UX for login and gives you the best bang for buck IMO. – cottsak Oct 19 '16 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.