15

If only the password hash is stored and the user inputs the original password, how does the program know that it is correct? I guess it could check all the possible salts but if there are 32bit salts then the program has to check all 2^32 salts (worst case) which seems like it would take a really long time.

Charles
  • 151
  • 1
  • 1
  • 3

3 Answers3

28

The answer is simply; the salt is stored alongside the password hash. A typical database scheme would look like;

uid  | username    | password         | password_salt
-----|-------------|------------------|--------------
0    | alice       | 862a6c81b7f8361b | 71e9c02731

The salt is not a secret. It is there to make certain types of attacks orders of magnitude more difficult.

This answer should contain everything you need to know.

If not, then this answer has even more information on the ins and outs of salting.

Community
  • 1
lynks
  • 10,646
  • 5
  • 29
  • 54
  • To be specific, the salt is there to prevent pre-computation attacks, like rainbow tables. – Polynomial Dec 17 '12 at 07:10
  • 3
    Some hashing algorithms, especially those designed for passwords, like BCrypt, store the salt as an integral part of the hash value, so you don't even need the extra column. – KeithS Dec 17 '12 at 21:16
  • 3
    @Polynomial: to be even more specific, salts prevent cost sharing, when attacking several passwords. Precomputed tables are one kind of cost sharing; salts also work against attacking several passwords in parallel. – Thomas Pornin Dec 28 '12 at 13:41
3

As has been mentioned, the salt is stored alongside the hash. The salt is mainly intended to protect your hashes against rainbow table attacks. In other words, brute force attacks cannot be run ahead of time

Aurand
  • 181
  • 1
  • 3
  • it isn't even limited to just running ahead of time. If this was the case, salt per db would be fine. It is also to prevent attacking the DB as a whole simultaneously. Rather, per record salts require that a separate rainbow table be computed for every record. – AJ Henderson Dec 17 '12 at 13:47
1

As lynks pointed out, the salt is stored with the hash. The point of salts is to make it so that someone can't attack the DB as a whole by looking for a password that matches the hash of any user.

For example, lets say I had the user table for really big website A and they had 100 million users. If they were using a 32 bit hash (which is not at all secure anyway) and every user had a password that resolved to a different hash, then I would only have to try about 43 passwords before I found one that matched some user. If, however, a different salt is used for each, then I have to attack each password individually.

AJ Henderson
  • 41,896
  • 5
  • 63
  • 110
  • 4
    Just thought I should mention the obvious, in case somebody gets the wrong idea: a 32-bit hash is not secure. – Thomas Dec 16 '12 at 23:50
  • @Thomas - updated to clarify that 32 bits isn't secure. You're right that that is probably worth mentioning even if not directly relevant to the question at hand. – AJ Henderson Dec 17 '12 at 13:46