salt usage for hashed password storage - design consideration

Question

This is part of my academic assignment and hence to ensure no one feels i'm asking for the answer. I've given my opinion.

Hashing is mathematical one way function that takes arbitrary length data and converts it to a fixed length output. Important thing is exactly similar text (data) when hashed with same algorithm (MD or SHA or any other) will always give same output. This brings an important challenge when storing sensitive data using hashing such as passwords - because same passwords when hashed and stored using same algorithm will generate same hash. Hence salting is recommended to counter “rainbow tables” which is the brute force for hashing.

There is one more attack to keep in mind which is the birthday paradox but because we’re referring to password / passphrase as compared to a lengthy data-set / document hence birthday paradox is out of the question and so are collisions (questions assumes a strong hashing algorithm).

Here is the question:

You are asked to implement the password storage for a system in which users are authenticated using password logins. You have to implement the storage without using a random number generator, and therefore cannot implement exactly the same salted storage as described in the lectures. There are at least three alternative ways to implement the table:

1. Method S1: use the constant “SA” as the salt for each entry in the table.

• Constant salt is the weak link. One may argue that length of the salt is also a security weakness. But the fact that SALT is constant throughout the table.
• It will lead to frequency analysis – password: 123456 with salt SA will always give same output across the table.
• So I wouldn’t use it.

2. Method S2: for each entry, use the hash of the first two characters of the password as the salt.

password: 123456 will be hashed as hash (salt(password)) = hash(12(123456))

• This is more secure from the perspective that SALT isn't constant. (as option 1)

• However, password: 123456 with salt (12) as per the rule, will lead to same hash.

• This will lead to frequency analysis as similar passwords in the DB will always be stored as same hash.

3. Method S3: use the number 0 as the salt for the first entry, and define the salt of each other entry as the hash of the previous entry.

Thus, the salt is 0 for the first entry, hash(0) for the second entry, hash(hash(0)) for the third entry, etc.

• This is what I assess to be same as block cipher in CBC mode.

• On the looks of it 0 may seem as a weak "SALT" but it acts as an IV here.

• Similar passwords will never be as similar hashes. Hence frequency analysis is difficult.

• It also makes it difficult to rainbow table (brute force) an entry individually and you will need entire table to get the plaintext as opposed to other designs wherein once you know the logic you can get plaintext passwords in the table.

  - I would use this design. As question expects me to design security and not integrity of the data. CDC is prone to integrity failure as if one entry gets corrupt all subsequent entries will be corrupt.

Kindly give me your thoughts.

Answer 1

The main purpose of a Salt is for identical passwords to be hashed differently. Options 1 and 2 fail at this, they modify the hash function slightly but in the end do not add a Salt in any meaningful sense. Rainbow tables still work, naive identification of identical passwords work, brute forcing all password simultaneously work.

Options 1 and 2 add no security over unsalted passwords, except perhaps a negligible slowdown in hash computation.

Option 3 provides real security, it prevents all 3 attack methods I mentioned earlier. If the Salt is saved with the password it would not be fragile, and corruption won't propagate. Nor would deleting an entry be an issue.

Essentially the basic premise of the problem lacking a random number generator is problematic when you have both storage and hash. If you have a hash function, building a good PRNG is trivial. An external entropy source is nice, but hardly required, even hashing the numbers 1,2,3,... would be reasonable for the purpose of producing salts(far better than options 1 or 2) despite predictability.

Clearly option 3.

Answer 2

This outgrew a comment.

In most password storage schemes (almost certainly the one from the lecture), the salt is stored along the hash and assumed available to an adversary trying to find password. Without this standard hypothesis, verifying a password in S3 would be cumbersome. It is thus reasonable to assume that the salt defined by S1, S2 and S3 is stored in clear along the password, contrary to what appears to be assumed.

Assuming salt is stored along the hash, the analysis that S2 is more secure than S1 would be seriously wrong.

Independently, the justification that in S3, identical passwords will never have identical hashes is incorrect, and that does not hold with certainty. Two different kinds of collisions could cause that identical passwords have identical hash, and the best we can do is justify that both are unlikely.

Also, it is not immediately clear why it matters that identical passwords will never have identical hashes; that should be explained, or reformulated.

For all three methods, a quantitative assessment of the work required to find a password would be nice, preferably with separation between finding a password for a certain account, or finding a password for any account (multi-target attack).

Answer 3

this is not the answer but I need space to reply

Thank you very much for your reply - fgrieu.

I have few questions to your response.

I'm using the premise that the algorithm is good or that I'm not concerned with how good the algorithm is. Let's suppose it's SHA-512 for which we're not aware of algorithmic weaknesses or known collisions. In this case too. The salt will remain static in S1 and relatively static in S2 from the perspective that not every user will have unique password. Yes, one may argue that every user in this instance has an unique password and that would eliminate the frequency attack BUT it will still be less secure from S3 because it is a much smaller entropy as compared to S3 wherin you're using hash (in our case 512 bit with output of 128 characters) as entropy for hashing which WILL give way less probablity of collision then a 2 character (even will full characterspace of numbers (9), alphabets (52) and symbols (20?) will equate to

For S2 - 2^81 vs for S3 - 128^61

Would you agree that this is a good measure for the quantitative computation you've referred to? (Asked to calculate)

I also feel we shouldn't be concerned with ALL the or targeted entries but computation for any random entry. As they haven't mentioned number of passwords in the DB but it's important to take into account real world scenraio where not everyone has a complex unique password as a possibility for our storage solution.

I also feel it's easier to find collisions for S1 and S2 as compared to S3 given the entropy / salt uniqueness given by hashing in S3 (avalanche efffect) as compared to static and almost static in S1 and S2 respectively.

Once again, thank you very much for your response.

Answer 4

As mentioned S1 and S2 are no good.

Your S3 implies you are not storing the salt with the password hash, but it should be. It also requires previous entries be in the database, if all prior users are deleted, the is nothing to generate from. This method is also predictable, if another user was to be added, an attacker could start working on cracking their hash with only the prior salt. In fact, he could start attacking ALL future users, just with additional computation.

Your salt needs to be unpredictable.

You can encrypt (AES with a fixed key) an incrementing counter, this would give you a 128-bit unpredictable salt without the need for an RNG. It would also make the first salt entry secure. As long as the fixed key is never disclosed (hardware security module?), future outputs will remain unpredictable. You only need to store the counter, and possibly the key (securely, outside of DB).

You can also use a hash of the username as a salt, it is not ideal, but if usernames are unique, salts should be unique. If they are generated in this way, the system should use an additional random fixed salt, prepended to all generated salts, so there is no chance a similar system would generate the same hash from a user/password combination. This is predictable enough that a specific future username can be targeted.

A better option would be to combine methods, such as:

1. Generate salt using counter, hash salted username
   $S = E_k(Ctr)$
   $S = H(S:U)$

2. Generate salt using counter, encrypt with salted hash of username
   $S = E_k(Ctr)$
   $S = E_{H(S:U)}(S)$

3. Generate salt using counter, XOR with truncated salted hash of username
   $S = E_k(Ctr)$
   $S = H(S:U)_{128} \oplus S$

None of those methods are directly reversible unless you have both the counter and the key, and even if you did, the addition of the username makes it less predictable. Keeping the key secure keeps all future salts secure and unpredictable.