Equivalent security of KMAC and different HMAC instances? In the August 2016 draft of SP 800-185, SHA-3 Derived Functions (pdf) there is a table for equivalent security settings for KMAC, the MAC derived from SHA-3, and some previous MACs (Table 1 on pages 19-20). According to that table, both HMAC-SHA256 and HMAC-SHA512 have security equivalent to that of KMAC256, just with two different output lengths – 256 and 512 bits, respectively.

Why is this?

According to SP 800-107 (pdf, see 5.3.4) HMAC-SHA512 can have up to 1024-bit security if the key is exactly that long, while HMAC-SHA256 tops out at 512 bits.

Does KMAC256 really match the security of HMAC-SHA512? And if KMAC256 is meant to have that security, would KMAC128 not be sufficient to match HMAC-SHA256? What is the actual security strength of these KMAC variants?
Yep, this is confusing indeed!  I think you're misreading SP 800-107.  If we go back a little bit from the part you refer to, to section 5.3.1, we have this (p. 13):


  The security strength provided by the HMAC algorithm depends on the security strength of the HMAC key, the underlying hash algorithm and the length of the MacTag.


Now, you've focused on section 5.3.4 ("Security Effect of the HMAC Key", my boldface), which says (p. 14, my boldface again):


  The effective security strength of the HMAC key is the minimum of the security strength of $K$ and the value of $2C$.


Reading this in the context of the first quote I provided, I think that this section is saying that if you use HMAC-SHA-512 with a 1024-bit key, then the effort for a key recovery attack is $2^{1024}$.  But there are other attacks on HMAC-SHA-512 than key recovery.  Since the output length is 512 bits, you can always generically forge a (message, tag) pair in $2^{512}$ attempts with guaranteed success.

So even though HMAC-SHA-512 supports a "security key strength" of up to 1024 bits, the output length always allows a cheaper attack than that.



I'm still confused by section 8.4 of the SP 800-185 draft, though.  They talk about the effects of key size and tag length on the security of KMAC, but they just don't explain how the capacity affects the security.  Earlier in section 4.1 (p. 10) they say this:


  [KMAC128 and KMAC256] differ somewhat in their technical security properties. Nonetheless, for most applications, both variants can support any security level up to 256 bits of security, provided that a long enough key is used, as discussed in Sec. 8.4.1 below.


So apparently the 256-bit capacity of KMAC128 doesn't always translate to a 128-bit cap on its security level.  But on the other hand this text would seem to imply that neither can support security levels above 256 bits, where HMAC-SHA-512 does, and then the equivalence table you point out would be false. (Not that it matters practically, of course—$2^{256}$ is a notably large number.)



The other source that might hold some answers is Bertoni et al's "Cryptographic Sponge Functions" paper, which discusses generic attacks against keyed modes of sponge functions (section 5.1, pp. 50ff).

Now, I'm not going to pretend I understand this one, but I'll highlight the bits that jumped out at me.  Section 5.11.2 (p. 51):


  As in the case of stream ciphers, the adversary can attempt state recovery [of the MAC] using tags. In total she needs at least $b$ bits of output to fully determine the state.


Here $b$ is the width of the sponge construction's transformation—in the case of Keccak, this is 1600 bits, which is longer than the 512 bit output size for the HMAC-SHA-512 replacement suggested in the draft.  Does this mean that the state recovery attacks are impossible, or that they become much more difficult?

They also mention in the same paragraph that if the tag length $n$ is smaller than the sponge's bitrate $r$, the state recovery attack's difficulty is unrelated to the capacity, $2^{b - n}/(m - 1)$ instead of $2^c / (m - 1)$.  In the case of KMAC256, the bitrate is 1088, which is larger than 512.

But they do also mention attacks whose effort is related to the capacity $c$ on p. 52.