1
$\begingroup$

I am designing a Hybrid Key exchange library using x25519 and Kyber, and the scheme I have in mind is as follows:

Alice sending a file/message to Bob:

Bob's Kyber public key + Random Data -> KEM => ciphertext, Kyber shared secret
Bob's Ed25519 public key + Alice's Ed25519 Secret Key + Kyber ciphertext -> X25519 => x25519 shared secret
Kyber shared secret + X25519 shared secret -> KDF => encryption key

Alice encrypts the file/message using the encryption key and sends it to Bob with the Kyber ciphertext.

Bob receiving a file/message from Alice:

Kyber ciphertext + Bob's secret key -> KEM => Kyber Shared Secret
Bob's Ed25519 secret key + Alice's Ed25519 public key -> X25519 => X25519 Shared Secret
Kyber shared secret + X25519 shared secret -> KDF => decryption key

Bob decrypts the message using the decryption key.

To simplify the restoration of these keys, I wanted to use the Ed25519 secret key (which is 64 bytes) to derive the Kyber key (specified in draft-schwabe-cfrg-kyber). However, if the Ed25519 key is found by a quantum computer, it can be used to derive the Kyber key as well.

Can using a method like BIP32, which uses CKD to derive multiple elliptic curves from a seed, prevent that from happening?

$\endgroup$
3
  • 1
    $\begingroup$ Better have a uniform random key and derive multiple keys from them using HKDF-expand $\endgroup$
    – kelalaka
    Nov 16, 2023 at 12:57
  • 1
    $\begingroup$ I might also go for an ECIES scheme so that two KEM's are used instead of a KEM + Key Agreement. $\endgroup$
    – Maarten Bodewes
    Nov 16, 2023 at 13:39
  • $\begingroup$ Is it intended that your question mentions Ed25519? Are you somehow reusing the keys for Ed25519 and X25519? Or is that what you mean by a 64 bytes secret key? $\endgroup$ Nov 16, 2023 at 21:49

1 Answer 1

2
$\begingroup$

You can usually compress the key generation of a few primitives to the generation of a suitably long secret random seed. Then use a PRG to derive as many seeds as needed. Each resulting seed then feeds the key generation routine of each primitive.

A concrete example would use HKDF to derive two seeds: Generate a random 256-bit seed $s$. Then, produce $$k_1, k_2 = \text{HKDF (s, "unique-info-string", 2)}.$$

$k_1, k_2$ can be used as Ed25519 secret key and the key generation seed for Kyber. You could use another round of HKDF to generate the two seeds used in the key generation of Kyber, as described in the draft you've linked.

Not that, in this case, you don't need the full power of HKDF. HKDF-Expand is sufficient.

$\endgroup$
3
  • $\begingroup$ I want to make something like PGP or minisign, so i don't want to generate a new keypair everytime, everyone would have a unique and static keypair and that would be their identity, the seed is to make the restoration easier, in this scenario can i use a XOF (like Shake256) to derive the seeds for Kyber and Ed25519? the seed is 128bytes and the Kyber needs 64byte seed and Ed25519 needs 32bytes seed so i will pass the master seed to a XOF and get a 64bytes and 32bytes seeds from it. Does using HKDF have any advantages in this case? $\endgroup$ Nov 18, 2023 at 10:25
  • $\begingroup$ @ZolaGonano For the specific choice of the XOF, HKDF and Shake achieve basically the same thing. There are a two-potential advantages of HKDF in this case: 1) "Domain separation" in the sense that shake is already used in Kyber so using a different primitive easily achieves this best practice. 2) Being a bit pedantic about the security guarantees. HMAC is believed to be a PRF, therefore; although I said we need a PRG, HMAC does the job as well. On the other hand, a XOFs doesn't necessarily need to provide PRG like security guarantees. Nonetheless, we expect SHAKE to work as a good PRG. $\endgroup$ Nov 20, 2023 at 9:42
  • $\begingroup$ So I guess, in the end, the question is: Why do you want to use a XOF for the task? What kind of tradeoffs are you considering. Finally, I am still confused as to why you mention Ed25519 while the question is about hybrid key exchange. $\endgroup$ Nov 20, 2023 at 9:45

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.