[openpgp] algorithm specification for PQC

[Falko Strenzke <[e-mail]>]

Dear all,

in the context of the joint efforts of Proton and BSI/MTG regarding the 
integration of PQC into OpenPGP we identified two design options that we 
would like to discuss with the community. For this purpose we currently 
assume that we introduce Kyber as a PQC-KEM in a composite algorithm 
combination with ECDH, and at least one PQC-SIG (Dilithium and 
potentially also SPHINCS+). For signatures, generally also composite 
combinations with ECDSA and EdDSA would be used, with the possible 
exception of SPHINCS+, which could in our view also be used as a 
standalone scheme.

Regarding the security levels, for now we consider the concrete 
combinations resulting from combining NIST PQC-Security Levels 1,3,5 for 
Kyber and 2,3,5 for Dilithium with the corresponding classical security 
parameters.

The two design options are:

* Option A: Each newly introduced scheme (in most cases a composite 
combination of PQC scheme with a classical scheme, as explained above) 
receives a new algorithm ID. Thus the algorithm ID is the _same_ for 
different curves.
* Option B: Each newly introduced scheme in combination with one curve 
level receives a new algorithm ID. This means that the algorithm ID is 
different for each curve.

***What we would like to learn from the community*** is whether there is 
a clear preference for one of the two choices. Knowing that there is 
such a clear opinion on this question at this early stage would help us 
insofar, as we would then potentially focus only on the preferred one 
and could discard the other.

---

In the following, we give a some more detailed discussion of the two 
choices.

# Option A:

This option would mean to introduce new Algorithm IDs (Cf. §9.1 in 
draft-ietf-openpgp-crypto-refresh-06) for fixed algorithm combinations, 
while the concrete security parameter level would be specified in the 
public key object only (as it is the case currently for all public key 
algorithms in OpenPGP). This would mean that we would have the following 
3 or 4 new algorithm IDs:

1. ECDH + Kyber
2. EdDSA + Dilithium
3. ECDSA + Dilithium
4. (SPHINCS+ standalone)

For the concrete parameters we would follow the current crypto-refresh 
implementation requirements for ECDH (i.e. MUST ECDH with MUST 
Curve25519 and SHOULD X448) and likewise for EdDSA (i.e. MUST EdDSA with 
MUST Ed25519 and SHOULD Ed448), and thus prescribe:

For encryption:

* MUST: Curve25519 + Kyber-Level1
* SHOULD: X448 + Kyber-Level5

For signature:

* MUST: Ed25519 + Dilithium-Level2
* SHOULD: Ed448 + Dilithium-Level5

Any other combination of Kyber/Dilithium with ECDH/ECDSA (with 
NIST/Brainpool curves) would be proposed as MAY, but including 
implementation guidance on the parameter combinations, e.g. saying that 
256-bit curves SHOULD be matched with NIST Level 1/2, 384-bit curves 
with NIST Level 3 and 512/521-bit curves with NIST Level 5.

To summarize: Option A would be normative on the algorithmic 
combinations through the Algorithm IDs and normative on the concrete 
parameter combinations through the implementation requirements via MUST, 
SHOULD, MAY. The advantages being:

- minimal impact on the Algorithm ID space (i.e. essentially one Alg-ID 
per Kyber and 2 Alg-IDs per PQC-SIG)
- apart from the mentioned implementation guidance there is no need for 
explicitly allowing other parametrizations via NIST- or Brainpool-curves 
explicitly
- being immediately able to combine e.g. Curve25519 with Kyber-Level5 
(if higher PQC security level is desired and ECC is considered to hedge 
against stronger future attacks) without the need to update.
- partial reuse of the ECDH/EdDSA/ECDSA definition on the implementation 
side

# Option B:

Option B is normative through fixed Algorithm IDs for concrete algorithm 
combinations+parameters and would, under the above stated assumptions, 
result in the following set of 12 or 13 proposed new algorithm IDs:

  1. X25519 + Kyber-Level1
  2. X448 + Kyber-Level5
  3. ECDH-brainpoolP384r1 + Kyber-Level3
  4. ECDH-brainpoolP512r1 + Kyber-Level5
  5. ECDH-NIST-P384 + Kyber-Level3
  6. ECDH-NIST-P521 + Kyber-Level5
  7. Ed25519 + Dilithium-Level2
  8. Ed448 + Dilithium-Level5
  9. ECDSA-brainpoolP384r1 + Dilithium-Level3
10. ECDSA-brainpoolP512r1 + Dilithium-Level5
11. ECDSA-NIST-P384 + Dilithium-Level3
12. ECDSA-NIST-P521 + Dilithium-Level5
13. (SPHINCS+ SHA-3)

However, in the draft we would certainly describe each combination 
generically as ECDH+Kyber and EdDSA+Dilithium and ECDSA+Dilithium to 
have a uniform packet structure.

Similarly to the other proposal we would keep 1 and 7 as MUST, 2 and 8 
as SHOULD, the others as MAY.

To summarize: Option B would be maximally normative through fixed 
Algorithm IDs for any algorithm+parameter-combination. The advantages being:

- There is absolutely no misunderstanding what the global 
interoperability parameters are.
- It would allow using the native format for X25519 and X448 
specification for the specific combinations.

On the other hand to introduce a new combination we'd have to follow the 
SPECIFICATION REQUIRED method (RFC8126) and update the clients.

Best
Aron, Falko, Stavros