IMO, what would be really ideal is the following goal
- An attacker who has access to the server database and also is watching the network traffic should not be able to impersonate the client(user) later.
The double hashing scheme doesn't achieve this. Since hash(password) is stored in the server DB, the attacker can just copy that and use it to login later. He just needs the hash, not the plain-text password to compute what the server asks for during authentication.
The above goal can be achieved by public-key cryptography. Its just like SSL working in reverse - server authenticating
the client/user based on user's private key. The practicality of assigning a private key to every user is a different matter though :)
Normally, private-key authentication doesn't work for most of these things because users expect to be able to log in with something they can remember, and any private key of decent strength is too long.
How about this for a login solution? For each user, you generate a private key and keep it on the server. But, you encrypt that private key with their password, and you don't keep that password or anything derived from it anywhere.
To log in, the server sends the encrypted private key and an authentication challenge to the client. The client then uses the password to decrypt the private key and respond to the challenge. Replay doesn't work, since the response is only good for that challenge. Watching the traffic on the server doesn't work, since you can only get the encrypted private key and the response. Snarfing the contents of the database doesn't even help, since you only get the encrypted private key.
For bonus points, I don't know if this is actually possible, make it so that it's impossible to tell whether a particular decryption of the private key is valid without using it to respond to an authentication challenge and sending that response to the server. This way it's impossible to brute-force the encrypted key, substantially mitigating problems with weak passwords.
Of course, I may have missed something obvious here....
Also, for your bonus question you can do something like this.
Enc-Priv-Key = Priv-Key XOR Trun(Hash(password))
where Trunc = Function to truncate to the length of the priv-key.
So, every (Enc-Priv-Key,password) pair combination is valid - it gives you a valid Priv-Key. Also, if you break into the server, you have Enc-Priv-Key and Pub-Key. Enc-Priv-Key is a random number assuming your hash(password) is random (which isn't true if your password is short but let's say it is). So, having Enc-Priv-Key shouldn't give you any information about Priv-Key.
Is every arbitrary sequence of bits a valid private key, though? Something tells me that it may not be, but I can't remember my RSA quite well enough to say for sure.
I suppose that even if not every sequence is valid, enough incorrect sequences will still be valid private keys to make a brute force attack impractical without server cooperation.
I was actually thinking that the client would store the private key somewhere (e.g. in an HTML5 browser:)) but what you described is brilliant and definitely works.
Something like that is not used probably because the bigger problem is clients getting hijacked, not servers.
Right, and when servers do get hijacked it tends to be a quick in and out, so compromises based on transient connections aren't much of a concern. Sending passwords over SSL with a good password hash on the other end solves everything if you assume that the attackers won't stick around listening on incoming connections.
Now I really want to implement my scheme using JavaScript crypto. If only I had a web site that needed secure logins.
The double hashing scheme doesn't achieve this. Since hash(password) is stored in the server DB, the attacker can just copy that and use it to login later. He just needs the hash, not the plain-text password to compute what the server asks for during authentication.
The above goal can be achieved by public-key cryptography. Its just like SSL working in reverse - server authenticating the client/user based on user's private key. The practicality of assigning a private key to every user is a different matter though :)