Does using a unique salt for each user help here? Is there a non-obvious reason why that approach is bad?
But too many people forget that before the popular Windows cracking tools were released, passwords were cracked exclusively by tools like JtR, which simply contain highly optimized loops for brute forcing passwords. "Salts" do nothing to slow this attack down, because they add insignificant time (really, none) to a single hash iteration.
Hashes like MD5, SHA1, and even SHA256 are designed to be fast. To succeed, they need to be able to handle multi-gigabit per-packet hash rates. They are designed explicitly both to be fast on general-purpose hardware and to be straightforward to optimize in purpose-built hardware. This is a bad, bad property for a password hash.
BCrypt is "optimized" to be slow - tuneably slow. SCrypt improves on BCrypt by being both slow on general purpose hardware and resistant to simple hardware speedups. PBKDF and "stretched" SHA1 are very simple contructions that are weaker than BCrypt and SCrypt but more buzzword compliant. All of them make it difficult to recover hundreds of thousands of passwords from a database dump.
See:
http://www.matasano.com/log/958/enough-with-the-rainbow-tabl...
Merely choosing a slower digest doessn't help, because the digest would have to be extremely slow (minutes or hours per password) to prevent somebody from running it against "password", "12345", etc for every row in the table. And that's the only kind of attack worth preventing -- if somebody can brute-force a 20-character alpha-num-symbol password in realtime, your choice of digest algorithm is irrelevant.
t1 = Time.now.to_i
100.times { BCrypt::Password.create("ugh8&eat") }
puts Time.now.to_i - t1
=> 12
t1 = Time.now.to_i
100.times { Digest::SHA1.hexdigest("ugh8&eat") }
puts Time.now.to_i - t1
=> 0
In contrast, assuming a 40-character (20 in config, 20 in database) alphanumeric salt, an attacker would have to perform 704423425546998022968330264616370176 digests per row to check 32M passwords.
Unless you believe that is an insufficient barrier, implementing BCrypt is merely degrading the user experience (12-second logins? come on) for no real improvement.
t = Time.now.to_i
1000000.times {Digest::SHA1.hexdigest("ugh8&eat")}
puts (Time.now.to_i - t).to_s
=>3
Edit: I match my parent's problem with 32M checks taking 12 years with my personal computer taking 132.86 seconds to calculate 32M SHA1s.
Increasing the digest time prevents an attacker with simultaneous access to the server and database from cracking very weak passwords, but at the cost of tripling or quadrupling how much time each request takes. There are some cases where this could be useful -- for example, running a dissident website in an authoritarian country -- but it's user-hostile to implement it anywhere else.
You're basically just splitting the passwords into two components--two-factor security--except that two-factor security requires two separate concepts, not simply requiring two passwords.
If an attacker can achieve a root login to your server, then they can read your config file, but they can also just change the login form to email them passwords. For this reason, most password defense is aimed at the assumption that the attacker gained access to the database server, but not the webserver. Historically, this has proven to be a safe assumption.
I kid, but I really think you and tptacek just have different standards. tptacek's is higher.
Well, that and the obnoxious trick question.
You do put them on a web server. It just happens to run software optimized for extracting a particular entry from a large data set :)
Ironically the way you suggest is more secure: because to compromise it (assuming the web app is out of the equation for the moment) requires a system exploit. Whereas you have the added complexity of the database as an additional weak point.
EDIT: im confused about the downvote.. what in particular appears wrong (so I can explain it). Having Database software certainly lowers security on any system :) it's another failure point (any good security text book will explain that)
If you have a table of 32 million hashed passwords with no salt (or they have the same salt and you know what it is), you can try a bunch of combinations, take the resulting hash, and look it up in the hashed password database. If you try the password "foobar" and any user has the password "foobar", you've found a username/password pair. Because there are 32 million potential matches, your chances are pretty good of eventually finding a bunch of matches by iterating over a bunch of potential passwords.
On the other hand, if you have a table of 32 million hashed passwords and salt combinations, where the salts are unique, you have to check the hash of "foobar" in combination with every user's salt before you can say that no user has the password "foobar". This is 32 million times slower, which is a significant difference regardless of the speed of the hashing algorithm.
If you want to brute force a particular user's password, the unique hash doesn't matter, but if you want to maximize the number of username/password pairs you can get, it seems to me like it would.
It is true that not even bothing to randomize your hashes is worse than doing so. But when we're talking about degrees of grave badness, I stop being super interested in the conversation.
If, for reasons passing my understanding, you are attached to the idea of using straight SHA1 to hash passwords, iterate SHA1 1000 times. That takes 2 extra lines of code (the opening and closing of the for loop) and significantly improves your security.
Let me put it this way: give me a database of 32 million username/password_hash combinations and the hash(password) function used and I can give you a valid username/password combination fairly quickly. Even if the hash function takes 10 seconds, because chances are one of those 32 million users has used "password" as a password, and it will only take me 10 seconds to compute the hash and find out which ones did.
If instead you give me 32 million username/password_hash/salt combinations, and the hash(password, salt) function used, just to list the users who have the password "password" will take 10 years.
The attack you're talking about --- searching for a radically reduced set of passwords --- is so fundamental to password security that you don't need any crypto to do it. Just open 50 concurrent connections to the login page and rip through the user list. At the same time, with the default BCrypt cost factor, just doing the password 'password' takes 1000 hours against a 32MM row data set.
Thanks, that's where my misunderstanding was. I've seen "salt" used (apparently, improperly) in cases where the hash is the same for all passwords. Even the wikipedia article seems to imply that use case.
The other part of my misunderstanding was that I was thinking of BCrypt as a deterministic function. Looking at an implementation, it looks like multiple calls to BCrypt::Password.create with the same value can result in different values, unlike how sha1($x) = sha1($x) for any $x.
The computational expense of a brute-force attack against a hash is the lesser of (hash length, text length). Well-known hash functions (md5, sha*) are optimized for large blocks of text, which leads to two properties: 1) they are made fast 2) them being fast is not a problem - if the text is long the strength against the brute-force attack is determined by the hash length which is very respectable for sha256 or even sha512.
However, the passwords themselves are small - the typical password is 8 characters and assuming 7 bits per character you're looking at search space of 56 bit, at which point it doesn't matter if your hash is 64, 128 or 512 bit because your strength is 56 bit. The search space can be further reduced by accounting fr various password selection biases, for example phonetic bias, tack-number-at-the-end bias, keyboard layout bias and so on.
To deal with small search spaces we need algorithmically slow hash functions - their slowness is not a problem because text is small, but it's a benefit against the brute-force attack.
Which is how it should work. Users shouldn't have to pick absurd passwords when the computer can do a better job of obscuring their password.
(Note: "them being fast", for "them" in SHA1, SHA256, etc, is not even considered a "problem"; it's considered a "huge feature", because these things are protecting individual data packets. It just happens that this primitive by itself is not useful for protecting passwords.)
So how much time does it normally take you to get this message across?
Even a small change in the message will (with an extremely high probability of 1-10^(-154)) result in a different hash, which will usually look completely different just like two unrelated random numbers do.
http://en.wikipedia.org/wiki/Whirlpool_(cryptography)
I used it for a while, then learned that using a fast hash, even looped plenty of times, is a bad idea for password storage when you have easy access to B/scrypt.
http://msdn.microsoft.com/en-us/library/system.security.cryp...
I did not find a bcrypt/scrypt implementation in standard .NET and I would be reluctant to use third-party security code I googled up somewhere.
I don't blame you for not wanting to use unverified third party security code though. RFC2898 is fine.
The parent poster has the right idea. For passwords, use bcrypt, scrypt, PBKDF, or a stretched hash.
http://en.wikipedia.org/wiki/Salt_%28cryptography%29
Edit: On second thought, I might have misread the question, perhaps you're intending to store the unique salt for each user, although that seems impractical to me since it would have to be just as obtainable as the password database.