How do I build a secure signing mechanism on top of HMAC

Question

Say we have a system with strong shared keys (not passphrases), and we're trying to sign messages sent by the server that will be visible to an attacker. E.g. storing session state in a signed cookie.

Is it safe to use HMAC directly with the shared key? I.e. the function will be determinant and the attacker can just build a collection of [message, MAC] pairs; can he/she compromise the shared key?

If not, is it safe to use hmac_key = HMAC(salt, shared key), where salt is new for every request and sent along with the MAC? Or do I need multiple iterations of this/PBKDF2?

I guess I want to know if using a salted key for HMAC provides any real protection of the key, not just seems more secure.

Answer 1

Technically, HMAC is a MAC, not a signature. Some people get the terminology wrong (in particular Microsoft's documentation) and call HMAC a signature, but things are clearer if you use the right words.

HMAC, when used with a secure hash function (say, SHA-256, but SHA-1 is fine too), is resistant to forgeries; that is, the attacker cannot succeed in computing a valid pair (m,h) where h is the correct HMAC value for message m, even if the attacker has access to many pairs (m',h') (where all m' are distinct from m). In particular, the attacker cannot guess the HMAC key, because obtaining the HMAC key would allow him to create a lot of forgeries.

Salts, and PBKDF2, make sense only if you envision that exhaustive search on the key might work. Salting and slow hashing (PBKDF2 does both) are mitigation measures to make life harder for the attacker in that case. In your scenario, the HMAC key is "strong", i.e. immune to exhaustive search (e.g. it is a sequence of 128 bits obtained from a cryptographically strong random source). Therefore, salts, PBKDF2 or other ritualistic elements won't make it any more secure. HMAC is already fine as it is.

Note that in the case of cookies, several users may collude and exchange their HMACed cookie values. A user could also record a cookie value, and send it back to you afterwards, even if the server sent him a newer cookie value. Depending on your usage context, this may or may not be a problem.