PQC public key format specification

[Werner Koch]

Hi!

Librepgp-00 has some preliminary specifications for the Kyber (ML-KEM)
algorithms.  This has been lifted from draft-wussler-openpgp-pqc-03.txt
by Stavros Kousidis, Falko Strenzke, and Aron Wussler.

There is currently a discussion on the IETF WG list regarding PQC but
given that they ignore the v5 key format entirely we are anyway free to
improve on this draft.

The idea of assigning a separate algorithm id to each variant of the
Kyber does not fit nicely into the PGP model of having an identifier for
the general algorithm and use the parameters to distinguish between
variants.  For example, with RSA the length of the modulus directly
gives the strengths of the algorithm and with the 3 ECC algorithms the
curve name and thus its strength is given by a separate parameter (the
curve's OID).

Right now the Kyber public key is this series of values:

 1. A fixed-length octet string representing an ECC public key in the
    format associated with the curve.  For ML-KEM-768+X25519 these are
    32 octets, for ML-KEM-1024+X448 these are 56 octets.

 2. A fixed-length octet string containing the ML-KEM public key,
    whose length depends on the algorithm.  For ML-KEM-768+X25519
    these are 1184 octets, for ML-KEM-1024+X448 these are 1568 octets.

In contrast an ECDH key is this series of values:

 1. A variable-length field containing a curve OID, formatted as: a
    one-octet size of the following field; values 0 and 0xFF are
    reserved for future extensions, the octets representing a curve OID

 2. A MPI of an EC point representing a public key;

 3. A variable-length field containing KDF parameters, formatted as
    follows: [...]

For Kyber we could just add item 2 to an ECC key and remove the KDF
parameters because they are fixed.  Thus I propose to change the
Kyber public key to:

 1. A variable-length field containing a curve OID, formatted as: a
    one-octet size of the following field; values 0 and 0xFF are
    reserved for future extensions, the octets representing a curve OID

 2. A MPI of an EC point representing a public key;

 3. A four-octet scalar octet count of the followed by an octet string
    containing the ML-KEM public key.  Note that valid octet counts are
    1184 for ML-KEM-768 and 1568 for ML-KEM-1024.

This would be a general framework for Kyber (ML-KEM).  We would then
give a table of valid combinations:

  | Curve  |         OID | ML-KEM-n | requirement |
  |--------+-------------+----------+-------------|
  | X25519 | 1.3.102.110 |      768 | MUST        |
  | X448   | 1.3.101.111 |     1024 | SHOULD      |

The advantages of this scheme is that it allows to introduce other
combinations iff a need ever arises.  Back then when we introduced ECC
with RFC6637, the OID specified curve allowed us to add the highly
demanded Brainpool curves without any problems and even the deployment
of ed25519 and cv25519 went pretty smooth.

Not that I introduced a four-octet scalar count instead of an MPI.  This
count is required for the variants of Kyber and also better fits into
the OpenPGP scheme of storing all parameters with their respective
length.

Given the size of a Kyber key it should not matter whether we use a four
instead of a sufficient two-octet count.  I consider four-octet easier.
Another option would be to use an extended definition of MPI; i.e.,
define a 32 bit MPI (or its Simple Octet String variant).  Using a DER
style length encoding would be more similar to the funny Huffman
encoding of the PGP packet length - but I doubt that anyone likes this.
Keeping the encoding similar to other parameters makes it easier to
re-use existing code.

For the algorithm ID I suggest to use 29 as suggested in the Wussler
draft for ML-KEM-768+X25519 but of course use that also for all other
combinations.  Even if the crypto-refresh folks settle for a different
scheme, we won't run into a conflict because we will use this only with
v5 keys.  Backporting PQC for v4 keys does not make any sense because it
is a new algorithm and, like X448, a new implementation is anyway
required.

The format for the secret key parameter and for the encryption packet
needs to be adjusted similar to the above suggested.  But let us first
finalize the public key format.

The use of the MPIs should be replaced by its extended but compatible
defintion of Simple Octet Strings.  But this is a separate task.


Shalom-Salam,

   Werner


-- 
The pioneers of a warless world are the youth that
refuse military service.             - A. Einstein
-------------- next part --------------
A non-text attachment was scrubbed...
Name: openpgp-digital-signature.asc
Type: application/pgp-signature
Size: 247 bytes
Desc: not available
URL: <https://librepgp.org/pipermail/librepgp-discuss/attachments/20240208/067c9fde/attachment.sig>