5
$\begingroup$

I just learned HMAC in class. Keys are zero-padded in HMAC hashing function. 10 and 1 will be both transformed into the same final key (e.g. 1000).
Isn't that a problem?

$\endgroup$
  • $\begingroup$ Why do you think it might be a problem? $\endgroup$ – Elias Oct 11 '17 at 7:55
  • 1
    $\begingroup$ @Elias It trivially results in equivalent keys. Which results in collisions and second pre-images in PBKDF2, since it uses the password as key. It's not a practical problem, but certainly bad design. $\endgroup$ – CodesInChaos Oct 11 '17 at 14:48
7
$\begingroup$

Ordinarily, the keys for a MAC algorithm are assumed to have a fixed length. (If they don't, e.g. if the "keys" are actually user-supplied passwords, then you should run them through a suitable KDF anyway.) When HMAC is used that way, there is no problem, since the padding process cannot map two keys to the same output.

(If the input keys are longer than the hash input block length, HMAC specifies that they are to be hashed before padding. In this case, two keys can end up getting hashed to the same value, but actually finding two such equivalent keys is as difficult as finding a collision for the hash function. The hashing step does reduce the effective keyspace size of HMAC to the hash output length; that's only an issue insofar as it makes a brute force key recovery attack as easy as a single brute force MAC forgery. But for normal applications of HMAC, the latter is already considered a break, and thus the hash output size should be chosen to make it infeasible.)

That said, precisely because of its flexibility and its strong security properties (PRF-ness), HMAC is not only used as a generic MAC, but also for other purposes such as, notably, as a component of password-based KDFs like PBKDF2. In such uses, the key padding (and hashing) in HMAC could cause issues if one isn't careful:

  • For keys longer than the hash input block size, $k$ and $H(k)$ are equivalent HMAC keys. This could be an issue e.g. in a carelessly designed application that used $H(k)$ as a key check value, and thereby revealed it to attackers.

  • Conceivably, a lazy application designer could be tempted to take advantage of HMAC's flexible key length and derive auxiliary keys from a master key simply by appending various suffixes to it. In such a case, using two suffixes of different length (including, possibly, the empty suffix) that only differed by the longer one having one or more null bytes appended to it could potentially yield equivalent subkeys.

  • Similarly, when HMAC is used for password hashing (e.g. as part of PBKDF2), two passwords that only differ by appended null bytes would be equivalent. Of course, people rarely use (or even allow) null bytes in passwords, and anyone who does is likely to run into bigger problems anyway (like the fact that many systems may store user input as a null-terminated string, effectively truncating it at the first null byte). And even if someone did somehow end up using such an equivalent null-padded password, the security implications would be essentially the same as if they'd simply reused the original password.

In practice, all of these issues are easily avoidable simply by being aware of them and not doing silly things like using null bytes in passwords or in subkey suffixes. The real problem with HMAC's key padding scheme is simply that it presents a subtle trap for careless cryptographers, and requires anyone analyzing HMAC-based schemes to be aware of its internal structure. It would be nicer and simpler if we could just treat HMAC as an ideal black-box PRF, but alas, due to the possibility of equivalent keys, that's not quite the case.

$\endgroup$
3
$\begingroup$

No, it is not a problem. You still have to know the key to calculate a MAC. If you randomly get a key that is the same after padding you essentially have guessed the original shorter key. The key needs to be long enough to prevent people from guessing it anyway.

$\endgroup$
  • $\begingroup$ I see. I neglected the fact that keys are very long. Thank you. $\endgroup$ – iamlazynic Oct 11 '17 at 8:11
  • $\begingroup$ If the keys are zero-padded, there's non-negligible probability you can find the hash collision with less effort. (if the key is random and long enough, practicaly it should be ok) $\endgroup$ – gusto2 Oct 11 '17 at 8:16
  • $\begingroup$ @gusto2 But you cannot find it with less effort than exactly what is to be expected for a key of that length. $\endgroup$ – Elias Oct 11 '17 at 17:20
2
$\begingroup$

It is not a "problem" to use a shorter key, as you said the key is padded to the block size as a part of the function. Not a problem in that the algorithm works with short keys, but you are trading off security strength of the HMAC.

See http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.198-1.pdf

and the referenced SP:

http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-107r1.pdf

The security strength of the HMAC algorithm depends, in part, on the security strength of the HMAC key, K. An HMAC key shall have a security strength that meets or exceeds the security strength required to protect the data over which the HMAC is computed.

The HMAC key shall be kept secret. When the secrecy of the HMAC key, K, is not preserved, an adversary that knows K, may impersonate any of the users that share that key in order to generate MacTags that seem to be authentic (i.e., MacTags that can be verified and are subsequently presumed to be authentic).

TLDR: the shorter the key prior to being padded, the less work needed to brute force the key.

$\endgroup$

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.