gpg: Initial support for generating Kyber subkeys.

* common/openpgpdefs.h (PUBKEY_ALGO_KY768_25519): Remove.
(PUBKEY_ALGO_KY1024_448): Remove.
(PUBKEY_ALGO_KYBER): New.  Use them everywhere instead of the removed.

* g10/build-packet.c (gpg_mpi_write_nohdr): Rename to
(gpg_mpi_write_opaque_nohdr): this.  Change callers.
(gpg_mpi_write_opaque_32): New.
(do_key): Support Kyber keys using the revised format.
* g10/gpg.h (MAX_EXTERN_KEYPARM_BITS): New.
* g10/parse-packet.c (read_octet_string): Add arg nbytes so support
reading with a length prefix.  Adjust callers.
(parse_key): Parse Kyber public keys.
* g10/misc.c (pubkey_get_npkey): Support Kyber.
(pubkey_get_nskey): Ditto.

* g10/keyid.c (pubkey_string): Support dual algorithms.
(do_hash_public_key): Support Kyber.
(nbits_from_pk): Ditto.
(keygrip_from_pk): Return the Kyber part for the ECC+Kyber dual algo.

* g10/keygen.c (struct common_gen_cb_parm_s): Add genkey_result2.
Note that this callback is not yet used.
(ecckey_from_sexp): Add optional arg sexp2 and use it for Kyber.
Change callers.
(ecckey_from_sexp): Do not leak LIST in case of an error.
(common_gen): Add arg keyparms2, change callers, and support Kyber.
(gen_kyber): New.
(get_keysize_range): Support Kyber.
(fixup_keysize): Simplify and support Kyber.
(do_create): Handle Kyber.
(parse_key_parameter_part): Remove algo strings "ky768" and "ky1024"
and add a generic "kyber" with default parameters.
--

This uses a revised format which is more aligned with the usual
OpenPGP structure.  A lot of things are still missing.  For example
support for handling two keygrips and checking both of them in a -K
listing.  There is also only ky768_bp384 as fixed algorithm for now.
No passphrase for the Kyber part of the dual algorithm is on purpose.

A test was done using

  gpg --quick-gen-key pqc1 nistp256

and then running

  gpg -v --quick-add-key <fingerprint> kyber

which creates a v5 subkey on a v4 primary key.  A second test using

  gpg --quick-gen-key pqc2 Ed448

followed by a --quick-add-key created a v5 key with a v5 subkey.

GnuPG-bug-id: 6815

9 files changed, 461 insertions, 110 deletions

diff --git a/common/openpgpdefs.h b/common/openpgpdefs.h
index d8672ac47..bf11d597f 100644
--- a/common/openpgpdefs.h
+++ b/common/openpgpdefs.h
@@ -172,8 +172,7 @@ typedef enum
     PUBKEY_ALGO_ELGAMAL     = 20, /* Elgamal encrypt+sign (legacy).  */
     /*                        21     reserved by OpenPGP.            */
     PUBKEY_ALGO_EDDSA       = 22, /* EdDSA.                          */
-    PUBKEY_ALGO_KY768_25519 = 29, /* Kyber768 + X25519    (aka ML-KEM-768)   */
-    PUBKEY_ALGO_KY1024_448  = 30, /* Kyber1024 + X448     (aka ML-KEM-1024)  */
+    PUBKEY_ALGO_KYBER       = 29, /* Kyber                           */
     PUBKEY_ALGO_DIL3_25519  = 35, /* Dilithium3 + Ed25519 (aka ML-DSA-65)    */
     PUBKEY_ALGO_DIL5_448    = 36, /* Dilithium5 + Ed448   (aka ML-DSA-87)    */
     PUBKEY_ALGO_SPHINX_SHA2 = 41, /* SPHINX+-simple-SHA2  (aka SLH-DSA-SHA2) */
diff --git a/g10/build-packet.c b/g10/build-packet.c
index 9927b7695..78828c8dc 100644
--- a/g10/build-packet.c
+++ b/g10/build-packet.c
@@ -433,7 +433,7 @@ sos_write (iobuf_t out, gcry_mpi_t a, unsigned int *r_nwritten)
  * Write an opaque string to the output stream without length info.
  */
 gpg_error_t
-gpg_mpi_write_nohdr (iobuf_t out, gcry_mpi_t a)
+gpg_mpi_write_opaque_nohdr (iobuf_t out, gcry_mpi_t a)
 {
   int rc;
 
@@ -452,6 +452,45 @@ gpg_mpi_write_nohdr (iobuf_t out, gcry_mpi_t a)
 }
 
 
+/*
+ * Write an opaque MPI string with a four-byte octet count to the
+ * output stream.  If R_NWRITTEN is not NULL the number of written
+ * bytes is stored there.  OUT may be NULL in which case only
+ * R_NWRITTEN is updated and error checking is done.
+ */
+gpg_error_t
+gpg_mpi_write_opaque_32 (iobuf_t out, gcry_mpi_t a, unsigned int *r_nwritten)
+{
+  gpg_error_t err;
+
+  if (gcry_mpi_get_flag (a, GCRYMPI_FLAG_OPAQUE))
+    {
+      unsigned int nbits, nbytes;
+      const void *p;
+
+      p = gcry_mpi_get_opaque (a, &nbits);
+      nbytes = (nbits + 7)/8;
+      if (out)
+        {
+          write_32 (out, nbytes);
+          err = p ? iobuf_write (out, p, nbytes) : 0;
+        }
+      else
+        err = 0;
+      if (r_nwritten)
+        *r_nwritten = 4 + (p? nbytes : 0);
+    }
+  else
+    {
+      err = gpg_error (GPG_ERR_BAD_MPI);
+      if (r_nwritten)
+        *r_nwritten = 0;
+    }
+
+  return err;
+}
+
+
 /* Calculate the length of a packet described by PKT.  */
 u32
 calc_packet_length( PACKET *pkt )
