11 ms·

A New, Simple Way to Salt your Hashes

22 points by pyroman 18y ago

sh1mmer 18y ago
To repeat the comment I made on the site: The problem with this is you have created a pattern which could (and probably does) introduce a cryptographic weakness. If someone knew or could guess you were using this tactic then they might be able to exploit it. While I don’t have an example of a specific weakness to MD5 to hand one of the basic rules of exploiting algorithms is knowing some of the source material or knowing about patterns within it. The point of using a salt is to use a piece of unknown material which is unique in each string. It’s common to generate random junk to use rather than anything meaningful. Personally I always take "new insight" into security tactics with a pinch of salt until they have been hammered on by a few people.
cperciva 18y ago
Don't do this. This is no better than using a single fixed salt for an entire site: An attacker who has access to your password file can iterate through possible passwords and for each password perform one computation to check if that password matches any of your users. The whole point of salting is to reduce an attacker to checking one possible user/password pair at once. You don't get this benefit if you use the method described in this article. The only attacker I can see this defending against is an attacker who has a precomputed table of password MD5s and doesn't have (hasn't bothered to create) a precomputed table of password-repeated-twice MD5s. So technically the method described is slightly more secure than simply storing (user, MD5(password)) pairs, since it avoids the "google to reverse MD5 hashes" pseudo-attack. But if you're going that low, you're pretty much lost already. Don't do this.
- tptacek 18y ago
  ... and, I assume you'd agree, if your password storage mechanism involves a single ultra-fast SHA1 or MD5 hash, salts are deck chairs on the Titanic anyways.
  - brlewis 18y ago
    Doesn't having a hash function that takes, say, 100x as long to compute as md5, only increase the cracking time by a factor of 100? Is that all there is to it?
    - cperciva 18y ago
      Is that all there is to it? Yes, but typically password hashes are constructed to be 1000x slower or more. A common construction is to iterate the hash, e.g., to store MD5(MD5(MD5(...(MD5(salt || password)...))) -- this allows you to trade password verification performance against password cracking time however you like, just by varying the number of times you iterate the hash.
    - Xichekolas 18y ago
      Well take the case of bcrypt and md5. Assuming bcrypt takes about 300 times as long^ as md5, then that would be the difference between cracking a password in a day versus a year. You'd need someone very patient to wait a whole year for your reddit password. And if you change your password every 6-12 months anyway, they are most likely screwed. ^ I picked 300 out of a hat, I think that bcrypt is usually 2-3 orders of magnitude slower, but no reason you can't recursively apply it to stretch it out even further.
      - tptacek 18y ago
        The time it takes bcrypt to verify one password is a tunable parameter; that's the fundamental feature of the algorithm. If you want a password check to take one full second, you can do that. A dictionary attack against one six-character password on that system, even offline against a captured hash, would take years.
  - cperciva 18y ago
    Now you're making things complicated. :-) You're absolutely right that a slow password hash should be used -- I left that part out because I wanted to make the non-saltiness of the "salt" clear without confusing people by talking about all the other things that they could do wrong.
- prakash 18y ago
  I don't say this enough, this is why I love this forum!! Thanks, Colin!
mrtron 18y ago
This for some reason struck me as a Homer Simpson moment - where he suggests every car come with one of those ribbons on the antenna so you can find it easier!
- rbanffy 18y ago
  That's really a great analogy.
sysop073 18y ago
I've seen the misconception that a salt is a fixed string before, I don't know where people get that from. You don't pick a salt and use it site-wide, you pick a different salt for each thing you're encrypting, so the standard salting mechanism is more secure than this
- stcredzero 18y ago
  Early on, people used fixed string salts. Some people learned and advanced.
  - brlewis 18y ago
    Can you cite this? I think you're making it up. It makes no sense for people early on to have misunderstood salts so badly. That kind of misunderstanding takes years to develop.
    - stcredzero 18y ago
      I am mistaken. (Faulty memory.) The early Unix salts were random, though they were only two characters.
t0pj 18y ago
I use a unique random salt when hashing passwords in a db. This is combined with another salt I keep in my codebase. If the data in the db gets out, they still do not have salt stored in my codebase (unless the entire server has been compromised). Right or wrong? Any thoughts?
- pyroman 18y ago
  Definitely better than what I was suggesting on the site.
- stcredzero 18y ago
  So the unique salt has to be transmitted from the server to the client in order to do authentication? Why not just use a hash of the username?
  - apgwoz 18y ago
    why would you need to transmit the unique salt? why would you transmit anything other than the form to the client? all the checks would be done on the server side. a) user enters username/password b) server looks up in a file the unique string and appends it to the password c) server finds username's salted-password hash d) server extracts hash from stored salted-password hash (possibly the first 4 characters or whatever) e) server concatenates salt, plaintext password and unique string and hashes via sha-N/md5 f) server compares to stored salted-password and if same performs login. otherwise sends generic "invalid username/password combination" message.
    - t0pj 18y ago
      That's exactly what I'm doing. I think stcredzero is concerned about the plaintext password passing through the pipes. In this case, unique salts and hashes are used to simply protect the database; when the data is stolen, a rainbow attack will not effectively work. Hashing those passwords also protects the user who uses the same email/id/password everywhere; if your db is compromised, you don't also compromise the user's identity (e-mail accounts, banking, etc). It depends on the app, but I also think sending salts to the client and doing some md5/javascript in the browser is generally overkill.
