3
$\begingroup$

While having a discussion about the future of Keccak in our library, we came to the discussion of how to properly assign a "block size" to Keccak (or more generally any sponge-based hash if possible), especially for use with HMAC (mostly out of API compatibility reasons).
The block size itself is a phenomen from the days when Merkle-Damgard hashes were the hash-functions of choice (such as MD5, SHA-1, SHA-2) and the HMAC security proof relies on the fact that the key is padded to at least a full block size and thus the block size requirement can't be eliminated from the HMAC interface.

So what's the cryptographic standard / recommended practice to assign a block size to Keccak (or a sponge-based hash)?

$\endgroup$
  • $\begingroup$ Lol... the first hit when I did a quick search. $\endgroup$ – jww Sep 19 '16 at 21:12
6
$\begingroup$

The "block size" matters for Merkle-Damgård functions because the HMAC security proof relies on that block size. For other functions, and in particular sponge functions, the block size for HMAC is mostly a matter of convention.

In fact, HMAC uses two nested calls to the function because such a construction is more or less needed to ensure security with MD function. This is widely considered to be a flaw in the Merkle-Damgård construction. Sponge functions are supposed not to have that flaw, so a simple $H(K || M)$ should be a secure MAC (assuming a proper definition for the concatenation to avoid ambiguities).

So why HMAC is not formally needed to make a MAC out of a sponge function, it can still be used, and any "block size" will work, with no problem to security. The only constraint is that the block size must be larger than the hash function output size, because HMAC mandates that when the key is longer than the block size, the hash of the key is used instead; this cannot work if the block size is smaller than the hash output.

In the case of Keccak, the submission package states in section 5.1.1:

Several standards that make use of a hash function assume it has an input block length and a fixed output length. A sponge function supports inputs of any length and returns an output of arbitrary length. When a sponge function is used in those cases, an input block length and an output length must be chosen. We distinguish two cases.

  • For the four SHA-3 candidates where the digest length is fixed, the input block length is assumed to be the bitrate r and the output length is the digest length of the candidate n ∈ {224, 256, 384, 512}.

  • For an instance with variable-length output, the output length n must be explicitly chosen to fit a particular standard. Since the input block length is usually assumed to be greater than or equal to the output length, the input block length can be taken as an integer multiple of the bitrate, mr, to satisfy this constraint.

And then, in section 5.1.3:

HMAC [1, 25] is fully specified in terms of a hash function, so it can be applied as such using one of the Keccak candidates. It is parameterized by an input block length and an output length, which we propose to choose as in Section 5.1.1 above.

Apart from length extension attacks, the security of HMAC comes essentially from the security of its inner hash. The inner hash is obtained by prepending the message with the key, which gives a secure MAC. The outer hash prepends the inner MAC with the key (but padded differently), so again giving a secure MAC. Of course, it is also possible to use the generic MAC construction given in [6], which requires only one application of the sponge function. From the security claim in [12], a PRF constructed using HMAC shall resist a distinguishing attack that requires much fewer than 2c/2 queries and significantly less computation than a pre-image attack.

So, in the case of Keccak (thus, presumably, SHA-3 too), the "block length" for HMAC is to be $1600 - 2x$, where $x$ is the hash output length, in bits (the "bitrate" and the "capacity" are such that their sum is $1600$, and the capacity is twice the hash output length).

$\endgroup$
  • $\begingroup$ capacity = 2 * output-size holds for SHA-3, but not SHAKE. $\endgroup$ – CodesInChaos Sep 10 '16 at 20:59
  • $\begingroup$ As the Keccak designers explain, they don't actually define the input block length for a variable-length output, except that it should be a multiple of the bitrate. I am not aware of any accepted, widespread convention for use of HMAC with SHAKE. $\endgroup$ – Thomas Pornin Sep 10 '16 at 21:03
4
$\begingroup$

Iterated hashes generally accumulate a fixed amount of data and then call a compression function (or a permutation in the case of sponges) on this data together with a chaining-value. The block size is how much data you can absorb between each such compression.

For sponges the input of the permutation consists of two parts. In one, whose size is called the capacity, you only use the output of the previous permutation. In the other you xor together the data and the output of the previous permutation. The block-size is the size of the latter part, where you inject the data.

=> BlockSize = PermutationSize - Capacity

For HMAC you want an empty accumulation buffer when you start absorbing data. This means you invoked the permutation right before that point. This is consistent with the above definition of block-size.


In theory the block-size of the first block could be different from later blocks, but that's not the case for SHA-3. HMAC would then use the size of the first block.

$\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.