@@ -639,8 +678,14 @@ do_key (iobuf_t out, int ctb, PKT_public_key *pk)
     {
       if (   (pk->pubkey_algo == PUBKEY_ALGO_ECDSA && (i == 0))
           || (pk->pubkey_algo == PUBKEY_ALGO_EDDSA && (i == 0))
-          || (pk->pubkey_algo == PUBKEY_ALGO_ECDH  && (i == 0 || i == 2)))
-        err = gpg_mpi_write_nohdr (a, pk->pkey[i]);
+          || (pk->pubkey_algo == PUBKEY_ALGO_ECDH  && (i == 0 || i == 2))
+          || (pk->pubkey_algo == PUBKEY_ALGO_KYBER && (i == 0)))
+        err = gpg_mpi_write_opaque_nohdr (a, pk->pkey[i]);
+      else if (pk->pubkey_algo == PUBKEY_ALGO_KYBER && i == 2)
+        {
+          /* Write a four-octet count prefixed Kyber public key.  */
+          err = gpg_mpi_write_opaque_32 (a, pk->pkey[2], NULL);
+        }
       else if (pk->pubkey_algo == PUBKEY_ALGO_ECDSA
                || pk->pubkey_algo == PUBKEY_ALGO_EDDSA
                || pk->pubkey_algo == PUBKEY_ALGO_ECDH)
@@ -779,9 +824,15 @@ do_key (iobuf_t out, int ctb, PKT_public_key *pk)
 
               for (j=i; j < nskey; j++ )
                 {
-                  if (pk->pubkey_algo == PUBKEY_ALGO_ECDSA
-                      || pk->pubkey_algo == PUBKEY_ALGO_EDDSA
-                      || pk->pubkey_algo == PUBKEY_ALGO_ECDH)
+                  if (pk->pubkey_algo == PUBKEY_ALGO_KYBER && j == 4)
+                    {
+                      if ((err=gpg_mpi_write_opaque_32 (NULL,pk->pkey[j], &n)))
+                        goto leave;
+                    }
+                  else if (pk->pubkey_algo == PUBKEY_ALGO_ECDSA
+                           || pk->pubkey_algo == PUBKEY_ALGO_EDDSA
+                           || pk->pubkey_algo == PUBKEY_ALGO_ECDH
+                           || pk->pubkey_algo == PUBKEY_ALGO_KYBER)
                     {
                       if ((err = sos_write (NULL, pk->pkey[j], &n)))
                         goto leave;
@@ -798,16 +849,26 @@ do_key (iobuf_t out, int ctb, PKT_public_key *pk)
             }
 
           for ( ; i < nskey; i++ )
-            if (pk->pubkey_algo == PUBKEY_ALGO_ECDSA
-                || pk->pubkey_algo == PUBKEY_ALGO_EDDSA
-                || pk->pubkey_algo == PUBKEY_ALGO_ECDH)
-              {
-                if ((err = sos_write (a, pk->pkey[i], NULL)))
-                  goto leave;
-              }
-            else
-              if ((err = gpg_mpi_write (a, pk->pkey[i], NULL)))
-                goto leave;
+            {
+              if (pk->pubkey_algo == PUBKEY_ALGO_KYBER && i == 4)
+                {
+                  err = gpg_mpi_write_opaque_32 (a, pk->pkey[i], NULL);
+                  if (err)
+                    goto leave;
+                }
+              else if (pk->pubkey_algo == PUBKEY_ALGO_ECDSA
+                       || pk->pubkey_algo == PUBKEY_ALGO_EDDSA
+                       || pk->pubkey_algo == PUBKEY_ALGO_ECDH)
+                {
+                  if ((err = sos_write (a, pk->pkey[i], NULL)))
+                    goto leave;
+                }
+              else
+                {
+                  if ((err = gpg_mpi_write (a, pk->pkey[i], NULL)))
+                    goto leave;
+                }
+            }
 
           write_16 (a, ski->csum );
         }
@@ -922,7 +983,7 @@ do_pubkey_enc( IOBUF out, int ctb, PKT_pubkey_enc *enc )
   for (i=0; i < n && !rc ; i++ )
     {
       if (enc->pubkey_algo == PUBKEY_ALGO_ECDH && i == 1)
-        rc = gpg_mpi_write_nohdr (a, enc->data[i]);
+        rc = gpg_mpi_write_opaque_nohdr (a, enc->data[i]);
       else if (enc->pubkey_algo == PUBKEY_ALGO_ECDH)
         rc = sos_write (a, enc->data[i], NULL);
       else
diff --git a/g10/ecdh.c b/g10/ecdh.c
index dbce846b9..4938e419d 100644
--- a/g10/ecdh.c
+++ b/g10/ecdh.c
@@ -156,11 +156,11 @@ build_kdf_params (unsigned char kdf_params[256], size_t *r_size,
     return gpg_error_from_syserror ();
 
   /* variable-length field 1, curve name OID */
-  err = gpg_mpi_write_nohdr (obuf, pkey[0]);
+  err = gpg_mpi_write_opaque_nohdr (obuf, pkey[0]);
   /* fixed-length field 2 */
   iobuf_put (obuf, PUBKEY_ALGO_ECDH);
   /* variable-length field 3, KDF params */
-  err = (err ? err : gpg_mpi_write_nohdr (obuf, pkey[2]));
+  err = (err ? err : gpg_mpi_write_opaque_nohdr (obuf, pkey[2]));
   /* fixed-length field 4 */
   iobuf_write (obuf, "Anonymous Sender    ", 20);
   /* fixed-length field 5, recipient fp (or first 20 octets of fp) */
diff --git a/g10/gpg.h b/g10/gpg.h
index c51bbbb46..167cdaf28 100644
--- a/g10/gpg.h
+++ b/g10/gpg.h
@@ -41,6 +41,10 @@
 /* Number of bits we accept when reading or writing MPIs. */
 #define MAX_EXTERN_MPI_BITS 16384
 
+/* Number of bytes we accept when reading four-octet count prefixed
+ * key parameters.  Needs to fit as a positive number into an int. */
+#define MAX_EXTERN_KEYPARM_BITS (32768*8)
+
 /* The maximum length of a binary fingerprints.  This is used to
  * provide a static buffer and will be increased if we need to support
  * longer fingerprints.  Warning: At some places we have some
diff --git a/g10/keygen.c b/g10/keygen.c
index c98deb635..8df8294d6 100644
--- a/g10/keygen.c
+++ b/g10/keygen.c
@@ -139,6 +139,9 @@ struct common_gen_cb_parm_s
    * may take a copy of this so that the result can be used after we
    * are back from the deep key generation call stack.  */
   gcry_sexp_t genkey_result;
+  /* For a dual algorithms the result of the second algorithm
+   * (e.g. Kyber). */
+  gcry_sexp_t genkey_result2;
 };
 typedef struct common_gen_cb_parm_s *common_gen_cb_parm_t;
 
@@ -1311,8 +1314,12 @@ curve_is_448 (gcry_sexp_t sexp)
 }
 
 