stcredzero 18y ago
Thought exercise: Then why not salt your hashes using some kind of lookup table on the password? With a bigger lookup table, you have a better chance of having a unique salt for most of your users. In fact, the bigger the table the better. But that takes up space, so why not use a function? But what kind of function? It should be cryptographically secure. Wait, I know, a hash function would be perfect! Basically, this is just adding another gimpy home-grown round to your hash function. It will make the attacker's job slightly harder, but as others have pointed out, you can still match any password from the file. I conclude that the best thing to do is to use a hash of the username as the password's salt.
- Jem 18y ago
  OK, I don't know that much about cryptography and salting (I let users of my scripts set a long 'pass-phrase' which gets used as the salt), but surely using a hash of the username would be no better than the method discussed in the post? Given that usernames are public - you know, for instance, that mine is jem - what level of security would that provide?
  - modoc 18y ago
    Using a known salt isn't great, but it still makes extracting the password orders of magnitude more difficult. Hashed passwords are typically attacked using a rainbow file. Basically you use a dictionary file to hash words from the dictionary file and store the plaintext word and the resulting hash together in a file/db/whatever. After you've hashed every word in the dictionary, you start doing combinations: wordword, wordnumber, wordnumberword, etc... Of course each time your add another element, you're exponentially increasing the time it takes to generate your rainbow file. Using a multi-character hash is basically adding another element to the password on behalf of the end user. Basically if we say it takes 100 hours (totally made up number, I suspect it's much higher-depending on password rules) to generate a comprehensive enough rainbow file to find an average password, if you add a 1 character alpha numeric salt, it now takes 3,600 hours to find that password. If you add 2 characters, it now takes 129,600 hours. And so on. Using a public username (and having your attackers know that's what you're using) means that you have to generate a full rainbow file for EACH user. So while it's not as good as a decent sized random salt, you can no longer take 100 hours of work and hope to extract 8,000 passwords from a site's password db/file. You have to do 100 hours of work PER user, and still have a 30-50% success rate. So to get the same 8,000 passwords you'd need to do 1,600,000 hours of work (assuming a 50% hit rate). So assuming you personally are not a specific target, the site itself is numberOfUsers* more time consuming to extract X passwords from, than a site that just uses MD5 with no salt.
tptacek 18y ago
Can anyone take a stab at explaining the fetish webdevs have for password salt schemes? I don't get it. Colin will probably agree with me: people who build authentication systems don't spend a lot of time thinking about salts. Of course, most of them wouldn't waste their time redesigning a password storage system; they'd use Mazieres/Provos "bcrypt" and be done with it. If an article like this makes even a couple of neurons in your head light up, you have better things to do than reinvent the password storage wheel. Use somebody else's good system. This is almost security 101.
- Xichekolas 18y ago
  For all you ruby/rails nuts out there, ruby already has a good gem that makes using bcrypt easy: http://bcrypt-ruby.rubyforge.org/ http://bcrypt-ruby.rubyforge.org/ It even handles the salting for you, so you don't have to think about it.
- ajross 18y ago
  Probably because salting is one of the easier crypto ideas to grok and one of the safer ones to get wrong? Salting is just a constant factor optimization (assuming password length is bounded and short). It's designed to remove the opportunity to do a dictionary lookup and force the attacker to actually compute the password hash. But it doesn't change the algorithmic time of the attack at all. So it's "safe" to pontificate about. At worst, you're going to make an attack available only to a person with a botted cluster of machines accessible to a single guy with a laptop. Meh.
