8 ms·

Question: From my understanding bcrypt is designed for security even when the hashed data is leaked. Each piece of data is uniquely salted and hashed to perhaps

by Olscore 10y ago

Question: From my understanding bcrypt is designed for security even when the hashed data is leaked. Each piece of data is uniquely salted and hashed to perhaps varying degrees of difficulty. So for a thought experiment, let's say a site made the password column of their user database public. Given an entirely public password column, even with associated usernames, would this have any use or decrease the security of those user accounts at all, aside from the obvious that their username is known?

andrewmunsell 10y ago
It would allow you to bruteforce the passwords without any sort of rate limiting. So, if you used a dictionary, you probably could get quite a few weak passwords in a short amount of time relative to a system that had proper rate limiting to prevent these kinds of attacks.
- Olscore 10y ago
  Ah derp. Totally forgot about rate limiting. Thank you.
  - sintaxi 10y ago
    I thought bcrypt was a deliberately slow algorithm so it cant necessarily be brute forced.
    - WA 10y ago
      But still much faster than an HTTP request to an Auth API that allows only, say, 5 requests per minute.
    - Olscore 10y ago
      Right, but you would still bypass the rate limiting of the server whether that be login attempts, http requests per second, firewall rules, latency or whatever when checking.
      - dogma1138 10y ago
        That's another rate limiting that has nothing to do with the hash strength. Good password hashing functions have internal rate limits that reduce the likelihood of anyone being able to break the hashes easily because they will be expensive even when fully implemented in hardware. For how long are they resilient it's another question but bcrypt is pretty good, it's quite slow, and is expensive to implement in ASIC/FPGA.
        sintaxi 10y ago
        This is what I was thinking about. Thanks.
- imdsm 10y ago
  You'd still need the salt though, right?
  - 15155 10y ago
    Bcrypt salts are ordinarily colocated with the hashes and the number of rounds used to compute them.
  - valleyer 10y ago
    The salt is typically stored with the hashed value. Its purpose is simply to prevent you from being able to use a single dictionary attack on all users.
  - andruby 10y ago
    The salt is usually stored with the hash. It prevents using pre-calculated rainbow tables. Without a salt you can check a password guess against all passwords. With a salt you can only test the guess against a single password.
- cm2187 10y ago
  Depends what you mean by short amount of time. Depending on the strength selected with bcrypt, it can easily take a second to check a hash. On a 30m password database, this will take a year on one machine to check just who is using "monkey" as a password.
  - fit2rule 10y ago
    > it can easily take a second to check a hash On what hardware?
    - cm2187 10y ago
      An i7 laptop. But even if you use an 18 cores server, it doesn't really change the point. It might take a month instead of a year. But it still doesn't scale, even to only check the most common passwords.
      - iagooar 10y ago
        How can you say it doesn't scale? You just need to spin up a cluster that is powerful enough to get down to let's say a week. The cost of this would be a joke for a company / institution of a certain size.
        cmdrfred 10y ago
        1 week only tests 1 password. It would have to run for years to get a decent set of results. I don't see how a company can afford all that hardware and power to do something that is illegal to begin with. How do they monetize it to get a return?
        iagooar 10y ago
        You just need to target certain accounts, no need for all.
        iagooar 10y ago
        And don't forget, that every 18 months, the amount of processing power you get for a modest price, doubles.
- xerophyte12932 10y ago
  wouldn't the slowness of bcrpyt be a hindrance enough? Of course rate limiting is a much greater barrier, but I thought the whole point of using bcrypt is that its naturally slow and prevents checking several passwords in a short time
  - TACIXAT 10y ago
    You can set the work factor (log rounds). Bcrypt is also cool because it doesn't scale well to GPUs, so it's still pretty slow even if you have decent hardware. The rounds are a trade off between how long your users will wait to login and how strong the hashes will be. The current recommendation is between 8 and 12 depending where you look. The best practice is to just check on the system you are running, I usually aim for the number of rounds nearest a half a second.
drrob 10y ago
I suppose the main danger is the possibility that someone might, at some point in the future if processing power should suddenly take a leap forward, come up with a way to crack them.
- bbcbasic 10y ago
  Would something like an ASIC help the attacker, I wonder?
  - drrob 10y ago
    Or some curious, thousands-of-computers strong grid-based cracking enterprise. I suppose, even constrained by the current state of tech, cracking bcrypt with some kind of massively parallel dictionary attack isn't entirely unfeasible.
