Using HMAC-SHA1 for API authentication - how to store the client password securely?

Question

In a RESTful API that uses S3-style authentication, the API client signs the request with his secret key using HMAC-SHA1, so the secret key is never transmitted over the wire. The server then authenticates the client by using that client's secret key to repeat the signature process itself and compare the result to the signature transmitted by the client.

This is all nice and good but it means the server requires access to the plaintext of the client's shared secret. That flies in the face of all the advice out there against storing user passwords in the clear inside your database. Storing only the salted hash of the password is not an option as far as I can tell - because then I can't verify the client's signature.

I should stress that my API is RESTful and thus should be stateless: I'd rather avoid a login step prior to other API calls.

One optional solution is to encrypt all user passwords using some symmetric key algorithm. However, the server would have to store the key to that encryption somewhere easily accessible, e.g. inside the source code. This is better than nothing but not an optimal solution (as @Rook mentioned in his answer, it violates CWE-257).

Another direction for a solution could be something around asymmetric signatures, but I can't figure out how to apply that to the HMAC, and can't find any articles on the subject.

Am I missing something obvious here? Many respectable providers have implemented this kind of authentication scheme - they can't all be violating common security principles, can they? If not, are there any best practices that you can share?

Solution 1

This is the downside of symmetric-key challenge-response style authentication - you don't put the secret on the wire, but you have to store the secret at both ends. (HMACs are symmetric key systems).

Note though that it's not a password - it's a shared secret. There's a fundamental difference here - a password is generally chosen by the user, whereas a shared secret is generated randomly and provided to the user (they're often called "API keys", in this context).

Storing passwords in a reversible format is bad, because if your database is compromised, then the attackers have obtained passwords that might (and probably have been) used elsewhere. Storing a shared secret, on the other hand, is not such a problem - the secret it's specific to your service, so all the attackers have gained is the ability to log in to your service.

On the other hand, it is possible to have an asymmetric system that doesn't have to store a secret at the server side. The basic idea is that the server knows the client's public key and current message sequence number. When sending an API request, the client increments the message sequence number and calculates a signature over the sequence number and the API request parameters, which the server can verify using the public key. The server rejects a message if it contains an old message sequence number, to prevent replay attacks.

Solution 2

Ideally after the user logs in you give them a Cryptographic Nonce which is used as the HMAC secret key K for the life of that session. This is a secure approach, but its not RESTful, because REST is stateless. This idea of an message authentication code issued per login is technically a form of state.

Encrypting passwords and storing them in the database is a violation of CWE-257.

Solution 3

I am not sure if i am missing something here but one option is to use hashed password as symmetric key.

Comments

[Elad]

Thank you @Rook. I should have mentioned that my API is RESTful and thus I'd rather avoid a login step. I edited my question accordingly.

[rook]

@Elad The argument can be made that you cannot have be truly stateless and have authentication because usernames and passwords are a form of state. Of course every authenticated REST implementation is going to to make this compromise for the sake of security.

[Elad]

I believe you're right, but asked my question with the hope of being proven wrong :) I'll keep it open for a while longer in case somebody does come up with a perfect solution.

[rook]

@Elad its a great question that is open for debate and interpretation.

[rook]

@Elad This post made me wonder, so I had to ask SO: stackoverflow.com/questions/5492683/…

[Elad]

Thanks @caf. The clarification of the difference between passwords and shared secrets is a good point. Even if my service gets screwed, at least I didn't screw others :)

[Elad]

The asymmetric system that you describe is a good scheme! But there's a trade-off (there always is, isn't there?). The problem is that now the client and server have to be coordinated. It's a pandora's box of strange bugs that no one understands until you realize that they got out of sequence. It also creates concurrency issues (if, for example, the client application has multiple instances accessing the API). In short, it adds a lot of complexity for the sake of security.

[Rafael Ibraim]

+1 for the clarification between 'shared secret' and 'password'. This answer was exactly what I was looking for.

[frostymarvelous]

Still do not understand what you mean by sequence number. Is that not supposed to act sort of like a nonce? how does that eliminate the need to store the shared secret exactly?

[frostymarvelous]

Then the consumer will need to know how you hash your passwords as well and if you use salts....... guess you see the problem now.

[frostymarvelous]

else, the user will need to know the hash to use for logins. which is not a simple inconvenience

[html_programmer]

Sorry for this late question. But how will a cryptographic nonce that is sent by the server arrive at the client? What happens if someone in the middle gets his hands on the nonce (assuming no SSL/TLS)? I have exactly this problem I can't seem to get passed.

[Jeroen Landheer]

@frostymarvelous Signatures can be made using a private key and verified using a public key. If the server knows the client's public key, they can verify the signature to authenticate the client. If the signature is correct, you can be sure the request came from the client and noone else, unless the client's private key has been compromised. The number is needed so the signature differs each time for each request to the server. Otherwise someone could grab the packet and ... send it again >(

[frostymarvelous]

@Jeroen Landheer that looks like a workable solution. Same security threat applies to native apps so I think it's an acceptable risk