- cperciva 18y ago
  Colin will probably agree with me: people who build authentication systems don't spend a lot of time thinking about salts. I agree, in the sense that people don't spend a lot of time thinking about breathing. We just do it. Grab 256 bits from /dev/random (or from your internal entropy pool, if you have one) and stick a salt or nonce onto password you hash and every protocol packet you send. Of course, most of them wouldn't waste their time redesigning a password storage system; they'd use Mazieres/Provos "bcrypt" and be done with it. For a straight-forward "users logging into a website", absolutely. But most people who design authentication systems have more stringent requirements, like "allow users to authenticate themselves in such a way that a bogus server can't steal their credentials", at which point things get a bit more interesting. :-)
jmtame 18y ago
Here's what I do: $password = hash_hmac(sha256,$_POST['password'],"pound_on_your_keyboard_here"); 256 bits of hashed goodness. Goodluck breaking that with a rainbow table.
jdavid 18y ago
a real attack might be like this find rainbow table with a char space of abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQURSTUVWXYZ0123456789!@#$%^&*()_+=-';:"` you now have a working hash map of 27-80gb of data. upon looking through the user/pass table you see that the user/pass table has a salt key for each record. at this point you know that some portion of the passwords will be reversible with the salt being a confirmation of finding the correct password. i know some of the rainbow tables out there are really fast at looking up a reverse md5 or sha1. pass look up in rainbow table you will at least find a collision, and if you are lucky, you will find the pass concatenated to the salt entry in the table. so if a hacker has your user/pass table, yikes.... ;-/ you are better off restricting read/write privileges to separate services. i would hate for a hacker to connect to your DB and to write their own salt and pass. we were working on this for one of the defcon games last year. NEVER REPLACE OBFUSCATION FOR REAL SECURITY. fighting rainbow tables requires larger hash functions that generate larger hashspaces that are less likely to fit on a single machine. i still wonder how long it will take for a proper cluster of GPUs to virtualize the hash space of a rainbow table into computational power.
ericwaller 18y ago
While on the topic of password best practices, are there any characters which should not be allowed in passwords? I've always assumed anything is safe since it's getting hashed anyway before hitting the db, but this got me wondering.

22 points by pyroman 18y ago

To repeat the comment I made on the site: The problem with this is you have created a pattern which could (and probably does) introduce a cryptographic weakness. If someone knew or could guess you were using this tactic then they might be able to exploit it. While I don’t have an example of a specific weakness to MD5 to hand one of the basic rules of exploiting algorithms is knowing some of the source material or knowing about patterns within it. The point of using a salt is to use a piece of unknown material which is unique in each string. It’s common to generate random junk to use rather than anything meaningful. Personally I always take "new insight" into security tactics with a pinch of salt until they have been hammered on by a few people.

cperciva 18y ago

Don't do this. This is no better than using a single fixed salt for an entire site: An attacker who has access to your password file can iterate through possible passwords and for each password perform one computation to check if that password matches any of your users. The whole point of salting is to reduce an attacker to checking one possible user/password pair at once. You don't get this benefit if you use the method described in this article. The only attacker I can see this defending against is an attacker who has a precomputed table of password MD5s and doesn't have (hasn't bothered to create) a precomputed table of password-repeated-twice MD5s. So technically the method described is slightly more secure than simply storing (user, MD5(password)) pairs, since it avoids the "google to reverse MD5 hashes" pseudo-attack. But if you're going that low, you're pretty much lost already. Don't do this.

