Repository: randombit/botan
Pull request #2982 (2022-05-31 10:27:46)

FIX: Kyber KEM with a KDF + some nitpicks
Turns out that the implementation of Kyber needed a bit more polishing:

* **KEM operations did not inherit from `KEM_XXcryption_with_KDF`**
  Hence, the interface would simply *ignore* the KDF and provider preferences of the user and always return the "Raw" shared secret.
* **`Kyber...::algo_name()` incorporated the algorithm parameters**
  I.e. the algo name would be reported as "Kyber-1024-90s-r3". This is not in line with the rest of the library's algorithms. Now, `algo_name()` will always report "Kyber-r3" and the key classes provide an additional `::mode()` accessor to investigate the algorithm parameters. To integrate with Kyber's preliminary OIDs, the `KyberMode` enum is now a small class that can perform the translation from and to OIDs.
* **"Raw" KDF resulted in an exception**
  In contrast to `PK_Ops::Key_Agreement_with_KDF` the respective KEM operations did not allow for a "Raw" KDF. This is needed though, e.g. to implement [TLS 1.3 hybrid key exchange](https://datatracker.ietf.org/doc/html/draft-ietf-tls-hybrid-design-04).
* **Partially disabling 90s or modern kyber resulted in a failing text-based test**


Patch:
diff --git a/src/lib/pubkey/kyber/kyber_common/kyber.cpp b/src/lib/pubkey/kyber/kyber_common/kyber.cpp
index 215afc6d2..b7035b6c3 100644
--- a/src/lib/pubkey/kyber/kyber_common/kyber.cpp
+++ b/src/lib/pubkey/kyber/kyber_common/kyber.cpp
@@ -43,6 +43,61 @@
 #include <limits>
 
 namespace Botan {
+
+namespace {
+
+KyberMode::Mode mode_from_string(const std::string& str)
+   {
+   if(str == "Kyber-512-90s-r3")
+      return KyberMode::Kyber512_90s;
+   if(str == "Kyber-768-90s-r3")
+      return KyberMode::Kyber768_90s;
+   if(str == "Kyber-1024-90s-r3")
+      return KyberMode::Kyber1024_90s;
+   if(str == "Kyber-512-r3")
+      return KyberMode::Kyber512;
+   if(str == "Kyber-768-r3")
+      return KyberMode::Kyber768;
+   if(str == "Kyber-1024-r3")
+      return KyberMode::Kyber1024;
+
+   throw Invalid_Argument(str + " is not a valid Kyber mode name");
+   }
+
+}
+
+KyberMode::KyberMode(Mode mode)
+   : m_mode(mode) {}
+
+KyberMode::KyberMode(const OID& oid)
+   : m_mode(mode_from_string(oid.to_string())) {}
+
+OID KyberMode::get_oid() const
+   {
+   return OID::from_string(to_string());
+   }
+
+std::string KyberMode::to_string() const
+   {
+   switch (m_mode)
+      {
+      case Kyber512_90s:
+         return "Kyber-512-90s-r3";
+      case Kyber768_90s:
+         return "Kyber-768-90s-r3";
+      case Kyber1024_90s:
+         return "Kyber-1024-90s-r3";
+      case Kyber512:
+         return "Kyber-512-r3";
+      case Kyber768:
+         return "Kyber-768-r3";
+      case Kyber1024:
+         return "Kyber-1024-r3";
+      }
+
+   unreachable();
+   }
+
 namespace {
 
 class KyberConstants
@@ -85,7 +140,7 @@ class KyberConstants
    public:
       KyberConstants(const KyberMode mode) : m_mode(mode)
          {
-         switch(mode)
+         switch(mode.mode())
             {
             case KyberMode::Kyber512:
             case KyberMode::Kyber512_90s:
@@ -109,39 +164,14 @@ class KyberConstants
                break;
             }
 
-         m_algo_name = [mode]
-            {
-            switch(mode)
-               {
-               case KyberMode::Kyber512:
-                  return "Kyber-512-r3";
-               case KyberMode::Kyber512_90s:
-                  return "Kyber-512-90s-r3";
-               case KyberMode::Kyber768:
-                  return "Kyber-768-r3";
-               case KyberMode::Kyber768_90s:
-                  return "Kyber-768-90s-r3";
-               case KyberMode::Kyber1024:
-                  return "Kyber-1024-r3";
-               case KyberMode::Kyber1024_90s:
-                  return "Kyber-1024-90s-r3";
-               }
-
-            // GCC 9 couldn't figure out that all enum cases were covered above...
-            unreachable();
-            }();
-
-         const bool kyber_90s =
-            (mode == KyberMode::Kyber512_90s || mode == KyberMode::Kyber768_90s || mode == KyberMode::Kyber1024_90s);
-
 #ifdef BOTAN_HAS_KYBER_90S
-         if(kyber_90s)
+         if(mode.is_90s())
             {
             m_symmetric_primitives = std::make_unique<Kyber_90s_Symmetric_Primitives>();
             }
 #endif
 #ifdef BOTAN_HAS_KYBER
-         if(!kyber_90s)
+         if(!mode.is_90s())
             {
             m_symmetric_primitives = std::make_unique<Kyber_Modern_Symmetric_Primitives>();
             }
@@ -163,9 +193,9 @@ class KyberConstants
       KyberConstants& operator=(const KyberConstants& other) = delete;
       KyberConstants& operator=(KyberConstants&& other) = default;
 
-      std::string algo_name() const
+      KyberMode mode() const
          {
-         return m_algo_name;
+         return m_mode;
          }
 
       size_t estimated_strength() const
@@ -229,7 +259,6 @@ class KyberConstants
    private:
       KyberMode m_mode;
       std::unique_ptr<Kyber_Symmetric_Primitives> m_symmetric_primitives;
-      const char* m_algo_name;
       size_t m_nist_strength;
       uint8_t m_k;
       uint8_t m_eta1;
@@ -1147,19 +1176,21 @@ class Kyber_KEM_Cryptor
          }
    };
 
-class Kyber_KEM_Encryptor final : public PK_Ops::KEM_Encryption, protected Kyber_KEM_Cryptor
+class Kyber_KEM_Encryptor final : public PK_Ops::KEM_Encryption_with_KDF,
+                                  protected Kyber_KEM_Cryptor
    {
    public:
-      Kyber_KEM_Encryptor(const Kyber_PublicKey& key) : Kyber_KEM_Cryptor(key.m_public->mode()), m_key(key)
+      Kyber_KEM_Encryptor(const Kyber_PublicKey& key, const std::string& kdf)
+         : KEM_Encryption_with_KDF(kdf)
+         , Kyber_KEM_Cryptor(key.m_public->mode())
+         , m_key(key)
          {
          }
 
-      void kem_encrypt(secure_vector<uint8_t>& out_encapsulated_key, secure_vector<uint8_t>& out_shared_key,
-                       size_t desired_shared_key_len, RandomNumberGenerator& rng, const uint8_t salt[],
-                       size_t salt_len) override
+      void raw_kem_encrypt(secure_vector<uint8_t>& out_encapsulated_key,
+                           secure_vector<uint8_t>& out_shared_key,
+                           RandomNumberGenerator& rng) override
          {
-         BOTAN_UNUSED(desired_shared_key_len, salt, salt_len);
-
          // naming from kyber spec
          auto H = m_mode.H();
          auto G = m_mode.G();
@@ -1188,18 +1219,19 @@ class Kyber_KEM_Encryptor final : public PK_Ops::KEM_Encryption, protected Kyber
       const Kyber_PublicKey& m_key;
    };
 
-class Kyber_KEM_Decryptor final : public PK_Ops::KEM_Decryption, protected Kyber_KEM_Cryptor
+class Kyber_KEM_Decryptor final : public PK_Ops::KEM_Decryption_with_KDF,
+                                  protected Kyber_KEM_Cryptor
    {
    public:
-      Kyber_KEM_Decryptor(const Kyber_PrivateKey& key) : Kyber_KEM_Cryptor(key.m_private->mode()), m_key(key)
+      Kyber_KEM_Decryptor(const Kyber_PrivateKey& key, const std::string& kdf)
+         : PK_Ops::KEM_Decryption_with_KDF(kdf)
+         , Kyber_KEM_Cryptor(key.m_private->mode())
+         , m_key(key)
          {
          }
 
-      secure_vector<uint8_t> kem_decrypt(const uint8_t encap_key[], size_t len_encap_key, size_t desired_shared_key_len,
-                                         const uint8_t salt[], size_t salt_len) override
+      secure_vector<uint8_t> raw_kem_decrypt(const uint8_t encap_key[], size_t len_encap_key) override
          {
-         BOTAN_UNUSED(desired_shared_key_len, salt, salt_len);
-
          // naming from kyber spec
          auto H = m_mode.H();
          auto G = m_mode.G();
@@ -1254,14 +1286,14 @@ class Kyber_KEM_Decryptor final : public PK_Ops::KEM_Decryption, protected Kyber
       const Kyber_PrivateKey& m_key;
    };
 
-std::string Kyber_PublicKey::algo_name() const
+KyberMode Kyber_PublicKey::mode() const
    {
-   return m_public->mode().algo_name();
+   return m_public->mode().mode();
    }
 
 AlgorithmIdentifier Kyber_PublicKey::algorithm_identifier() const
    {
-   return AlgorithmIdentifier(get_oid(), AlgorithmIdentifier::USE_EMPTY_PARAM);
+   return AlgorithmIdentifier(mode().get_oid(), AlgorithmIdentifier::USE_EMPTY_PARAM);
    }
 
 size_t Kyber_PublicKey::estimated_strength() const
@@ -1484,16 +1516,20 @@ std::unique_ptr<PK_Ops::KEM_Encryption> Kyber_PublicKey::create_kem_encryption_o
       const std::string& params,
       const std::string& provider) const
    {
-   BOTAN_UNUSED(rng, params, provider);
-   return std::unique_ptr<PK_Ops::KEM_Encryption>(new Kyber_KEM_Encryptor(*this));
+   BOTAN_UNUSED(rng);
+   if(provider.empty() || provider == "base")
+      return std::make_unique<Kyber_KEM_Encryptor>(*this, params);
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::KEM_Decryption> Kyber_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& rng,
       const std::string& params,
       const std::string& provider) const
    {
-   BOTAN_UNUSED(rng, params, provider);
-   return std::unique_ptr<PK_Ops::KEM_Decryption>(new Kyber_KEM_Decryptor(*this));
+   BOTAN_UNUSED(rng);
+   if(provider.empty() || provider == "base")
+      return std::make_unique<Kyber_KEM_Decryptor>(*this, params);
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 } // namespace Botan
diff --git a/src/lib/pubkey/kyber/kyber_common/kyber.h b/src/lib/pubkey/kyber/kyber_common/kyber.h
index ad0856654..30440819a 100644
--- a/src/lib/pubkey/kyber/kyber_common/kyber.h
+++ b/src/lib/pubkey/kyber/kyber_common/kyber.h
@@ -14,6 +14,7 @@
 #ifndef BOTAN_KYBER_COMMON_H_
 #define BOTAN_KYBER_COMMON_H_
 
+#include <botan/asn1_obj.h>
 #include <botan/der_enc.h>
 #include <botan/exceptn.h>
 #include <botan/pk_keys.h>
@@ -25,14 +26,34 @@
 #endif
 
 namespace Botan {
-enum class KyberMode
+
+class BOTAN_PUBLIC_API(3, 0) KyberMode
    {
-   Kyber512,
-   Kyber512_90s,
-   Kyber768,
-   Kyber768_90s,
-   Kyber1024,
-   Kyber1024_90s
+   public:
+      enum Mode
+         {
+         Kyber512,
+         Kyber512_90s,
+         Kyber768,
+         Kyber768_90s,
+         Kyber1024,
+         Kyber1024_90s
+         };
+
+      KyberMode(Mode mode);
+      KyberMode(const OID& oid);
+
+      OID get_oid() const;
+      std::string to_string() const;
+
+      Mode mode() const { return m_mode; }
+      bool is_90s() const { return m_mode == Kyber512_90s || m_mode == Kyber768_90s || m_mode == Kyber1024_90s; }
+
+      bool operator==(const KyberMode& other) const { return m_mode == other.m_mode; }
+      bool operator!=(const KyberMode& other) const { return !(*this == other); }
+
+   private:
+      Mode m_mode;
    };
 
 enum class KyberKeyEncoding
@@ -55,7 +76,7 @@ class BOTAN_PUBLIC_API(3, 0) Kyber_PublicKey : public virtual Public_Key
 
       virtual ~Kyber_PublicKey() = default;
 
-      std::string algo_name() const override;
+      std::string algo_name() const override { return "Kyber-r3"; }
 
       AlgorithmIdentifier algorithm_identifier() const override;
 
@@ -71,6 +92,8 @@ class BOTAN_PUBLIC_API(3, 0) Kyber_PublicKey : public virtual Public_Key
             const std::string& params,
             const std::string& provider) const override;
 
+      KyberMode mode() const;
+
       void set_binary_encoding(KyberKeyEncoding encoding)
          {
          m_key_encoding = encoding;
diff --git a/src/lib/pubkey/pk_ops.cpp b/src/lib/pubkey/pk_ops.cpp
index 02f23f84d..1f543c06b 100644
--- a/src/lib/pubkey/pk_ops.cpp
+++ b/src/lib/pubkey/pk_ops.cpp
@@ -143,14 +143,17 @@ void PK_Ops::KEM_Encryption_with_KDF::kem_encrypt(secure_vector<uint8_t>& out_en
    secure_vector<uint8_t> raw_shared;
    this->raw_kem_encrypt(out_encapsulated_key, raw_shared, rng);
 
-   out_shared_key = m_kdf->derive_key(desired_shared_key_len,
-                                      raw_shared.data(), raw_shared.size(),
-                                      salt, salt_len);
+   out_shared_key = (m_kdf)
+      ? m_kdf->derive_key(desired_shared_key_len,
+                          raw_shared.data(), raw_shared.size(),
+                          salt, salt_len)
+      : raw_shared;
    }
 
 PK_Ops::KEM_Encryption_with_KDF::KEM_Encryption_with_KDF(const std::string& kdf)
    {
-   m_kdf = KDF::create_or_throw(kdf);
+   if(kdf != "Raw")
+      m_kdf = KDF::create_or_throw(kdf);
    }
 
 secure_vector<uint8_t>
@@ -162,14 +165,17 @@ PK_Ops::KEM_Decryption_with_KDF::kem_decrypt(const uint8_t encap_key[],
    {
    secure_vector<uint8_t> raw_shared = this->raw_kem_decrypt(encap_key, len);
 
-   return m_kdf->derive_key(desired_shared_key_len,
-                            raw_shared.data(), raw_shared.size(),
-                            salt, salt_len);
+   if(m_kdf)
+      return m_kdf->derive_key(desired_shared_key_len,
+                               raw_shared.data(), raw_shared.size(),
+                               salt, salt_len);
+   return raw_shared;
    }
 
 PK_Ops::KEM_Decryption_with_KDF::KEM_Decryption_with_KDF(const std::string& kdf)
    {
-   m_kdf = KDF::create_or_throw(kdf);
+   if(kdf != "Raw")
+      m_kdf = KDF::create_or_throw(kdf);
    }
 
 }


Test patch:
diff --git a/src/tests/test_kyber.cpp b/src/tests/test_kyber.cpp
index 1b0347604..459d6bb44 100644
--- a/src/tests/test_kyber.cpp
+++ b/src/tests/test_kyber.cpp
@@ -18,11 +18,11 @@
 #include <memory>
 
 #if defined(BOTAN_HAS_KYBER) || defined(BOTAN_HAS_KYBER_90S)
-   #include <botan/block_cipher.h>
    #include <botan/hex.h>
    #include <botan/kyber.h>
    #include <botan/oids.h>
    #include <botan/rng.h>
+   #include <botan/pubkey.h>
 #endif
 
 namespace Botan_Tests {
@@ -36,8 +36,6 @@ class KYBER_Tests final : public Test
          {
          Test::Result result(test_name);
 
-         const size_t shared_secret_length = 32;
-
          // Alice
          const Botan::Kyber_PrivateKey priv_key(Test::rng(), mode);
          const auto pub_key = priv_key.public_key();
@@ -51,16 +49,14 @@ class KYBER_Tests final : public Test
 
          // Bob (reading from serialized public key)
          Botan::Kyber_PublicKey alice_pub_key(pub_key_bits, mode, Botan::KyberKeyEncoding::Full);
-         const auto enc = alice_pub_key.create_kem_encryption_op(Test::rng(), "", "");
-
+         auto enc = Botan::PK_KEM_Encryptor(alice_pub_key, Test::rng(), "Raw", "base");
          Botan::secure_vector<uint8_t> cipher_text, key_bob;
-         enc->kem_encrypt(cipher_text, key_bob, shared_secret_length, Test::rng(), nullptr, 0);
+         enc.encrypt(cipher_text, key_bob, 0 /* no KDF */, Test::rng());
 
          // Alice (reading from serialized private key)
          Botan::Kyber_PrivateKey alice_priv_key(priv_key_bits, mode, Botan::KyberKeyEncoding::Full);
-         const auto dec = alice_priv_key.create_kem_decryption_op(Test::rng(), "", "");
-         const auto key_alice =
-            dec->kem_decrypt(cipher_text.data(), cipher_text.size(), shared_secret_length, nullptr, 0);
+         auto dec = Botan::PK_KEM_Decryptor(alice_priv_key, Test::rng(), "Raw", "base");
+         const auto key_alice = dec.decrypt(cipher_text, 0 /* no KDF */, std::vector<uint8_t>());
 
          result.confirm("shared secrets are equal", key_alice == key_bob);
 
@@ -71,14 +67,16 @@ class KYBER_Tests final : public Test
          // Broken cipher_text from Alice (wrong length)
          result.test_throws("fail to read cipher_text", "unexpected length of ciphertext buffer", [&]
             {
-            dec->kem_decrypt(cipher_text.data(), cipher_text.size() - 5, shared_secret_length, nullptr, 0);
+            auto short_cipher_text = cipher_text;
+            short_cipher_text.pop_back();
+            dec.decrypt(short_cipher_text, 0, std::vector<uint8_t>());
             });
 
          // Invalid cipher_text from Alice
          Botan::secure_vector<uint8_t> reverse_cipher_text;
          std::copy(cipher_text.crbegin(), cipher_text.crend(), std::back_inserter(reverse_cipher_text));
          const auto key_alice2 =
-            dec->kem_decrypt(reverse_cipher_text.data(), reverse_cipher_text.size(), shared_secret_length, nullptr, 0);
+            dec.decrypt(reverse_cipher_text, 0, std::vector<uint8_t>());
          result.confirm("shared secrets are not equal", key_alice != key_alice2);
 
          return result;
@@ -118,8 +116,6 @@ Test::Result run_kyber_test(const char* test_name, const VarMap& vars, Botan::Ky
    const auto ct_in = vars.get_req_bin("CT");
    const auto ss_in = vars.get_req_bin("SS");
 
-   const size_t shared_secret_length = 32;
-
    // Kyber test RNG
    Fixed_Output_RNG kyber_test_rng(random_in);
 
@@ -131,19 +127,20 @@ Test::Result run_kyber_test(const char* test_name, const VarMap& vars, Botan::Ky
    result.test_eq("Secret Key Output", priv_key.private_key_bits(), sk_in);
 
    // Bob
-   auto enc = pub_key->create_kem_encryption_op(kyber_test_rng, "", "");
+   auto enc = Botan::PK_KEM_Encryptor(*pub_key, kyber_test_rng, "Raw", "base");
    Botan::secure_vector<uint8_t> cipher_text, key_bob;
-   enc->kem_encrypt(cipher_text, key_bob, shared_secret_length, kyber_test_rng, nullptr, 0);
+   enc.encrypt(cipher_text, key_bob, 0 /* no KDF */, kyber_test_rng);
    result.test_eq("Cipher-Text Output", cipher_text, ct_in);
    result.test_eq("Key B Output", key_bob, ss_in);
 
    // Alice
-   auto dec = priv_key.create_kem_decryption_op(kyber_test_rng, "", "");
-   auto key_alice = dec->kem_decrypt(cipher_text.data(), cipher_text.size(), shared_secret_length, nullptr, 0);
+   auto dec = Botan::PK_KEM_Decryptor(priv_key, kyber_test_rng, "Raw", "base");
+   const auto key_alice = dec.decrypt(cipher_text, 0 /* no KDF */, std::vector<uint8_t>());
    result.test_eq("Key A Output", key_alice, ss_in);
 
    // Algorithm identifiers
-   result.test_eq("algo name", priv_key.algo_name(), algo_name);
+   result.test_eq("algo name", priv_key.algo_name(), "Kyber-r3");
+   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);
 
    return result;
@@ -207,6 +204,22 @@ class Kyber_Encoding_Test : public Text_Based_Test
          }
 
    public:
+      bool skip_this_test(const std::string &algo_name, const VarMap &) override
+         {
+         const auto mode = name_to_mode(algo_name);
+#if defined(BOTAN_HAS_KYBER)
+         if(!mode.is_90s())
+            return false;
+#endif
+#if defined(BOTAN_HAS_KYBER_90S)
+         if(mode.is_90s())
+            return false;
+#endif
+
+         BOTAN_UNUSED(algo_name, mode);
+         return true;
+         }
+
       Test::Result run_one_test(const std::string& algo_name, const VarMap& vars) override
          {
          Test::Result result("kyber_encodings");