Secure authentication: partial client-side key stretching... please review/criticize my idea

Question

I am trying to figure out what would be the 'perfect' authentication system for a website.

On one end, we know that simple hashing algorithms can be brute-forced or cracked in other ways. Hence why MD5 is no longer recommended. The best solution for secure password storage, it seems, is making use of key stretching in combination with salting (i.e. using PBKDCF2, bcrypt or scrypt). For those who haven't heard of it, key stretching implies that a hashing algorithm will be computed through many iterations (not just once), causing each brute force attempt to take an unreasonable amount of time to compute.

Now, having users sign up, authenticate or change their password, and having the server use key stretching to store the password does ensure proper password protection -- but leaves the door open for DoS attacks. Mainly, a hacker could just flood it with authentication attempts with random passwords, and the server would choke on computing all those iterations for all those attempts.

I'm trying to get the best of both worlds -- secure password storage with key stretching, without the DoS door opened. Here's my idea, and I want to know if I'm overseeing anything, or if there's any problem in my logic... sometimes, when you're too close to the problem...

The idea is:

1. CLIENT-SIDE: Website user inputs username, password

2. CLIENT-SIDE: Website uses AJAX request to the server to retrieve the salt and number of iterations attached with the user's record (based on username match)

3. CLIENT-SIDE: Authentication Step 1. Website computes, on the client's computer with Javascript, all the hashing iterations MINUS ONE (I will explain why later). The computation is performed using a well-known algorithm, such as PBKDF2, bcrypt, or scrypt. Website sends the result to server.

4. SERVER-SIDE: Authentication Step 2. Server receives the username + hashed password (minus one iteration). Performs last iteration (with PBKDF2, bcrypt or scrypt) Compares with stored value to determine if combination is correct. Returns response to website.

Now, why all iterations minus one? If a hacker gets a copy of the database, and the server would expect a fully-hashed password to be provided, it would be equivalent to storing the passwords in plain text. Hacker would copy and paste the hash and use the authentication service. As such, we can't return it directly.

However, since we theoretically can't 'reverse' hashing, having the server only accept a n-1 iterated hash means the hacker can't guess what the previous iteration looked like, based on what we see in the database. Is that correct?

In the end, we have the majority of the work performed on the client-side (server only does one iteration), eliminating the DoS threat, but we also have passwords stored with full-on key-stretching with salt, a most secure practice.

Am I missing anything? Would this be an ideal way to implement an authentication system? Let me know! I'm just wondering if I'm missing anything here...

Answer 1

Client-side hashing works, conceptually. The problem, though, is that of power. In a Web context, client uses Javascript, and Javascript is feeble for computing intensive tasks. The client already uses a system which may have a relatively small CPU (it could be a cheap smartphone, for instance), but Javascript adds its own overhead, which is huge (because it is interpreted, hard to JIT, and lacks decent integer types). As a rough estimate, client-side hashing in Javascript will be 20 to 40 times slower than password hashing on a decent server.

Unfortunately, user's patience does not stretch; the user tolerates one or two seconds of delay, no more. So when you use client-side hashing, you have to use less iterations than when you use server-side hashing, which weakens the whole picture.

Or, said otherwise, as long as you handle the login process of no more than twenty users per second, server-side hashing will allow you to use more iterations than client-side hashing, and thus be better for security.

If the client uses a Java applet, then it is much more powerful; the "20x" factor becomes "3x". But Java applets have fallen out of fashion and won't work on tablets and smartphones. Mobile clients with a dedicated app may revive the concept of client-side password hashing.

As for the details, the best way is not to "remove one iteration" from the algorithm, but to add an extra hash: cryptographic algorithms are complex animals, and though password hashing function internally use "iterations", they don't necessarily use only iterations. For instance, you cannot easily remove "the last iteration" of bcrypt and get a partial result to be transmitted to the server. So, instead, do all iterations on the client, send the result R to the server, and the server stores both the salt, and h(R) for some hash function h (e.g. SHA-256).

Answer 2

SRP already allows for client-side key stretching because the it has a client-side KDF. If you're so inclined, you can spend 15 minutes burning cycles while stretching your key, every time you login, without impacting server performance.

This is just one of many of its benefits.

Answer 3

One flaw that I can see is, since you are doing n-1 iteration on the client side, the use of bcrypt/scrypt/PBKCDF doesn't make sense. As the use of these algorithms is to make cracking of passwords time consuming and computation intensive. In present scenario, an attacker will have the n-1 iteration hash readily available and further requiring only another 1 iteration to guess the password. Which would be trivial for any attacker and in my knowledge carried out on a simple desktop machine.

One possible solution to prevent DoS is, if somebody (malicious user) wants to log into the account, then after certain threshold number of attempts you can stop the user from logging in for certain time and keep increasing this time exponentially. For example, let the threshold attempts be 3. If a user with username 'user123' is logging in, (s)he enters 3 wrong passwords, after that you can block the account for 5 seconds. If again there is a wrong attempt after 5 seconds, you can block the accounts for 10 seconds and so on.

This way you ensure that one user is not hogging your resource and making any bruteforce attack time consuming and eventually unfeasible.

EDIT: Another issue with this approach is, you are sending the salt to the client side. Salt is used to make the brute-forcing of passwords hard. In the present scenario, the attacker will also have the salt corresponding to the username easily available.

Also, if client disables javascript, then he/she won't be able to log in to the website. But this may not be a major issue, as modern websites are heavily dependent on javascripts and require it to be enabled on the client.

Answer 4

With a slow key-derivation function you want to achieve two goals:

Prevent an attacker from being able to login

The client-side iterated hash, can be seen as a password replacement itself, which is sent to the server and will be hashed once again and stored. If an attacker can find out this password replacement he could login. Since the output of the pre-iterated hash (BCrypt) is about 60 characters (with 7 constant characters and 21 known salt characters), there would still be more than 1E50 combinations to test, so brute forcing seems unpracticable.

Prevent an attacker to get the original password, he can use on other web services

To find out the original password, an attacker would still have to do all iterations. So the iterations done on the client-side will slow down dictionary attacks (testing of often used passwords).

So actually your scheme seems to work, at least i cannot see an obvious flaw. There is one problem with BCrypt though, this algorithm uses the original password and the salt in each iteration, so you could not do one iteration more, instead you would have to calculate an additional hash on the server.

Please also read Thomas Pornin's answer, there are practical reasons, to do the hashing server side (and he is the expert).