[openpgp] Aligning KEM combiner in OpenPGP and LAMPS

[Aron Wussler <[e-mail]>]

Hi everyone,

This thread sparks from an open MR [1] from Mike, and a brief sync we had between the authors after IETF 121.

Our problem statement in short: our KEM combiner is SP800-108 based, and this is not okay for FIPS compliance because we use X25591 and X448 in the construction. At IETF 121 it was suggested to align it with LAMPS, given that draft-ietf-lamps-pq-composite-kem has a FIPS-compliant SHA3 combiner based on SP800-56C.

The PR [1] changes the combiner to the following construction:

SHA3-256(mlkemKeyShare || ecdhKeyShare || ecdhCipherText || ecdhPublicKey || domSep)

Now, this is missing the algorithm ID, but added that it would fit most of the criteria expressed on the list in the past [2]:
 ✓ Compliant with NIST SP800-56C, as a one-step function (as in section 4, omitting the counter).
 ✓ Having the ML-KEM first, and therefore appearing as a key derivation for ML-KEM, with X25519/448 as part of the "fixedInfo".
 ✓ Using SHA3-256 (approved hash in FIPS 202).
 ✓ Having a trailing domain separation.
 ✗ Containing the ML-KEM public key and ciphertext.

Regarding the last point, that's the only one not met, we had extensive discussion on the OpenPGP list and it seems like there are some voices for including those[2]. We had decided to err on the safe side, and include those. Now, this is not set in stone, and can be changed if the list wishes to.

In order to have a single construction that works, I would propose the following concrete options:

1a.  KDF(mlkemSS || tradSS || CT || PK || Domain)
      where CT = "tradCT" and PK = "tradPK" for LAMPS, and CT = "mlkemCT || tradCT" and PK = "mlkemPK || tradPK" for OpenPGP

1b.  KDF(mlkemSS || tradSS || CT || Domain)
      where CT = "tradCT" and Domain = "tradPK || Domain" for LAMPS, and CT = "mlkemCT || tradCT" and Domain = "algID" for OpenPGP, and we drop PKs in OpenPGP (needed according to [3], and we already have "tradPK" in the ECDH KDF deriving tradSS)

2a. KDF(mlkemSS || tradSS || tradCT || tradPK || Domain)
      where Domain is "Domain" for LAMPS, and "mlkemCT || mlkemPK || algId" for OpenPGP

2b. KDF(mlkemSS || tradSS || tradCT || Domain)
      where Domain is "tradPK || Domain" for LAMPS, and "mlkemCT || algId" for OpenPGP, and we drop "mlkemPK" in OpenPGP (same as 1b, not needed according to [3])

2c. KDF(mlkemSS || tradSS || tradCT || tradPK || Domain)
      where we drop mlkemCT and mlkemPK in the OpenPGP construction, fully aligning to LAMPS. Note that this would imply re-writing the security considerations, and while this has been proven safe for X-Wing, there are differing opinions on the security of this with ML-KEM 1024.

All the options with KDF being SHA3-256 only for all options in OpenPGP (LAMPS allows also HKDF-SHA256).

Out of these concrete instantiations, I would like to know if there is any preference or if you see any issue. It would be ideal if we could align (modulo different "Domain" definition) with both draft-ietf-lamps-pq-composite-kem and draft-ehlen-openpgp-nist-bp-comp (that at the moment points to the main pqc draft for the KEM combiner).

Cheers,
Aron

[1] https://github.com/openpgp-pqc/draft-openpgp-pqc/pull/159
[2] https://mailarchive.ietf.org/arch/msg/openpgp/HP5uSF4X1bYyuGOMOHed42mH6aQ/
[3] https://doi.org/10.1007/978-3-319-76578-5_7

--
Aron Wussler
Sent with ProtonMail, OpenPGP key 0x7E6761563EFE3930