# How secure would HMAC-SHA3 be?

It would be possible to implement the HMAC construction with (draft) SHA-3, leading to HMAC-SHA3-224, HMAC-SHA3-256, HMAC-SHA3-384, HMAC-SHA3-512 (the last 3 digits are the output size $\ell$, where $\ell/8$ is the $L$ parameter in HMAC). All that's missing to apply the familiar $$\text{HMAC}(K,\text{text})=H(K\oplus\text{opad}, H(K\oplus\text{ipad},\text{text}))$$ is a definition of the block size $b$, where $b/8$ is the $B$ parameter in HMAC. That is necessary to determine the size of $\text{ipad}$ and $\text{opad}$ (and above what size $K$ needs to be replaced by $H(K)$ beforehand). However, the original and improved security arguments/"proofs" of HMAC are made for the Merkle–Damgård structure, and thus do not directly apply to HMAC-SHA3.

How secure would these HMAC-SHA3-$\ell$ be? What does $b$ needs to be for each of the four $\ell$ values? What kind of security arguments/"proofs" can be made?

Would HMAC-SHA3 be any stronger than the generic sponge MAC?

HMAC is briefly discussed in the Keccak submission (section 5.1.3), but I do not understand that a proof is given or a security claim made.

Update: that makes reference to section 5.1.1 which I now read as suggesting that we should have the HMAC blocksize $b$ multiple of the so-called bitrate $r$; thus for output $\ell$ of 224 (resp. 256, 384, 512), $b$ a multiple of 1152 (resp. 1088, 832, 576). That's in agreement with these NIST slides

-
I would assume that the standard HMAC security levels would apply as long as the padded key is a multiple of $r$ and at least as large as $c$. For rates 800 and larger (1600 bit state) that is the case already, but SHA3-512 has a rate of 576, so the "blocksize" would need to be 1152. That would assure the first message bits are absorbed into the state starting at the first bit. – Richie Frame Apr 25 '14 at 7:32
@Richie Frame: the Keccak submission (and NIST slides I just added) seem to use the bitrate $r$ as block size, without the at least as large as $c$ condition that you suggest. I am without informed opinion. – fgrieu Oct 17 '14 at 19:51

## 1 Answer

The Keccak submission says:

From the security claim in [12], a PRF constructed using HMAC shall resist a distinguishing attack that requires much fewer than $2^{c/2}$ queries and significantly less computation than a pre-image attack.

Here, $c$ denotes the capacity of the sponge, i.e. the effective size of the internal state in bits.

Since HMAC is a deterministic iterated MAC (in particular, it does not use a nonce), it is always vulnerable to a generic birthday-based existential forgery attack requiring on the order of $2^{c/2}$ MAC queries (Preneel & Oorschot, 1999).

Thus, the claimed security level of HMAC-SHA3 is the same as the overall maximum attainable security level for HMAC, or any other deterministic iterated MAC construction, with the same effective internal state size.

-
@fgrieu: As far as I can tell, the argument is that Keccak provides this level of security when used with the generic sponge MAC construction (= prepend key to message; CSF §5.11.2), of which the inner HMAC pass can be seen as an instance. That security, in turn, is claimed to follow from the Keccak flat sponge claim (Keccak reference §1.5), which is a pretty strong claim that, loosely speaking, says that Keccak is as good as a random oracle against attacks using $\lll 2^{c/2}$ work. – Ilmari Karonen Apr 26 '14 at 6:16
Reading the quote again, it is a fine claim if we read "shall resist a" as "resists any". I now see how it states a bound on the number of queries of: $2^{c/2-\xi}$ for some moderate $\xi$ with a derivation and $\xi\lll c/2$. Your answer and above comment helped understanding how that comes, thanks a lot! I now see that for HMAC-SHA3-$\ell$ that bound becomes $2^{\ell-\xi}$ queries, which is much better than the $2^{\ell/2}$ queries of the generic attack that you quote and applies to HMAC-SHA-256 and HMAC-SHA-512. – fgrieu Apr 26 '14 at 9:01
However I'm still uncertain about: •A) the computational bound; is that also $2^{\ell-\xi}$ operations? •B) if we have better bound for that with HMAC than with the generic sponge MAC? •C) the importance in bound derivations that the blocksize $b$ is a multiple of the bitrate $r$ (1152, 1088, 832, 576 for $\ell$ of 224,256,384,512), both for HMAC and the generic sponge MAC. – fgrieu Apr 26 '14 at 9:03