- merb 10y ago
  eventually at least on PBKDF2 you could also increase the number of rounds taken. So if somebody logs in you could recalculate the PBKDF2 hash.
  - drrob 10y ago
    Indeed, though I suppose you've got to hope that the keeper of the passwords gets their hands on a similar level of processing power as the attackers do, with which they can increase the encryption work factor.
  - DasIch 10y ago
    You can upgrade hashes offline as well. You just hash the existing hash with the new algorithm/configuration and remember algorithm, salt and any other parameters for all previously used algorithms. If you have all that information you can take the same path to verify the password and replace the chained hash with a simple hash that's faster to calculate.
curryhoward 10y ago
It's an interesting thought, but it would be a catastrophe. Even if you can't brute force strong passwords due to many rounds of hashing, you can still check the hashes/salts against common passwords. You can't do a rainbow table attack, but you can do a dictionary attack.
MarkMc 10y ago
It would substantially reduce the security of the system. A large percentage of passwords are on the top-10000 password list, and for such passwords it is easy to reverse the hash using brute force
e12e 10y ago
> would this have any use or decrease the security of those user accounts at all Yes: http://www.pxdojo.net/2015/08/what-i-learned-from-cracking-4000.html http://www.pxdojo.net/2015/08/what-i-learned-from-cracking-4... Now, this assumes typical storage, that "leaking the password column" means leaking hashed password+salt. Without the salt, things would go slower - but it's sort of an artificial constraint - what you're talking about, is leaking the stuff the server needs to have to check a valid password. And that generally means the hash and the salt. More generally, there's an upper bound on how difficult it can be made for the server to verify a password; conceptually this is: ((the amount of time a user is willing to wait to be logged in) - overhead) / (resources available on the server for checking the password) Ok. You don't actually divide the time by the resources, but the point is that if you have 10.000 (valid) logins a minute, you probably can't dedicate 4 high-end GPUs on max throttle for 1 second to check every login attempt. But an attacker might have those kind of resources. Which means, there's a very real practical limit to how hard it can be made to validate a password guess (a cracking attempt) -- and it will be some small fraction of the time your server takes to validate a login. Which means that no "easy" passwords (eg: dictionary words) are ever "safe" passwords (safe against an off-line attack). My guesstimate (mostly pulled out of thin air, and late night napkin "calculations") are that for any password to be "secure" it would need ~64 bits of entropy. Maybe that's a high estimate, given a solid work factor, but I don't think so. The problem is, that 64 bits is actually quite a lot of information to memorize. In short: you'll likely only remember one or two such passwords. Use them to lock your password manager, and have machine generated random passwords for the rest (because what you don't want is to ever re-use passwords, as passwords are generally always susceptible to sniffing, shoulder-surfing, being filmed, keylogged or otherwise captured in plain text). For a little more about some of my thoughts on generating passwords that are secure, friendly to current systems ("password rules"), friendly to humans (feasible to remember and type from memory without visual feedback), see these comments: https://news.ycombinator.com/item?id=11772700 https://news.ycombinator.com/item?id=11772700 (I keep coming back to this idea, but so far I've concluded that 64, 96 and 128 bits is rather a lot to type in, almost no matter how it's encoded. So I'm not sure how useful such a system will end up being. But maybe I'll finally just prototype it, and ask for help in testing it (the "security" part is intentionally trivial, but the usability part is the interesting bit -- will it actually help us in using secure, machine generated passwords, or will we still have trouble remembering them?)
fredley 10y ago
bcrypt and other modern hashing algorithms allow strengthening your hashes (by computing more iterations) at a later date should technological advances make your current number of rounds too weak. This allows you to 'upgrade' your password hashes from 20 rounds to 20,000 without needing the user to re-enter their password. If you publish your hashes at any point, you lose the benefits of this, if your hashes become weakened by technological progress you need to reset your users' passwords.
ck2 10y ago
How can a salt change on every encoding? There has to be a reference point, no?
- tim333 10y ago
  You can hash a fixed salt + password + some other user info like surname or email address. That way if you have the salt you can't just compute the hash of salt+"123456" to see who had that, you have to compute separately for each user.
  - jfindley 10y ago
    What? No. Don't use a fixed salt. Each record should have a unique, random salt. You then store salt:hash(salt+password). There are numerous guides on how to do this properly, for example https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet
    - DasIch 10y ago
      Though of coure you don't actually do that, you use something like bcrypt that does this for you.
      - jfindley 10y ago
        Yes absolutely this - I was just trying to explain how salts should implemented - in the real world always use something like bcrypt or scrypt that does all this for you.
        tim333 10y ago
        OK, I think I got my terminology wrong. But my thinking was that as well as using bcrypt or whatever on the info in the database you can add some random value stored in code rather than in the database so if your database is compromised it's still a job for them to crack it. Not quite sure what you call that.
