1
$\begingroup$

I'm developing a program that uses a hybrid Key Encapsulation Mechanism (KEM) scheme, employing Kyber and X25519, with each producing a 32-byte shared secret. What would be the best scheme to combine these two shared secrets and derive a key for encryption?

I have a few schemes in mind:

  • First scheme:
CONCATENATED_KEY = kyber_shared_secret XOR x25519_shared_secret
ENCRYPTION_KEY = HKDF(CONCATENATED_KEY)
  • Second scheme:
KYBER_KEY = HKDF(kyber_shared_secret)
X25519_KEY = HKDF(x25519_shared_secret)

ENCRYPTION_KEY = KYBER_KEY XOR X25519_KEY
  • Third scheme:
ENCRYPTION_KEY = HKDF(kyber_shared_secret, x25519_shared_secret)

I'm not sure if these schemes are secure, or if there's a better scheme or algorithm to derive a key from two shared secrets or concatenate them.

$\endgroup$
1
  • 1
    $\begingroup$ The Hybrid key exchange in TLS 1.3 Internet-Draft uses concatenation before using a KDF (third scheme I presume, except usually || is the notation). The first scheme also works and is mentioned in an ENISA whitepaper from memory as an alternative, but you don't normally XOR parameters together before hashing. The second scheme should be avoided as there's no KDF. Another (worse) option is to do the classically secure key exchange and then the post-quantum KEM inside that secure channel. $\endgroup$ Dec 2, 2023 at 18:46

2 Answers 2

0
$\begingroup$

One of the best tools for the job is a so-called dual-PRF. That is a pseudo-random function that is secure whether it's keyed normally or by the output. HMAC has been widely used as a dual PRF, although this paper justified its dual-PRF security only recently. Recalling that $$\mathrm{HKDF.Extract}(ikm,salt) = \mathrm{HMAC}(salt,ikm),$$ then scheme 3 is what comes close. But there are some important differences to note:

  • Note that $\mathrm{HKDF}$ takes 4 inputs ($ikm, salt, info, len$); then calls $\mathrm{HKDF.Extract}$ and $\mathrm{HKDF.Expand}$. So, in your notation, this amounts to passing one of the shared secrets as $ikm$ and the other as $salt$.

  • When considering Kyber and X25519, x25519_shared_secret should be a uniform random value; otherwise, the security argument doesn't work here. So, you'll need a first round of $\mathrm{HKDF.Extract}$ on the DH shared value (i.e., the group element) before using the dual-PRF.

  • If you are trying to build a hybrid (authenticated) key exchange (AKE), consider proposals that have received at least some analysis instead. For example, the paper Hybrid Key Encapsulation Mechanisms and Authenticated Key Exchange gives some pointers on converting an AKE to be secure in the hybrid setting.

Concatenation combiner with HKDF. Although this scheme has been proposed often (also your first proposal), I don't know any security analysis that justifies its use. Especially when combined with HKDF, it doesn't seem that the security analysis of HKDF is relevant for the security of this scheme.

$\endgroup$
2
$\begingroup$

As a rule of thumb, when you're combining two values, there's a risk if a simple relationship between the values can be observed in the combination. In your first two schemes, if kyber_shared_secret = x25519_shared_secret then ENCRYPTION_KEY is a constant. With the first scheme, it's even worse: having equal bits in the two shared secrets means that those bits cancel out. This can exacerbate the consequences of partial breakage, for example through a side channel or through fault injection.

The first scheme is also fragile for a non-security reason: it only works if the two shared secrets have the same size. You can't tune the parameters of the scheme, for example to use a different curve.

The third scheme is probably ok in practice because HKDF is very robust (for fixed-size inputs) and all of its inputs contribute to the indistinguishability of the results. (HKDF has three inputs and you don't specify which inputs you're passing, but for HKDF this doesn't really matter.)

But a more mainstream way to combine secrets would be to concatenate them and use the result as the secret of a variable-secret-size key derivation function.

ENCRYPTION_KEY = HKDF(secret=kyber_shared_secret + x25519_shared_secret)

(+ is simple concatenation, which is fine here since the two sides have a fixed length. Note that if both sides were variable-length, you would need extra work to make the combination unambiguous.)

I can't think of a reason to prefer any of your proposals over this one.

$\endgroup$
8
  • $\begingroup$ Do you know of any security analysis that supports the concatenation as a good/robust combiner? AFAIK, the security proof of HKDF doesn't really support this much less in the context on an AKE. $\endgroup$ Dec 3, 2023 at 17:30
  • $\begingroup$ @MarcIlunga Why would it not be a good combiner? HKDF-Extract is equivalent to HMAC (with an optional salt), and concatenation is the standard way of hashing more data. $\endgroup$ Dec 3, 2023 at 21:01
  • 1
    $\begingroup$ @samuel-lucas6, I should probably start by saying that I don't expect any practical issue with this construction. My point is that I am not convinced, any security analysis currently supports this combiner. But I am happy to get pointers! In the context of (authenticated) key exchanges, a robust combiner must be secure, even assuming the attacker may know or influence on of the secret. The original security analysis of Krawczyk does not make any claim for such a scenario. $\endgroup$ Dec 3, 2023 at 21:21
  • 1
    $\begingroup$ One use case for HKDF.Extract as a combiner is because it's known to be a dual PRF. Which provides robust combiner properties. There are other dual PRFs construction, but they are likely too new to be adopted. $\endgroup$ Dec 3, 2023 at 21:24
  • $\begingroup$ @MarcIlunga Yes, that's what I mean. Your point about the dual-PRF security seems to carry to HKDF, although I haven't read that paper. For things like this though, I don't think proofs are that important. If something is being used by major protocol designers, it should be fine. Even Expand without Extract types of KDFs are likely ok in practice. $\endgroup$ Dec 4, 2023 at 8:28

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.