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

## 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.

### 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.

### 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?

-
Have a look at the SRP protocol, it might do what you want. –  Paŭlo Ebermann Jun 27 '12 at 19:18
I like the idea of SRP, but from looking at the documentation it seems to be a lot of back-and-forth between the client and the server. My goal is that the client only makes one call to the server. –  EAMann Jun 27 '12 at 19:48
There is no way to hash a password with different salts and compare the results to see that it is the same - if it were, the salting would be useless. So either the client needs to remember the salt too, or the server has to tell the salt to the client. (Or there is some homomorphic encryption solution to this.) –  Paŭlo Ebermann Jun 27 '12 at 19:53
By the way, if you're really paranoid about security, don't use a general purpose hash function (SHA###) for password hashing. Use bcrypt or PBDKF2, which are actually designed for securely hashing passwords. –  Brendan Long Jun 27 '12 at 20:57
SRP has minimal back-and-forth: Just two messages to derive a shared key. There are two more messages if you want authentication. –  Eyal Aug 30 '12 at 14:07

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

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.

-
If you already use public key cryptography, take a look on SRP - at least it is not homebrew. –  Smit Johnth Mar 23 '13 at 14:46

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.

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.

-

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.
-

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.

-
@DavidSchwartz That's not true. The server stores sha2(sha2(client_salt+password)+server_salt), which is not sufficient to log in. To log in, you need the inner part (sha2(client_salt+password)), which cannot be easily found from the stored data (the whole point of password hashing). Your question seems to be implying that sha2 is reversible, which is not (except in trivial cases like dictionary attacks, and no password in a dictionary is ever safe). You could improve it by using bcrypt, but the idea is sound. –  Brendan Long Jun 27 '12 at 20:48
This doesn't help. The OP wanted to avoid sending the password in the clear over the channel. With this method, the password is sha2(client_salt + password) (since that's what the client needs to log in), and it's sent in the clear over the channel. –  David Schwartz Jun 27 '12 at 20:53
@DavidSchwartz It seems to solve the two major problems: (1) the server never sees the plaintext password and (2) stealing the hashed password isn't sufficient to log in. There are probably better solutions but this does solve the problem posed in the question. –  Brendan Long Jun 27 '12 at 20:55
The question says: "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." Your scheme sends the password in plaintext over the wire. –  David Schwartz Jun 27 '12 at 20:58
I read it that way too. However, "password" means whatever the client needs to access the server. In your scheme, the password is sha2(client_hash + password), since that's what the client needs to authenticate. (Anyone who stole that could log into this service as the client.) –  David Schwartz Jun 27 '12 at 21:02