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?