Context

I am trying to build a simple protocol for key derivation. I want to use SHA-3 family hash functions, which (as far as I understand) should not be combined with HMAC because their security properties make HMAC redundant. Thus, HKDF — which uses HMAC — would also be unsuitable for key derivation using SHA-3 family hash functions.

Proposed Protocol

Suppose that Alice and Bob derive a shared secret (e.g., through ECDH) $R_{AB}$, but they want to derive some key material suitable for a symmetric cipher based on this secret. In my proposed protocol, Alice wants to communicate with Bob, so she generates a random sequence $n$ with length $256$ bits and sends this sequence to Bob (assume that Bob and Alice already possess each other's public keys and can therefore derive a shared secret). Alice computes $$ S_{AB} = \operatorname{KMAC256}\left(n,R_{AB},256,\text{"KDF"}\right) $$ where the parameters are ordered as described in NIST SP 800-185 §4.2.

Since Bob also possesses $n$ and can derive $R_{AB}$, he can also perform this computation to get $S_{AB}$.

If a new key is needed, either Alice or Bob can regenerate $n$, and the value of $S_{AB}$ will change to a (seemingly) unrelated value.

Questions

1. Is $S_{AB}$ secure for use as an encryption key or the key for a MAC?
2. Is there any simple improvement that could make this algorithm more secure?
3. Does my logic in the explanation make sense?

TL;DR Yes, you can use KMAC as a KDF, preferably using KMAC as defined in the NIST standard for KDF's.

This has been specified in NIST SP 800-108r1, August 2022, Key Derivation Using Pseudorandom Functions, section 4.4.

Let's quote the relevant part:

In this section, a KDF specification of KMAC#(K, X, L, S) takes the following parameters:

1. $K_{IN}$ - The key-derivation key;
2. $X$ – The context, a bit string containing the information related to the derived keying material;
3. $L$ − An integer specifying the desired output length (in bits) of the derived keying material;
4. $S$ − The label, an optional customization bit string; for example, Label can be an encoding of the characters “KDF” or “KDF4X” in 8-bit ASCII.

$K_{OUT} = KMAC\#(K_{IN}, X, L, S)$.

Here, KMAC# indicates the use of either KMAC128 or KMAC256. For clarity I've removed the remapping of the parameters ($K$ to $K_{IN}$, $S$ to $Label$ etc.).

The presentation on the NIST site by John Kelsey shows how and why KMAC could be used as KDF.

The idea that the bits are dependent on all bits of the input keying material follows from the functionality provided as PRF. Not all MAC's are considered PRF's, but KMAC certainly is.

KMAC was explicitly defined to provide domain separation with SHA3 and SHAKE, domain separation using a configuration string as well as a configurable output size. As such it is perfectly situated to be used as KDF.

Remarks;

• If KMAC is used as a KDF I would strongly recommend that a configuration string $S$ is provided, as that would also mean that calculating a MAC over identical input / output of the same size will not likely generate the same output. NIST recommends to prefix the string "KDF" for domain separation. Of course, reusing a key for separate purposes should be avoided anyway.
• The context $X$ is also the location for an optional nonce. A salt has not been defined, but a salt is identical to a "random nonce". Adding a salt may well increase the security of the function, see the HKDF specifications for more information.
• I'd myself use the label $L$ set to “KCV” to create a key check value, where possible also using a random nonce.

One somewhat trickier property of KMAC is that the output of the function is unrelated if the output size is specified differently. On the one hand it means that it is "more difficult to shoot yourself in the foot" and leak key material. That also means that you cannot use KMAC to generate a stream. For that reason it is probably best to call the function separately for each secret or randomized component such as key and IV.

Fortunately KMAC is relatively efficient, and having separate calls is generally fine. It also works better with e.g. hardware devices; having a KDF spit out both a key and an IV at the same time may be tricky to implement, as the IV is not directly related to the key object.

For completeness I'll include the definition for KMAC so you can see how the parameters are used within the cSHAKE hash functions. I'll not dive into cSHAKE if you don't mind.

KMAC128 and KMAC256 themselves have been defined in NIST SP 800-185, Section 4.3. KMAC128 has been defined as:

1. newX = bytepad(encode_string(K), 168) || X || right_encode(L).
2. return cSHAKE128(newX, L, “KMAC”, S).

for KMAC256 replace 168 with 136 and cSHAKE128 with cSHAKE256.