Is using slow password hashing on the client side easier attackable than on the server side? As we know, one should use a slow password hashing algorithm instead of a fast one for storing passwords, to hinder brute force attacks when the database is compromised. The problem with this is that for every login we also need to run this slow password hashing algorithm, which for remote logins could be a considerate CPU load on the login server if many people try this at the same time.

This night, I had an idea on how to solve this (in a new protocol for password authentication):


The user types in his username
The client sends the username to the server.
The server sends a salt (and maybe other parameters) to the client
The user types in its password
The client calculates a slow hash (bcrypt-like) from this password, using the salt (and maybe the security parameter, e.g. iteration count) provided by the server
The client sends this hash value to the server
The server calculates another cheap salted hash (SHA-2-like) of the sent hash value, and compares it with the value stored in the database.
(Optional, to avoid remote brute-forcing and DOS: wait a small time before sending back the answer, and limit the number of parallel connections for each user/IP.)


The communication should be encrypted, of course (as the sent hash value is the effective password).

(Add the obvious way of generating and storing the passwords.)

I'm assuming this:


The output of the first hash is not really recognizable as such, e.g. there is
no cheap way to iterate only the possible outputs of the first hash instead of
all strings of this size. If I understand right, bcrypt has this property (if
we only look on the actual ctext part of the output, having length of 192 bits).

(A comment from ZoFreX seems to indicate that this is not the case.
Any details on this?)
The second hash is preimage-resistant, e.g. there is no significantly better
way of finding a preimage fitting to a given hash than brute-forcing the input space.


Then we have:


The first (slow) hash avoids (or rather slows down) brute-force/dictionary
attacks over the password space. (It is salted to avoid rainbow tables.)
The second (fast) hash avoids that an attacker which gets somehow read access to the
database can immediately use the data to login into the system: The attacker will
need to brute-force the (in the bcrypt example 192 bit large) output space of the
first hash to find a preimage (which then would be usable as a password).

If we think it is needed to slow this down even more, we could use a second (low-factor)
bcrypt here instead of a really fast hash.
Since the slow hash is done on the client-side, the server load is not as high
as for server-side slow hashing. (I'm assuming a quite high work factor for bcrypt.)


Here are my questions:


Is there already a protocol which works similar to this? (From the comments, this seems off-topic here. Feel free to mention it anyway if you happen to know one, but concentrate on the next question.)
Are there any weaknesses of this protocol idea compared to a usual server-side slow password hashing?
There exists something which is one step further than your idea. Look up SRP: this is a Password-Authenticated Key Exchange protocol; the two parties (client and server) who run the protocol end up with a newly generated shared key (which can be used to derive encryption and integrity-check keys), with mutual authentication with regards to a shared statically known secret which can be of relatively low entropy (say, a password).

In your system, this would mean that the password is first derived into the shared secret with something slow (bcrypt), and then use the result as the "password" in SRP. SRP has been designed so that the server stores only what amounts to a hash of the "password", not the password itself, so obtaining a copy of the server database does not allow an attacker to log in; it only makes him able to run an offline dictionary attack on the password, at which point the initial bcrypt hits him hard.

The beauty of PAKE protocols is that they are inherently immune to offline dictionary attacks from eavesdroppers: the protocol can be run "in the clear" and this still does not give a passive or even active attacker any way to learn enough to "try" passwords at his leisure. Only an attacker who hacks into the server may get such data, and even then he does not have the password (the password-derived-value-through-bcrypt, in the setup we envision here), just a hash thereof. So there is no need to establish a SSL/TLS tunnel beforehand. Even better, it is possible to use SRP as the initial handshake for a SSL/TLS tunnel; this is standard, and GnuTLS is an opensource implementation of that. A particular appeal of TLS-with-SRP is that client-server authentication is then mutual with regards to the password, which implies that there is no certificate whatsoever.

A possibly troublesome issue is that the number of iterations in bcrypt must be set so that it is slow (for the attacker) but still tolerable (on whatever machine bcrypt is to be executed). If you want bcrypt to run on the client, and also accommodate a variety of clients, some of which being possibly quite anemic (e.g. a 3 years old netbook, like mine: old mono-core Atom clocked at 800 MHz; also think about smartphones), then you have to tune the bcrypt iteration count accordingly. The patience of the average user being, let's say, somewhat limited, this prevents you from setting a bcrypt iteration count as high as you would like. On the other hand, you can muster 100% of the client CPU resources for that (client might be multitasking, but the user is unitask), which probably compensates much of that effect.

Summary: use bcrypt on the client, then use the result as "password" in TLS-with-SRP.