Recent leaks of unsalted password hashes from several sites has spawned a lot of discussion about password security. Experts agree that salting password hashes is a good idea, but there is disagreement about what other measures should be taken.
There is major disagreement about whether hashing should be slowed down. On one hand slowing down the hash function will slow down brute force attacks (including dictionary attacks and rainbow tables). On the other hand slowing down the hash function will slow down legitimate usage by the same factor. A webapplication using a slow hashfunction for password verification is vulnerable to DoS attacks.
A question was raised about whether it was possible to offload some of this extra work to the client through javascript in a secure fasion. What you see above is a proof-of-concept that shows the answer to that question is yes.
When a server validates a password it hashes the password along with other information, which may include username, salt, and pepper. The solution I propose include another piece of information, a four digit pin-code, which is computed by javascript.
As you type in the form above the javascript code computes a pin-code. In a real application the pin-code would be submitted along with the other fields. The server validates the combination of all the values. The pin-code is computed using a public algorithm from the login name and password.
An attacker trying to brute force the password hash would either have to compute the pin-code, which requires 4096 invocations of the SHA256 compression function or try all possible pin-codes which requires on average 4500 invocations of the hash function used on the server side. Either way the attack is slowed down by a factor of about 4000.
If javascript is not available the pin-code entry field is just another input field that the user will need to fill in manually. Since the algorithm to compute it is public, the pin-code can be obtained through a wide range of different methods, as long as you know the login and password.
The algorithm uses SHA256. In order to avoid dealing with byte-ordering in the javascript code it works with 32 bit integers in all calculations. Unicode code points are used directly in the hash function. The sequence of 32 bit integers to hash is constructed as follows
There are a few important properties about above construction. The password goes in the beginning of the sequence of words to hash such that none of the compression function results can be reused for different passwords. Additionally the login and application name goes immediately after the password such that calculations for a specific password cannot be reused for a different user. The application/site name is any fixed string to identify the application and/or site, such that it is harder to reuse any of the calculations for multiple sites. Finally the sequence of zeros was choosen such that the 64 W+K values can be precomputed, this allows for optimizations of the javascript code.
Once the SHA256 calculation is finalized the first word of the result is used for PIN calculation. This word is known as A in descriptions of SHA256. The PIN is calculated using the formula (A%9000)+1000. A calculation is chosen that will not produce leading zeros to avoid any confusion about whether leading zeros can be omitted.
This proof of concept has not been peer-reviewed. If you want to use it, I recommend you have it reviewed by somebody knowledgeable in the field. Any secure design can potentially become insecure due to implementation flaws, that goes for this design as well.
There is a few features that would be nice to have, which the current implementation does not provide. It would be nice to have the bulk of the client side computation done in native code, unfortunately javascript doesn't provide the primitives to achieve this. Additionally it would be nice to have the client side computation done in a way that could be verified on the server side with asymptotically less computing time than was used on the client.
The proof of concept shows the PIN being updated as you type. Any real implementation should not do that. Anybody who watches the screen and see the PIN codes corresponding to partial passwords could use those to work their way back to the password. Additionally it is a waste of CPU time. A real implementation would compute the PIN once, just before submitting the form.
This construction is meant as an alternative for excessive itteration of the hash function on the server side. When using these PINs, I believe it is safe to reduce the number of itterations back to just four. If you have strong confidence in the hash function used on the server, you could go down all the way to just one hashing step on the server.
The pin construction is not meant as an alternative for all the other means you can take to protect the passwords. You still need to hash passwords on the server. You still need to include a random salt with at least 64 bits of entropy in the data that you hash. Including some application specific value in the data that you hash on the server is a good idea. Including some site specific value in the data that you hash on the server is also a good idea.
When the password is updated in the first place, the new PIN should be computed on the server. You don't want to be in a situation where a browser bug can produce invalid password entries in your password database. This is not a major DoS vector since such code is only executed for already authenticated users, and you can rate limit password updates to no more than five new passwords per hour per user.
When password verification fails you can log some additional information for auditing and debugging purposes. There are values that are good to log, and there are values that are not good to log. Never ever log password or pin-code. For logging purposes you can compute a few pin-codes on the server side as long as you don't try to do it for every login. Restrict your pin-code calculations to a single thread. Once it cannot keep up with the rate of failing logins just take random samples of the failing logins. In the end statistics on the distribution of reasons for failues is all you need.
A possible algorithm that could be used if you want to produce extra logging information on the server side is as follows:
If the algorithm did compute the pin values, you still don't log any of the pin values. You do however compare the pin values and log what happened. The following outcomes are possible: