Comment by tptacek | Hacker News Reader

Comment by tptacek | Hacker News Reader

Parent Full thread

The "salt" --- which, so far as I can tell, is a term used almost never in academic crypto research --- defeats one very effective exotic attack: the "rainbow table", where an attacker builds a database of perfect hash :: string correspondances.

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...

I certainly get why a slower hash would curb brute force attacks, but when I'm talking about unique salts, slowing down the hash is not the purpose I have in mind.

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.

Every time I bring this up, which is often because it is, apparently, all I ever talk about here, people misconstrue what I'm saying as some kind of argument against "salted" hashes.

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.

I'm not misconstruing your argument as against salted hashes, but as downplaying the advantages of using a unique salt over an install-specific salt (not sure that's the best term, but I'm referring to the type of salt you might find in a config.py file).

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.

"Salts" have been password-specific since Ken Thompson invented them in the '70s. We're not talking about different approaches: the approach you're talking about is unsafe.

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.

> "Salts" have been password-specific since Ken Thompson invented them in the '70s.

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.

I've read your explanation of this problem several times in the past and only now I figured out (I think) the problem you are pointing out. This seems to be substance of your argument, as I understood it:

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.

Yes. Think also of it this way: poor user password selection (and here we mean "ugh&8eat" is a weak password) sabotages the complexity of the attack, and adaptive hashing (like SCrypt) fixes that problem algorithmically.

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.)

Okay.

So how much time does it normally take you to get this message across?

Here's a funny thing: every time this comes up, someone asks me if Whirlpool solves the problem. What is it with Whirlpool?

It creates long (512-bit) digests, and:

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.

The second graf describes every cryptographically secure hash, though.

But we force users to choose obscure passwords to discourage dictionary attacks (so I thought) not to protect them in case our dbs are hacked. A computer may be able to obscure a password better than the average user but at the end of the day the user still has to commit that password to memory, which may be why people stick with the same simple passwords to begin with.

Yes, and adaptive hashing makes those memorable passwords significantly more safe.

My understanding was that hashing a hash was stupid because you've effectively limited your attacker's search space. That is, in the beginning the password or pass phrase can be any length (probably up to 255), but after hashing you've restricted it to a known length composed of known characters. Therefore, you've decimated the overall search space. It seems like iteratively rehashing your hash 1000 times would make things significantly more insecure.

A SHA1 hash is, what, 160 bits long? That's better than most AES keys. Nobody attacks passwords by directly attacking the SHA1 algorithm.

"salting" also prevents brute-forcing. Assuming a bare-basics implementation (20-char salt in config file, 20-char salt per user, prepended to the password), the only way an attacker can brute-force passwords in a reasonable timeframe is to compromise the server itself. At that point, it would be just as easy to make the login form mail him passwords.

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.

If you can't understand the significance of these two results (and this is with the default cost factor for BCrypt), you're just arguing to hear yourself talk.

  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

I could raise the number of iterations to bring SHA1 above the measurement floor, but I don't want to lock my computer up with pointless BCrypt cycles.

Using these numbers, it would take your computer roughly 12 years to check 32M passwords against that string. That's a long time, but feasible (with additional power), and more specialized systems can bring it within reach.

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.

I think that the salient detail is this:

    t = Time.now.to_i
    1000000.times {Digest::SHA1.hexdigest("ugh8&eat")}
    puts (Time.now.to_i - t).to_s
    =>3

Sure, 120ms is a bit long, but I think it would be beneficial to security to require more than 3µs.

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.

There are lots of ideas which are beneficial, but not particularly useful. For example, requiring passwords to be at least 120 characters would (in theory) make passwords more difficult to compromise, but in practice users are just going to type "password" 15 times.

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.

Calculating a BCrypt hash with the default cost factor takes about as long as reading an uncached file off a conventional filesystem. What a silly thing to try to optimize. Really? It's killing you to spend 100ms on password hashing? Ok, dial it down to 50ms. BCrypt is tunable.

His computer is taking 12 seconds for 100 iterations. The time spent checking the password would be more like 120 ms, totally in the order of a decently fast http request.

If the attacker can get the list of password hashes, what's stopping him from getting your salts too?

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.

Salts are usually stored in two components; one is in the database and unique per row, to prevent cracking multiple rows at once. The other component is in a config file in the server -- it adds a constant number of bytes to the input for any brute force attempt.

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.

If your webserver machines are so secure, why put them in the database at all? Just store the passwords on disk there, rsync the password file across all machines and you're set.

I kid, but I really think you and tptacek just have different standards. tptacek's is higher.

Lots more web app flaws allow you to read arbitrary files than allow you to get a shell on the app server. There are cases where SQL Injection by itself is sufficient to get the contents of files. I think that's what bothers me most about using SHA1(k, nonce, password) as a hash.

Well, that and the obnoxious trick question.

If your webserver machines are so secure, why put them in the database at all?

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)

What do you think about halting password puzzles?

http://crypto.stanford.edu/~xb/security07/index.html

I think anything ending in "KDF" gives me warm fuzzies, and that whatever you code in already has a library for BCrypt.

For those using .NET there is a built-in implementation of PBKDF2, it's called called Rfc2898DeriveBytes:

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.

There's Bcrypt.NET, which looks reasonable to me. It's a direct port of jBCrypt (Java).

I don't blame you for not wanting to use unverified third party security code though. RFC2898 is fine.

Thanks for that!

Reply on news.ycombinator.com