Using HMAC-SHA1 for API authentication - how to store the client password securely?
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?
Answer
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.