2
$\begingroup$

We know that CRYSTALS-KYBER's KEM (key encapsulation mechanism) key generation algorithm is:

Output:

  • Public key pk $\in B^{12\cdot k\cdot n/8+32}$,

  • Secret key sk $\in B^{24\cdot k\cdot n/8+96}$

  1. $z \leftarrow B^{32}$ (32-byte string)

  2. $(pk, sk′) =$ Kyber.CPAPKE.KeyGen()

  3. sk $=$ (sk$\||$pk$\||H$(pk)$\||$z) (here $H$ is a hash function with 256-bit output)

  4. return (pk, sk )

My question is why pk is considered to be a part of sk? Also, why $H(pk)$ is considered to be a part of sk. Since $H$ is in public domain and also pk is in public domain, what is the logic behind this? Consequently, the final size of sk includes the size of pk.

$\endgroup$

2 Answers 2

4
$\begingroup$

@DannyNiu is correct in noting that the public key is a necessary part of the ML-KEM.Decaps_internal, but the reason why this should be protected in the same way as the secret key has additional subtleties.

What the values mean mathematically

Firstly, we note that in the idealised (M)LWE set-up $A\mathbf s+\mathbf e =\mathbf t$, the value sk (written $\mathrm {dk_{PKE}}$ in the standard) corresponds to $\mathbf s$ and the value pk (written $\mathrm {ek_{PKE}}$ in the standard) corresponds to $\mathbf t$. We note that the value $\mathbf s$ is sufficient information to recover execute K-PKE.Decrypt which is the core functionality, just as the the $\mathbf t$ is sufficient (with additional random value $r$) to execute K-PKE.Encrypt for a given payload $m$. We also note that $\mathbf s$ alone is insufficient to recreate $\mathbf t$.

Binding derived keys to the public key

Taking this observation further, we note that the private key $\mathbf s$ can be associated to multiple public keys $\mathbf t'$ by generating multiple different $\mathbf e'$ values. Indeed, an adversary has a high probability of generating a legitimate alternative public key by adding a smattering of $\pm 1$ values to the actual $\mathbf t$. Even if the key could not be legitimately generated, there are no checks on either side to validate that the key generation process has been followed legitimately. This gives adversaries the chance to probe the encapsulation/decapsulation method by modifying $\mathbf t$. With more aggressive perturbations, this could allow failure boosting attacks. To defend against these, the designers bind the shared key $K$ to the "correct" $\mathbf t$ value by including $H(\mathrm{ek_{PKE}})$ in the derivation used by both sides (as seen in the functions ML-KEM.Encaps_internal and ML-KEM.Decaps_internal).

Protecting the decapsulator's version of the public key

It is important therefore that the decapsulator protects the a copy of the legitimate hash of the public key from modification. If they depend on an external public source for the value of H(pk), this external source could be modified by an adversary and the above error-boosting attack could be applied. Moreover, they should also protect the value pk itself as an adversary taking the role of the encapsulator could generate an encapsulation based on a different $\mathrm t'$ and produce a $K$ bound to the legitimate H(pk) (unless the decapsulator checks the hash, which they are not required to do). It is true that the decapsulator could simply store pk and rederive H(pk) with each key establishment; this would trade-off secure storage with computation.

TL;DR

If the decapsulator does not preserve a copy of their legitimate private key, they run the risk of public key modification by the adversary which can then be used to conduct failure-boosting attacks.

Moral

There are lots of ways to shoot yourself in the foot with lattice-based cryptography; don't mess with the designs in search of efficiencies unless you really know what you're doing.*


$\endgroup$
1
  • $\begingroup$ +1 for "be careful even if you think you know what you're doing" $\endgroup$
    – poncho
    Commented Sep 10 at 11:18
2
$\begingroup$

Kyber/ML-KEM re-encrypts the decrypted ciphertext to confirm that it's not a corrupt ciphertext aimed at attacking the user of the private key (through decryption failure amplification or other mean). This is part of a form of Fujisaki-Okamoto transformation, and helps achieving IND-CCA.

$\endgroup$

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.