Your comment about not trusting the client confuses me. You don't have to "trust" the client to do cryptography for you. You simply define the cryptography it has to do, and if it doesn't do it, then it doesn't produce what you need to log in.
This is not an unusual practice, either. For example, any time you log into a remote computer using an ssh key, your ssh client is performing cryptography to authenticate you with the server. There is no problem in doing this, because the only way to perform the cryptography such that the authentication is successful is to have the right secret key. You could certainly write a custom ssh client that does some different cryptography, but that would be pointless, as the result would be an inability to connect.
There are, I think, two goals at play here. One is what you linked: preventing replay attacks. That is fairly easily solved by doing a double hash with a randomly generated salt. There is no problem in "trusting" the client to do this, because if they don't do it the way you specify, they don't produce the correct result. The only (feasible) way to generate a result that lets you log in is by combining the random salt with the correct password. This is important because otherwise an attacker could sniff your traffic and then impersonate you.
The second goal is in not having your password exposed if the site's database is compromised. Related, it would also be nice to not have your password exposed if the site is compromised and the attacker is watching incoming connections.
SSL solves the first goal, of preventing replay attacks. Not having your password exposed if the database is compromised is solved by hashing passwords. However, if you send the password in plaintext (or encrypted in such a way that the other end can retrieve plaintext, as with SSL) then the last, related goal fails: an attacker with total control can grab your password if you log in during the time he has control.
By doing hashing on the client, you can prevent that, and when implemented properly it can still avoid the rest.
The situation we were discussing is not analogous to the SSH situation you describe because the key, namely hash(password), is not secret (the attacker knowing it was the premise of the scenario). It doesn't matter what mumbo-jumbo (not an insult, just an illustrative phrasing) you require the client to do, an attacker can do it just as well. The system is still vulnerable to attacks (which are not exactly replay attacks by the strict definition, but are still trivially equivalent) because it depends upon the key being secret, which is not the case.
Hashing on the client does not satisfy the first goal and sending the password in plaintext does not satisfy the second goal. A different solution altogether would be necessary to satisfy both goals.
I'm still confused. With my proposed system, how do you perform a replay attack (or the trivial equivalent thereof) without access to the server's database?
There are two scenarios here, and I think we are each discussing a different one.
The first scenario is where the attacker obtained the hash from the wire which is what I think you're assuming to be the case. Then yes, double hashing would protect against replay attacks.
The second scenario is where the attacker obtained the hash from the database which is what I assumed to be the case. Double hashing would not protect against these attacks (which are not, strictly speaking, replay attacks).
I'm not interested in belaboring this point any further, because I think you came up with a better solution to both issues in another post[1].
When the attacker obtains the hash from the database, this does indeed let him carry out the rough equivalent of a reply attack, but it doesn't let him carry it out on any other site. The reason you don't want passwords stored (or transmitted) in plaintext is so that an attack doesn't compromise the user's accounts everywhere. This double hashing scheme avoids that, but yes, leaves your account on this one site compromised if the database is copied.
Glad you liked the other scheme. It's more complex, but seems better. I really have to try it out at some point.
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.
This is not an unusual practice, either. For example, any time you log into a remote computer using an ssh key, your ssh client is performing cryptography to authenticate you with the server. There is no problem in doing this, because the only way to perform the cryptography such that the authentication is successful is to have the right secret key. You could certainly write a custom ssh client that does some different cryptography, but that would be pointless, as the result would be an inability to connect.
There are, I think, two goals at play here. One is what you linked: preventing replay attacks. That is fairly easily solved by doing a double hash with a randomly generated salt. There is no problem in "trusting" the client to do this, because if they don't do it the way you specify, they don't produce the correct result. The only (feasible) way to generate a result that lets you log in is by combining the random salt with the correct password. This is important because otherwise an attacker could sniff your traffic and then impersonate you.
The second goal is in not having your password exposed if the site's database is compromised. Related, it would also be nice to not have your password exposed if the site is compromised and the attacker is watching incoming connections.
SSL solves the first goal, of preventing replay attacks. Not having your password exposed if the database is compromised is solved by hashing passwords. However, if you send the password in plaintext (or encrypted in such a way that the other end can retrieve plaintext, as with SSL) then the last, related goal fails: an attacker with total control can grab your password if you log in during the time he has control.
By doing hashing on the client, you can prevent that, and when implemented properly it can still avoid the rest.