How does bcrypt keep up with Moore's law?

I have been seeing recommendations to use bcrypt to hash passwords because of its ability to keep up with Moore's Law.

Apparently the reason for this is because it would take much longer for an attacker to crack a bcrypt hash than a hash generated by a g开发者_如何学Pythoneneral purpose hash function like SHA256.

How is that possible? How can an algorithm be deliberately slow in spite of Moore's law?

---

bcrypt is configurable with a parameter called "work factor". Internally, it will perform an operation which is similar to hashing, many times successively. The "many" is the part that can be configured, up to several billions. So, to cope with Moore's law, just crank up that setting. Another function which can be made as slow as wanted is PBKDF2 (see the "iteration count" parameter).

Note that the point of making the password hashing slow is to make things difficult for the attacker, but it also mechanically makes things slow for the "honest systems" too; that's a trade-off. See this answer (on security.stackexchange) for more details.

---

An attacker will want to try all 216,553 english words.

Plus another 12 bits of effort for the common variations, which lets say gives a list of 887,001,088 (2²⁹) possible passwords.

BCrypt takes about 4,342,912 (i.e. 2²²) operations to calculate one hash (at cost=12).

A core today provides about 2³¹ cycles/sec; the state of the art is 8 = 2³ cores per processor for a total of 2³ * 231 = 2³⁴ cycles/sec. A server typically has 4 processors, increasing the total to 2² * 2³⁴ = 2³⁶ cycles/sec. 2²² cycles to calculate one hash * 2²⁹ possible (common) passwords = 2⁵¹ cycles to run through all (common) passwords.

This means that it would take a 4-processor, octo-core, server about 2⁵¹ / 2³⁶ = 2¹⁵ seconds (9 hours) to run through all common passwords.

In reality my password is not common, and uses about 44-bits. 2⁴⁴ passwords * 2²² cycles per password = 2⁶⁶ cycles to try all uncommon passwords. 2⁶⁶ / 2³⁶ cycles/second = 2³⁰ seconds (34 years) to find my password.

Moore's Law's says the processing power doubles every 18 months.

• today: 34 years to find my uncommon password
• 1.5 years: 17 years
• 3 years: 8.5 years
• 4.5: 4.25 years
• 6 years: 2.125 years
• 7.5 years: 1 year
• 9 years: 6 months
• 10.5 years: 3 months
• 12 years: 6 weeks
• 13.5 years: 3 weeks
• 15 years: 10 days
• 17.5 years: 5 days
• 19 years: 63 hours
• 20.5 years: 31 hours

That's now bcrypt holds up against Moore's Law.

Increase the cost factor from 12 to 13 and that will double the times involved.