What kind of attack could one perform if you generate private keys using SHA3(master_key || nonce)?

Question

I'm aware HMAC is more appropriate than SHA3(master_key || nonce), but I do not understand what kind of attack could be performed against that strategy. How could an attacker use this fact to figure out your private keys?

Answer 1

I'm aware HMAC is more appropriate than SHA3(master_key || nonce) [...]

Not in any big way, just in details. If your master_key is a uniform random or pseudorandom key, and the derived keys are required to be pseudorandom, what you want here is a pseudo-random function (PRF) keyed with the master key, and with your nonce as the message. This is why HMAC is often used in this situation—if the compression function of the underlying hash function is a PRF, then HMAC is a PRF as well. The compression functions of SHA-1 and SHA-2 are conjectured to be PRFs.

If master_key's size is fixed, then SHA-3(master_key || msg) is also conjecturally a PRF. The Keccak team's paper on cryptographic sponge functions vouches for this usage (p. 20):

3.1.2 Keying

One can turn a sponge function into a keyed function by including in the input a secret key $K$. In its most simple form, $M$ consists of the concatenation of a key $K$ and an input $M'$, so either $M = K\|M'$ or $M = M'\|K$. Traditionally, such a function is called a pseudo-random function (PRF) $F_K(M')$. If the sponge function behaves like a random oracle, the PRF behaves as a random function to anyone not knowing the key $K$ but having access to the sponge function. The key can be put before or after the message. Putting it before allows state precomputation (see Section 3.1.3) and results in better resistance against generic attacks.

But the thing that HMAC does that the simple SHA3(master_key || nonce) doesn't is it pads the key to fit a whole block, which unambiguously delimits the key from the message and thus allows for variable length keys and precomputation. The Keccak authors agree with this approach and recommend it as well:

3.1.2 State precomputation

A sponge function processes its input $M$ in blocks of $r$ bits. One may apply some form of padding in the formatting of the input to pre-compute state values. For example, if in a keyed sponge the key $K$ is padded to a complete input block, one can compute the state value obtained after absorbing the key and store this. When evaluating the keyed sponge for this particular key $K$, one can start directly from the stored state value, saving a call to $f$.

NIST just recently finalized SP 800-185 ("SHA-3 Derived Functions"), which specifies a function called KMAC that implements this pad-and-prepend paradigm. In addition, KMAC:

1. Is based on the SHAKE functions (the SHA-3 extendable output length functions) so it can produce outputs of any length you like;
2. Incorporates the output length into the computation so that the same key and nonce produce different results at different output lengths.

So KMAC, if you can find and implementation or write your own (I haven't seen any implementations yet!), is the SHA-3 counterpart to HMAC, and thus KMAC(master_key, nonce, len) would be preferable to SHA3(master_key || nonce).

Answer 2

KDFs

What you are trying to describe are different implementations of a key based key derivation function (KBKDF) which in turn is a specific form of key derivation function (KDF) that uses a key (and not a password).

The attacker would not be able to reverse the hash when using SHA3(master_key || nonce). The reversal could not even happen for SHA-1; the fact that SHA-1 is broken for collision resistance does not matter for this construction. HMAC is more appropriate because a keyed hash / PRF has better cryptographic properties than a hash.

$H(k | c)$ is actually a known KDF called KDF1 or 2 (those just differ in initial counter value $c$). As described here it is probably still secure. However, if you want real, standardized, proven security I'd probably recommend HKDF using SHA-512 as underlying hash. That should be secure until SHA-512 is broken to the extreme.

On HMAC

HMAC protects the underlying hash function against certain attacks. It should always be secure if a large enough key is used and the underlying hash is sufficiently secure - but that's even the case for MD5. HMAC also alleviates length extension attacks for the underlying hash. However, for SHA-3 there should be no length extension attacks possible, so SHA3(master_key || nonce) would not be affected by length extension attacks anyway.

HMAC is rather overkill for SHA-3 as it hashes the key twice after applying two different masks, while the protection it offers is inconsequential to SHA-3. So HMAC-SHA3 could considered an option because the HMAC construction is secure with any sufficiently secure hash. The more efficient KMAC construction is described in SP 800-185 and could be used instead - if it is available in the programming environment anyway.

TL;DR

Now that you know that you need a KBKDF, I suppose it is a good idea to use a well described one. I'd strongly recommend HKDF or HKDF-expand. NIST SP 800-108 has a few more KBKDF's, but NIST standardized HKDF afterwards for good reasons.