Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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})$?

share|improve this question
    
I think the answer to 2. is 'no', but I'd like to see some justification for it. –  otus Jun 30 at 9:38
    
One allows streaming the message without yet knowing the nonce. $\;$ –  Ricky Demer Jun 30 at 9:50
    
@RickyDemer, Ok, sure and vice versa for the other. However, I'm more interested in whether there's a difference in security. –  otus Jun 30 at 9:54

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
In practice it's Merkle–Damgård hashes (MD5, SHA-1/2) that get used in HMAC. –  otus Jun 30 at 12:15
1  
@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 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 at 12:27
    
SHA-3 supports a simpler MAC construction. That's not really relevant to this question, though. –  otus Jun 30 at 12:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.