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

1. Is there a standardized way to include a nonce in HMAC authentication?

2. Is there any theoretical difference in between $H_K(\text{Msg}||\text{Nonce})$ and $H_K(\text{Nonce}||\text{Msg})$?

-
I think the answer to 2. is 'no', but I'd like to see some justification for it. – otus Jun 30 '14 at 9:38
One allows streaming the message without yet knowing the nonce. $\;$ – Ricky Demer Jun 30 '14 at 9:50

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.

-

All the security definitions I am aware of for a cryptographic hash functions remain the same, if you apply a 1:1 mapping before hashing. In other words, if $f$ and $g$ are each others inverse, and $h$ is a secure cryptographic hash, then $x \to h(f(x))$ is also a secure cryptographic hash according to any security definition, I know of.

Under such definition, the order in which you concatenate elements before hashing does not matter (as long as reordering doesn't introduce ambiguity about boundaries between elements).

However to the best of my knowledge, being able to produce a collision for a hash function does not immediately break the security of an HMAC based on that hash. This means HMAC based on an insecure hash, might be secure. But in that case it is no longer obvious, that reordering of elements preserve security properties.

To perform any more analysis beyond that point requires knowledge about the internals of the hash function. You could analyze the HMAC construction assuming a hash based on the Merkle-Damgaard construction or a sponge construction.

It is also worth noting, that collision resistance is not sufficient to make a HMAC secure.

-
In practice it's Merkle–Damgård hashes (MD5, SHA-1/2) that get used in HMAC. – otus Jun 30 '14 at 12:15
@otus Before SHA3, Merkle–Damgård hashes would be used for practically everything needing a cryptographic hash. And due to that, HMAC was designed under the assumption, that a Merkle–Damgård hash would be used. However other constructions had been analyzed and proven secure in a random oracle model, and there is a huge gap between the theoretical oracle model and the practical Merkle–Damgård construction. The sponge construction was invented to narrow the gap between theory and practice. – kasperd Jun 30 '14 at 12:22
@otus There are enough similarities between Merkle–Damgård constructions and sponge constructions, that some proofs are likely to apply equally to both. And being similar also makes it simpler to analyse, what the differences between them does mean to security. I don't know if the well known HMAC construction is the preferred construction to use, if you want to build MAC out of SHA3, or if there exist other MAC constructions specifically designed for use with sponge hashes. – kasperd Jun 30 '14 at 12:27
SHA-3 supports a simpler MAC construction. That's not really relevant to this question, though. – otus Jun 30 '14 at 12:29