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

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 15 Sep 2021 21:32:48 +0000

>    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 feel dense today, so take this with a grain of salt - but it's my understanding that all the NIST PQC KEM finalists "have KDF inside". And their proofs depend on it.

>    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)

Did not look at RFC 5990, so can't comment. 

In case of PQC KEMs, they take care of this issue "under the hood", and provide both peers with the "sanitized" shared secret. Doing the "internal KDF" is necessary for the proofs to hold, and to foil some attacks...

>    .  .  .  whether this is actually how KEM outputs are intended to be used,
>    or if you need to hash them with protocol context values first.

Good question! IMHO, it depends on what you consider "protocol context".

>    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.

IMHO, it might be a good idea to add the complete protocol (not KEM!) context (similar to what TLS is doing for Key Confirmation) to the KDF that intakes the KEM output. In many cases it is unnecessary, but it does not hurt, and doesn't take a whole lot of CPU cycles.

    -----Original Message-----
    From: Spasm <[email-masked]> On Behalf Of Bruckert, Leonie
    Sent: September 15, 2021 5:23 AM
    To: [email-masked]
    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.
    _______________________________________________
    Spasm mailing list
    [email-masked]
    https://www.ietf.org/mailman/listinfo/spasm

---

From: "Markku-Juhani O. Saarinen" <[email-masked]>
Date: Thu, 16 Sep 2021 11:48:45 +0100

From: Mike Ounsworth <[email-masked]>

> 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.
>

Hi Mike and Others,

Yes .. fortunately contemporary (PQC) KEMs do not output such version
bytes; all output bits are significant "full entropy". This is due to the
Fujisaki-Okamoto transform generally used for CCA security and the related
QROM proofs. With "RSA KEMs" things were perhaps a bit different.

If you look at the implementations, the shared secret output is usually
directly from SHA3/SHAKE via the FO transform select logic. This mechanism
is very carefully designed by cryptographers. And as Uri noted, it is a
"part of the algorithm" and KAT test vectors, etc.

On the implementation front, much attention has been paid specifically to
shared secret output due to "decryption failure oracles". Implementations
of a couple of NIST PQC round 3 finalists were broken this way. It is okay
for encapsulation to fail in case of an invalid public key, but
decapsulation "never fails" explicitly, even in case of obviously invalid
ciphertext; a synthetic ("implicit failure") shared secret is generated
instead.

So decapsulation actually produces a "uniform" output even in the case of
nonsense ciphertext. If the shared secret is used with something like AEAD
(for purposes of public-key message encryption/decryption), the decryption
failure occurs only during MAC verification. Having an additional hash or
KDF there is possible, but it needs to be constant time.

Hardware implementations use the SHAKE/SHA3 output to their advantage, as a
masked Keccak module can output the shared secret in masked shares, which
is precisely what one needs for side-channel secure on-chip management of
SSPs.

In software, there's a generic attack on decryption failure oracles (in
shared secret generation).
For timing oracles: https://eprint.iacr.org/2020/743
The algorithm design teams made a bad fix that timing attack.. that allowed
key recovery even without the timing oracle on Round 3 FrodoKem and SIKE
reference implementations.
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/kSUKzDNc5ME/m/EMFYz9RNCAAJ
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/QvhRo7T2OL8/m/4gSe5coAAwAJ
Note that both implementations still passed "normal KATs" that do not have
decryption failures.

So I urge people to avoid messing with the internals of KEMs such as shared
secret generation, ciphertext serialization, or key serialization. I can
almost promise you that an innocent-looking functional "optimization" will
lead to security problems unless you're familiar with the security proofs..

(.. Mike's Kyber and SIKE examples..)

>
> 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.
>

"Full entropy output" is an assumption that we're also making in the
hardware interface designs, and it seems to apply to all relevant NIST
finalist PQC KEM algorithms.

Cheers,
- Markku

Dr. Markku-Juhani O. Saarinen <[email-masked]> PQShield, Oxford UK.