Re: [lamps] Which PQC KEMs can be used for composite encryption?

["Bruckert, Leonie" <[e-mail]>]

Hi Mike,

Comments inline.

> Hi Leonie, thanks for starting this discussion.
> 
> I guess the Too Long; Didn't Read here is: Can we assume a KDF is always
> included in a KEM encaps(), or do we need to do one explicitly as part of
> composite-encryption?
> 
> I think (but could be wrong) that CCA security is orthogonal to whether the
> KEM output (ie shared secret) can be used directly as a symmetric key, or if it
> needs to be run through a KDF first. For example, I could imagine a KEM that
> outputs an IND-CCA shared secret prefixed with a fixed version byte; you
> can't use that directly as a one-time-pad key because of the fixed version
> byte.

I am not an expert in KEM constructions either, but this sounds plausible.

> 
> That security consideration text is there because we've been struggling to
> understand whether, with the KEM specifications that will be standardized
> by NIST, the KEM would be expected to output a shared secret that can be
> used directly as a one-time-pad (i.e. the bits of the shared secret are a
> random key). If I'm reading your email properly, you're advocating that a
> KEM's output should be hashed together with some protocol-level
> contextual values before it's used?

That is not what I was trying to say. I rather observed that a KDF or hash function is incorporated in the NIST KEMs. I try to explain my thoughts in the next paragraph.

> As an example of a PQC KEM that should work, Kyber (as per the Round 3
> submission docs) has a KDF as the last step of the CCAKEM algorithm:
> K := KDF(K||H(c))
> So, it should be ok to be used directly in our scheme.

Okay, let's take Kyber as an example, but you could easily think of another PQC KEM.
The 'K's in the formula above are actually not the same, so I added a '*' for clarification.

In 
K := KDF(K* || H(c)) 
K is the final key that is returned by Kyber. It may be used directly for encryption. K* is a random value that is chosen by Alice. K* is encapsulated by Alice resulting in a ciphertext. This ciphertext is transmitted to Bob. Bob runs the decapsulation and gets K*. Both Alice and Bob use the KDF to derive the key K.

Now consider a composite encryption scenario where Alice wants to send a message to Bob. 
Bob owns a composite public key consisting of two component keys. Let's assume that the first component key can be used with e.g. Kyber. 

According to the draft, the content encryption key is split into two shares: CEK = S1 XOR S2. This is achieved by generating a random S1 and calculating the second share as S2 = CEK XOR S1.
While writing this, I just noticed that I overlooked the case distinction in the encryption process described in the draft. So, I think I do not have a problem here anymore. In case of KEMs the share is not randomly chosen, but output of the encapsulation (S1 =  K).

Then I am totally fine. Sorry for causing confusion. I misleadingly assumed S1 = K* which is of course nonsense. 

Regards,
Leonie

