Recommended key lengths for BLAKE2b

Question

RFC 7693 provides the following table of standard parameter sets for BLAKE2b without a key (where nn is the hash size in bytes):

|             | Collision | Hash |
| Algorithm   |  Security |  nn  |
+-------------+-----------+------+
| BLAKE2b-160 |   2**80   |  20  |
| BLAKE2b-256 |   2**128  |  32  |
| BLAKE2b-384 |   2**192  |  48  |
| BLAKE2b-512 |   2**256  |  64  |

However, for BLAKE2b with a key it only notes that the key length kk must be in the range 0 <= kk <= 64 bytes. The BLAKE2 documentation doesn't seem to provide any more detail.

In RFC 2104, the definition of HMAC includes specific recommendations for the key length (where B is the block length and L the length of hash outputs of the hash function H):

The key for HMAC can be of any length (keys longer than B bytes are first hashed using H). However, less than L bytes is strongly discouraged as it would decrease the security strength of the function. Keys longer than L bytes are acceptable but the extra length would not significantly increase the function strength.

Questions:

1. What are the recommended combinations of key length and output length for BLAKE2b as a MAC to get the usual 128-/256-bits of security?

2. What is a good way to estimate the bits of security provided by other combinations?

3. What is some good reading material that covers questions like this, since the audience of the RFC is clearly assumed to know such things?

Answer 1

The Analysis of BLAKE2's Modes of Operation paper gives a PRF bound for keyed BLAKE2b with a key of size $k$, under the assumption that the underlying block cipher is ideal (Corollary 3): $$ \text{Adv}^{\mathrm{PRF}}_{\text{BLAKE2b}}(\mathcal{D}) \le \frac{q^2}{2^{1024}} + \frac{2q^2}{2^{512}} + \frac{q}{2^{256}} + \frac{q}{2^k}\,. $$ Here, $q$ is the complexity of the distinguisher, i.e., calls to the hash function.

Given this PRF bound, the MAC security of BLAKE2b with output size $t$ can be derived as $$ \text{Adv}^{\mathrm{MAC}}_{\text{BLAKE2b}}(\mathcal{D}) \le \frac{q^2}{2^{1024}} + \frac{2q^2}{2^{512}} + \frac{q}{2^{256}} + \frac{q}{2^k} + \frac{q_v}{2^t}\,, $$ where $q_v$ represents the number of forgery attempts.

Seeing this, two things look clear:

• It is pointless to have a key over $256$ bits, since security begins degrading by other means by that point.

• The tag size influences the probability that a forgery succeeds; thus, it cannot be small enough that an attacker can succeed 'by chance'.

All in all, the same recommendations for HMAC also apply to keyed BLAKE2. A 256-bit key with a 128-bit tag seems like a reasonable choice for most purposes.