Is there a standard way to use a nonce with HMAC? Many protocols use HMAC on messages that include a nonce, but they don't seem to do it in a consistent way. For example, in OAuth the nonce is in the middle of an URL-encoded key-value string, like this:

POST&http%3A%2F%2Fexample.com%2Frequest&a2%3Dr%2520b%26a3%3D2%2520q
%26a3%3Da%26b5%3D%253D%25253D%26c%2540%3D%26c2%3D%26oauth_consumer_
key%3D9djdj82h48djs9d2%26oauth_nonce%3D7d8f3e4a%26oauth_signature_m
ethod%3DHMAC-SHA1%26oauth_timestamp%3D137131201%26oauth_token%3Dkkk
9d7dh3k39sjv7

This is probably because different protocols use the nonce for different purposes. However, I'm interested specifically in using a nonce with a constant message to get different authenticators for repeated messages (with the same key).


Is there a standardized way to include a nonce in HMAC authentication?
Is there any theoretical difference in between $H_K(\text{Msg}||\text{Nonce})$ and $H_K(\text{Nonce}||\text{Msg})$?
Under the assumption that $(K,\text{Msg})\to H_K(\text{Msg})$ is a secure MAC (be it HMAC or any other MAC), and $\text{Nonce}$ does not repeat and is of fixed size, both $H_K(\text{Msg}||\text{Nonce})$ and $H_K(\text{Nonce}||\text{Msg})$ are demonstrably secure, in the sense that an adversary not knowing $K$ can't distinguish either from random, even for iteratively chosen $\text{Nonce}$ and $\text{Msg}$.

When $(K,\text{Msg})\to H_K(\text{Msg})$ is HMAC, and we do no trust the underlying hash, and the weakness of this hash is bad enough that HMAC is not secure, it is hard to tell which of $\text{HMAC}_K(\text{Msg}||\text{Nonce})$ or $\text{HMAC}_K(\text{Nonce}||\text{Msg})$ is likely to be least broken. I wouldn't worry about that, because HMAC is secure with less-than-collision-resistant-hashes both in theory and practice (MD5's collision-resistance has been torn to pieces, but HMAC-MD5 so far stands valiantly). Any remaining security may depend more on what constraints the adversary really has on $\text{Msg}$, and what really counts as a success, than on anything else.