In NIST SP800-107, NIST claims that the security strength of HMAC is MIN(security of HMAC key, $2L$). $L$ is the length of the output of the underlying hash function. Let's take HMAC-SHA256 as an example. If the key used is larger than 512-bits, it is truncated to $L$ bits, which is 256-bits. However, if the key is smaller or equal 512-bits, the key is not truncated. Now, let's assume that key length is 384-bits. According to NIST, the strength of HMAC-SHA256 with this key is min(384, 2*256) = 384. However, since the output HMAC size is 256-bits, an adversary can guess an HMAC-SHA256 for an arbitrary message with success probability $2^{-256}$. In this case, how is the strength able to be defined as 384-bits? How can it be larger than the output size of the HMAC?
-
$\begingroup$ I agree that (at least that part of the document - I haven't read the whole thing) is terribly worded. Explanations of MAC security level tend to be confusing. There's a generic attack on HMAC that's related to the chaining value (internal state size) and the tag length. For HMAC-SHA256, that technically brings the naive security level down to 128 bits because the chaining value and output length are 256 bits. However, as pointed out by Daniel, NIST ignores that completely because it isn't practical, but neither is the pre-image attack. $\endgroup$– samuel-lucas6Jul 15, 2022 at 18:23
-
2$\begingroup$ I would also like to point out that NIST says 2C, not 2L. The chaining value (internal state size) is C. SHA384 has a chaining value of 512 bits, not 384, demonstrating how C doesn't necessarily equal L. $\endgroup$– samuel-lucas6Jul 15, 2022 at 18:31
-
$\begingroup$ Please look here: csrc.nist.rip/library/… IST says: "The security strength of the HMAC algorithm4 is the minimum of the security strength of K and the value of 2L (i.e., security strength = min(security strength of K, 2L)). " at section 5.3.4 $\endgroup$– Evgeni VakninJul 16, 2022 at 4:44
-
$\begingroup$ This document is newer. That's what I was referring to. $\endgroup$– samuel-lucas6Jul 16, 2022 at 7:37
1 Answer
The NIST SP800 107 handles the "tag-and-hope" attack separately from the security strength quoted which is the amount of work an adversary would have to do to produce tags that are guaranteed to verify.
Instead we look to section 5.3.5 where a limit, $2^t$, is set on the number of failed tags required to trigger a resetting event so that the probability of accepting a false tag before resetting is triggered is given by $2^{t-\lambda}$. Systems are invited to determine what an acceptable value of this probability is in order to defend against rare event attacks. No specific advice is given, though values $\lambda=40, 64, 92$ and $t=20, 30, 35$ are given as examples. For other rare event attacks, I've seen $2^{-40}$ and $2^{-64}$ quoted as acceptable levels of risk.
The underlying philosophy is that attacks requiring the attacker to submit large amounts of chosen data to the system are not considered when evaluating the security strength. For example footnote 4 on page 14 includes the lines:
the success of a collision attack [...] would require the collection of at least $2^{80}$ pairs of chosen plaintexts and their corresponding HMAC values. This is an impractical task. So, the collision attack is not considered in this document.
Irrespective of whether or not one accepts this security model, it is the one used by NIST.
-
1$\begingroup$ I think that NIST should specify the strength against existential forgery attack, because this is what a system security designer is interested in. $\endgroup$ Jul 16, 2022 at 5:16