7 ms·

Enjoyable read, but I question the bit near the end claiming that salts wouldn't help much against this kind of attack. From my understanding, per-user salting

by tomku 13y ago

Enjoyable read, but I question the bit near the end claiming that salts wouldn't help much against this kind of attack. From my understanding, per-user salting does substantially slow down this kind of attack because it forces you to calculate a different hash for each user/plaintext combination rather than hashing a suspected plaintext once and comparing the hash against the whole list. What it doesn't slow down is the brute-force cracking of a single targeted hash. Am I missing something there, or is the article wrong?

chm 13y ago
Where/how do you store the salts?
- tomku 13y ago
  Right next to the hashed passwords. The point of salting isn't to add an additional level of secrecy, it's just to prevent the reuse of hashing work for attacking other users.
  - chm 13y ago
    But doesn't this render the process useless? If an attacker gets access to the hashes, he also gets access to the salts. If both hashes and salts were isolated, I suppose it would be much more secure, although maybe too slow.
    - arjie 13y ago
      Without salts: Generate table of hashes vs. Plaintext for all plaintext up to certain length. Maybe use rainbow tables. Now, for each entry use this table. Time to get plaintext of n hashes is constant. With salt: Generate table of hashes vs. Plaintext by appending salt to each possible plaintext of given length. For first entry use first salt to generate this table. Table is now useless for second salt if it is different. Time to attack n hashes scales linearly.
    - baddox 13y ago
      The salts provide their primary benefit (rendering rainbow tables useless) even when the attacker possesses the salts and the hashed passwords.
    - ams6110 13y ago
      The point of the salt is to prevent precomputing the hashes (a rainbow table). Per-user salts take this a step farther, so that even if two users choose the same password, they will have different hashes. What the article really points out is what people have been saying for a while now, that if your passwords are exposed, salting really doesn't add more than a roadbump to a cracker if you are computing your hashes with fast message-digest algorithms like MD5 or SHA.
      - qu4z-2 13y ago
        I dunno... in the example there, I'd say that it costing 16000x as much to crack the passwords would be a little more than a "roadbump". (assuming people are renting {C,G}PUs in the cloud to perform the attacks)
    - tomku 13y ago
      Absolutely not. Like I said, the point of the salt is not to provide a "second password" that needs to be independently stolen. It's to make the results from a cracking attempt on one account useless on the password of another. If you've read the article, you have a pretty good idea of how it works without salting. You have a list of N password hashes, and you come up with candidate passwords. You run each candidate password through the hash function, and compare the resulting hash to your list. If it matches any of them, you've got the plaintext for those user accounts. The key thing here is that you only have to hash each candidate password once, and you can compare that hash to as many accounts as you'd like. Now, let's add in a salt. It's stored next to the password, so after stealing the password db you've got a list of password hashes, each with its own salt. In order to check a candidate password against a particular user account, you have to append that user account's salt to the candidate, then hash it and compare against the stored hash. That part isn't any slower. The problem is when you try to take that hash and compare it to other accounts. Even if two users have the same plaintext password, their password hashes will be different because they have different salts. The end result is that you have to hash each candidate password fresh for every user.
      - chm 13y ago
        That's what I understood from the article, and why I suggested the salts and hashes should be handled separately. If you give the attacker the salts, difficulty scales linearly. For two identical plaintexts, all that differs is the salt, but it is given to him. If you store the hashes and salts separately (the technical details of which I know nothing about), then you augment the keyspace exponentially. For N byte salts, using P characters, you augment it by N^P. Furthermore, who forces you to append a salt? You could prepend. Or n-pend. I'm just throwing ideas around.
        nknighthb 13y ago
        The server must have access to both the salt and the hash to verify a password. Therefore, upon compromise of the server, the attacker automatically has access to both the salt and the hash. There is no way around this problem that isn't simply obfuscation.
    - deleted 13y ago
      [deleted]
    - lambda 13y ago
      A salt is not for adding extra secrecy. It's for making it take more work to solve a large number of passwords at once. It doesn't need to be stored separately to do this. What you're thinking of is a secret-splitting scheme; where you split a secret among multiple parties, where you need the information from both parties to reconstruct the secret. That's a valid cryptographic technique, but that's not what's meant when you say "salted password". The problem is, for passwords, that approach isn't really workable. Whatever machine is verifying the passwords will need access to the full hash to do so, so if it's compromised, you could get access to the full hash. I suppose you could split the verification into two parts, on two separate machines. Each one would have it's own password database, with independent salts, and the machine trying to authenticate the user would request verification from each of the other machines before allowing you in. However, that would make your password system slower and more fragile; now if either of those machines goes offline, your login functionality breaks (and yes, you could do a "two out of three" system to avoid that, but now you're talking about tripling your hardware requirements just for your password verification system). Really the best bang for your buck will come from (a) securing your system so that it doesn't reveal your password database in the first place and (b) using bcrypt, scrypt, or PBKDF2 to make brute forcing a database that is disclosed much more difficult. It's far more likely that you will build a secure system by following basic security practices like isolating services and giving each the minimum privilege that it needs, doing code review, keeping inessential services off of important machines, using prepared statements rather than building SQL queries from user-supplied strings, and so on, as well as using off-the-shelf security components that have been well tested like the above hash algorithms, than you will by designing your own password system using some novel technique to spread the secret out among multiple machines.
      - PwdRsch 13y ago
        There actually has been research on how to split passwords across multiple servers (one example http://www.passwordresearch.com/papers/paper270.html http://www.passwordresearch.com/papers/paper270.html), and RSA is currently marketing a commercial product that does this. While I agree that most people probably aren't concerned enough about password exposure to do this, there are effective solutions to accommodate those that are.
- markdown 13y ago
  Right there in the same field as the password: <salt>::<hashed_password> The pepper on the other hand shouldn't be in the db. Hardcode that into a config file.
  - eropple 13y ago
    "Pepper"s are essentially meaningless and provide no real benefit over a salt. And you should be using bcrypt anyway.
    - markdown 13y ago
      > "Pepper"s are essentially meaningless and provide no real benefit over a salt. Citation needed. There appears to be a case where it could prove to be an advantage: http://security.stackexchange.com/questions/3272/password-hashing-add-salt-pepper-or-is-salt-enough http://security.stackexchange.com/questions/3272/password-ha... > And you should be using bcrypt anyway. Yeah, except bcrypt isn't always an option. Eg: on Google App Engine.
      - deleted 13y ago
        [deleted]
      - eropple 13y ago
        Yeah, that's why I said "essentially" instead of "totally". Writing your own MAC is not a good idea, pretty much full-stop. tptacek has talked about this[1] before. In the sort of environment that necessitates stupid hashing, if your database is owned your app is owned anyway. If bcrypt isn't an option, you straight-up need a better platform. It's inexcusable to refuse to protect your users--if you're not using bcrypt/scrypt/PKBDF2 you're mistreating your users. [1] - https://news.ycombinator.com/item?id=5663818 https://news.ycombinator.com/item?id=5663818
        danielweber 13y ago
        I know at least one major security company (that deals with Fortune 500 companies) is recommending having an extra key inside the app server, distinct from the database, since there are situations where someone can get the a copy of the DB and not your server. The fact that they're big doesn't mean they're right, of course. But I know I've seen a bunch of news stories about DB leaking and I haven't seem a bunch about the source code to the website leaking. (Obviously there is some confirmation bias there.)
- theboss 13y ago
  Salting would definitely make a difference. The point of salting is to increase the complexity and overhead of generating rainbow tables. The first mistake here is the use of MD5. MD5 is flat out broken. Do Not use md5. Do use bcrypt. In your db, you can store the salt right there....next to the hash... How a salt increases the complexity is quite simple. If a attack has a giant rainbow table, the salt causes him to increase the size of his rainbow table and the space required to hold it and the pre-processing time to generate it. For example Here is what your database might look like with a 3 byte salt password : salt hunter2 : 100 qwerty1 : 101 Here is what the attacks rainbow tables will have to look like qwerty1 : 101 hunter2 : 100 qwerty1 : 100 hunter2 : 101 hunter2 : 103 qwerty1 : 102 ... .. . That's about it. There are other purposes of the salt too but other people talked about those ones.
  - smcl 13y ago
    If anyone doesn't get the "hunter2" reference: http://www.bash.org/?244321 http://www.bash.org/?244321
lbarrow 13y ago
The article clearly explained that using more salts was preferable to using a global salt and did a good job of explaining why. They didn't come out and say that a per-user salt is best, but that's the natural conclusion of the argument they developed.
- tomku 13y ago
  Maybe we read different articles, but the one I read seemed intent on strongly downplaying the amount of extra security that salting provides. It actually uses the phrase "minimal amount of protection" to describe a salt's effect on cracking attempts. That seems like a strange choice of words when salting would've completely changed the outcome of the cracking attempts described in the article. Edit: To be clear, I'm aware that salting doesn't protect against targeted attacks, but the attacks discussed in the article weren't targeted. One of the major reasons[1] they were able to crack 16,000 passwords in a few hours was due to the lack of salting. [1]: The other being the choice of MD5 rather than bcrypt/scrypt/PBKDF2/etc, naturally.
  - reeses 13y ago
    Salting wouldn't have changed the outcome of the cracking attempts in the article. The primary focus was on how pre-computed hashes (rainbow tables, etc.) are no longer a tool used by most people attacking password lists because GPU-based hashers are efficient enough, the dicts long enough, and the methods of permuting the dicts (combinations, leet substitutions, markov chains, etc.) are rich enough that storing all possible hashes is actually less effective than writing an MD5 kernel for your AMD GPU and letting it go, monitoring for trends in the output.
    - claudius 13y ago
      But with a per-user salt, they would have to attack each password individually, using each of these techniques with each given salt and hope for a coincidence with the stored hash, rather than run their techniques and compare the resulting hashes to the stored ones? Something like: Global hash: while(s = guess()) { if (md5(s,salt) in list) { print s; delete(md5(s,salt),list); } } Unique hash: while(s = guess()) { foreach(h in list) { if (md5(s,salt)==h) { print s; delete(h,list); } } } The former requires one md5 calculation and one lookup per guess, the latter needs n md5 calculations per guess. That certainly is quite a difference, assuming the bottleneck to be md5.
iuguy 13y ago
I'm in the middle of researching re-evaluating rainbow table attacks in light of Moore's law, GPUs and Crack (lookup) tables, I've also looked into countermeasures. What you're describing is partially correct. When you crack passwords (either with rainbow tables or by brute force) you generate an iterator or use a dictionary and work through this generating hashes (with rainbow tables this works via a series (or chain) of what are called hash reduction functions instead of a plain iterator). You then compare the hash you've generated against all the hashes being subjected to the crack. Where there's a match, you win! If you're targeting a single hash and it's unsalted, rainbow tables will work as they're precomputed. It's inefficient, but it'll work. If you're using a salt, rainbow tables need to be pre-computed for the salt - I actually did this years back with a team for oracle 10g SYS and other default user passwords as the username was used as the salt. If you're targeting a single hash and it's salted then the iterative or dictionary approach will still work in roughly the same time as the salt is known. Separating the salt means you have to brute force it which is a PITA but generally because the way hashes tend to be stored (remember we're talking about a mechanism that shouldn't really be used anyway) the salt needs to be accessible by that system so you can dump the salt out regardless. Depending on where my current research goes it looks like some salting mechanisms may be feasibly pre-computable now beyond those that use predictable salts. GPUs allow you to create and traverse enormous chains in rainbow tables and while having to precompute per salt will be a PITA it looks like it is possible with sufficient storage and GPU power.
- csense 13y ago
  What if a site uses 128-bit salts generated by a good (perhaps hardware-based) RNG?
  - mikegioia 13y ago
    That will remove pre-computed rainbow tables from the equation.
    - iuguy 13y ago
      Only really for the time being (and a considerable time to come, Quantum and Biological computing enhancements notwithstanding) but for a salt that big it makes far much more sense to use a key derivation function as you're effectively generating two keys otherwise (one user generated, the other - salt - via PRNG).

by tomku 13y ago

chm 13y ago

Where/how do you store the salts?

tomku 13y ago
Right next to the hashed passwords. The point of salting isn't to add an additional level of secrecy, it's just to prevent the reuse of hashing work for attacking other users.
- chm 13y ago
  But doesn't this render the process useless? If an attacker gets access to the hashes, he also gets access to the salts. If both hashes and salts were isolated, I suppose it would be much more secure, although maybe too slow.
  - arjie 13y ago
    Without salts: Generate table of hashes vs. Plaintext for all plaintext up to certain length. Maybe use rainbow tables. Now, for each entry use this table. Time to get plaintext of n hashes is constant. With salt: Generate table of hashes vs. Plaintext by appending salt to each possible plaintext of given length. For first entry use first salt to generate this table. Table is now useless for second salt if it is different. Time to attack n hashes scales linearly.
  - baddox 13y ago
    The salts provide their primary benefit (rendering rainbow tables useless) even when the attacker possesses the salts and the hashed passwords.
  - ams6110 13y ago
    The point of the salt is to prevent precomputing the hashes (a rainbow table). Per-user salts take this a step farther, so that even if two users choose the same password, they will have different hashes. What the article really points out is what people have been saying for a while now, that if your passwords are exposed, salting really doesn't add more than a roadbump to a cracker if you are computing your hashes with fast message-digest algorithms like MD5 or SHA.
    - qu4z-2 13y ago
      I dunno... in the example there, I'd say that it costing 16000x as much to crack the passwords would be a little more than a "roadbump". (assuming people are renting {C,G}PUs in the cloud to perform the attacks)
  - tomku 13y ago
    Absolutely not. Like I said, the point of the salt is not to provide a "second password" that needs to be independently stolen. It's to make the results from a cracking attempt on one account useless on the password of another. If you've read the article, you have a pretty good idea of how it works without salting. You have a list of N password hashes, and you come up with candidate passwords. You run each candidate password through the hash function, and compare the resulting hash to your list. If it matches any of them, you've got the plaintext for those user accounts. The key thing here is that you only have to hash each candidate password once, and you can compare that hash to as many accounts as you'd like. Now, let's add in a salt. It's stored next to the password, so after stealing the password db you've got a list of password hashes, each with its own salt. In order to check a candidate password against a particular user account, you have to append that user account's salt to the candidate, then hash it and compare against the stored hash. That part isn't any slower. The problem is when you try to take that hash and compare it to other accounts. Even if two users have the same plaintext password, their password hashes will be different because they have different salts. The end result is that you have to hash each candidate password fresh for every user.
    - chm 13y ago
      That's what I understood from the article, and why I suggested the salts and hashes should be handled separately. If you give the attacker the salts, difficulty scales linearly. For two identical plaintexts, all that differs is the salt, but it is given to him. If you store the hashes and salts separately (the technical details of which I know nothing about), then you augment the keyspace exponentially. For N byte salts, using P characters, you augment it by N^P. Furthermore, who forces you to append a salt? You could prepend. Or n-pend. I'm just throwing ideas around.
      - nknighthb 13y ago
        The server must have access to both the salt and the hash to verify a password. Therefore, upon compromise of the server, the attacker automatically has access to both the salt and the hash. There is no way around this problem that isn't simply obfuscation.
  - deleted 13y ago
    [deleted]
  - lambda 13y ago
    A salt is not for adding extra secrecy. It's for making it take more work to solve a large number of passwords at once. It doesn't need to be stored separately to do this. What you're thinking of is a secret-splitting scheme; where you split a secret among multiple parties, where you need the information from both parties to reconstruct the secret. That's a valid cryptographic technique, but that's not what's meant when you say "salted password". The problem is, for passwords, that approach isn't really workable. Whatever machine is verifying the passwords will need access to the full hash to do so, so if it's compromised, you could get access to the full hash. I suppose you could split the verification into two parts, on two separate machines. Each one would have it's own password database, with independent salts, and the machine trying to authenticate the user would request verification from each of the other machines before allowing you in. However, that would make your password system slower and more fragile; now if either of those machines goes offline, your login functionality breaks (and yes, you could do a "two out of three" system to avoid that, but now you're talking about tripling your hardware requirements just for your password verification system). Really the best bang for your buck will come from (a) securing your system so that it doesn't reveal your password database in the first place and (b) using bcrypt, scrypt, or PBKDF2 to make brute forcing a database that is disclosed much more difficult. It's far more likely that you will build a secure system by following basic security practices like isolating services and giving each the minimum privilege that it needs, doing code review, keeping inessential services off of important machines, using prepared statements rather than building SQL queries from user-supplied strings, and so on, as well as using off-the-shelf security components that have been well tested like the above hash algorithms, than you will by designing your own password system using some novel technique to spread the secret out among multiple machines.
    - PwdRsch 13y ago
      There actually has been research on how to split passwords across multiple servers (one example http://www.passwordresearch.com/papers/paper270.html http://www.passwordresearch.com/papers/paper270.html), and RSA is currently marketing a commercial product that does this. While I agree that most people probably aren't concerned enough about password exposure to do this, there are effective solutions to accommodate those that are.
markdown 13y ago
Right there in the same field as the password: <salt>::<hashed_password> The pepper on the other hand shouldn't be in the db. Hardcode that into a config file.
- eropple 13y ago
  "Pepper"s are essentially meaningless and provide no real benefit over a salt. And you should be using bcrypt anyway.
  - markdown 13y ago
    > "Pepper"s are essentially meaningless and provide no real benefit over a salt. Citation needed. There appears to be a case where it could prove to be an advantage: http://security.stackexchange.com/questions/3272/password-hashing-add-salt-pepper-or-is-salt-enough http://security.stackexchange.com/questions/3272/password-ha... > And you should be using bcrypt anyway. Yeah, except bcrypt isn't always an option. Eg: on Google App Engine.
    - deleted 13y ago
      [deleted]
    - eropple 13y ago
      Yeah, that's why I said "essentially" instead of "totally". Writing your own MAC is not a good idea, pretty much full-stop. tptacek has talked about this[1] before. In the sort of environment that necessitates stupid hashing, if your database is owned your app is owned anyway. If bcrypt isn't an option, you straight-up need a better platform. It's inexcusable to refuse to protect your users--if you're not using bcrypt/scrypt/PKBDF2 you're mistreating your users. [1] - https://news.ycombinator.com/item?id=5663818 https://news.ycombinator.com/item?id=5663818
      - danielweber 13y ago
        I know at least one major security company (that deals with Fortune 500 companies) is recommending having an extra key inside the app server, distinct from the database, since there are situations where someone can get the a copy of the DB and not your server. The fact that they're big doesn't mean they're right, of course. But I know I've seen a bunch of news stories about DB leaking and I haven't seem a bunch about the source code to the website leaking. (Obviously there is some confirmation bias there.)
theboss 13y ago
Salting would definitely make a difference. The point of salting is to increase the complexity and overhead of generating rainbow tables. The first mistake here is the use of MD5. MD5 is flat out broken. Do Not use md5. Do use bcrypt. In your db, you can store the salt right there....next to the hash... How a salt increases the complexity is quite simple. If a attack has a giant rainbow table, the salt causes him to increase the size of his rainbow table and the space required to hold it and the pre-processing time to generate it. For example Here is what your database might look like with a 3 byte salt password : salt hunter2 : 100 qwerty1 : 101 Here is what the attacks rainbow tables will have to look like qwerty1 : 101 hunter2 : 100 qwerty1 : 100 hunter2 : 101 hunter2 : 103 qwerty1 : 102 ... .. . That's about it. There are other purposes of the salt too but other people talked about those ones.
- smcl 13y ago
  If anyone doesn't get the "hunter2" reference: http://www.bash.org/?244321 http://www.bash.org/?244321

lbarrow 13y ago

The article clearly explained that using more salts was preferable to using a global salt and did a good job of explaining why. They didn't come out and say that a per-user salt is best, but that's the natural conclusion of the argument they developed.

tomku 13y ago
Maybe we read different articles, but the one I read seemed intent on strongly downplaying the amount of extra security that salting provides. It actually uses the phrase "minimal amount of protection" to describe a salt's effect on cracking attempts. That seems like a strange choice of words when salting would've completely changed the outcome of the cracking attempts described in the article. Edit: To be clear, I'm aware that salting doesn't protect against targeted attacks, but the attacks discussed in the article weren't targeted. One of the major reasons[1] they were able to crack 16,000 passwords in a few hours was due to the lack of salting. [1]: The other being the choice of MD5 rather than bcrypt/scrypt/PBKDF2/etc, naturally.
- reeses 13y ago
  Salting wouldn't have changed the outcome of the cracking attempts in the article. The primary focus was on how pre-computed hashes (rainbow tables, etc.) are no longer a tool used by most people attacking password lists because GPU-based hashers are efficient enough, the dicts long enough, and the methods of permuting the dicts (combinations, leet substitutions, markov chains, etc.) are rich enough that storing all possible hashes is actually less effective than writing an MD5 kernel for your AMD GPU and letting it go, monitoring for trends in the output.
  - claudius 13y ago
    But with a per-user salt, they would have to attack each password individually, using each of these techniques with each given salt and hope for a coincidence with the stored hash, rather than run their techniques and compare the resulting hashes to the stored ones? Something like: Global hash: while(s = guess()) { if (md5(s,salt) in list) { print s; delete(md5(s,salt),list); } } Unique hash: while(s = guess()) { foreach(h in list) { if (md5(s,salt)==h) { print s; delete(h,list); } } } The former requires one md5 calculation and one lookup per guess, the latter needs n md5 calculations per guess. That certainly is quite a difference, assuming the bottleneck to be md5.

iuguy 13y ago

I'm in the middle of researching re-evaluating rainbow table attacks in light of Moore's law, GPUs and Crack (lookup) tables, I've also looked into countermeasures. What you're describing is partially correct. When you crack passwords (either with rainbow tables or by brute force) you generate an iterator or use a dictionary and work through this generating hashes (with rainbow tables this works via a series (or chain) of what are called hash reduction functions instead of a plain iterator). You then compare the hash you've generated against all the hashes being subjected to the crack. Where there's a match, you win! If you're targeting a single hash and it's unsalted, rainbow tables will work as they're precomputed. It's inefficient, but it'll work. If you're using a salt, rainbow tables need to be pre-computed for the salt - I actually did this years back with a team for oracle 10g SYS and other default user passwords as the username was used as the salt. If you're targeting a single hash and it's salted then the iterative or dictionary approach will still work in roughly the same time as the salt is known. Separating the salt means you have to brute force it which is a PITA but generally because the way hashes tend to be stored (remember we're talking about a mechanism that shouldn't really be used anyway) the salt needs to be accessible by that system so you can dump the salt out regardless. Depending on where my current research goes it looks like some salting mechanisms may be feasibly pre-computable now beyond those that use predictable salts. GPUs allow you to create and traverse enormous chains in rainbow tables and while having to precompute per salt will be a PITA it looks like it is possible with sufficient storage and GPU power.

csense 13y ago
What if a site uses 128-bit salts generated by a good (perhaps hardware-based) RNG?
- mikegioia 13y ago
  That will remove pre-computed rainbow tables from the equation.
  - iuguy 13y ago
    Only really for the time being (and a considerable time to come, Quantum and Biological computing enhancements notwithstanding) but for a salt that big it makes far much more sense to use a key derivation function as you're effectively generating two keys otherwise (one user generated, the other - salt - via PRNG).