Question

It was stated that the inclusion of the salt in the UNIX password scheme increases the difficulty of guessing. Let’s use a case to explain why it is asserted that the salt increases security although the salt is stored in plaintext in the same entry as the corresponding ciphertext password. Let’s assume that (1) a computing system adopts the traditional UNIX password scheme (password length: up to 8 characters) and (2) the adversary has obtained a password file containing 4000 entries, each using a unique 12-bit salt. (Hint: there are 95 printable ASCII characters.)        

1. In order to crack all the 4000 hashed passwords in the password file on a UNIX system, how many times does the hash routine, i.e., crypt(3), need to run in the worst case?

2. If the salt is NOT used, how many times does the hash routine, i.e., crypt(3), need to run in the worst case in order to crack all the 4000 hashed passwords?       

3. If 24-bit salt is used for this case, does the hash routine need to run more times in the worst case to crack all the 4000 hashed passwords? If so, how many more?  

Answer 1

Instead of using the result of the hash function directly as the result (i.e., one round), the result can be re-hashed several times (i.e., multiple rounds). crypt, by default, uses 5000 rounds. Thus, to test a single password, 5000 hashes instead of 1 hash have to be computed SO, if there are 4000 entries then 4000*5000 encrypt has to run... By intertwining the password and the salt in every round, additional complexity and hence slowdown can be introduced. For instance, hashcat on the build server of the IS&C group can test ≈ 157M salted SHA-512 hashes per second, while it can only test ≈ 16.7K SHA-512 crypt passwords (e.g. from a passwd file), thus having a slowdown factor of ≈ 9400. Alternatively, a pepper achieves a similar result, because the attacker has to compute multiple hashes for each guess. For instance, for an 8 bit pepper, the attacker has to compute 256 (2 8 ) hashes to for each password guess, because she has to try each possible password-pepper combination. A salt does not affect the offline testing performance per se (see also answer to question 3b). Salts prevent the attacker from using pre-computed dictionaries and, hence, to test passwords “live”, i.e., once she knows the salt value for password, she must test all possible password values in combination with this salt. However, the overhead of computing hash(password) vs. hash(salt|password) is negligible (assuming the salt length is reasonable and not in the range of megabytes or more)