How can I validate a hashed password if all I have is another hash?

Question

The Scenario

I have a client-side web application that bounces requests against a server-side API. For the sake of simplicity, every request must pass a username and password. This is similar to old school XML-RPC where the username and password are passed as parameters in every request.

However, as this is a REST service, some of the requests (GET and DELETE) don't have message bodies and must pass the username and password as query variables in the URL:

GET http://application.url/endpoint?username=xxxx&password=xxxx

This is, frankly, a bad idea. Requests are logged on the server, so if I send the password in plaintext, it's now sitting in a log file somewhere on the server. I don't ever want to be sending the password in plaintext over the wire, so I'm stuck with a dilemma.

Approach 1

The first approach to solving this over-the-wire problem was proposed by a coworker:

1. Encrypt the password using something like Blowfish and store it in the database.
2. The client hashes the plaintext password plus some salt using some known scheme (i.e. SHA512).
3. The client send the hash and salt to the server.
4. The server decrypts the stored password, hashes it with the provided salt, and compares it to the provided hash.

This is an effective means of sending sensitive data across the wire (if the logs were read, no one would be able to snag the password). But it breaks another one of my personal security rules - I have access to the user's original password!

If the password is stored in the database using reversible encryption, then it's still vulnerable to attack. Someone could steal my database and decrypt the password. To me, this is almost as bad as storing it in plaintext to begin with.

The server should not have access to the plain text password.

Approach 2

This approach was suggested in passing by a fellow developer and, on the surface, seems to solve some of my problems.

1. Hash the password with some salt and store the hash and salt in the database (no plaintext!).
2. The client encrypts the password using the server's known public RSA key
3. The client sends the ciphertext to the server.
4. The server decrypts the password using its private key and hashes the recovered plaintext with a known salt.
5. The server compares the computed hash with the hash stored in the database.

Once again, an effective way to prevent sending the plaintext password over the wire. It has the added benefit of never storing the plaintext on the server as well.

But it still bugs me, because the server can see the plaintext after decryption. Though I can build the system today to be secure, there's no guarantee another developer won't add logging somewhere in the future and write the plaintext to disk.

I'd be much happier if the server never had access to the plain text password.

End Goal

At the moment, approach #2 is the best solution I've come up with and will probably be what I end up implementing. But there is an ideal solution out there ... I just don't know how practical (or even possible) it might be:

