30

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{message})=H(K\oplus\text{opad}\mathbin\|H(K\oplus\text{ipad}\mathbin\|\text{message}))$$ 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?

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

Community
  • 1
fgrieu
  • 131,696
  • 12
  • 284
  • 553
  • 2
    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 07: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
  • For late visitors, NIST does CAVP validations for HMAC-SHA3 now (but the informal test vectors seems to not contain changes): http://csrc.nist.gov/groups/STM/cavp/message-authentication.html#test-vectors – eckes Mar 19 '17 at 09:30

1 Answers1

16

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.

Ilmari Karonen
  • 45,208
  • 5
  • 101
  • 174
  • 1
    @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](http://sponge.noekeon.org/CSF-0.1.pdf) §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](http://keccak.noekeon.org/Keccak-reference-3.0.pdf) §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 06: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 09:01
  • 2
    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 09:03