Storing Passwords Securely
throwingfire.com
throwingfire.com
Colin Percival's "scrypt" password hash is:
1) production-ready (and has been for a long time)
2) superior to bcrypt, as it is designed to be expensive in both CPU and memory (hence, scrypt is "memory-hard", whereas bcrypt is not)
I don't have time to go into further detail. I encourage you to check it out. It's quite simply "the future of password hashing". (Bcrypt will be defeated by natural advances in multi-core hardware; scrypt won't ever be.)
Passwords hashed with scrypt with sufficiently-high strength values (there are 3 tweakable input numbers) are fundamentally impervious to being cracked. I use the word "fundamental" in the literal sense, here; even if you had the resources of a large country, you would not be able to design any hardware (whether it be GPU hardware, custom-designed hardware, or otherwise) which could crack these hashes. Ever. (For sufficiently-small definitions of "ever". At the very least "within your lifetime"; probably far longer.)
I personally agree that "Use bcrypt." should become "Use scrypt." soon. My main gripe is that there is far less library support for it, at least for now.
I would expect that within 5-10 years, scrypt will be the normal suggestion. It really is much better on the fundamentals, so much so that some experts recommend it even in spite of its relative newness. For the moment, though, there are arguments to be made either way.
If you have no other choice but to iterate SHA1 many thousands of times, that's still better than what most apps do, and in the grand scheme of things almost "ok".
scrypt is fine. If you have a library that supports it, go ahead and use it.
While I won't recommend people simply iterating a hash many times, I also won't slap people down for it anymore. In the grand scheme of things, there are a billion more likely routes of attack than someone breaking your 20000-rounds-of-SHA1 hashes.
When looking at jBCrypt for instance, they're only at version 0.3 with no updates since 2010, makes me really nervous of using it.
1. http://packages.debian.org/search?keywords=scrypt
2. http://packages.ubuntu.com/search?keywords=scrypt
Making it memory-hard makes it also memory hard.
That's a tautology, unless the hyphen means something different.
Basically it's a matter of "what do we have which they would have to pay extra for".
This seems like a bad idea to me. If a hacker gets access to the salted passwords, in this case he'll probably figure out how to get access to the salts too.
I figure if the salt is stored in the code (or a config file...) rather than the database itself, at least it's two different hacks to get (1) the salted hashes, and (2) the salt.
Am I misunderstanding?
You might feel like adding a hidden component but it won't noticeably help security and it's not a salt.
Usually we fetch user/email, hash password, compare to hash in database - authenticate if match or deny if not.
Thanks for bringing this up--the concept of salt makes a lot more sense to me now.
A common and simple password setup is hash(username+password) or hash(private_account_attribute+password).
Also, use bcrypt/scrypt/similar.
Not exactly. Having a salt at all mitigates rainbow table attacks, having a unique salt per password also limits brute-force attacks (you can't brute-force the whole table trying out cleartexts with a given salt, you have to brute-force each password individually).
Having a global unique salt is already better than no salt at all.
So one-salt-per-user is clearly better, but one-salt-for-all is still better than no-salt-at-all.
Anyway, you want to store a new salt (not just a system-wide 'this is my salt' salt) for each stored password anyway, so you will need to store that data somewhere. You could obfuscate a little by storing the salts elsewhere, but it seems a little extreme.
Think about it. If you use the same salt for all passwords then I can easily create a rainbow table consisting of "keyword" + salt hashes and doing so I can crack multiple passwords.
However if there is a different salt for each password then this type of attack becomes more difficult as I have to essentially do the same amount of work for only a single password.
Finally, we need to store the salt in the database because it's needed in order to recreate the hash using the user's password for authentication.
There are deeper attacks too, but the above are just what can be derived from a bit of reading up on how the SHA family of hashes works.
For a closely related problem/solution, reading up on HMAC is quite enlightening.
That's not a rainbow table, a rainbow table is a list of precomputed hashes (which you'd just do once on a cluster you pay — of buy from a guy who did — and then store/stash)
But you're brute-forcing the whole table (you can look for matches after each computation) instead of having to individually brute-force each password. But you wouldn't keep the forced salted hashes around since there's no need for them once you've tested the leaked hashes.
You are right of course there is no need to keep hashes about once they have been compared against the db.
A hash unique to the site would require the attacker to create a site-specific rainbow table, but once created it can be used for all passwords. Having a unique hash per password means that the attacker would have to generate unique password tables per user, which for a suitable salt & algo is impractical, even if (as they normally are) the salts are stored with the passwords.
Too often people assume one way or the other (and come up with their own hare-brained password encryption scheme, defending it from all-comers).
As an example, find the md5 of a dictionary word and google it, its original value is bound to be in the first or second result. Now find the md5 of that word and a random string (aka a salt)... google and there shouldn't be any results. and even if there was due to a collision, that password wouldn't work, because it would be resalted prior to the comparison happening.
Hi Phil -
Yes. Salts are to defeat things like this: http://en.wikipedia.org/wiki/Rainbow_table
Aye. There are two points to the salt:
1. Avoid precomputed hash attacks ("rainbow table") where the attacker has a big list of hashes:password, and can just walk the table of (leaked) password hashes to get the cleartext. A global salt is sufficient for that, and where it's stored does not matter (can be a config file or a config table or whatever)
2. Avoid the attacker being able to brute-force the whole collection at once, there each password needs its own salt: the attacker needs a pair of (salt, hash) to be able to brute-force each and every password, it can't just compute a million (salted) hashes and cross-check all the table, it has to do so for each and every password it wants to crack. This requires a unique salt per password/hash, and the salt can just be stored with the hash.
Salts are not secrets, they just exist to make the hashing of a given user's password unique. They are generally returned as part of the hash function's result (alongside the number of rounds, so the result has the shape (cost, salt, hash)), it's understood and expected that the attacker knows them: it does not matter to their purpose.
On a more esoteric note: If you are looking to resist quantum algorithms attacks, there are post-quantum algorithms for that[1] (they are computed on normal machines, but the problems behind the crypstosystems are hard to solve even for quantum computers).
[1] http://crypto.stackexchange.com/questions/494/what-is-the-po...
[With the obvious caveat: Advice not for production use, If you have to ask...]
Post-quantum is cool alright, but it's not really a thing that implementers need to worry about.
alternatively, you could bcrypt all hashes now, and anytime you authenticate, making sure to MD5/SHA hash the plaintext password before checking the password using bcrypt.
legacy code and especially authentication code that has huge exposure (code path hit during every login and potentially every session auth) is difficult/risky to change once deployed. making things "more secure" has always been a hard sell to management... until a disaster like this happens!
https://github.com/ato/clojars-web/compare/68872652fc427cc1....
We had a month or two grace period in which anyone logging in would have their password upgraded to bcrypt automatically, then wiped the SHA1s.
https://groups.google.com/forum/#!msg/clojure/Xg1I0rgt85s/Vf...
if hashed_password.startswith("sha$"):
hashed_password = bcrypt(hashed_password)
Here is the relevant code for django-bcrypt: https://github.com/dwaiter/django-bcrypt/blob/master/django_....
In your case, you could probably do this:
if not hashed_password.startswith("bc$")\
and sha(entered_password) == hashed_password:
hashed_password = "bc$" + bcrypt(entered_password)
Of course, you have to account for the prefix identifier when validating an entered password against the stored hash.
YMMV.
hashed_password = bcrypt(entered_password)
I'm not really sure where to stand on this. On one hand, we have PLENTY of security articles stating the same thing (bcrypt, bcrypt, and just in case you've forgotten... bcrypt), which leads to an observed over saturation of the same subject matter. On the other hand, we have a huge company like LinkedIn that doesn't have the presence of mind to use something other than vanilla SHA-1. Maybe there's just too much lazyness/ stupidity in the world to require a constant barrage of the same security articles every week.
Ironically, the algorithm to upgrade to bcrypt is simple. Add a flag to the account table if they've upgraded or not. Next time the user signs in successfully, re-hash their password with bcrypt, toggle the flag, and update the password_hash value in the database.
I think the reason that this happens so often is that regular developers just don't care. But that's because they don't know why they should care. Given a proper explanation (and an attention span longer than "Squirrel!"), any reasonable developers would (at least, should) care.
People often ask "why use bcrypt", and the response is that they should google it. If you look through the first page of google results for [why use bcrypt], though, none have a good discussion of the reasonable alternatives, or when you might want to use one or the other.
Coda Hale's post has a pretty good explanation of why bcrypt is good, but I personally find this to be more in-depth.
There are a multitude of sophisticated third-party solutions to authentication. Facebook, Twitter, and Google all offer competent solutions. Don't like those? Use BrowserID.
Integrating any of these is actually quite a bit easier than rolling your own solution. It reduces hack risk, provides a better experience for your customers (what was my password again?), and almost certainly will be more reliable than your website.
Someone, somewhere will be storing user passwords/digests for the foreseeable future. And they will do it incorrectly.
HN is full of web developers rolling unnecessary username/password solutions. The fact that this is such a hot issue - as opposed to esoterica like TCP frame size - shows that far too many developers are homebrewing solutions rather than outsourcing.
Someone has to store the passwords, it would be good if there was a way you could be assured your data at rest was safe.
Personally, I never feel particularly secure when typing passwords into text boxes on random PHP forms. On the other hand, I feel fairly confident that the folks at FB, Google, Twitter, and Mozilla know how to store a password and secure their infrastructure.
The biggest UX issue is currently the up-front email roundtrip for new accounts. In the long run this experience will improve considerably when primary identity providers support the protocol directly. In the short run it's still not bad.
So is there research that proves that hashing a hash of a hash of a hash (x100000) doesn't result in a smaller range of values than a single hash for SHA algorithms? Is there no such convergence?
But don't use stretched SHA1. Use bcrypt or scrypt or PBKDF2, all of which explicitly address this particular concern.
This only really protects against SQL injection attacks, though/when there is actually a separation between where you store the bcrypt digests and where you store the pepper. (Granted, there are a lot of SQL injection attacks.)
The first section of the article IMHO was not needed in regards to a simple hash. Forums have been hashing their passwords with salts for how long now ?
Or invalidate and send an email.
http://reddit.com/r/changelog/comments/lj0cb/reddit_change_p...
One thing I didn't find solution for is keyloggers and other similar attacks. If you look at the whole securing your service as a whole, you have to acknowledge the risk of keyloggers also. Now with Flame, Stuxnet and all the other nice things still in the shadows keyloggers can suddenly become also a risk in a large scale.
On the other hand, if it's so hard to roll your own, can somebody point out the security flaws in the given Python function? Seems pretty straightforward to my untrained eye.
I still think any article talking about verifying credentials is obligated to mention that string comparison could be an attack vector.
Like I said, it plants a seed. And, I've seen way too many naive implementations where it is needed (like simple token-based auth systems) to know that this seed needs to be spread a lot more.
It feels sometimes like people hear about the idea of timing attacks and then want to see them everywhere.
Sure, that's simple. You're leaking information about the password hash to the attacker, which they can use to speed up an attack where they have large offline resources but are limited in their online guessing capacity.
Let's e.g. assume we have an unsalted hash, but the system limits us to one guess per second. The password is hashed, then compared with ==, taking some variable time we'll assume can be measured.
We use an iterated timing attack to discover a prefix of the password hash, then run an offline dictionary or brute force attack using that prefix. Passwords that match the known part of the hash are tried online, potentially revealing more of the hash as we go.
> It feels sometimes like people hear about the idea of timing attacks and then want to see them everywhere.
When it comes to side channel attacks, "vulnerable" is the default state.
Feel free to peruse some SHA-256 hashes with slightly above six bytes of fixed prefix - several orders of magnitude more difficult to find than a mere 32 bits partial collision: http://blockexplorer.com/
Now you can argue about how likely it is for an attacker to actually bother to find and exploit such a weakness, and how a salt would mitigate the severity and so forth, but the takeaway here is that this attack can be trivially and permanently defeated by using a timing independent comparison function.
Here I model the server as a simple function that takes a password, hashes it, and compares it to a known digest with an '==' substitute. The function returns true or false, but also leaks information about how long the match was, through a simulated timing leak.
This lets me identify the dictionary word that was used as a password using just 23 login attempts, instead of the expected 19300 from a brute force attack.
In effect, you're giving the attacker the ability to perform an almost offline attack, as if they possessed the password hash, by supplying however much of the hash they need.
I don't see how this would not be a security problem, if you acknowledge that testing a HMAC with == is.
Again, this is trivially preventable by using a timing independent comparison.
I wasn't trying to be condescending when I asked how it was significant. I really didn't understand what you meant.
I've added a note to the article.
Some things a reader of this thread would want to know, to make sense of it:
* C memcmp (which is what Python uses) is below the known measurement floor for remote timing.
* With (many) repeated trials and statistical filtering, the floor is (IIRC, but just Google [crosby wallach timing]) hundreds of nanoseconds on a LAN, tens of microseconds on a WAN.
* The difference between 1 and 2 bytes of matched SHA1 hash is certainly not a millisecond.
* Even if it was a millisecond, which it isn't, you'd come to that conclusion only after many repeated trials.
* To make this attack appear worthwhile, you introduced an artificial rate limit of 1 attempt per second, but obviously ignored that limit when trying to measure the (very noisy) timing of each hash byte.
* Obviously, you can't time a randomized hash, because you don't know enough to generate proposed password hashes to match against.
* The 4-byte shared prefix you're looking for is probably not present in the set of all valid passwords; or, put differently, you'd have better luck just guessing likely passwords through repeated trials than you would making repeated trials to find a next prefix byte.
I'm not disputing that there's information of some sort "leaked" in a password hash comparison; I'm just disputing that it's valuable in any way to a real world attacker.
A more effective way to try to launch this attack would be to try to dump the set of all users known to the system. This attack, far more straightforward than the one you proposed, also doesn't work because of measurement difficulties, but it at least has value in theory, doesn't depend on arbitrary shifting obstacles for the attacker, and nobody in the history of web app development has ever tried to stop it.
I didn't ignore the time limit. As long as login attempts are much slower than offline bruteforcing, all that matters is whether we need less attempts total. Since it lets you cut your attempts by some fraction with a corresponding constant cost, it always wins out for a large number of passwords. In the toy example it's about a wash if you assume 1000 samples per 'attempt'
I won't examine each of your plausibility objections, but I'll note that the case is identical when checking a HMAC. You shouldn't rely on those assumptions if you can avoid it.
Simply put, using a timing independent comparison is best practice both for checking MACs and password hashes, and I think it is wrong to dissuade people from doing so.
For other readers, the == operator is comparing a password hash, as opposed to a password itself. One of the properties of a secure hash function is that, changes to the input drastically changes the output. Thus this attack is one of brute force and not a timing attack on the == operator.
People should use proven KDFs for password authentication, not implement their own (including using my SHA-salting/iteration examples.)
Edit: removed "in web apps"
I believe that point was well made, even though in a technical sense, the exact error was unfounded.
I'm not sure that password-as-a-service would be worth the overhead involved, but password-as-a-library is functionally equivalent from a developer's perspective and is already the norm. The only question, then, is "which library?" which is what this article attempts to address.
it is open source, and supported by all platforms i use (windows,osx,android,ios) and the interface is pretty well designed. Once local database is open, simply doing ctrl+c on any of the sites copies the password to clipboard for a very limited time.
this is still a major pain, especially since you need to protect the safe with a long password and this is particularly painful to type on mobile devices.
return getDigest(password, salt) == digest
getDigest returns a tuple
Bullshit. MD5 is just fine, as long as you use the salt.
Here, hack this:
MD5(password + salt) = "b520542710812f347432232b2a1fba83"
salt = "MD5 rules"Use bcrypt or scrypt. Don't make up your own crypto.
[1] Crypto benchmarks: http://www.cryptopp.com/benchmarks.html
It will explain why "salts are useless for preventing dictionary attacks or brute force attacks."
The entire article is excellent - and every colleague who I've ever pointed at it, has come away nodding their head and seeing the light.
The key-takeway (but please, read the entire article) is: "It doesn’t affect how fast an attacker can try a candidate password, given the hash and the salt from your database."
Salts only help you from precomputed dictionary attacks ("Rainbow Tables") - but, if someone is brute forcing you, the value of a salt just disappeared.
Sure, a very large salt might slow down the first iteration a little (but not necessarily subsequent ones, and it wouldn't require more memory, at least with most hash functions), so you're almost always better off just stretching the key--then you save the storage costs too.
$ echo -n "Spiderpig1MD5 rules" | md5sum
b520542710812f347432232b2a1fba83 -
MD5 is broken.
Maybe Linkedin should've used this ;-)