Do any security experts recommend bcrypt for password storage?
On the surface bcrypt, an 11 year old security algorithm designed for hashing passwords by Niels Provos and David Mazieres, which is based on the initialization function used in the NIST approved blowfish algorithm seems almost too good to be true. It is not vulnerable to rainbow tables (since creating them is too expensive) and not even vulnerable to brute force attacks.
However 11 years later, many are still using SHA2x with salt for storing password hashes and bcrypt is not widely adopted.
- What is the NIST recommendation with regards to bcrypt (and password hashing in general)?
- What do prominent security experts (such as Arjen Lenstra and so on) say about using bcrypt for password hashing?
Yes, bcrypt has many savvy supporters, though of course you want to tune the number of iterations with performance and tune other defenses with DoS attacks in mind. See also How to securely hash passwords? - IT Security and Password Hashing add salt + pepper or is salt enough?
@tkbx Some years ago, maybe. Actually, MD5 isn't considered secure anymore. Have a look at MD5 considered harmful today from 2008, for example.
As a quick note, I personally take either bcrypt or pbkdf2 (depending on the platform) and benchmark different settings. Depending on what I'm using it for I use settings that cause it to take a given time. Like for a desktop application I'd aim around 80ms (I have a relatively fast laptop), or for a server I'd benchmark on the server and aim depending on what traffic I'm expecting.
To answer the question in the title: Yes. I am a Senior Information Security Architect and regularily write cryptographic policies for our customers. bcrypt is one of the algorithms I explicitly recommend for password hashing.
Bcrypt has the best kind of repute that can be achieved for a cryptographic algorithm: it has been around for quite some time, used quite widely, "attracted attention", and yet remains unbroken to date.
Why bcrypt is somewhat better than PBKDF2
If you look at the situation in details, you can actually see some points where bcrypt is better than, say, PBKDF2. Bcrypt is a password hashing function which aims at being slow. To be precise, we want the password hashing function to be as slow as possible for the attacker while not being intolerably slow for the honest systems. Since "honest systems" tend to use off-the-shelf generic hardware (i.e. "a PC") which are also available to the attacker, the best that we can hope for is to make password hashing N times slower for both the attacker and for us. We then adjust N so as not to exceed our resources (foremost of which being the user's patience, which is really limited).
What we want to avoid is that an attacker might use some non-PC hardware which would allow him to suffer less than us from the extra work implied by bcrypt or PBKDF2. In particular, an industrious attacker may want to use a GPU or a FPGA. SHA-256, for instance, can be very efficiently implemented on a GPU, since it uses only 32-bit logic and arithmetic operations that GPU are very good at. Hence, an attacker with 500$ worth of GPU will be able to "try" many more passwords per hour than what he could do with 500$ worth of PC (the ratio depends on the type of GPU, but a 10x or 20x ratio would be typical).
Bcrypt happens to heavily rely on accesses to a table which is constantly altered throughout the algorithm execution. This is very fast on a PC, much less so on a GPU, where memory is shared and all cores compete for control of the internal memory bus. Thus, the boost that an attacker can get from using GPU is quite reduced, compared to what the attacker gets with PBKDF2 or similar designs.
That means one should make any password function as efficient as possible for the setting in which it will operate. The designers of crypt failed to do this. They based crypt on DES, a particularly inefficient algorithm to implement in software because of many bit transpositions. They discounted hardware attacks, in part because crypt cannot be calculated with stock DES hardware. Unfortunately, Biham later discovered a software technique known as bitslicing that eliminates the cost of bit transpositions in computing many simultaneous DES encryptions. While bitslicing won't help anyone log in faster, it offers a staggering speedup to brute force password searches.
which shows that the hardware and the way it can be used is important. Even with the same PC as the honest system, an attacker can use bitslicing to try several passwords in parallel and get a boost out of it, because the attacker has several passwords to try, while the honest system has only one at a time.
Why bcrypt is not optimally secure
The bcrypt authors were working in 1999. At that time, the threat was custom ASIC with very low gate counts. Times have changed; now, the sophisticated attacker will use big FPGA, and the newer models (e.g. the Virtex from Xilinx) have embedded RAM blocks, which allow them to implement Blowfish and bcrypt very efficiently. Bcrypt needs only 4 kB of fast RAM. While bcrypt does a decent job at making life difficult for a GPU-enhanced attacker, it does little against a FPGA-wielding attacker.
This prompted Colin Percival to invent scrypt in 2009; this is a bcrypt-like function which requires much more RAM. This is still a new design (only two years) and nowhere nearly as widespread as bcrypt; I deem it too new to be recommended on a general basis. But its career should be followed.
(Edit: scrypt turned out to not to fully live up to its promises. Basically, it is good for what it was designed to do, i.e. protect the encryption key for the main hard disk of a computer: this is a usage context where the hashing can use hundreds of megabytes of RAM and several seconds worth of CPU. For a busy server that authenticates incoming requests, the CPU budget is much lower, because the server needs to be able to serve several concurrent requests at once, and not slow down to a crawl under occasional peak loads; but when scrypt uses less CPU, it also uses less RAM, this is part of how the function is internally defined. When the hash computation must complete within a few milliseconds of work, the used RAM amount is so low that scrypt becomes, technically, weaker than bcrypt.)
What NIST recommends
NIST has issued Special Publication SP 800-132 on the subject of storing hashed passwords. Basically they recommend PBKDF2. This does not mean that they deem bcrypt insecure; they say nothing at all about bcrypt. It just means that NIST deems PBKDF2 "secure enough" (and it certainly is much better than a simple hash !). Also, NIST is an administrative organization, so they are bound to just love anything which builds on already "Approved" algorithms like SHA-256. On the other hand, bcrypt comes from Blowfish which has never received any kind of NIST blessing (or curse).
While I recommend bcrypt, I still follow NIST in that if you implement PBKDF2 and use it properly (with a "high" iteration count), then it is quite probable that password storage is no longer the worst of your security issues.
What is a "high" iteration count? And I don't really understand why you still recommend bcrypt over PBKDF2
TL;DR: bcrypt is better than PBKDF2 because PBKDF2 can be better accelerated with GPUs. As such, PBKDF2 is easier to brute force offline with consumer hardware.
@ExplosionPills My rule of thumb for a "high" iteration count is: as large as possible without causing too many users to complain about the delay. I generally tune bcrypt / pbkdf2 to take around 250-500ms (1-2s for admin accounts) on my production server while it's under light load. This policy seems to track w/ OpenBSD's recommended bcrypt settings, and any other context-dependant recommendations I've found.
@EliCollins: I'm rather curious here - could using a high iteration count introduce the possibility of DDOS attacks against the server? For example, if I were to POST hundreds of login attempts to the server simultaneously, the server would immediately become overwhelmed with attempting to hash all of the passwords. Are there ways to avoid that potential problem?
@GeorgeEdison I've been wondering about that question too, and haven't found a good answer. 1) You could rate-limit the login page based on load, but that doesn't scale well. 2) offload hashing to a separate server, so the DDOS just affects concurrent logins, but that's just a variant of option 1. 3) use a nonce (e.g. the csrf token) to add a hashcash-style proof of work to your login, but that doesn't help much against a botnet. 4) The DDOS first has to find a valid user account, so delay invalid-user errors with a sleep() call to match the hash time.
@GeorgeEdison to avoid DDOS check the username before checking the password. Then if there have been multiple failed login attempts in a row for that user (say, 10 of them) reject the password without even checking it unless the account has "cooled off" for a few minutes. This way an account can be DDOS'd but not the whole server, and it makes even horribly weak passwords impossible to brute force without an offline attack.
@AbhiBeckert What happens if the legitimate user gets caught trying to log in while his account is under attack from a botnet? (Answer: DOS). Also, skipping the password check for bad usernames provides a timing-based oracle that tells the attacker which accounts exist. If you retain the IP for successful logins (there are good reasons not to), you can give those IPs priority and check the password even if the username is "locked out".
NIST's blessing doesn't carry the same weight it used to. http://www.wired.com/threatlevel/2013/09/nsa-backdoor/all/ (I doubt this applies to PBKDF2, but it's food for thought.)
@TerisRiel I don't mind if a user's account goes offline due to a DOS attack. In the real world it doesn't actually happen, and if it does... well that's better than the account being hacked.
Sure, DOS the user, they'll get some warning that will alert them that something is going on (if, as @Abhi Beckert says, it ever even happens in real life). Avoid an oracle attack by sleeping any failed usernames for the amount of time you'd take to check the password.
@JanusTroelsen: scrypt turned out not to be as good as expected; I added an appropriate paragraph in the answer.
BCrypt appears to be cracked now- does this affect the answer? http://www.itproportal.com/2015/09/11/11-million-unbreakable-ashley-madison-passwords-broken/
@MatthewMartin: you read the article wrong -- bcrypt is not cracked at all; the attacked passwords were hashed twice, once with bcrypt and once with a homemade, weak invocation of MD5. The researchers broke the weak homemade hash based on MD5 (that is, they did not "break" it, they just tried a lot of passwords until a match was found, and it was fast because the homemade hash was very fast and unsalted).
@ThomasPornin So basically they decided to make bcrypt "even more secure"? My rule of thumb is "If this improvement is so good, the experts would have found it long before me."
@corsiKa: it was more a case of two developers working over the same user passwords, but not talking to each other; one knowing what bcrypt is, the other not knowing. This is a case of a generic rule: if the attacker has the choice between two ways to obtain the information he seeks, he will choose the easiest for him.
How up-to-date is this answer in 2016? For example, how does Argon2 (which won the Password Hashing Competition) hold up compared to PBKDF2, bcrypt, etc? As this is a widely-read post it would be good to see periodic updates to this answer that either reaffirm its relevance or update its recommendations.
@ThomasPornin I feel like a paragraph on Argon2 would be the cherry-on-top of this already excellent answer.
@joshreesjones I think that merits a separate question, as this question and answer are specifically about bcrypt.
To the suggestion one should check the username first, then fast-fail if the username isn't present -- that means an attacker can learn which usernames exist and which do not. To keep from leaking that, you'd want every password check to be the same length of time.
@MikkoRantalainen Modern GPUs (even in 2012 when you wrote that comment) can easily handle bcrypt. The requirement is for 4 KiB of fast memory. This means that each GPU shader needs to have at least that much memory allocated to it from the global pool of memory. A GPU with, say, 500 shaders and 1 GiB of VRAM will be able to give each and ever shader a full **2 MiB** of memory. Even one with 256 MiB of VRAM (which is very low) can allocate over a hundred times more memory than bcrypt requires to 500 shaders. Now, ASICs on the other hand...
@forest the point of bcrypt and GPUs is not that bcrypt requires massive amounts of memory. If you need to spend lots of memory, see scrypt. The bcrypt algorithm is about random access of RAM which was not the strong point of GPUs. Newer GPUs have less problems with that but PBKDF2 is still easier task for GPUs.
@MikkoRantalainen Is the random access heavily key-dependent? Random access on a single 4 KiB page of memory seems like it wouldn't be particularly difficult for a GPU, even if GDDR5 memory has higher latency than DDR3 or DDR4.
@forest I'm not sure if access pattern depends on key. According to https://github.com/freedomofpress/securedrop/issues/180#issuecomment-29662610 https://www.usenix.org/system/files/conference/woot14/woot14-malvoni.pdf https://crypto.stackexchange.com/a/401/1267 and https://crypto.stackexchange.com/a/35352/1267 it seems GPUs have problems with pseudorandom access patterns that *modify* the memory and as a result, GPUs are not faster with bcrypt than similarly priced CPUs.
@MikkoRantalainen Oh that's interesting! So it seems each group of cores has its own shared memory (which is very fast), along with the main memory (which is slow for concurrent access). At least in 2011, the shared memory was too small to hold 4 KiB. I wonder if that has changed for any modern GPUs.
See also: "Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks" https://eprint.iacr.org/2016/027.pdf (especially chapter 5)
bcrypt has a significant advantage over a simply salted SHA-256 hash: bcrypt uses a modified key setup algorithm which is timely quite expensive. This is called key strengthening, and makes a password more secure against brute force attacks, since the attacker now needs a lot more time to test each possible key.
In the blog post called "Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes", which I personally recommend you to read, Thomas Ptacek, the author and a security researcher recommends the usage of bcrypt.
Personally, I've been looking at PBKDF2 lately, which is a key derivation function that applies a pseudo-random function (e.g. cryptographic hash) to the input password along with a salt, and then derives a key by repeating the process as many times as specified. Although it's a key derivation function, it uses the principle of key strengthening at its core, which is one of many things you should strive for when deciding on how to securely generate a hash of a password.
To quote Thomas Ptacek from the above linked post:
Speed is exactly what you don’t want in a password hash function.
Basic assumption of bcrypt is that it is slow, but that is just an assumption, a weakness could exist that allows to drastically cut down execution time, or hardware evolutions could bypass the slowness (same as for Scrypt). PKBDF on the other hand relies on a well tested hash for which fairly fast near-optimal hardware already exists, which means that the time and complexity parameters are well known (and can be leveraged through repetition). PKBDF defenders know exactly what attackers can do within an order of magnitude, bcrypt defenders do not.
@EricGrange: it's true that PKBDF defenders know what attackers can do. Unfortunately, the attackers can do at least 10-20x faster than the defenders. Defender wants to use bcrypt because it *currently seems* to give much less edge for the attacker. Basically the fans of bcrypt think that the algorithm seems good enough to trust and it makes the playing field more level for the defender and attacker. If you think that giving at least 10-20x performance boost to the attacker is okay, then PKBDF is better choice because the tradeoffs are better understood.
@EricGrange This is true for ALL algorithms. As time goes by and more cryptanalysis is done, we can become increasingly confident (but never completely sure) that a particular algorithm doesn't have a particular weakness. The notion that we can know with certainty the risks for PBKDF2 but not bcrypt is absurd.
According to https://www.usenix.org/system/files/conference/woot14/woot14-malvoni.pdf attacker is only 2x faster with custom hardware than bcrypt defender using generic i7 CPU. Seems much better than attacker being 10-20x faster with PKBDF than the defender.
I think Gui's suggestion about PBKDF2 has merit, although I know Rook disagrees strongly. If only they were clear about their reasoning!
Regardless, there's no reason to use a salted SHA-256 hash in comparison to HMAC-SHA256. HMAC has the advantage of blocking extension attacks.
+1 for mentioning HMAC, which I completely forgot to mention as the more secure alternative to a simply salted SHA-256 hash. Length extension attacks are well known; the Flickr API once was compromised because it used to sign API calls using `MD5(secret + argument list)` (see " Flickr's API Signature Forgery Vulnerability " [PDF] for further information)
@curiousguy (Better late than never...) Storing a password hashed with a salt can be done by calculating an HMAC, using the password as the HMAC key and the salt as the HMAC message. This is more secure than naively calculating `H(salt || password)`, though an actual password hashing function like bcrypt is preferable.
@curiousguy HMAC is the PRF most commonly used in PBKDF2. So don't use bare HMAC either. Use PBKDF2 (with HMAC-SHA256 or HMAC-SHA512), bcrypt, or scrypt. That's it. Don't invent or use anything else. Custom schemes are bound to be wrong. These three are well-vetted and easy to use. Realize that PBKDF2 is the most vulnerable to hardware accelerated dictionary attacks and scrypt is the least vulnerable.
NIST is a United States based government organization, and thus follows FIPS (United States based) standards, which do not include blowfish, but do include SHA-256 and SHA-512 (and even SHA-1 for non-digital signature applications, even in NIST SP800-131A, which delineates how long each older algorithm can be used for what purpose).
For any business required to comply with U.S. NIST or FIPS standards, bcrypt is not a valid option. Check every nation's laws and regulations separately if you do business there, of course.
PBKDF2 is fine; the real trick is to get Tesla (GPU based) cards in the honest servers so the iterations can be made high enough to compete with GPU based crackers. For PBKDF2 in 2012, OWASP recommends at least 64,000 iterations on their Password Storage Cheat Sheet, doubled every 2 years.
It seems to me that using scrypt or bcrypt (changing the software) is easier than adding expensive (in terms of up front costs and energy costs) hardware to millions of servers. At a higher level, any key stretching function is just an attempt to add more entropy to the password. If (and only if) the password is strong enough to begin with (e.g. a 128-bit random number encoded as 10 diceware words), a single iteration of PBKDF2 is adequate protection.
The purpose of *crypt functions or PBKDF2 is to store the password in such away that its very hard to find the original password. They do not make the password any stronger. A single iteration of PBKDF2 makes it easy to brute force guess at what the password is. If it takes a second of CPU time per guess then brute forcing becomes unrealistic.
A GPU won't help a webserver hash a single or a few passwords quickly. It only helps to hash many (thousands) of passwords simultaneously.
How come NIST thinks PBKDF2 is fine, when bcrypt is harder to bruteforce locally? And does this mean, that if you have a service that encrypts using `bcrypt`, then US businesses won't be allowed to use the service?
It might be worth looking at Argon2 which won the Password Hashing Competition.
Welcome to the Information Security Stack exchange. Since this answer doesn't directly address bcrypt, it might be better left as a comment. Thank you for taking the time to answer a question, and I hope you have a positive and informative experience here!
I took a look at this competition, the list of candidates does not include bcrypt, scrypt and PBKDF2.