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

[Mike Ounsworth <[e-mail]>]

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.

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?


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.

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

iQIzBAEBCAAdFiEE3zFKr4OUJ0GHtLDCQlNDNDsJayMFAmFByYgACgkQQlNDNDsJ
ayNu1w//W3mJD9LJ43KxEVv0t9etwv1Rw21ztRmb0biWskF1JJkxZIUmXBdb7MS9
Sct7czMb/oNL/jrFqbiAHREwI2M5CVQ88v2YIGvA7T562amU3NBH/HbHZSwReByB
nQlV+JmEEovHM75pasOEUGAYBVLG3smbRSNl0rQqk0hvCUPpWfuXxyVuxCYzaGu7
XxvhfU0RSCE/e76xzf90WQQn1IylH8tCKrXST5+x+pxk2W2MkyNVzOqTBg7sycdg
YJLLyK4aHm7emrlh6xOxSCVKVqsxKzGNV8/TRo/lvd3zhjTj6Ij5pLctBIgSHeA4
rGSjqviKrMmFErnX3OeXgkPDNebQpxL0nrO7+vyJspzJ1C4SM2XQzvewjUSCa0gS
163eQI+ufvbEBp48BqGNcnrYPgjs+CIKvbcK4a5ETbtCT9HG+chED4v62x261YKw
q6c6/1kEbd1hS3raaWKFEmhned2JP5WTGTu5/PARvA4hTqEaxnujBEF8qja3jz4Q
NIwXSjtuOQGe+XVpNDGIYSCXDMWNSCdaDTXCuWuiWwYUvb5jad+qSpQCpnEe9AKB
pQPgEV2Z0eIUB5FRBQwy27/ZWHzmL/VnJwb5MtuNg2cBNw+TBYCdaNo8KV1uTeRP
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.