Repository: randombit/botan
Pull request #3212 (2023-01-23 09:09:18)

Dilithium/Kyber in X.509
This introduces glue code to allow using Kyber keys in X.509 certificates (for usage 'key exchange' only). Also, Dilithium keys can now be used to sign X.509 objects. I updated `unit_x509` on a best effort basis. Are there more tests that need adaption?

I posted some potential inconsistencies for discussion below.

Closes https://github.com/randombit/botan/issues/3208.

#### Algorithm Naming Conventions

Kyber and Dilithium are incorporating the algorithm parameters ("size" and "modern vs. 90s/AES") into their algo name. Therefore, `Public_Key::algo_name()` returns something along the lines of "Kyber-1024-90s-r3" or "Dilithium-6x5-r3". For other common asymmetric algorithms `Public_Key::algo_name()` is static (e.g. "RSA" or "ECDSA" regardless of the key size). The same reflects in their (preliminary) OID assignments -- one OID per algorithm configuration. Latest IETF drafts for [Kyber](https://datatracker.ietf.org/doc/draft-uni-qsckeys-kyber/00/) and [Dilithium](https://datatracker.ietf.org/doc/draft-uni-qsckeys-dilithium/00/) suggest that this approach is correct. Nevertheless, I find it inconsistent with the rest of the library.

#### OID Assignment

When we added Kyber, the prelimenary OID assignments were taken from the (now outdated) [draft-uni-qsckeys 00](https://datatracker.ietf.org/doc/draft-uni-qsckeys/00/). To the best of my understanding, latest drafts deliberately leave the OIDs to be defined. Hence, for Dilithium we use OIDs under Botan's private arc. Should we do the same for the Kyber OIDs? (I saw that [oids.rst](https://github.com/randombit/botan/blob/master/doc/dev_ref/oids.rst) actually already reserved a number for Kyber in 2019.

#### X.509 Key Usage for Kyber

I'm not entirely sure how to deal with Kyber keys here. Technically Kyber is a KEM, not a KEX: I.e. it could be used for key encipherment, no? Should we allow 'encryption' in `verify_cert_constraints_valid_for_key_type()`, therefore? Or is there a specific key usage for KEMs already?


Patch:
diff --git a/src/build-data/oids.txt b/src/build-data/oids.txt
index f3c4b6cb4..e048e6e1d 100644
--- a/src/build-data/oids.txt
+++ b/src/build-data/oids.txt
@@ -26,12 +26,12 @@
 1.3.6.1.4.1.2.267.10.4.4 = Kyber-1024-90s-r3
 
 # Dilithium OIDs are currently in Botan's private arc
-1.3.6.1.4.1.25258.1.9.1 = Dilithium-r3/4x4
-1.3.6.1.4.1.25258.1.9.2 = Dilithium-r3/6x5
-1.3.6.1.4.1.25258.1.9.3 = Dilithium-r3/8x7
-1.3.6.1.4.1.25258.1.10.1 = Dilithium-AES-r3/4x4
-1.3.6.1.4.1.25258.1.10.2 = Dilithium-AES-r3/6x5
-1.3.6.1.4.1.25258.1.10.3 = Dilithium-AES-r3/8x7
+1.3.6.1.4.1.25258.1.9.1 = Dilithium-4x4-r3
+1.3.6.1.4.1.25258.1.9.2 = Dilithium-6x5-r3
+1.3.6.1.4.1.25258.1.9.3 = Dilithium-8x7-r3
+1.3.6.1.4.1.25258.1.10.1 = Dilithium-4x4-AES-r3
+1.3.6.1.4.1.25258.1.10.2 = Dilithium-6x5-AES-r3
+1.3.6.1.4.1.25258.1.10.3 = Dilithium-8x7-AES-r3
 
 # XMSS
 1.3.6.1.4.1.25258.1.5 = XMSS-draft6
diff --git a/src/lib/asn1/oid_maps.cpp b/src/lib/asn1/oid_maps.cpp
index 350ae3439..4b5f8aa5f 100644
--- a/src/lib/asn1/oid_maps.cpp
+++ b/src/lib/asn1/oid_maps.cpp
@@ -1,7 +1,7 @@
 /*
 * OID maps
 *
-* This file was automatically generated by ./src/scripts/oids.py on 2023-01-18
+* This file was automatically generated by src/scripts/oids.py on 2023-01-23
 *
 * All manual edits to this file will be lost. Edit the script
 * then regenerate this source file.
@@ -144,16 +144,16 @@ std::unordered_map<std::string, std::string> OIDS::load_oid2str_map()
       { "1.3.6.1.4.1.2.267.8.2.2", "Kyber-512-r3" },
       { "1.3.6.1.4.1.2.267.8.3.3", "Kyber-768-r3" },
       { "1.3.6.1.4.1.2.267.8.4.4", "Kyber-1024-r3" },
-      { "1.3.6.1.4.1.25258.1.10.1", "Dilithium-AES-r3/4x4" },
-      { "1.3.6.1.4.1.25258.1.10.2", "Dilithium-AES-r3/6x5" },
-      { "1.3.6.1.4.1.25258.1.10.3", "Dilithium-AES-r3/8x7" },
+      { "1.3.6.1.4.1.25258.1.10.1", "Dilithium-4x4-AES-r3" },
+      { "1.3.6.1.4.1.25258.1.10.2", "Dilithium-6x5-AES-r3" },
+      { "1.3.6.1.4.1.25258.1.10.3", "Dilithium-8x7-AES-r3" },
       { "1.3.6.1.4.1.25258.1.3", "McEliece" },
       { "1.3.6.1.4.1.25258.1.5", "XMSS-draft6" },
       { "1.3.6.1.4.1.25258.1.6.1", "GOST-34.10-2012-256/EMSA1(SHA-256)" },
       { "1.3.6.1.4.1.25258.1.8", "XMSS-draft12" },
-      { "1.3.6.1.4.1.25258.1.9.1", "Dilithium-r3/4x4" },
-      { "1.3.6.1.4.1.25258.1.9.2", "Dilithium-r3/6x5" },
-      { "1.3.6.1.4.1.25258.1.9.3", "Dilithium-r3/8x7" },
+      { "1.3.6.1.4.1.25258.1.9.1", "Dilithium-4x4-r3" },
+      { "1.3.6.1.4.1.25258.1.9.2", "Dilithium-6x5-r3" },
+      { "1.3.6.1.4.1.25258.1.9.3", "Dilithium-8x7-r3" },
       { "1.3.6.1.4.1.25258.3.1", "Serpent/CBC" },
       { "1.3.6.1.4.1.25258.3.101", "Serpent/GCM" },
       { "1.3.6.1.4.1.25258.3.102", "Twofish/GCM" },
@@ -320,12 +320,12 @@ std::unordered_map<std::string, OID> OIDS::load_str2oid_map()
       { "DSA/EMSA1(SHA-3(512))", OID({2,16,840,1,101,3,4,3,8}) },
       { "DSA/EMSA1(SHA-384)", OID({2,16,840,1,101,3,4,3,3}) },
       { "DSA/EMSA1(SHA-512)", OID({2,16,840,1,101,3,4,3,4}) },
-      { "Dilithium-AES-r3/4x4", OID({1,3,6,1,4,1,25258,1,10,1}) },
-      { "Dilithium-AES-r3/6x5", OID({1,3,6,1,4,1,25258,1,10,2}) },
-      { "Dilithium-AES-r3/8x7", OID({1,3,6,1,4,1,25258,1,10,3}) },
-      { "Dilithium-r3/4x4", OID({1,3,6,1,4,1,25258,1,9,1}) },
-      { "Dilithium-r3/6x5", OID({1,3,6,1,4,1,25258,1,9,2}) },
-      { "Dilithium-r3/8x7", OID({1,3,6,1,4,1,25258,1,9,3}) },
+      { "Dilithium-4x4-AES-r3", OID({1,3,6,1,4,1,25258,1,10,1}) },
+      { "Dilithium-4x4-r3", OID({1,3,6,1,4,1,25258,1,9,1}) },
+      { "Dilithium-6x5-AES-r3", OID({1,3,6,1,4,1,25258,1,10,2}) },
+      { "Dilithium-6x5-r3", OID({1,3,6,1,4,1,25258,1,9,2}) },
+      { "Dilithium-8x7-AES-r3", OID({1,3,6,1,4,1,25258,1,10,3}) },
+      { "Dilithium-8x7-r3", OID({1,3,6,1,4,1,25258,1,9,3}) },
       { "ECDH", OID({1,3,132,1,12}) },
       { "ECDSA", OID({1,2,840,10045,2,1}) },
       { "ECDSA/EMSA1(SHA-1)", OID({1,2,840,10045,4,1}) },
diff --git a/src/lib/pubkey/dilithium/dilithium_common/dilithium.cpp b/src/lib/pubkey/dilithium/dilithium_common/dilithium.cpp
index 54962cb09..700491b11 100644
--- a/src/lib/pubkey/dilithium/dilithium_common/dilithium.cpp
+++ b/src/lib/pubkey/dilithium/dilithium_common/dilithium.cpp
@@ -103,17 +103,17 @@ calculate_t0_and_t1(const DilithiumModeConstants& mode,
 
 DilithiumMode::Mode dilithium_mode_from_string(const std::string& str)
    {
-   if(str == "Dilithium-r3/4x4")
+   if(str == "Dilithium-4x4-r3")
       { return DilithiumMode::Dilithium4x4; }
-   if(str == "Dilithium-AES-r3/4x4")
+   if(str == "Dilithium-4x4-AES-r3")
       { return DilithiumMode::Dilithium4x4_AES; }
-   if(str == "Dilithium-r3/6x5")
+   if(str == "Dilithium-6x5-r3")
       { return DilithiumMode::Dilithium6x5; }
-   if(str == "Dilithium-AES-r3/6x5")
+   if(str == "Dilithium-6x5-AES-r3")
       { return DilithiumMode::Dilithium6x5_AES; }
-   if(str == "Dilithium-r3/8x7")
+   if(str == "Dilithium-8x7-r3")
       { return DilithiumMode::Dilithium8x7; }
-   if(str == "Dilithium-AES-r3/8x7")
+   if(str == "Dilithium-8x7-AES-r3")
       { return DilithiumMode::Dilithium8x7_AES; }
 
    throw Invalid_Argument(str + " is not a valid Dilithium mode name");
@@ -134,17 +134,17 @@ std::string DilithiumMode::to_string() const
    switch(m_mode)
       {
       case DilithiumMode::Dilithium4x4:
-         return "Dilithium-r3/4x4";
+         return "Dilithium-4x4-r3";
       case DilithiumMode::Dilithium4x4_AES:
-         return "Dilithium-AES-r3/4x4";
+         return "Dilithium-4x4-AES-r3";
       case DilithiumMode::Dilithium6x5:
-         return "Dilithium-r3/6x5";
+         return "Dilithium-6x5-r3";
       case DilithiumMode::Dilithium6x5_AES:
-         return "Dilithium-AES-r3/6x5";
+         return "Dilithium-6x5-AES-r3";
       case DilithiumMode::Dilithium8x7:
-         return "Dilithium-r3/8x7";
+         return "Dilithium-8x7-r3";
       case DilithiumMode::Dilithium8x7_AES:
-         return "Dilithium-AES-r3/8x7";
+         return "Dilithium-8x7-AES-r3";
       }
 
    unreachable();
@@ -652,7 +652,7 @@ bool Dilithium_PublicKey::check_key(RandomNumberGenerator&, bool) const
 std::unique_ptr<PK_Ops::Verification> Dilithium_PublicKey::create_verification_op(const std::string& params,
       const std::string& provider) const
    {
-   BOTAN_ARG_CHECK(params.empty(), "Unexpected parameters for verifying with Dilithium");
+   BOTAN_ARG_CHECK(params.empty() || params == "Pure", "Unexpected parameters for verifying with Dilithium");
    if(provider.empty() || provider == "base")
       return std::make_unique<Dilithium_Verification_Operation>(*this);
    throw Provider_Not_Found(algo_name(), provider);
diff --git a/src/lib/pubkey/kyber/kyber_common/kyber.cpp b/src/lib/pubkey/kyber/kyber_common/kyber.cpp
index 331511237..3cf7e5053 100644
--- a/src/lib/pubkey/kyber/kyber_common/kyber.cpp
+++ b/src/lib/pubkey/kyber/kyber_common/kyber.cpp
@@ -1296,11 +1296,21 @@ KyberMode Kyber_PublicKey::mode() const
    return m_public->mode().mode();
    }
 
+std::string Kyber_PublicKey::algo_name() const
+   {
+   return get_oid().to_formatted_string();
+   }
+
 AlgorithmIdentifier Kyber_PublicKey::algorithm_identifier() const
    {
    return AlgorithmIdentifier(mode().get_oid(), AlgorithmIdentifier::USE_EMPTY_PARAM);
    }
 
+OID Kyber_PublicKey::get_oid() const
+   {
+   return mode().get_oid();
+   }
+
 size_t Kyber_PublicKey::estimated_strength() const
    {
    return m_public->mode().estimated_strength();
diff --git a/src/lib/pubkey/kyber/kyber_common/kyber.h b/src/lib/pubkey/kyber/kyber_common/kyber.h
index 490c88037..7ae1b863f 100644
--- a/src/lib/pubkey/kyber/kyber_common/kyber.h
+++ b/src/lib/pubkey/kyber/kyber_common/kyber.h
@@ -81,10 +81,12 @@ class BOTAN_PUBLIC_API(3, 0) Kyber_PublicKey : public virtual Public_Key
 
       virtual ~Kyber_PublicKey() = default;
 
-      std::string algo_name() const override { return "Kyber-r3"; }
+      std::string algo_name() const override;
 
       AlgorithmIdentifier algorithm_identifier() const override;
 
+      OID get_oid() const override;
+
       size_t key_length() const override;
 
       size_t estimated_strength() const override;
diff --git a/src/lib/pubkey/pk_algs.cpp b/src/lib/pubkey/pk_algs.cpp
index 893b2793e..698aaa029 100644
--- a/src/lib/pubkey/pk_algs.cpp
+++ b/src/lib/pubkey/pk_algs.cpp
@@ -375,7 +375,7 @@ create_private_key(const std::string& alg_name,
 #if defined(BOTAN_HAS_DILITHIUM) || defined(BOTAN_HAS_DILITHIUM_AES)
    if(alg_name == "Dilithium" || alg_name == "Dilithium-")
       {
-      const DilithiumMode mode(params.empty() ? "Dilithium-r3/6x5" : params);
+      const DilithiumMode mode(params.empty() ? "Dilithium-6x5-r3" : params);
       return std::make_unique<Dilithium_PrivateKey>(rng, mode);
       }
 #endif
diff --git a/src/lib/x509/key_constraint.cpp b/src/lib/x509/key_constraint.cpp
index 09a4c059a..957e4cdc3 100644
--- a/src/lib/x509/key_constraint.cpp
+++ b/src/lib/x509/key_constraint.cpp
@@ -74,13 +74,14 @@ void verify_cert_constraints_valid_for_key_type(const Public_Key& pub_key,
 
    size_t permitted = 0;
 
-   const bool can_agree = (name == "DH" || name == "ECDH");
-   const bool can_encrypt = (name == "RSA" || name == "ElGamal");
+   const bool can_agree = (name == "DH" || name == "ECDH" || name.starts_with("Kyber-"));
+   const bool can_encrypt = (name == "RSA" || name == "ElGamal" || name.starts_with("Kyber-"));
 
    const bool can_sign =
       (name == "RSA" || name == "DSA" ||
        name == "ECDSA" || name == "ECGDSA" || name == "ECKCDSA" || name == "Ed25519" ||
-       name == "GOST-34.10" || name == "GOST-34.10-2012-256" || name == "GOST-34.10-2012-512");
+       name == "GOST-34.10" || name == "GOST-34.10-2012-256" || name == "GOST-34.10-2012-512" ||
+       name.starts_with("Dilithium-"));
 
    if(can_agree)
       {
diff --git a/src/lib/x509/x509_obj.cpp b/src/lib/x509/x509_obj.cpp
index 4d4f4b1df..021ff4766 100644
--- a/src/lib/x509/x509_obj.cpp
+++ b/src/lib/x509/x509_obj.cpp
@@ -193,7 +193,7 @@ Certificate_Status_Code X509_Object::verify_signature(const Public_Key& pub_key)
    std::string padding;
    if(sig_info.size() == 2)
       padding = sig_info[1];
-   else if(pub_key_algo == "Ed25519" || pub_key_algo == "XMSS")
+   else if(pub_key_algo == "Ed25519" || pub_key_algo == "XMSS" || pub_key_algo.starts_with("Dilithium-"))
       padding = "Pure";
    else
       return Certificate_Status_Code::SIGNATURE_ALGO_BAD_PARAMS;
@@ -358,6 +358,11 @@ std::string choose_sig_algo(AlgorithmIdentifier& sig_algo,
       sig_algo = AlgorithmIdentifier(OID::from_string("XMSS"), AlgorithmIdentifier::USE_EMPTY_PARAM);
       return padding;
       }
+   else if(algo_name.starts_with("Dilithium-"))
+      {
+      sig_algo = key.algorithm_identifier();
+      return "Randomized";
+      }
    else
       {
       throw Invalid_Argument("Unknown X.509 signing key type: " + algo_name);


Test patch:
diff --git a/src/tests/test_dilithium.cpp b/src/tests/test_dilithium.cpp
index 5aef3eda4..12a90f2cc 100644
--- a/src/tests/test_dilithium.cpp
+++ b/src/tests/test_dilithium.cpp
@@ -371,14 +371,14 @@ class Dilithium_Keygen_Tests final : public PK_Key_Generation_Test
          return
             {
 #if defined(BOTAN_HAS_DILITHIUM_AES)
-            "Dilithium-AES-r3/4x4",
-            "Dilithium-AES-r3/6x5",
-            "Dilithium-AES-r3/8x7",
+            "Dilithium-4x4-AES-r3",
+            "Dilithium-6x5-AES-r3",
+            "Dilithium-8x7-AES-r3",
 #endif
 #if defined(BOTAN_HAS_DILITHIUM)
-            "Dilithium-r3/4x4",
-            "Dilithium-r3/6x5",
-            "Dilithium-r3/8x7",
+            "Dilithium-4x4-r3",
+            "Dilithium-6x5-r3",
+            "Dilithium-8x7-r3",
 #endif
             };
          }
diff --git a/src/tests/test_kyber.cpp b/src/tests/test_kyber.cpp
index ce4d76f88..c21e72023 100644
--- a/src/tests/test_kyber.cpp
+++ b/src/tests/test_kyber.cpp
@@ -209,7 +209,7 @@ Test::Result run_kyber_test(const char* test_name, const VarMap& vars, Botan::Ky
    result.test_eq("Key A Output", key_alice, ss_in);
 
    // Algorithm identifiers
-   result.test_eq("algo name", priv_key.algo_name(), "Kyber-r3");
+   result.test_eq("algo name", priv_key.algo_name(), algo_name);
    result.confirm("algo mode", priv_key.mode() == mode);
    result.test_eq("algo id", Botan::OIDS::oid2str_or_throw(priv_key.algorithm_identifier().oid()), algo_name);
 
diff --git a/src/tests/unit_x509.cpp b/src/tests/unit_x509.cpp
index 5e8254b91..b3c5fd5d1 100644
--- a/src/tests/unit_x509.cpp
+++ b/src/tests/unit_x509.cpp
@@ -1252,6 +1252,38 @@ Test::Result test_valid_constraints(const Botan::Private_Key& key,
          verify_cert_constraints_valid_for_key_type(key, typical_usage.sign_everything);
          });
       }
+   else if(pk_algo == "Kyber")
+      {
+      // Kyber can encrypt and agree
+      result.test_throws("all constraints not permitted", [&key, &typical_usage]()
+         {
+         verify_cert_constraints_valid_for_key_type(key, typical_usage.all);
+         });
+      result.test_throws("cert sign not permitted", [&key, &typical_usage]()
+         {
+         verify_cert_constraints_valid_for_key_type(key, typical_usage.ca);
+         });
+      result.test_throws("signature not permitted", [&key, &typical_usage]()
+         {
+         verify_cert_constraints_valid_for_key_type(key, typical_usage.sign_data);
+         });
+      result.test_throws("non repudiation not permitted", [&key, &typical_usage]()
+         {
+         verify_cert_constraints_valid_for_key_type(key, typical_usage.non_repudiation);
+         });
+      result.test_throws("crl sign not permitted", [&key, &typical_usage]()
+         {
+         verify_cert_constraints_valid_for_key_type(key, typical_usage.crl_sign);
+         });
+      result.test_throws("sign, cert sign, crl sign not permitted", [&key, &typical_usage]()
+         {
+         verify_cert_constraints_valid_for_key_type(key, typical_usage.sign_everything);
+         });
+
+      verify_cert_constraints_valid_for_key_type(key, typical_usage.key_agreement);
+      verify_cert_constraints_valid_for_key_type(key, typical_usage.data_encipherment);
+      verify_cert_constraints_valid_for_key_type(key, typical_usage.key_encipherment);
+      }
    else if(pk_algo == "RSA")
       {
       // RSA can do everything except key agreement
@@ -1319,7 +1351,7 @@ Test::Result test_valid_constraints(const Botan::Private_Key& key,
          });
       }
    else if(pk_algo == "DSA" || pk_algo == "ECDSA" || pk_algo == "ECGDSA" || pk_algo == "ECKCDSA" ||
-           pk_algo == "GOST-34.10")
+           pk_algo == "GOST-34.10" || pk_algo == "Dilithium")
       {
       // these are signature algorithms only
       result.test_throws("all constraints not permitted", [&key, &typical_usage]()
@@ -1630,7 +1662,7 @@ class X509_Cert_Unit_Tests final : public Test
          {
          std::vector<Test::Result> results;
 
-         const std::string sig_algos[] { "RSA", "DSA", "ECDSA", "ECGDSA", "ECKCDSA", "GOST-34.10", "Ed25519" };
+         const std::string sig_algos[] { "RSA", "DSA", "ECDSA", "ECGDSA", "ECKCDSA", "GOST-34.10", "Ed25519", "Dilithium" };
 
          for(const std::string& algo : sig_algos)
             {
@@ -1726,7 +1758,7 @@ class X509_Cert_Unit_Tests final : public Test
          /*
          These are algos which cannot sign but can be included in certs
          */
-         const std::vector<std::string> enc_algos = { "DH", "ECDH", "ElGamal" };
+         const std::vector<std::string> enc_algos = { "DH", "ECDH", "ElGamal", "Kyber" };
 
          for(const std::string& algo : enc_algos)
             {