How To Safely Store A Password

I'm familiar with cperciva's scrypt, and I think it's a great solution. That said, I've only seen C and Ruby bindings for it.

I'd love to recommend its use over bcrypt, as memory constraints are much more expensive than computational constraints, but recommending something most developers don't have access to would result in more weak hashing schemes in production.

The mistake you're making is thinking of bcrypt as a protection for end-users and their passwords.

It isn't. Bcrypt exists to protect application developers.

A user with a crappy password is getting his account busted one way or another. You're right to point that out. Cryptography won't solve that problem.

The problem crypto solves is this: a crappy web app that loses its user table is royally screwed if its devs settled for "salted hashes". At the whim of their attackers, hundreds or thousands of their user's passwords are going to hit Rapidshare. That's what the devs will be famous for.

Bcrypt keeps that from happening. You'll get famous behind losing 1000 passwords. You won't get famous behind losing 20.

Also, you point out that "successfully discouraging your users from using a crappy password has much better repercussions." This is true, and I'm curious to know how you personally achieve this with your users, given that the vast majority[1] of users choose spectacularly crap passwords.

[1] http://www.imperva.com/docs/WP_Consumer_Password_Worst_Pract...

You're talking about a completely different problem.

Yes, many users pick crappy passwords. That's a social problem, one that is difficult to address with technology[1].

Storing passwords on the server is unrelated to whether or not the user picked a good password. If an attacker gets ahold of a copy of your database, they will have a much easier time of turning SHA1 hashes of passwords into actual passwords than of turning bcrypt-encrypted passwords into actual passwords (the latter being orders of magnitude more difficult, maybe to the point of being impractical as a target vector).

[1] You can always do things like require certain types of password complexity: minimum length, choice of characters from different character classes and cases, etc. But then you end up just moving the problem elsewhere: instead of using the crappy password they remember, the user has to write down their complex password, or maybe even store it in a text file on their hard drive.

Using a new and unproven hashing primitive to add a constant factor is much more secure than encrypting with a reliable, heavily researched protocol because __________________

Foiled again! Curse you, Ptacek!

Only experts should be allowed to innovate in the security domain. Passwords on lolcats are serious business!

We certainly don't want people in the software engineering industry to come up with new ideas, implement them, and see how they work in real life. That could lead to advancement in the field, and that would be bad, because I might have to learn something new. Shudder.

I'll forgo a mathematical argument in favor of a practical one. If you have a choice between offloading complexity to your users or your developers, you should choose your developers every time. Rather that requiring complex password schemes from your users, have your developers use a slow hashing algorithm instead.

Once you go down the road of "not doubting a hacker's ingenuity", you might as well give up and stop applying OS patches. In any case, with "16 byte salts and SHA-512", you're pitting hackers against the folk wisdom of PHP developers. With bcrypt, you're pitting hackers against the IACR. You can't know everything, but you can pick the right battles.

If you can force your users to pick strong passwords, good for you. But in practice, that's almost impossible.

I'm not even checking your math, because that's 4.8 months to crack one user's password. A spectacular win compared to "salted hashes".

Presumably, bcrypt is something that has been vetted by crypto experts, whereas your idea is just some random thing you thought up. Maybe you personally are a crypto expert and know for a fact that your plan will work, but the vast majority of people aren't. A packaged solution like bcrypt that doesn't give the developer enough rope to hang themselves (and their users) is a much better idea.

The idea is a developer will just do:

  passwd_str = bcrypt_string_from_password(passwd);
  db_store_password(userid, passwd_str);

and just be done with it, rather than having to decide between ROT13 (kidding), hashing, salted hashing, HMAC, etc. A couple years ago I thought applying SHA1 to a password before storing it in the DB was perfectly fine. Later I discovered that it was better to use a salt. More recently I've discovered that both of those approaches are flawed. Fortunately I've never written a large-scale application that deals with storing passwords, but I'm sure there are many application developers like me who would write much safer password storage routines if they didn't have to be the one to select an algorithm.

Now, I'm not saying bcrypt is the answer (I know nothing about it beyond what I've read on HN), but that's the general problem with your hypothetical proposal.

Nothing enormous; that's basically what PBKDF1 does. cperciva might correct me on this, but IIRC there are some minor concerns, addressed by PBKDF2, which is a slightly more complicated construction, about the iterated hash function degenerating into cycles. I don't think there have ever been any practical results exploiting this. PBKDF2 is just as good a choice as bcrypt, and a better-supported one.

Make the client's computer do the work.

First, tens of thousands of connections per second boils down to orders of magnitude fewer logins. In a typical modern web app, plenty of entire sessions are completed off a stored session token and never touch the login code.

Second, plenty of apps that are far bigger than yours have scaled bcrypt without event. 37signals is a public example. Other larger apps are using it without talking about it.

Third, in the spectacularly unlikely event that password hashing became a scalability obstacle, it's pure compute and scales horizontally without a problem. Note: I've never heard of someone having to do this.

Finally, the whole point of bcrypt is that it's tuneable. You dial it up to your pain threshold, and in the process cripple brute force attackers.

If those tens of thousands of connections per second are tens of thousands on logins, per second, then the computational value of your hash function seems likely to be the least of your problems :)

The bcrypt algorithm has salting built-in.

The article is talking about the problem of storing passwords in a database in order to authenticate logins. This is for people writing web-apps, not users looking to secure their own passwords.

Because it means with <single piece of secret info>, your entire customer base's worth of passwords is now decrypted.

You've now gone from "Even if we get attacked, we've chosen a provably difficult / secure storage method. The damage should be negligible." to "If we get attacked - I hope like hell they don't get <single piece of secret info>."

An attack is an attack. If they can get in and steal your password database, what's to say that they can't get access to the key that decrypts your reversible database?

Essentially, because it is reversible.

In other words, the information needed to extract the true raw-text password is actually included in the encrypted string.

With a hash, only a representation of the raw-text is being stored. Even if you knew exactly what was done to create that representation, you're still a long way off from understanding the raw-text.

If you treat both the key and the salt as being "known to the developer only" and either of these becomes compromised, you still don't have they raw-text of a hash, but you've got everything you need for the encrypted.

Did you read the article? The problem is that someone trying to bruteforce your MD5 hash won't add that sleep(500). Bcrypt is slow by design.

I hope you're being sarcastic, but if not, it is because an attacker could take out the call to sleep(500) again.

I'm guessing you haven't read Provos and Mazières' USENIX paper. In the design considerations, they say:

In general, a password algorithm, whatever its cost, should execute with near optimal efficiency in any setting in which it sees legitimate use, while offering little opportunity for speedup in other contexts.

PBKDF1 and PBKDF2 both rely upon general-purpose hash functions, which are much faster in dedicated computing environments such as FPGA or GPU clusters. The Eksblowfish algorithm at the heart of bcrypt is extremely resistent to optimization.

This is crucial for password storage, since if a CUDA implementation is 3-4 orders of magnitude faster than the implementation your application uses, you've just chipped off a huge chunk of the advantage offered by your hash function.

What a bizarre comment. PBKDFn and bcrypt are two very similar approaches to the same problem. If you're married to PKCS/IETF standards, go ahead and use PBKDF2. You're still essentially following the advice of this blog post.