OS login password: How does it work?

Question

I am making an application to create a password for a user. I am a bit baffled over how it all works though. Namely I want to be sure that my application will store the correct hash so the user can actually login!

I found this code:

pwhash=$(echo $password | mkpasswd -s -m sha-512)

Now if I run the same password I get two totally different hashes:

$ echo 'test' | mkpasswd -s -m sha-512
$6$QRsW.mu9wC$CSvMrGkfU6.lu14.sNRrZ8Kiyi0zUdlcAH1VBBd.LoTZDmehuoGnsaywm/WD.9GARwINQnp3jJzxQHWlCk3RI0
$ echo 'test' | mkpasswd -s -m sha-512
$6$rN7ishjxd89AjMS$HpN53OoL3m81rPyrKFgpm2Nm2YWJ96nP4gNLu4GO0Jjy9K6lVhB6v7c0L7/998h74oTMGFzLK6w4zku7U3soW0

So this to me shows just how little I know. If the same password generates two different hashes, how can the OS know that I entered the right password in the login screen? What will it compare the entered password hash with?

Also a bit about salt.. the salt is supposed to always be different, so how can the OS know what salt to use for the password at every login attempt?

Answer 1

You get different values because different salts are used. The salt is the second field in the hashed password.

There exist large rainbow tables that make the lookup of hashes of common passwords very cheap. The point of salt is to dramatically increase the cost of precalculating hashes for all commonly used passwords. So salt basically makes a password uncommon. That is, it makes a password so long and random that it is unfeasible to precalculate the hash for all common passwords for all possible salts.

Given that the goal of salt is to prevent successful precalculation attacks, it doesn't need to be a secret, it just needs to be long and random. This allows the salt to be stored in clear-text along with each hashed password. This is fortunate as the salt is needed to validate the password when the user authenticates.

An example of a bad implementation of salt would be to use a single byte. In that scenario an attacker could precalculate all hashes for common passwords for the 256 possible salts. That is expensive but not expensive enough. That salt isn't large enough.

Another example of mis-salting is to use the same salt on every password. That allows an attacker to precalculate a single table that contains the hashes of all common passwords for that one salt. This would be expensive but much cheaper than having to create a table for each password. That's why each password hash has its own salt.

Edit: Salting does not reduce the cost of brute-forcing a single password. Salting just forces you to brute-force passwords instead of precomputing their hashes. You protect against brute-forcing by using a slow hash function and calling it many times on successive output of itself. For example, running bcrypt (which is designed to be slow even with a GPU or other specialized hardware) 1024 times. While PHP stores the number of iterations in the password field, on Linux the number of iterations is configured by the PAM 'rounds' option. Several users here say that the default for their Debian Linux install is 1000 iterations for SHA-512.

Of course, no answer about passwords is complete without a reference to this answer, a detailed explanation about the state of the art for password storage.