1
$\begingroup$

Is if the result of HMAC-sha256 distinguishable from random noise?

If so, given:

  • a collection of 1000 keys, and
  • 1000 messages of random noise, 100 signed by each of only 10 of those keys

Can any clue be found as to which messages were signed by which of the 1000 keys.

edit:

Assuming 4KB messages, indistinguishable from random noise, and 32 byte keys, also indistinguishable from random noise.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ You mentioned in another comment that you are concerned that the attacker may have access to the original messages. Does the attacker also have access to the larger pool of keys? If so, then determining which key was used for which signature is trivially easy. If not, then I am not sure why you mention that there are 1000 keys, of which you only use 10? $\endgroup$ – Neil Slater Feb 23 '15 at 13:10
  • 1
    $\begingroup$ Good catch - the attacker does not have any of the keys. $\endgroup$ – fadedbee Feb 23 '15 at 14:05
  • 1
    $\begingroup$ I was concerned only that the attacker might be able to work out that 800 messages were signed by key A, and 100 by key B, etc. $\endgroup$ – fadedbee Feb 23 '15 at 14:06
3
$\begingroup$

If the keys and messages are known, yes, you can distinguish which were used - because you can test them all. If not, then this is "sligtly harder" (= not really possible with big enough values). Anything of the further answer will assume that the attacker doesn't know the keys or the messages.

The definition of HMAC looks like this: $HMAC(K, m) = H(K \oplus opad || H((K \oplus ipad) || m))$ with $k$ as the key and $m$ as the message. $opad$ and $ipad$ are constant, different values while $H()$ is the used hash function - in your case SHA-256. We can see that the end result is the output of a hash function. If there's nothing special happening with the key or the message inside the function, than all security features about the hash should also hold for HMAC. Finding the original message (while having the output of the hash function) should be hard - that's called preimage resistance. As long as the keys and messages were long enough, it shouldn't be possible (with non-ignorable probability) to find the orignal message in a reasonable time. Good hash functions should also be not distinguishable from truly random output, so this should also be no problem.

Even if you have every message HMAC-hashed with every key it is still not possible to say which HMACs were calculated with the same key / with the same message. The attacker will only see $1\,000\,000$ random looking bit strings ($1000$ keys times $1000$ messages) and have no clue what to do with them.

As soon as there are patterns in the keys or messages, it will be easier to attack the hashes. $80$ bit of entropy (from message and key together) should be enough to ward of any brute force attack. No hash is secure if the messages are small enough.

The document Keying hash functions for message authentication has more informations and the security proofs for HMAC. You can read there why it should be not really possible to find the used messages and key in your scheme - if they are big enough.

|improve this answer
$\endgroup$
  • $\begingroup$ See edit, are these sizes big enough? Also, I am particularly worried that the messages are available to the attacker. Does that make it possible to find the keys, before the universe dies? $\endgroup$ – fadedbee Feb 23 '15 at 13:01
  • 1
    $\begingroup$ @chrisdew: Yes, if they are really true random bits, than that's fully enough for every purpose. $\endgroup$ – Nova Feb 23 '15 at 13:27
  • $\begingroup$ Is the result of PBKDF2-HMAC-SHA1 (using high-entropy random salt and random key and 2^N dkLen) also indistinguishable from random noise? $\endgroup$ – KrisWebDev Apr 1 '16 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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