nailer 10y ago
I thought this was from a phishing attack - eg, plaintext, not bcrypt hashes?

by Olscore 10y ago

andrewmunsell 10y ago

It would allow you to bruteforce the passwords without any sort of rate limiting. So, if you used a dictionary, you probably could get quite a few weak passwords in a short amount of time relative to a system that had proper rate limiting to prevent these kinds of attacks.

Olscore 10y ago
Ah derp. Totally forgot about rate limiting. Thank you.
- sintaxi 10y ago
  I thought bcrypt was a deliberately slow algorithm so it cant necessarily be brute forced.
  - WA 10y ago
    But still much faster than an HTTP request to an Auth API that allows only, say, 5 requests per minute.
  - Olscore 10y ago
    Right, but you would still bypass the rate limiting of the server whether that be login attempts, http requests per second, firewall rules, latency or whatever when checking.
    - dogma1138 10y ago
      That's another rate limiting that has nothing to do with the hash strength. Good password hashing functions have internal rate limits that reduce the likelihood of anyone being able to break the hashes easily because they will be expensive even when fully implemented in hardware. For how long are they resilient it's another question but bcrypt is pretty good, it's quite slow, and is expensive to implement in ASIC/FPGA.
      - sintaxi 10y ago
        This is what I was thinking about. Thanks.
imdsm 10y ago
You'd still need the salt though, right?
- 15155 10y ago
  Bcrypt salts are ordinarily colocated with the hashes and the number of rounds used to compute them.
- valleyer 10y ago
  The salt is typically stored with the hashed value. Its purpose is simply to prevent you from being able to use a single dictionary attack on all users.
- andruby 10y ago
  The salt is usually stored with the hash. It prevents using pre-calculated rainbow tables. Without a salt you can check a password guess against all passwords. With a salt you can only test the guess against a single password.
cm2187 10y ago
Depends what you mean by short amount of time. Depending on the strength selected with bcrypt, it can easily take a second to check a hash. On a 30m password database, this will take a year on one machine to check just who is using "monkey" as a password.
- fit2rule 10y ago
  > it can easily take a second to check a hash On what hardware?
  - cm2187 10y ago
    An i7 laptop. But even if you use an 18 cores server, it doesn't really change the point. It might take a month instead of a year. But it still doesn't scale, even to only check the most common passwords.
    - iagooar 10y ago
      How can you say it doesn't scale? You just need to spin up a cluster that is powerful enough to get down to let's say a week. The cost of this would be a joke for a company / institution of a certain size.
      - cmdrfred 10y ago
        1 week only tests 1 password. It would have to run for years to get a decent set of results. I don't see how a company can afford all that hardware and power to do something that is illegal to begin with. How do they monetize it to get a return?
        iagooar 10y ago
        You just need to target certain accounts, no need for all.
        iagooar 10y ago
        And don't forget, that every 18 months, the amount of processing power you get for a modest price, doubles.
xerophyte12932 10y ago
wouldn't the slowness of bcrpyt be a hindrance enough? Of course rate limiting is a much greater barrier, but I thought the whole point of using bcrypt is that its naturally slow and prevents checking several passwords in a short time
- TACIXAT 10y ago
  You can set the work factor (log rounds). Bcrypt is also cool because it doesn't scale well to GPUs, so it's still pretty slow even if you have decent hardware. The rounds are a trade off between how long your users will wait to login and how strong the hashes will be. The current recommendation is between 8 and 12 depending where you look. The best practice is to just check on the system you are running, I usually aim for the number of rounds nearest a half a second.

drrob 10y ago

I suppose the main danger is the possibility that someone might, at some point in the future if processing power should suddenly take a leap forward, come up with a way to crack them.

bbcbasic 10y ago
Would something like an ASIC help the attacker, I wonder?
- drrob 10y ago
  Or some curious, thousands-of-computers strong grid-based cracking enterprise. I suppose, even constrained by the current state of tech, cracking bcrypt with some kind of massively parallel dictionary attack isn't entirely unfeasible.
merb 10y ago
eventually at least on PBKDF2 you could also increase the number of rounds taken. So if somebody logs in you could recalculate the PBKDF2 hash.
- drrob 10y ago
  Indeed, though I suppose you've got to hope that the keeper of the passwords gets their hands on a similar level of processing power as the attackers do, with which they can increase the encryption work factor.
