salt usage for hashed password storage - design consideration 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.
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.