> The same should be true of SIKE KEM (Round 3 SIKE spec 1.3.11 Algorithm 2
> Encaps) as it also finishes by hashing everything.
> 
> The consensus at the LAMPS interim was to bring these discussions back to
> RSA-KEM (5990). The KEM shared secret Z is not itself IID, so they run it
> through a KDF (by itself) in Step 3 to be able to use it as a KEK.
> KEK = KDF (Z, kekLen)
> WK = Wrap (KEK, K)
> 
> 
> So we have two examples of compatible KEMs, and one that isn't directly but
> could be made compatible. But we're not sufficiently expert in KEMs to know
> if this applies only to some PQC KEMs, to all PQC KEMs, or all KEMs present
> and future. Or, to your point, whether this is actually how KEM outputs are
> intended to be used, or if you need to hash them with protocol context
> values first. We believed, from looking at the Kyber and SIKE construction
> that an extra KDF step (and parameter) was unnecessary, but we're happy to
> add it if it improves security or makes this mode more generally applicable to
> more KEM primitives.
> 
> I am eager to hear from people more expert than myself in KEM
> constructions :)
> 
> ---
> Mike Ounsworth
> 
> -----Original Message-----
> From: Spasm <[e-mail]> On Behalf Of Bruckert, Leonie
> Sent: September 15, 2021 5:23 AM
> To: [e-mail]
> Subject: [EXTERNAL] [lamps] Which PQC KEMs can be used for composite
> encryption?
> 
> WARNING: This email originated outside of Entrust.
> DO NOT CLICK links or attachments unless you trust the sender and know the
> content is safe.
> 
> __________________________________________________________
> ____________
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
> 
> Hi,
> 
> I recently looked into the composite encryption described in draft-
> ounsworth-pq-composite-encryption, in particular option 2 (encryption and
> KEMs).
> 
> If I understood correctly, the data encryption key is split into at least two
> shares, each being encrypted/encapsulated under the respective
> component public key.
> 
> I was wondering which PQC KEMs can be used with this mode. A
> requirement mentioned in the draft is that
> 
> "all component KEMs MUST produce a shared secret whose bits are
> independent and uniformly distributed (aka "uniformly IID"
> or "uniformly random" or "full entropy") and therefore the shared secret is
> safe to use directly as a symmetric key."
> 
> As far as I know, the NIST candidates are IND-CCA secure KEMs where the
> value being encapsulated is not directly used as shared secret. Instead it is
> fed into a hash function together with some other values (e.g. the public
> key) in order to receive the shared secret. Thus, I would conclude that these
> KEMs are not qualified.
> 
> So my question is: Do we know any PQC KEM that can be used with this
> mode?
> 
> If I use KEMs in a composite encryption mode, I certainly want them to be
> CCA secure so I can use the public key multiple times. Otherwise it won't
> make sense to put them in a certificate.
> 
> Please clarify if I am wrong with my thoughts.
> 
> Regards,
> Leonie
> -----BEGIN PGP SIGNATURE-----
> Comment: Using gpg4o v6.0.124.9651 - https://www.gpg4o.de/
> Charset: utf-8
> 
> iQIzBAEBCAAdFiEE3zFKr4OUJ0GHtLDCQlNDNDsJayMFAmFByYgACgkQQlNDN
> DsJ
> ayNu1w//W3mJD9LJ43KxEVv0t9etwv1Rw21ztRmb0biWskF1JJkxZIUmXBdb7
> MS9
> Sct7czMb/oNL/jrFqbiAHREwI2M5CVQ88v2YIGvA7T562amU3NBH/HbHZSwRe
> ByB
> nQlV+JmEEovHM75pasOEUGAYBVLG3smbRSNl0rQqk0hvCUPpWfuXxyVuxCY
> zaGu7
> XxvhfU0RSCE/e76xzf90WQQn1IylH8tCKrXST5+x+pxk2W2MkyNVzOqTBg7syc
> dg
> YJLLyK4aHm7emrlh6xOxSCVKVqsxKzGNV8/TRo/lvd3zhjTj6Ij5pLctBIgSHeA4
> rGSjqviKrMmFErnX3OeXgkPDNebQpxL0nrO7+vyJspzJ1C4SM2XQzvewjUSCa0
> gS
> 163eQI+ufvbEBp48BqGNcnrYPgjs+CIKvbcK4a5ETbtCT9HG+chED4v62x261YKw
> q6c6/1kEbd1hS3raaWKFEmhned2JP5WTGTu5/PARvA4hTqEaxnujBEF8qja3jz4
> Q
> NIwXSjtuOQGe+XVpNDGIYSCXDMWNSCdaDTXCuWuiWwYUvb5jad+qSpQCp
> nEe9AKB
> pQPgEV2Z0eIUB5FRBQwy27/ZWHzmL/VnJwb5MtuNg2cBNw+TBYCdaNo8KV
> 1uTeRP
> ASCIAvecw7809QAx4okUChvIBR/25qBJkGthNOLXnA9mqzINdGw=
> =Bqt8
> -----END PGP SIGNATURE-----
> Any email and files/attachments transmitted with it are confidential and are
> intended solely for the use of the individual or entity to whom they are
> addressed. If this message has been sent to you in error, you must not copy,
> distribute or disclose of the information it contains. Please notify Entrust
> immediately and delete the message from your system.