- DasIch 10y ago
  You can upgrade hashes offline as well. You just hash the existing hash with the new algorithm/configuration and remember algorithm, salt and any other parameters for all previously used algorithms. If you have all that information you can take the same path to verify the password and replace the chained hash with a simple hash that's faster to calculate.

curryhoward 10y ago

It's an interesting thought, but it would be a catastrophe. Even if you can't brute force strong passwords due to many rounds of hashing, you can still check the hashes/salts against common passwords. You can't do a rainbow table attack, but you can do a dictionary attack.

MarkMc 10y ago

It would substantially reduce the security of the system. A large percentage of passwords are on the top-10000 password list, and for such passwords it is easy to reverse the hash using brute force

e12e 10y ago

> would this have any use or decrease the security of those user accounts at all Yes: http://www.pxdojo.net/2015/08/what-i-learned-from-cracking-4000.html http://www.pxdojo.net/2015/08/what-i-learned-from-cracking-4... Now, this assumes typical storage, that "leaking the password column" means leaking hashed password+salt. Without the salt, things would go slower - but it's sort of an artificial constraint - what you're talking about, is leaking the stuff the server needs to have to check a valid password. And that generally means the hash and the salt. More generally, there's an upper bound on how difficult it can be made for the server to verify a password; conceptually this is: ((the amount of time a user is willing to wait to be logged in) - overhead) / (resources available on the server for checking the password) Ok. You don't actually divide the time by the resources, but the point is that if you have 10.000 (valid) logins a minute, you probably can't dedicate 4 high-end GPUs on max throttle for 1 second to check every login attempt. But an attacker might have those kind of resources. Which means, there's a very real practical limit to how hard it can be made to validate a password guess (a cracking attempt) -- and it will be some small fraction of the time your server takes to validate a login. Which means that no "easy" passwords (eg: dictionary words) are ever "safe" passwords (safe against an off-line attack). My guesstimate (mostly pulled out of thin air, and late night napkin "calculations") are that for any password to be "secure" it would need ~64 bits of entropy. Maybe that's a high estimate, given a solid work factor, but I don't think so. The problem is, that 64 bits is actually quite a lot of information to memorize. In short: you'll likely only remember one or two such passwords. Use them to lock your password manager, and have machine generated random passwords for the rest (because what you don't want is to ever re-use passwords, as passwords are generally always susceptible to sniffing, shoulder-surfing, being filmed, keylogged or otherwise captured in plain text). For a little more about some of my thoughts on generating passwords that are secure, friendly to current systems ("password rules"), friendly to humans (feasible to remember and type from memory without visual feedback), see these comments: https://news.ycombinator.com/item?id=11772700 https://news.ycombinator.com/item?id=11772700 (I keep coming back to this idea, but so far I've concluded that 64, 96 and 128 bits is rather a lot to type in, almost no matter how it's encoded. So I'm not sure how useful such a system will end up being. But maybe I'll finally just prototype it, and ask for help in testing it (the "security" part is intentionally trivial, but the usability part is the interesting bit -- will it actually help us in using secure, machine generated passwords, or will we still have trouble remembering them?)

fredley 10y ago

bcrypt and other modern hashing algorithms allow strengthening your hashes (by computing more iterations) at a later date should technological advances make your current number of rounds too weak. This allows you to 'upgrade' your password hashes from 20 rounds to 20,000 without needing the user to re-enter their password. If you publish your hashes at any point, you lose the benefits of this, if your hashes become weakened by technological progress you need to reset your users' passwords.

ck2 10y ago

How can a salt change on every encoding? There has to be a reference point, no?

tim333 10y ago
You can hash a fixed salt + password + some other user info like surname or email address. That way if you have the salt you can't just compute the hash of salt+"123456" to see who had that, you have to compute separately for each user.
- jfindley 10y ago
  What? No. Don't use a fixed salt. Each record should have a unique, random salt. You then store salt:hash(salt+password). There are numerous guides on how to do this properly, for example https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet
  - DasIch 10y ago
    Though of coure you don't actually do that, you use something like bcrypt that does this for you.
    - jfindley 10y ago
      Yes absolutely this - I was just trying to explain how salts should implemented - in the real world always use something like bcrypt or scrypt that does all this for you.
      - tim333 10y ago
        OK, I think I got my terminology wrong. But my thinking was that as well as using bcrypt or whatever on the info in the database you can add some random value stored in code rather than in the database so if your database is compromised it's still a job for them to crack it. Not quite sure what you call that.

nailer 10y ago

I thought this was from a phishing attack - eg, plaintext, not bcrypt hashes?