tptacek 18y ago
... and, I assume you'd agree, if your password storage mechanism involves a single ultra-fast SHA1 or MD5 hash, salts are deck chairs on the Titanic anyways.
- brlewis 18y ago
  Doesn't having a hash function that takes, say, 100x as long to compute as md5, only increase the cracking time by a factor of 100? Is that all there is to it?
  - cperciva 18y ago
    Is that all there is to it? Yes, but typically password hashes are constructed to be 1000x slower or more. A common construction is to iterate the hash, e.g., to store MD5(MD5(MD5(...(MD5(salt || password)...))) -- this allows you to trade password verification performance against password cracking time however you like, just by varying the number of times you iterate the hash.
  - Xichekolas 18y ago
    Well take the case of bcrypt and md5. Assuming bcrypt takes about 300 times as long^ as md5, then that would be the difference between cracking a password in a day versus a year. You'd need someone very patient to wait a whole year for your reddit password. And if you change your password every 6-12 months anyway, they are most likely screwed. ^ I picked 300 out of a hat, I think that bcrypt is usually 2-3 orders of magnitude slower, but no reason you can't recursively apply it to stretch it out even further.
    - tptacek 18y ago
      The time it takes bcrypt to verify one password is a tunable parameter; that's the fundamental feature of the algorithm. If you want a password check to take one full second, you can do that. A dictionary attack against one six-character password on that system, even offline against a captured hash, would take years.
- cperciva 18y ago
  Now you're making things complicated. :-) You're absolutely right that a slow password hash should be used -- I left that part out because I wanted to make the non-saltiness of the "salt" clear without confusing people by talking about all the other things that they could do wrong.
prakash 18y ago
I don't say this enough, this is why I love this forum!! Thanks, Colin!

mrtron 18y ago

This for some reason struck me as a Homer Simpson moment - where he suggests every car come with one of those ribbons on the antenna so you can find it easier!

rbanffy 18y ago
That's really a great analogy.

sysop073 18y ago

I've seen the misconception that a salt is a fixed string before, I don't know where people get that from. You don't pick a salt and use it site-wide, you pick a different salt for each thing you're encrypting, so the standard salting mechanism is more secure than this

stcredzero 18y ago
Early on, people used fixed string salts. Some people learned and advanced.
- brlewis 18y ago
  Can you cite this? I think you're making it up. It makes no sense for people early on to have misunderstood salts so badly. That kind of misunderstanding takes years to develop.
  - stcredzero 18y ago
    I am mistaken. (Faulty memory.) The early Unix salts were random, though they were only two characters.

t0pj 18y ago

I use a unique random salt when hashing passwords in a db. This is combined with another salt I keep in my codebase. If the data in the db gets out, they still do not have salt stored in my codebase (unless the entire server has been compromised). Right or wrong? Any thoughts?

pyroman 18y ago
Definitely better than what I was suggesting on the site.
stcredzero 18y ago
So the unique salt has to be transmitted from the server to the client in order to do authentication? Why not just use a hash of the username?
- apgwoz 18y ago
  why would you need to transmit the unique salt? why would you transmit anything other than the form to the client? all the checks would be done on the server side. a) user enters username/password b) server looks up in a file the unique string and appends it to the password c) server finds username's salted-password hash d) server extracts hash from stored salted-password hash (possibly the first 4 characters or whatever) e) server concatenates salt, plaintext password and unique string and hashes via sha-N/md5 f) server compares to stored salted-password and if same performs login. otherwise sends generic "invalid username/password combination" message.
  - t0pj 18y ago
    That's exactly what I'm doing. I think stcredzero is concerned about the plaintext password passing through the pipes. In this case, unique salts and hashes are used to simply protect the database; when the data is stolen, a rainbow attack will not effectively work. Hashing those passwords also protects the user who uses the same email/id/password everywhere; if your db is compromised, you don't also compromise the user's identity (e-mail accounts, banking, etc). It depends on the app, but I also think sending salts to the client and doing some md5/javascript in the browser is generally overkill.

stcredzero 18y ago

Thought exercise: Then why not salt your hashes using some kind of lookup table on the password? With a bigger lookup table, you have a better chance of having a unique salt for most of your users. In fact, the bigger the table the better. But that takes up space, so why not use a function? But what kind of function? It should be cryptographically secure. Wait, I know, a hash function would be perfect! Basically, this is just adding another gimpy home-grown round to your hash function. It will make the attacker's job slightly harder, but as others have pointed out, you can still match any password from the file. I conclude that the best thing to do is to use a hash of the username as the password's salt.