+/* Extract the parameters in OpenPGP format from SEXP and put them
+ * into the caller provided ARRAY.  SEXP2 is used to provide the
+ * parameters for dual algorithm (e.g. Kyber).  */
 static gpg_error_t
-ecckey_from_sexp (gcry_mpi_t *array, gcry_sexp_t sexp, int algo)
+ecckey_from_sexp (gcry_mpi_t *array, gcry_sexp_t sexp,
+                  gcry_sexp_t sexp2, int algo)
 {
   gpg_error_t err;
   gcry_sexp_t list, l2;
@@ -1364,8 +1371,46 @@ ecckey_from_sexp (gcry_mpi_t *array, gcry_sexp_t sexp, int algo)
     goto leave;
 
   gcry_sexp_release (list);
+  list = NULL;
 
-  if (algo == PUBKEY_ALGO_ECDH)
+  if (algo == PUBKEY_ALGO_KYBER)
+    {
+      if (!sexp2)
+        {
+          err = gpg_error (GPG_ERR_MISSING_VALUE);
+          goto leave;
+        }
+
+      list = gcry_sexp_find_token (sexp2, "public-key", 0);
+      if (!list)
+        {
+          err = gpg_error (GPG_ERR_INV_OBJ);
+          goto leave;
+        }
+      l2 = gcry_sexp_cadr (list);
+      gcry_sexp_release (list);
+      list = l2;
+      if (!list)
+        {
+          err = gpg_error (GPG_ERR_NO_OBJ);
+          goto leave;
+        }
+
+      l2 = gcry_sexp_find_token (list, "p", 1);
+      if (!l2)
+        {
+          err = gpg_error (GPG_ERR_NO_OBJ); /* required parameter not found */
+          goto leave;
+        }
+      array[2] = gcry_sexp_nth_mpi (l2, 1, GCRYMPI_FMT_OPAQUE);
+      gcry_sexp_release (l2);
+      if (!array[2])
+        {
+          err = gpg_error (GPG_ERR_INV_OBJ); /* required parameter invalid */
+          goto leave;
+        }
+    }
+  else if (algo == PUBKEY_ALGO_ECDH)
     {
       array[2] = pk_ecdh_default_params (nbits);
       if (!array[2])
@@ -1377,6 +1422,7 @@ ecckey_from_sexp (gcry_mpi_t *array, gcry_sexp_t sexp, int algo)
 
  leave:
   xfree (curve);
+  gcry_sexp_release (list);
   if (err)
     {
       for (i=0; i < 3; i++)
@@ -1515,7 +1561,7 @@ do_create_from_keygrip (ctrl_t ctrl, int algo,
   if (algo == PUBKEY_ALGO_ECDSA
       || algo == PUBKEY_ALGO_EDDSA
       || algo == PUBKEY_ALGO_ECDH )
-    err = ecckey_from_sexp (pk->pkey, s_key, algo);
+    err = ecckey_from_sexp (pk->pkey, s_key, NULL, algo);
   else
     err = key_from_sexp (pk->pkey, s_key, "public-key", algoelem);
   if (err)
@@ -1543,12 +1589,13 @@ do_create_from_keygrip (ctrl_t ctrl, int algo,
 }
 
 
-/* Common code for the key generation function gen_xxx.  The optinal
+/* Common code for the key generation function gen_xxx.  The optional
  * (COMMON_GEN_CB,COMMON_GEN_CB_PARM) can be used as communication
- * object.
+ * object.  A KEYPARMS2 forces the use of a dual key (e.g. Kyber+ECC).
  */
 static int
-common_gen (const char *keyparms, int algo, const char *algoelem,
+common_gen (const char *keyparms, const char *keyparms2,
+            int algo, const char *algoelem,
             kbnode_t pub_root, u32 timestamp, u32 expireval, int is_subkey,
             int keygen_flags, const char *passphrase,
             char **cache_nonce_addr, char **passwd_nonce_addr,
@@ -1559,6 +1606,7 @@ common_gen (const char *keyparms, int algo, const char *algoelem,
   PACKET *pkt;
   PKT_public_key *pk;
   gcry_sexp_t s_key;
+  gcry_sexp_t s_key2 = NULL;
 
   err = agent_genkey (NULL, cache_nonce_addr, passwd_nonce_addr, keyparms,
                       !!(keygen_flags & KEYGEN_FLAG_NO_PROTECTION),
@@ -1570,14 +1618,32 @@ common_gen (const char *keyparms, int algo, const char *algoelem,
       return err;
     }
 
+  if (keyparms2)
+    {
+      err = agent_genkey (NULL, NULL, NULL, keyparms2,
+                          1 /* No protection */,
+                          NULL, timestamp,
+                          &s_key2);
+      if (err)
+        {
+          log_error ("agent_genkey failed for second algo: %s\n",
+                     gpg_strerror (err) );
+          gcry_sexp_release (s_key);
+          return err;
+        }
+    }
+
   if (common_gen_cb && common_gen_cb_parm)
     {
       common_gen_cb_parm->genkey_result = s_key;
+      common_gen_cb_parm->genkey_result2 = s_key2;
       err = common_gen_cb (common_gen_cb_parm);
       common_gen_cb_parm->genkey_result = NULL;
+      common_gen_cb_parm->genkey_result2 = NULL;
       if (err)
         {
           gcry_sexp_release (s_key);
+          gcry_sexp_release (s_key2);
           return err;
         }
     }
@@ -1596,10 +1662,12 @@ common_gen (const char *keyparms, int algo, const char *algoelem,
     pk->expiredate = pk->timestamp + expireval;
   pk->pubkey_algo = algo;
 
-  if (algo == PUBKEY_ALGO_ECDSA
-      || algo == PUBKEY_ALGO_EDDSA
-      || algo == PUBKEY_ALGO_ECDH )
-    err = ecckey_from_sexp (pk->pkey, s_key, algo);
+  if (algo == PUBKEY_ALGO_KYBER)
+    err = ecckey_from_sexp (pk->pkey, s_key, s_key2, algo);
+  else if (algo == PUBKEY_ALGO_ECDSA
+           || algo == PUBKEY_ALGO_EDDSA
+           || algo == PUBKEY_ALGO_ECDH )
+    err = ecckey_from_sexp (pk->pkey, s_key, NULL, algo);
   else
     err = key_from_sexp (pk->pkey, s_key, "public-key", algoelem);
   if (err)
@@ -1610,6 +1678,7 @@ common_gen (const char *keyparms, int algo, const char *algoelem,
       return err;
     }
   gcry_sexp_release (s_key);
+  gcry_sexp_release (s_key2);
 
   pkt = xtrycalloc (1, sizeof *pkt);
   if (!pkt)
@@ -1675,7 +1744,7 @@ gen_elg (int algo, unsigned int nbits, KBNODE pub_root,
     err = gpg_error_from_syserror ();
   else
     {
-      err = common_gen (keyparms, algo, "pgy",
+      err = common_gen (keyparms, NULL, algo, "pgy",
                         pub_root, timestamp, expireval, is_subkey,
                         keygen_flags, passphrase,
                         cache_nonce_addr, passwd_nonce_addr,
@@ -1767,7 +1836,7 @@ gen_dsa (unsigned int nbits, KBNODE pub_root,
     err = gpg_error_from_syserror ();
   else
     {
-      err = common_gen (keyparms, PUBKEY_ALGO_DSA, "pqgy",
+      err = common_gen (keyparms, NULL, PUBKEY_ALGO_DSA, "pqgy",
                         pub_root, timestamp, expireval, is_subkey,
                         keygen_flags, passphrase,
                         cache_nonce_addr, passwd_nonce_addr,
@@ -1868,7 +1937,7 @@ gen_ecc (int algo, const char *curve, kbnode_t pub_root,
     err = gpg_error_from_syserror ();
   else
     {
-      err = common_gen (keyparms, algo, "",
+      err = common_gen (keyparms, NULL, algo, "",
                         pub_root, timestamp, expireval, is_subkey,
                         *keygen_flags, passphrase,
                         cache_nonce_addr, passwd_nonce_addr,
@@ -1880,6 +1949,79 @@ gen_ecc (int algo, const char *curve, kbnode_t pub_root,
 }
 
 
+/* Generate a dual ECC+Kyber key.  Note that KEYGEN_FLAGS will be
+ * updated by this function to indicate the forced creation of a v5
+ * key.  */
+static gpg_error_t
+gen_kyber (int algo, unsigned int nbits, const char *curve, kbnode_t pub_root,
+         u32 timestamp, u32 expireval, int is_subkey,
+         int *keygen_flags, const char *passphrase,
+         char **cache_nonce_addr, char **passwd_nonce_addr,
+         gpg_error_t (*common_gen_cb)(common_gen_cb_parm_t),
+         common_gen_cb_parm_t common_gen_cb_parm)
+{
+  gpg_error_t err;
+  char *keyparms1;
+  const char *keyparms2;
+
+  log_assert (algo == PUBKEY_ALGO_KYBER);
+
+  if (nbits == 768)
+    keyparms2 = "(genkey(kyber768))";
+  else if (nbits == 1024)
+    keyparms2 = "(genkey(kyber1024))";
+  else
+    return gpg_error (GPG_ERR_UNSUPPORTED_ALGORITHM);
+
+  if (!curve || !*curve)
+    return gpg_error (GPG_ERR_UNKNOWN_CURVE);
+
+  *keygen_flags |= KEYGEN_FLAG_CREATE_V5_KEY;
+
+  if (!strcmp (curve, "Curve25519"))
+    {
+      keyparms1 = xtryasprintf
+        ("(genkey(ecc(curve %zu:%s)(flags djb-tweak comp%s)))",
+         strlen (curve), curve,
+         (((*keygen_flags & KEYGEN_FLAG_TRANSIENT_KEY)
+           && (*keygen_flags & KEYGEN_FLAG_NO_PROTECTION))?
+          " transient-key" : ""));
+    }
+  else if (!strcmp (curve, "X448"))
+    {
+      keyparms1 = xtryasprintf
+        ("(genkey(ecc(curve %zu:%s)(flags comp%s)))",
+         strlen (curve), curve,
+         (((*keygen_flags & KEYGEN_FLAG_TRANSIENT_KEY)
+           && (*keygen_flags & KEYGEN_FLAG_NO_PROTECTION))?
+          " transient-key" : ""));
+    }
+  else  /* Should we use the compressed format?  Check smartcard support.  */
+    {
+      keyparms1 = xtryasprintf
+        ("(genkey(ecc(curve %zu:%s)(flags nocomp%s)))",
+         strlen (curve), curve,
+         (((*keygen_flags & KEYGEN_FLAG_TRANSIENT_KEY)
+           && (*keygen_flags & KEYGEN_FLAG_NO_PROTECTION))?
+          " transient-key" : ""));
+    }
+
+  if (!keyparms1)
+    err = gpg_error_from_syserror ();
+  else
+    {
+      err = common_gen (keyparms1, keyparms2, algo, "",
+                        pub_root, timestamp, expireval, is_subkey,
+                        *keygen_flags, passphrase,
+                        cache_nonce_addr, passwd_nonce_addr,
+                        common_gen_cb, common_gen_cb_parm);
+      xfree (keyparms1);
+    }
+
+  return err;
+}
+
+
 /*
  * Generate an RSA key.
  */
@@ -1928,7 +2070,7 @@ gen_rsa (int algo, unsigned int nbits, KBNODE pub_root,
     err = gpg_error_from_syserror ();
   else
     {
-      err = common_gen (keyparms, algo, "ne",
+      err = common_gen (keyparms, NULL, algo, "ne",
                         pub_root, timestamp, expireval, is_subkey,
                         keygen_flags, passphrase,
                         cache_nonce_addr, passwd_nonce_addr,
@@ -2547,6 +2689,12 @@ get_keysize_range (int algo, unsigned int *min, unsigned int *max)
       def=255;
       break;
 
+    case PUBKEY_ALGO_KYBER:
+      *min = 768;
+      *max = 1024;
+      def = 768;
+      break;
+
     default:
       *min = opt.compliance == CO_DE_VS ? 2048: 1024;
       *max = 4096;
@@ -2562,45 +2710,44 @@ get_keysize_range (int algo, unsigned int *min, unsigned int *max)
 static unsigned int
 fixup_keysize (unsigned int nbits, int algo, int silent)
 {
+  unsigned int orig_nbits = nbits;
+
   if (algo == PUBKEY_ALGO_DSA && (nbits % 64))
     {
       nbits = ((nbits + 63) / 64) * 64;
-      if (!silent)
-        tty_printf (_("rounded up to %u bits\n"), nbits);
     }
   else if (algo == PUBKEY_ALGO_EDDSA)
     {
-      if (nbits != 255 && nbits != 441)
-        {
-          if (nbits < 256)
-            nbits = 255;
-          else
-            nbits = 441;
-          if (!silent)
-            tty_printf (_("rounded to %u bits\n"), nbits);
-        }
+      if (nbits < 256)
+        nbits = 255;
+      else
+        nbits = 441;
     }
   else if (algo == PUBKEY_ALGO_ECDH || algo == PUBKEY_ALGO_ECDSA)
     {
-      if (nbits != 256 && nbits != 384 && nbits != 521)
-        {
-          if (nbits < 256)
-            nbits = 256;
-          else if (nbits < 384)
-            nbits = 384;
-          else
-            nbits = 521;
-          if (!silent)
-            tty_printf (_("rounded to %u bits\n"), nbits);
-        }
+      if (nbits < 256)
+        nbits = 256;
+      else if (nbits < 384)
+        nbits = 384;
+      else
+        nbits = 521;
+    }
+  else if (algo == PUBKEY_ALGO_KYBER)
+    {
+      /* (in reality the numbers are not bits) */
+      if (nbits < 768)
+        nbits = 768;
+      else if (nbits > 1024)
+        nbits = 1024;
     }
   else if ((nbits % 32))
     {
       nbits = ((nbits + 31) / 32) * 32;
-      if (!silent)
-        tty_printf (_("rounded up to %u bits\n"), nbits );
     }
 
+  if (!silent && orig_nbits != nbits)
+    tty_printf (_("rounded to %u bits\n"), nbits);
+
   return nbits;
 }
 
@@ -3330,6 +3477,12 @@ do_create (int algo, unsigned int nbits, const char *curve, kbnode_t pub_root,
                    keygen_flags, passphrase,
                    cache_nonce_addr, passwd_nonce_addr,
                    common_gen_cb, common_gen_cb_parm);
+  else if (algo == PUBKEY_ALGO_KYBER)
+    err = gen_kyber (algo, nbits, curve,
+                   pub_root, timestamp, expiredate, is_subkey,
+                   keygen_flags, passphrase,
+                   cache_nonce_addr, passwd_nonce_addr,
+                   common_gen_cb, common_gen_cb_parm);
   else if (algo == PUBKEY_ALGO_RSA)
     err = gen_rsa (algo, nbits, pub_root, timestamp, expiredate, is_subkey,
                    *keygen_flags, passphrase,
@@ -3434,6 +3587,7 @@ parse_key_parameter_part (ctrl_t ctrl,
     ; /* We need the flags before we can figure out the key to use.  */
   else if (algo)
     {
+      /* This is one of the algos parsed above (rsa, dsa, or elg).  */
       if (!string[3])
         size = get_keysize_range (algo, NULL, NULL);
       else
@@ -3443,14 +3597,15 @@ parse_key_parameter_part (ctrl_t ctrl,
             return gpg_error (GPG_ERR_INV_VALUE);
         }
     }
-  else if (!ascii_strcasecmp (string, "ky768"))
-    {
-      algo = PUBKEY_ALGO_KY768_25519;
-      is_pqc = 1;
-    }
-  else if (!ascii_strcasecmp (string, "ky1024"))
+  else if (!ascii_strcasecmp (string, "kyber"))
     {
-      algo = PUBKEY_ALGO_KY1024_448;
+      /* Get the curve and check that it can technically be used
+       * (i.e. everything except the EdXXXX curves.  */
+      curve = openpgp_is_curve_supported ("brainpoolP384r1", &algo, NULL);
+      if (!curve || algo == PUBKEY_ALGO_EDDSA)
+        return gpg_error (GPG_ERR_UNKNOWN_CURVE);
+      algo = PUBKEY_ALGO_KYBER;
+      size = 768;
       is_pqc = 1;
     }
   else if (!ascii_strcasecmp (string, "dil3"))
@@ -3782,6 +3937,8 @@ parse_key_parameter_part (ctrl_t ctrl,
  *   cv25519 := ECDH using curve Curve25519.
  *   cv448   := ECDH using curve X448.
  *   nistp256:= ECDSA or ECDH using curve NIST P-256
+ *   kyber   := Kyber with the default parameters
+ *   ky768_bp384 := Kyber-768 with BrainpoolP256r1 as second algo
  *
  * All strings with an unknown prefix are considered an elliptic
  * curve.  Curves which have no implicit algorithm require that FLAGS
@@ -6495,7 +6652,7 @@ gen_card_key (int keyno, int algo, int is_primary, kbnode_t pub_root,
   else if (algo == PUBKEY_ALGO_ECDSA
            || algo == PUBKEY_ALGO_EDDSA
            || algo == PUBKEY_ALGO_ECDH )
-    err = ecckey_from_sexp (pk->pkey, s_key, algo);
+    err = ecckey_from_sexp (pk->pkey, s_key, NULL, algo);
   else
     err = gpg_error (GPG_ERR_PUBKEY_ALGO);
   gcry_sexp_release (s_key);
diff --git a/g10/keyid.c b/g10/keyid.c
index 7e4c50b59..b42d918a4 100644
--- a/g10/keyid.c
+++ b/g10/keyid.c
@@ -74,12 +74,18 @@ pubkey_letter( int algo )
    is copied to the supplied buffer up a length of BUFSIZE-1.
    Examples for the output are:
 
-   "rsa3072"  - RSA with 3072 bit
-   "elg1024"  - Elgamal with 1024 bit
-   "ed25519"  - ECC using the curve Ed25519.
-   "E_1.2.3.4"  - ECC using the unsupported curve with OID "1.2.3.4".
+   "rsa3072"     - RSA with 3072 bit
+   "elg1024"     - Elgamal with 1024 bit
+   "ed25519"     - EdDSA using the curve Ed25519.
+   "cv25519"     - ECDH using the curve X25519.
+   "ky768_cv448  - Kyber-768 with X448 as second algo.
+   "ky1025_bp512 - Kyber-1024 with BrainpoolP256r1 as second algo.
+   "E_1.2.3.4"   - ECC using the unsupported curve with OID "1.2.3.4".
+   "unknown_N"   - Unknown OpenPGP algorithm N.
    "E_1.3.6.1.4.1.11591.2.12242973" ECC with a bogus OID.
-   "unknown_N"  - Unknown OpenPGP algorithm N.
+
+   Note that with Kyber we use "bp" as abbreviation for BrainpoolP and
+   ignore the final r1 part.
 
    If the option --legacy-list-mode is active, the output use the
    legacy format:
@@ -97,6 +103,9 @@ char *
 pubkey_string (PKT_public_key *pk, char *buffer, size_t bufsize)
 {
   const char *prefix = NULL;
+  int dual = 0;
+  char *curve;
+  const char *name;
 
   if (opt.legacy_list_mode)
     {
@@ -116,19 +125,34 @@ pubkey_string (PKT_public_key *pk, char *buffer, size_t bufsize)
     case PUBKEY_ALGO_ECDH:
     case PUBKEY_ALGO_ECDSA:
     case PUBKEY_ALGO_EDDSA:     prefix = "";    break;
-    case PUBKEY_ALGO_KY768_25519: prefix = "ky768";       break;
-    case PUBKEY_ALGO_KY1024_448:  prefix = "ky1024";      break;
+    case PUBKEY_ALGO_KYBER:     prefix = "ky"; dual = 1;  break;
     case PUBKEY_ALGO_DIL3_25519:  prefix = "dil3";        break;
     case PUBKEY_ALGO_DIL5_448:    prefix = "dil5";        break;
     case PUBKEY_ALGO_SPHINX_SHA2: prefix = "sphinx_sha2"; break;
     }
 
+
   if (prefix && *prefix)
-    snprintf (buffer, bufsize, "%s%u", prefix, nbits_from_pk (pk));
+    {
+      if (dual)
+        {
+          curve = openpgp_oid_to_str (pk->pkey[0]);
+          /* Note that we prefer the abbreviated name of the curve. */
+          name = openpgp_oid_to_curve (curve, 2);
+          if (!name)
+            name = "unknown";
+
+          snprintf (buffer, bufsize, "%s%u_%s",
+                    prefix, nbits_from_pk (pk), name);
+          xfree (curve);
+        }
+      else
+        snprintf (buffer, bufsize, "%s%u", prefix, nbits_from_pk (pk));
+    }
   else if (prefix)
     {
-      char *curve = openpgp_oid_to_str (pk->pkey[0]);
-      const char *name = openpgp_oid_to_curve (curve, 0);
+      curve = openpgp_oid_to_str (pk->pkey[0]);
+      name = openpgp_oid_to_curve (curve, 0);
 
       if (name)
         snprintf (buffer, bufsize, "%s", name);
@@ -308,6 +332,23 @@ do_hash_public_key (gcry_md_hd_t md, PKT_public_key *pk, int use_v5)
               pp[i] = NULL;
               nn[i] = 0;
             }
+          else if (pk->pubkey_algo == PUBKEY_ALGO_KYBER && i == 2)
+            {
+              /* Ugly: We need to re-construct the wire format of the
+               * key parameter.  It would be easier to use a second
+               * second index for pp and nn which could bump
+               * independet of i.  */
+              const char *p;
+
+              p = gcry_mpi_get_opaque (pk->pkey[i], &nbits);
+              pp[i] = xmalloc ((nbits+7)/8 + 1);
+              if (p)
+                memcpy (pp[i], p, (nbits+7)/8);
+              else
+                pp[i] = NULL;
+              nn[i] = (nbits+7)/8;
+              n += nn[i];
+            }
           else if (gcry_mpi_get_flag (pk->pkey[i], GCRYMPI_FLAG_OPAQUE))
             {
               const char *p;
@@ -805,11 +846,28 @@ namehash_from_uid (PKT_user_id *uid)
 
 
 /*
- * Return the number of bits used in PK.
+ * Return the number of bits used in PK.  For Kyber we return the
+ * octet count of the Kyber part and not of the ECC (thus likely
+ * values are 768 or 1024).
  */
 unsigned int
 nbits_from_pk (PKT_public_key *pk)
 {
+  if (pk->pubkey_algo == PUBKEY_ALGO_KYBER)
+    {
+      unsigned int nbits;
+      if (!gcry_mpi_get_opaque (pk->pkey[2], &nbits))
+        return 0;
+      switch (nbits/8)
+        {
+        case 800:  nbits =  512; break;
+        case 1184: nbits =  768; break;
+        case 1568: nbits = 1024; break;
+        default:   nbits = 0;    break;  /* Unkown version.  */
+        }
+      return nbits;
+    }
+  else
     return pubkey_nbits (pk->pubkey_algo, pk->pkey);
 }
 
@@ -1292,6 +1350,17 @@ keygrip_from_pk (PKT_public_key *pk, unsigned char *array)
       }
       break;
 
+    case PUBKEY_ALGO_KYBER:
+      {
+        char tmpname[15];
+
+        snprintf (tmpname, sizeof tmpname, "kyber%u", nbits_from_pk (pk));
+        err = gcry_sexp_build (&s_pkey, NULL,
+                               "(public-key(%s(p%m)))",
+                               tmpname, pk->pkey[2]);
+      }
+      break;
+
     default:
       err = gpg_error (GPG_ERR_PUBKEY_ALGO);
       break;
diff --git a/g10/misc.c b/g10/misc.c
index 24242cc30..432fe1760 100644
--- a/g10/misc.c
+++ b/g10/misc.c
@@ -801,8 +801,7 @@ openpgp_pk_algo_usage ( int algo )
           use = PUBKEY_USAGE_CERT | PUBKEY_USAGE_SIG | PUBKEY_USAGE_AUTH;
           break;
 
-      case PUBKEY_ALGO_KY768_25519:
-      case PUBKEY_ALGO_KY1024_448:
+      case PUBKEY_ALGO_KYBER:
           use = PUBKEY_USAGE_ENC | PUBKEY_USAGE_RENC;
           break;
 
@@ -1724,6 +1723,7 @@ pubkey_get_npkey (pubkey_algo_t algo)
     case PUBKEY_ALGO_ECDSA:     return 2;
     case PUBKEY_ALGO_ELGAMAL:   return 3;
     case PUBKEY_ALGO_EDDSA:     return 2;
+    case PUBKEY_ALGO_KYBER:     return 3;
     default: return 0;
     }
 }
@@ -1744,6 +1744,7 @@ pubkey_get_nskey (pubkey_algo_t algo)
     case PUBKEY_ALGO_ECDSA:     return 3;
     case PUBKEY_ALGO_ELGAMAL:   return 4;
     case PUBKEY_ALGO_EDDSA:     return 3;
+    case PUBKEY_ALGO_KYBER:     return 5;
     default: return 0;
     }
 }
@@ -1783,8 +1784,7 @@ pubkey_get_nenc (pubkey_algo_t algo)
     case PUBKEY_ALGO_ECDSA:     return 0;
     case PUBKEY_ALGO_ELGAMAL:   return 2;
     case PUBKEY_ALGO_EDDSA:     return 0;
-    case PUBKEY_ALGO_KY768_25519: return 4;
-    case PUBKEY_ALGO_KY1024_448:  return 4;
+    case PUBKEY_ALGO_KYBER:     return 4;
     default: return 0;
     }
 }
diff --git a/g10/packet.h b/g10/packet.h
index a13d3cdc8..40e5051c0 100644
--- a/g10/packet.h
+++ b/g10/packet.h
@@ -863,7 +863,9 @@ gpg_error_t build_keyblock_image (kbnode_t keyblock, iobuf_t *r_iobuf);
 int build_packet (iobuf_t out, PACKET *pkt);
 gpg_error_t build_packet_and_meta (iobuf_t out, PACKET *pkt);
 gpg_error_t gpg_mpi_write (iobuf_t out, gcry_mpi_t a, unsigned int *t_nwritten);
-gpg_error_t gpg_mpi_write_nohdr (iobuf_t out, gcry_mpi_t a);
+gpg_error_t gpg_mpi_write_opaque_nohdr (iobuf_t out, gcry_mpi_t a);
+gpg_error_t gpg_mpi_write_opaque_32 (iobuf_t out, gcry_mpi_t a,
+                                     unsigned int *r_nwritten);
 u32 calc_packet_length( PACKET *pkt );
 void build_sig_subpkt( PKT_signature *sig, sigsubpkttype_t type,
 			const byte *buffer, size_t buflen );
diff --git a/g10/parse-packet.c b/g10/parse-packet.c
index 34760a2d1..2163787cb 100644
--- a/g10/parse-packet.c
+++ b/g10/parse-packet.c
@@ -188,13 +188,21 @@ mpi_read (iobuf_t inp, unsigned int *ret_nread, int secure)
 }
 
 
-/* Read an octet string of length NBYTES from INP and return it at
- * R_DATA.  On error return an error code and store NULL at R_DATA.
- * PKTLEN shall give the current lenhgth of the packt and is updated
- * with each read. If SECURE is true, the integer is stored in secure
- * memory (allocated using gcry_xmalloc_secure).  */
+/* If NLENGTH is zero read an octet string of length NBYTES from INP
+ * and return it at R_DATA.
+ *
+ * If NLENGTH is either 1, 2, or 4 and NLENGTH is zero read an
+ * NLENGTH-octet count and use this count number octets from INP and
+ * return it at R_DATA.
+ *
+ * On error return an error code and store NULL at R_DATA.  PKTLEN
+ * shall give the current length of the packet and is updated with
+ * each read. If SECURE is true, the integer is stored in secure
+ * memory (allocated using gcry_xmalloc_secure).
+ */
 static gpg_error_t
-read_octet_string (iobuf_t inp, unsigned long *pktlen, unsigned int nbytes,
+read_octet_string (iobuf_t inp, unsigned long *pktlen,
+                   unsigned int nlength, unsigned int nbytes,
                    int secure, gcry_mpi_t *r_data)
 {
   gpg_error_t err;
@@ -204,12 +212,48 @@ read_octet_string (iobuf_t inp, unsigned long *pktlen, unsigned int nbytes,
 
   *r_data = NULL;
 
-  if (nbytes*8 > MAX_EXTERN_MPI_BITS)
+  if ((nbytes && nlength)
+      || (!nbytes && !(nlength == 1 || nlength == 2 || nlength == 4)))
+    {
+      err = gpg_error (GPG_ERR_INV_ARG);
+      goto leave;
+    }
+
+  if (nlength)
+    {
+      for (i = 0; i < nlength; i++)
+        {
+          if (!*pktlen)
+            {
+              err = gpg_error (GPG_ERR_INV_PACKET);
+              goto leave;
+            }
+          c = iobuf_readbyte (inp);
+          if (c < 0)
+            {
+              err =  gpg_error (GPG_ERR_INV_PACKET);
+              goto leave;
+            }
+          --*pktlen;
+          nbytes <<= 8;
+          nbytes |= c;
+        }
+
+      if (!nbytes)
+        {
+          err =  gpg_error (GPG_ERR_INV_PACKET);
+          goto leave;
+        }
+    }
+
+  if (nbytes*8 > (nbytes==4? MAX_EXTERN_KEYPARM_BITS:MAX_EXTERN_MPI_BITS)
+      || (nbytes*8 < nbytes))
     {
       log_error ("octet string too large (%u octets)\n", nbytes);
       err = gpg_error (GPG_ERR_TOO_LARGE);
       goto leave;
     }
+
   if (nbytes > *pktlen)
     {
       log_error ("octet string larger than packet (%u octets)\n", nbytes);
@@ -1408,7 +1452,6 @@ parse_pubkeyenc (IOBUF inp, int pkttype, unsigned long pktlen,
   int i, ndata;
   unsigned int n;
   PKT_pubkey_enc *k;
-  int is_ky1024 = 0;
 
   k = packet->pkt.pubkey_enc = xmalloc_clear (sizeof *packet->pkt.pubkey_enc);
   if (pktlen < 12)
@@ -1467,23 +1510,19 @@ parse_pubkeyenc (IOBUF inp, int pkttype, unsigned long pktlen,
       if (rc)
         goto leave;
     }
-  else if (k->pubkey_algo == PUBKEY_ALGO_KY768_25519
-           || (is_ky1024 = (k->pubkey_algo == PUBKEY_ALGO_KY1024_448)))
+  else if (k->pubkey_algo == PUBKEY_ALGO_KYBER)
     {
       log_assert (ndata == 4);
       /* Get the ephemeral public key.  */
-      n = is_ky1024? 56 : 32;
-      rc = read_octet_string (inp, &pktlen, n, 0, k->data + 0);
+      rc = read_octet_string (inp, &pktlen, 4, 0, 0, k->data + 0);
       if (rc)
         goto leave;
       /* Get the Kyber ciphertext.  */
-      n = is_ky1024? 1568 : 1088;
-      rc = read_octet_string (inp, &pktlen, n, 0, k->data + 1);
+      rc = read_octet_string (inp, &pktlen, 4, 0, 0, k->data + 1);
       if (rc)
         goto leave;
       /* Get the algorithm id.  */
-      n = 1;
-      rc = read_octet_string (inp, &pktlen, n, 0, k->data + 2);
+      rc = read_octet_string (inp, &pktlen, 0, 1, 0, k->data + 2);
       if (rc)
         goto leave;
       /* Get the wrapped symmetric key.  */
@@ -2681,17 +2720,25 @@ parse_key (IOBUF inp, int pkttype, unsigned long pktlen,
         {
           if (    (algorithm == PUBKEY_ALGO_ECDSA && (i == 0))
                || (algorithm == PUBKEY_ALGO_EDDSA && (i == 0))
-               || (algorithm == PUBKEY_ALGO_ECDH  && (i == 0 || i == 2)))
+               || (algorithm == PUBKEY_ALGO_ECDH  && (i == 0 || i == 2))
+               || (algorithm == PUBKEY_ALGO_KYBER && (i == 0)))
             {
               /* Read the OID (i==0) or the KDF params (i==2).  */
 	      err = read_sized_octet_string (inp, &pktlen, pk->pkey+i);
             }
+          else if (algorithm == PUBKEY_ALGO_KYBER && i == 2)
+            {
+              /* Read the four-octet count prefixed Kyber public key.  */
+	      err = read_octet_string (inp, &pktlen, 4, 0, 0, pk->pkey+i);
+            }
           else
             {
+              /* Read MPI or SOS.  */
               unsigned int n = pktlen;
               if (algorithm == PUBKEY_ALGO_ECDSA
                   || algorithm == PUBKEY_ALGO_EDDSA
-                  || algorithm == PUBKEY_ALGO_ECDH)
+                  || algorithm == PUBKEY_ALGO_ECDH
+                  || algorithm == PUBKEY_ALGO_KYBER)
                 pk->pkey[i] = sos_read (inp, &n, 0);
               else
                 pk->pkey[i] = mpi_read (inp, &n, 0);
@@ -2707,7 +2754,8 @@ parse_key (IOBUF inp, int pkttype, unsigned long pktlen,
               mpi_print (listfp, pk->pkey[i], mpi_print_mode);
               if ((algorithm == PUBKEY_ALGO_ECDSA
                    || algorithm == PUBKEY_ALGO_EDDSA
-                   || algorithm == PUBKEY_ALGO_ECDH) && i==0)
+                   || algorithm == PUBKEY_ALGO_ECDH
+                   || algorithm == PUBKEY_ALGO_KYBER) && i==0)
                 {
                   char *curve = openpgp_oid_to_str (pk->pkey[0]);
                   const char *name = openpgp_oid_to_curve (curve, 0);
@@ -3044,21 +3092,32 @@ parse_key (IOBUF inp, int pkttype, unsigned long pktlen,
           /* Not encrypted.  */
 	  for (i = npkey; i < nskey; i++)
 	    {
-              unsigned int n;
 
               if (pktlen < 2) /* At least two bytes for the length.  */
                 {
                   err = gpg_error (GPG_ERR_INV_PACKET);
                   goto leave;
                 }
-              n = pktlen;
-              if (algorithm == PUBKEY_ALGO_ECDSA
-                  || algorithm == PUBKEY_ALGO_EDDSA
-                  || algorithm == PUBKEY_ALGO_ECDH)
-                pk->pkey[i] = sos_read (inp, &n, 0);
+              if (algorithm == PUBKEY_ALGO_KYBER && i == npkey+1)
+                {
+                  err = read_octet_string (inp, &pktlen, 4, 0, 1, pk->pkey+i);
+                  if (err)
+                    goto leave;
+                }
               else
-                pk->pkey[i] = mpi_read (inp, &n, 0);
-              pktlen -= n;
+                {
+                  unsigned int n = pktlen;
+
+                  if (algorithm == PUBKEY_ALGO_ECDSA
+                      || algorithm == PUBKEY_ALGO_EDDSA
+                      || algorithm == PUBKEY_ALGO_ECDH
+                      || algorithm == PUBKEY_ALGO_KYBER)
+                    pk->pkey[i] = sos_read (inp, &n, 0);
+                  else
+                    pk->pkey[i] = mpi_read (inp, &n, 0);
+                  pktlen -= n;
+                }
+
               if (list_mode)
                 {
                   es_fprintf (listfp, "\tskey[%d]: ", i);