1. Hash the password with some salt and store both in the database (no plaintext!).
2. The client hashes the password on its end with its own salt.
3. The client sends the hash (and the salt?) to the server.
4. The server runs some other functionality to see if the two hashes (its and the client's) were generated by the same plaintext - it does not get the plaintext.

I could wire up some kind of challenge/response system (where the client asks for a salt, hashes the password with that salt, sends the response, and the server compares it with what it expected), but I'm trying to keep requests to a minimum. So you'd only make one call to the server when you make the request rather than one call to authenticate and another to execute.

Is this last scenario even possible?

Answer 1

With the method below, the server never sees either the password or the key the password decrypts.

To generate a password:

The client generates a new RSA key, encrypts it with the password (using something like PBKDF2 to generate a symmetric key), and hands the server the RSA public key and the encrypted private key.

To Authenticate:

The server sends the client the encrypted RSA private key and a challenge. The client uses the password to decrypt the RSA private key and then signs the challenge. The client sends the signed challenge back to the server. The server verifies the signature with the RSA public key.

Caution:

Make sure changing passwords involves creating a new private key, not re-encrypting the old one with the new password.

--

This has an extra request. You can avoid that with two tricks:

1. Have the client store the encrypted private key so it doesn't need to ask the server for it.

2. Have the client store a sequence number to use as the challenge (or a timestamp and a random number), so it doesn't need to get a challenge from the server.

Answer 2

Something like this should work, right?

There's no reason you have to use sha2, you can use any cryptographic hash function. I just used sha2 everywhere for simplicity.

Server Side

To store the password, store the result of: sha2(sha2(client_salt + password) + server_salt), as well as client and server salts

Client Side

1. Have the server transmit client_salt to the client (since salts should always be unique, this will likely require a call to your API to determine a user's client salt).
2. Have the client send sha2(client_salt + password) for verification
3. The server can then validate the password by taking the clients input, and hashing it with the server salt. Like sha2([sha2(client_salt + password)] + server_salt) where the piece in []'s is from the client.

I'm pretty sure there's pretty much no way to get around the fact that you know the salts, and can generate the rainbow tables for decryption, but I think this provides a good amount of protection, without a ton of overhead.

Answer 3

You could try this :

1. Of your first login, the client can send to the server E(hash(password),n) with ku [public key of server] The server can decrypt and store the nth hash of the hash value.

2. From then on, the client can generate the (n-1)th hash of the password and send it, along with a tag encrypted with the public key of the server.

   E(hash^(n-1)(password),new_n,tag) using ku

3. The server can decrypt this with its private key, hash the first value, check it with what it has and store the new_n th hash for the next login. The client is authenticated and a tag(challenge ?) has been established for this session.

4. Every message can be concatenated to the tag and then encryted. The first response of the server to the client thus serves both as an authentication as well as the first meassage back.

5. For all further communication in that session, either party on decryption, can verify whether the tag matches the client generated tag for that session. Assuming the server knows the public key of the client.

Even if the hash values on the server are compromised, your passwords are safe. Plus, authentication in a single interaction.

Also, the tag can be used to authenticate every interaction between server and client for each session, if required, hence session is also secure.

Answer 4

My understanding is that you want the system to work like this:

• authorized users have a client-side application that sends messages to a server.
• for simplicity, every message sends both a username and something that proves to the server that it really came from someone who knows that user's password (as a proxy for "it really came from that user").
• some of the messages are logged on the server.
• If some attacker listens to the messages over the wire, and somehow can read those message logs on the server -- for example, the attacker steals the server backup tapes -- we want to set things up so that attacker is still unable to send messages to the server that trick the server into thinking that message came from an authorized user.

My understanding is that "digital signatures" and "message authentication codes" are two popular solutions to this problem.

With digital signatures, possibly using some OpenPGP-compatible crypto library to handle most of the details,

Setup and key changes / password changes

• The client-side application creates a new private signing key locally, and from that generates the corresponding public verifying key. (Typically the client-side application encrypts the private signing key with a key derived from the user's password and stores the encrypted key locally; David Schwartz mentions a nonstandard variant that stores the encrypted key on the server).
• Each user (or the client-side application on her behalf) sends the public verifying key to the server, and somehow convinces the server that this is the public verifying key for some specific username. (The various ways of doing this could take up a whole new question).

Authentication: client side

• The client-side application somehow gets the local user's private signing key. (Typically the user types in a passphrase, which is fed into a KDF to get a decryption key, and that key is used to decrypt the private signing key).
• The signing algorithm uses the private signing key and the message to produce a signature, which is somehow sent with the message.

Authentication: server side

• When the server gets the message and the associated signature, the server's signature verifying algorithm fetches the public verifying key for that user, and attempts to verify that message with its associated signature.
• If the verifying algorithm returns with "verified", then we can be certain that the message could only have come from someone who knows that user's private signing key (which is a pretty good proxy for "could only have come from that user").
• If the verifying algorithm returns with "not verified" ... then perhaps the message came from an attacker who (unsuccessfully) attempted to forge a message; or perhaps the message or its signature or both just got accidentally damaged or truncated in transit.

Answer 5

Your first solution was already pretty good, but some changes need to be made:

1) The server should generate the salt, randomly of course. This is to prevent someone from listening to your commucation and re-submiting your request again with the same salt and the same hash. This is impossible if the server chooses the salt.

2) Use public/private key instead of password, store public key on the server, and private key at the client (the private key file is still encrypted using a normal password, but neigter that nor the private key is ever sent to the server).

3) To send a request, first ask the server for the salt, then hash the request+salt, then encrypt that using your private key. Then send the request, and the signature to the server, and the server will verify that it was signed with the same salt it sent you a moment ago.

4) When a user is registering, they will create the private/public pair themself, and then send their username and public key to make the registration. The only disadvantage comes when a single user wants to log in from multiple devices, best way would be to physicly (on a flash drive for example) transport the private key, but other solutions are also possible.