4 ms·

Does using a unique salt for each user help here? Is there a non-obvious reason why that approach is bad?

by paulgb 17y ago

mgrouchy 17y ago
I'd be interested in knowing the answer to this too.
tptacek 17y ago
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-tables-what-you-need-to-know-about-secure-password-schemes/ http://www.matasano.com/log/958/enough-with-the-rainbow-tabl...
- ephermata 17y ago
  What do you think about halting password puzzles? http://crypto.stanford.edu/~xb/security07/index.html http://crypto.stanford.edu/~xb/security07/index.html
  - tptacek 17y ago
    I think anything ending in "KDF" gives me warm fuzzies, and that whatever you code in already has a library for BCrypt.
- mgrouchy 17y ago
  Thanks for that!
- jmillikin 17y ago
  "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.
  - tptacek 17y ago
    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.
    - jmillikin 17y ago
      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.
      - harpastum 17y ago
        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.
- paulgb 17y ago
  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.
  - tptacek 17y ago
    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.
    - paulgb 17y ago
      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.
- DenisM 17y ago
  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.cryptography.rfc2898derivebytes.aspx 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.
  - tptacek 17y ago
    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.
madair 17y ago
The salt is used for the original encryption, after which the plaintext is thrown away, then when you need to compare what the user enters next time, you use the same salt with the password entered every time. http://en.wikipedia.org/wiki/Salt_%28cryptography%29 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.
timhill 17y ago
I Am Not A Cryptographer, so take this with a grain of salt. Using a unique salt for each user "helps", but is still insecure. The problem is that hash functions such as SHA or MD5 are designed to be very fast. This means that even with unique salts it is still fairly trivial to try a large number of passwords on a large number of users and crack many or them. The parent poster has the right idea. For passwords, use bcrypt, scrypt, PBKDF, or a stretched hash.

Does using a unique salt for each user help here? Is there a non-obvious reason why that approach is bad?

by paulgb 17y ago

Does using a unique salt for each user help here? Is there a non-obvious reason why that approach is bad?

mgrouchy 17y ago

I'd be interested in knowing the answer to this too.

tptacek 17y ago

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-tables-what-you-need-to-know-about-secure-password-schemes/ http://www.matasano.com/log/958/enough-with-the-rainbow-tabl...

ephermata 17y ago
What do you think about halting password puzzles? http://crypto.stanford.edu/~xb/security07/index.html http://crypto.stanford.edu/~xb/security07/index.html
- tptacek 17y ago
  I think anything ending in "KDF" gives me warm fuzzies, and that whatever you code in already has a library for BCrypt.
mgrouchy 17y ago
Thanks for that!
jmillikin 17y ago
"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.
- tptacek 17y ago
  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.
  - jmillikin 17y ago
    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.
    - harpastum 17y ago
      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.
paulgb 17y ago
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.
- tptacek 17y ago
  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.
  - paulgb 17y ago
    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.
DenisM 17y ago
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.cryptography.rfc2898derivebytes.aspx 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.
- tptacek 17y ago
  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.

madair 17y ago

The salt is used for the original encryption, after which the plaintext is thrown away, then when you need to compare what the user enters next time, you use the same salt with the password entered every time. http://en.wikipedia.org/wiki/Salt_%28cryptography%29 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.

timhill 17y ago

I Am Not A Cryptographer, so take this with a grain of salt. Using a unique salt for each user "helps", but is still insecure. The problem is that hash functions such as SHA or MD5 are designed to be very fast. This means that even with unique salts it is still fairly trivial to try a large number of passwords on a large number of users and crack many or them. The parent poster has the right idea. For passwords, use bcrypt, scrypt, PBKDF, or a stretched hash.