3
$\begingroup$

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?
$\endgroup$
4
  • $\begingroup$ SHA-3 can and is combined with HMAC and HKDF, but it's less efficient than KMAC. KMAC can be used for key derivation like HMAC, but you're not including the public keys at the moment, and how is the random sequence being sent securely? You'd probably be better off hashing the shared secret concatenated with both public keys and using that as the key. The context string should also be more unique than that (e.g. [application] [timestamp] [purpose]). $\endgroup$ Oct 28, 2022 at 7:49
  • $\begingroup$ Would it be problematic to send the random sequence in plaintext? That is what I meant. If Mallory does have $n$ (in addition to $256$ and $\text{"KDF"}$) — but not $R_{AB}$ — wouldn't $n$ still be completely useless? As far as I know, she couldn't use it to calculate the derived key or anything like that. $\endgroup$ Oct 29, 2022 at 1:43
  • $\begingroup$ Also, you say "The context string should also be more unique than that," which is an interesting point. Do you happen to have a citation for that (perhaps some part of NIST SP 800-185 that I didn't see)? $\endgroup$ Oct 29, 2022 at 1:45
  • 1
    $\begingroup$ What you're doing is basically the Extract step of HKDF, with the random sequence as a non-secret salt. That's fine; the attacker won't know the shared secret. However, having a salt may be unnecessary depending on how you're doing the key exchange (e.g. if there are ephemeral keys involved). As for the context string, it's just better practice to have something unique to the application. The format I used there is a BLAKE3 recommendation. 'KDF' is fine but could be better. $\endgroup$ Oct 29, 2022 at 8:42

2 Answers 2

4
$\begingroup$
  1. Does my logic in the explanation make sense?

HMAC is a technique for constructing Pseudo-Random Functions (PRF) from the cryptographic hash functions. It achieves this with the use of a key and which is loosely called keyed-hash.

HKDF uses HMAC in the expanding and extracting step as PRF and can be used to derive multiple keys easily. The security of the expanding step based on PRF and any secure randomness extractor can be used in extracting step.

The prefix-PRF function $F_k\colon m \mapsto H(k \mathbin\| m)$ is conjectured to be PRF and this was the design goal of SHA-3. NIST designed KMAC as MAC with some domain separation.

KMAC is a PRF (conjectured), so one can just replace HMAC with KMAC. KMAC is faster to achieve PRF since it doesn't need to use double hashing as in HMAC (remember length extension attack on prefix construction)

Also, the encodings of points of an elliptic curve are not uniform. To derive a cryptographic key from the output of ECDH, hashing with a cryptographic hash function is always advised.

  1. Is $S_{AB}$ secure for use as an encryption key or the key for a MAC?

Well, as said in the comments, add more context to hashing/PRF including the context by concatenating; public keys, time stamps, purpose, application, etc.

  1. Is there any simple improvement that could make this algorithm more secure?

The context advice in 1 and use HKDF with KMAC. Now, HKDF is in TLS 1.3. and it is well-established. Also, one can derive an initial key with ECDH+KDF and then derive multiple keys with HKDF just by changing the info parameter. Just call expand again and again on the initial key.

This can be done with the $S$ parameter of KMAC, too. I don't see a danger there.

$\endgroup$
9
  • $\begingroup$ Nice answer. "HKDF uses HMAC in the expand and extracting step as PRF", if I am not mistaken, HMAC in extract is more of an extractor rather than a PRF since we don't have a key yet... Or do you mean PRF in the sense of PRF-ODH, which is sometimes used in analysis of TLS handshake? $\endgroup$ Oct 28, 2022 at 11:29
  • $\begingroup$ That was referring to section 6 of the HMAC paper. The aim of extract step is outputting a pseudo-random key $\endgroup$
    – kelalaka
    Oct 28, 2022 at 12:04
  • $\begingroup$ Section 6 of the paper states that the security of HKDF requires both PRF and Extractor security. So, it isn't very clear (for me, at least) to see the PRF security in the context of Extract. Hence the question, if we rely on PRF security of Extract, then the Extract step doesn't seem to be strictly necessary. $\endgroup$ Oct 28, 2022 at 12:14
  • 1
    $\begingroup$ And the update looks good to mew ;) $\endgroup$ Oct 28, 2022 at 12:48
  • 1
    $\begingroup$ FYI: I've added an answer where KMAC is directly used as KDF, as specified by NIST in SP 800-108Ar1, which was actually already published at the time of this writing. $\endgroup$
    – Maarten Bodewes
    Mar 7, 2023 at 22:09
2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ PS If anybody of NIST reads this: please give functions a name and assign them an OID. Just indicating that a function is secure is not enough. I guess that at least the parameter order is well defined this time, so there has been progress in this regard. $\endgroup$
    – Maarten Bodewes
    Mar 7, 2023 at 22:12
  • $\begingroup$ Nice. Thanks. I'll read it more when I've time.. $\endgroup$
    – kelalaka
    Mar 8, 2023 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.