Jem 18y ago
OK, I don't know that much about cryptography and salting (I let users of my scripts set a long 'pass-phrase' which gets used as the salt), but surely using a hash of the username would be no better than the method discussed in the post? Given that usernames are public - you know, for instance, that mine is jem - what level of security would that provide?
- modoc 18y ago
  Using a known salt isn't great, but it still makes extracting the password orders of magnitude more difficult. Hashed passwords are typically attacked using a rainbow file. Basically you use a dictionary file to hash words from the dictionary file and store the plaintext word and the resulting hash together in a file/db/whatever. After you've hashed every word in the dictionary, you start doing combinations: wordword, wordnumber, wordnumberword, etc... Of course each time your add another element, you're exponentially increasing the time it takes to generate your rainbow file. Using a multi-character hash is basically adding another element to the password on behalf of the end user. Basically if we say it takes 100 hours (totally made up number, I suspect it's much higher-depending on password rules) to generate a comprehensive enough rainbow file to find an average password, if you add a 1 character alpha numeric salt, it now takes 3,600 hours to find that password. If you add 2 characters, it now takes 129,600 hours. And so on. Using a public username (and having your attackers know that's what you're using) means that you have to generate a full rainbow file for EACH user. So while it's not as good as a decent sized random salt, you can no longer take 100 hours of work and hope to extract 8,000 passwords from a site's password db/file. You have to do 100 hours of work PER user, and still have a 30-50% success rate. So to get the same 8,000 passwords you'd need to do 1,600,000 hours of work (assuming a 50% hit rate). So assuming you personally are not a specific target, the site itself is numberOfUsers* more time consuming to extract X passwords from, than a site that just uses MD5 with no salt.

tptacek 18y ago

Can anyone take a stab at explaining the fetish webdevs have for password salt schemes? I don't get it. Colin will probably agree with me: people who build authentication systems don't spend a lot of time thinking about salts. Of course, most of them wouldn't waste their time redesigning a password storage system; they'd use Mazieres/Provos "bcrypt" and be done with it. If an article like this makes even a couple of neurons in your head light up, you have better things to do than reinvent the password storage wheel. Use somebody else's good system. This is almost security 101.

Xichekolas 18y ago
For all you ruby/rails nuts out there, ruby already has a good gem that makes using bcrypt easy: http://bcrypt-ruby.rubyforge.org/ http://bcrypt-ruby.rubyforge.org/ It even handles the salting for you, so you don't have to think about it.
ajross 18y ago
Probably because salting is one of the easier crypto ideas to grok and one of the safer ones to get wrong? Salting is just a constant factor optimization (assuming password length is bounded and short). It's designed to remove the opportunity to do a dictionary lookup and force the attacker to actually compute the password hash. But it doesn't change the algorithmic time of the attack at all. So it's "safe" to pontificate about. At worst, you're going to make an attack available only to a person with a botted cluster of machines accessible to a single guy with a laptop. Meh.
cperciva 18y ago
Colin will probably agree with me: people who build authentication systems don't spend a lot of time thinking about salts. I agree, in the sense that people don't spend a lot of time thinking about breathing. We just do it. Grab 256 bits from /dev/random (or from your internal entropy pool, if you have one) and stick a salt or nonce onto password you hash and every protocol packet you send. Of course, most of them wouldn't waste their time redesigning a password storage system; they'd use Mazieres/Provos "bcrypt" and be done with it. For a straight-forward "users logging into a website", absolutely. But most people who design authentication systems have more stringent requirements, like "allow users to authenticate themselves in such a way that a bogus server can't steal their credentials", at which point things get a bit more interesting. :-)

jmtame 18y ago

Here's what I do: $password = hash_hmac(sha256,$_POST['password'],"pound_on_your_keyboard_here"); 256 bits of hashed goodness. Goodluck breaking that with a rainbow table.

jdavid 18y ago

a real attack might be like this find rainbow table with a char space of abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQURSTUVWXYZ0123456789!@#$%^&*()_+=-';:"` you now have a working hash map of 27-80gb of data. upon looking through the user/pass table you see that the user/pass table has a salt key for each record. at this point you know that some portion of the passwords will be reversible with the salt being a confirmation of finding the correct password. i know some of the rainbow tables out there are really fast at looking up a reverse md5 or sha1. pass look up in rainbow table you will at least find a collision, and if you are lucky, you will find the pass concatenated to the salt entry in the table. so if a hacker has your user/pass table, yikes.... ;-/ you are better off restricting read/write privileges to separate services. i would hate for a hacker to connect to your DB and to write their own salt and pass. we were working on this for one of the defcon games last year. NEVER REPLACE OBFUSCATION FOR REAL SECURITY. fighting rainbow tables requires larger hash functions that generate larger hashspaces that are less likely to fit on a single machine. i still wonder how long it will take for a proper cluster of GPUs to virtualize the hash space of a rainbow table into computational power.

ericwaller 18y ago

While on the topic of password best practices, are there any characters which should not be allowed in passwords? I've always assumed anything is safe since it's getting hashed anyway before hitting the db, but this got me wondering.