Since I released my demo/example modified Challenge-Response Ajax PHP Login System about a month ago (which was based on ideas from Paul Johnston), I’ve been receiving some questions about why salting was not incorporated into the system. In particular, there was a discussion at a Dutch-language forums, which I somewhat understood after Google translation.

Here, I’ll try to address some of these concerns and answer some questions.

Salt of the earth

To understand why salting is used, we must first understand exactly what it is. Just like regular salt, in cryptography, salting is used to alter the “taste” or output of some process.

In the case of password storage, most people would realize that you should never store lists of users’ passwords in plaintext, because if that data is ever compromised, attackers will gain access not only the compromised accounts but could potentially use the passwords to gain access to user accounts on other services/sites. This is because people often reuse the same passwords across multiple account/services.

The easiest way to avoid this is to store the hash of the password. A hash is a one-way function, that is, once you compute the hash of a value, you cannot obtain the original from just the hashed value. Some typical hash functions are MD5 or the more secure family of SHA hash functions.

However, this still doesn’t fully conceal passwords. If an attacker were to obtain the list of hashed passwords, they could try a dictionary-based attack to discover the original inputs. This involves hashing common words to see if they hash to the correct value. Since people often use common words or combinations of such, a dictionary-based attack has the advantage of having far fewer combinations that the attacker needs to try compared to a true brute-force attack.

Adding variability

This problem can be mitigated by salting, which basically amounts to combining the password with additional input before passing it into the hash function. This alters the end output from the hash function so that a dictionary-based attack cannot be used, provided the salt is kept a secret. A comparison example:

Without salting:
hash(A) -> B;

With salting:
hash (A + S) -> C;

In the first example, salting was not used before hashing. Assuming the value ‘A’ is a common word or phrase, an attacker can use a dictionary-attack to determine what the value of ‘A’ was. (I.E. what value hashes to the value of ‘C’)

With salting, things become more difficult. If the attacker does not know the value of the salt (S), they cannot use a dictionary-based attack because the actual input will not be a common word or phrase. Instead, they must try all values in the dictionary with all possible values of the salt. In fact, every bit of the added salt value doubles the number of computations in a dictionary-based attack. The important point to retain here is the salt value must be kept a secret in order to obtain this benefit.

One other benefit of salting is to ensure that two accounts with the same password don’t produce the same hash. This can be accomplished by making different accounts have different salts. The obvious benefit of this is to decrease the information leakage from the hashes, as otherwise, equivalent hashes would infer equivalent passwords.

Salting and the modified Challenge-Response System

With the modified challenge-response system, it isn’t clear to me how salting could be used to improve it. Here’s a quick re-cap of how it works:

Signup:

1. Server sends random1
2. Client sends hex_sha1(hex_hmac_sha1(password, random1))

Login:

1. Server sends random1 and random2
2. Client sends hex_hmac_sha1(password, random1) and hex_sha1(hex_hmac_sha1(password, random2))

To login, the user must present two values: One to verify that they know the password, and the second value, which is used to set the response that must be computed for the next login.

Because the client must compute the next response value, it’s a bit tricky to implement salting in a way that’s beneficial.

One possible method would be to further hash the second value (hex_sha1(hex_hmac_sha1(password, random1))) with a server secret before storing it in the database. This would complicate things should the database be compromised but not the server secret, since a dictionary attack would become much harder with the extra variability of a server secret. In this case, the work flow would look something like this:

Signup

1. Server sends random1
2. Client sends hex_sha1(hex_hmac_sha1(password, random1)) [Let's call this value `hashed_challenge_response` for brevity]
3. Server stores hex_hmac_sha1(server_secret, hashed_challenge_response)

Login:

1. Server sends random1 and random2
2. Client sends hex_hmac_sha1(password, random1) and hex_sha1(hex_hmac_sha1(password, random2))
3. Server computes hex_sha1(hex_hmac_sha1(password, random1)) [Call this `hashed_challenge_response_received`]
4. Server checks if hex_hmac_sha1(server_secret, hashed_challenge_response_received) equals the value previously stored. If so, authentication was successful and a new challenge-response is stored based on the second value received.

Note that this method would not improve the login security anymore, since an attacker who captured the intermediate traffic of a successful login could still conduct an offline dictionary attack, which this challenge-response system is unfortunately susceptible to.

However, the modified system does benefit from the use of the `random1` and `random2` challenge strings, which are stored alongside the response values. Since these are random and different for each user (and for each subsequent login), accounts with the same password will not have the same hash-response. This effectively gives the second lesser benefit of salting.

The modified challenge-response system also suffers from the inability of the server to enforce strong passwords. Because the initial value sent during registration is a hashed value of the password and a random value, the server cannot be aware of any properties of the password such as its length or composition. The only aspect that could be enforced server-side would be to make sure the password was not blank! My suggestion is to (attempt to) enforce password complexity using JavaScript on the client side. Such rules can obviously be circumvented but are better than nothing.

Conclusion

Hopefully I’ve shed some light on the topic of salting in relation to the modified challenge-response Ajax PHP login system. I’m no security expert, so you should not take my advise as scripture. Please don’t hesitate to give me your comments or feedback!