The right answers to this problem are BCrypt, SCrypt, PBKDF, or (at a minimum) salted "stretched" SHA1, iterated many thousands of times.
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.
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.
The parent poster has the right idea. For passwords, use bcrypt, scrypt, PBKDF, or a stretched hash.
I'm particularly curious about how using (for example) BCrypt will prevent brute-forcing "12345", "password", or any of the other simple strings many people use.
The second point is valid but not particularly meaningful. You could also try "12345" and "password" over the network using the login page as an oracle, given a list of usernames.
But with SHA1, you can feasibly do large combinations of phonemes with numbers and punctuation across millions of accounts. People with passwords like "ugh8&eat" will lose their accounts.
You can tune BCrypt so that just "12345", by itself, is too painful to run across 32MM rows to be worth a PR stunt.
For example, I just generated a salt/digest combination for a simple example password. It is digested using SHA-1, and the password is four ASCII digits. Here is the database row -- '|' is a delimiter between the fields.
algo | user_salt | digest
----------------------------------------------------------------------
sha1 | lyhsus1eizh815xz69pv | d418a6088847d6f2e5b0e3d2ecf2e300454a0885
It takes 5us on this system to do one SHA1 calculation. You're not using ASCII "digits" (if you were, I'd know, because brute forcing all the 4-digit numeric strings took less than a second); you meant characters. There are ~130MM 4-digit character combinations in standard ASCII.
Maybe I'm misunderstanding something about this challenge, but, if I'm not, post the code you used to generate this comment so I don't waste my time attacking a salt that is secretly Base64'd, and in 10 hours, you can mail your check to Amnesty International.
Does that mean that doing so is OK, except for the read any file breach?
Because I've been doing that cookie authentications. Database and file reads are not something I'm worried about (for this situation), but I don't want the cookie to be easy to crack.
I.e. auth = sha1('long secret string' . 'user_id' . 'password') /* I include the password to invalidate existing cookies if someone changes their password */
I then set a cookie to the user_id, and another cookie to auth, and check them on every page.
Also, I'm not him, so I'd like to know why doing the config salt second instead of first is bad. I thought you could do a partial hash, i.e. hash the config salt once, then just keep updating it with the rest. Meaning, the config salt should go second, not first.
If the config salt is the second term hashed, the scheme has a basic crypto flaw, one you can't make if you just use BCrypt or PBKDF like a reasonable developer instead of designing your own vanity scheme.
If the password is changed, all session identifiers must be invalidated. If it's a session table, delete all entries, if it's a hash - well your hash had better include the password somehow (a hash of the password hash, i.e. the one stored in the db, is fine, as long as changing the password changes the final hash).
i just don't see it as a good idea to have the password be one of the inputs to the value of the session identifier in any way, which was my point.
you can handle every scenario you bring up without tying password to session id.
Isn't it up to the attacker to figure out the rest of the details? As an attacker, do you think he has a separate config salt in a file or a separate table or secondary system? That's why you DO spend 10 hours on attacking it if you want the results. His posting seems quite legitimite to me.
If your second graf is valid, then it is equally valid to say that rot13'ing your passwords before you hash them is an effective security measure, because you're right, I'd never guess you'd be that dumb.
"The config salt isn't present in my post -- I'm assuming a database breach, like that which usually occurs. The digest does include a config salt, of course -- this isn't the '70s."
I do agree this is a learning exercise. I also agree that as an attacker you still have to make a lot of presumptions such as maybe they did use a keyed SHA1 process or use Base64. Again, why is this not a legitimite question? He was not trying to trick you anymore than an attacker would have to guess/try/reason what the dev/secofr implemented.
You're a post count leader here but either I am overly sensitive to reading snarkiness or I simply don't understand. I have no problem admitting I'm not a security expert but again there are some good questions from others here. Help us out here.
But who cares? This is silly. Secure password schemes don't need to protect a key file to avoid being broken, and they don't need you to know how Merkle-Damgaard works to implement without blowing up. Any password scheme that has a "config salt" is a vanity scheme. Adding a "config salt" is less secure than literally just looping 1000 times around SHA1.
Security schemes designed as exercises in vanity have a poor track record.
On a different note, why aren't more webapps tracking login attempts? Is this too difficult to implement based on simple but sane "timeout" rules?
Also, if an attacker does have access to the db through an injection and is able to dump/download the db what is really stopping the attacker from using a multitude of cheap machines? I'm just a small shop and I turn up 19 or 20(half cab)u dual density servers(16 cores/u) every few months. So I'm looking at 320 cores that a 32 million record database distributed over is actually pretty small. Does any kind of encryption matter at that point? In this day, that kind of processing power is cheap.
When you start worrying about attackers who will lease massive numbers of servers to crack your passwords, you dial up the cost on your hashes. You can do that transparently with BCrypt, migrating users as they log in. Every tiny incremental increase to the cost of a single login you make creates drastic cost increases for your attackers. You are on the right side of the scaling problem, the attacker is on the wrong side, and you can play the game indefinitely.
Because you've been assuming that the database will be breached and that no other kind of attack can happen.