Repository: randombit/botan
Pull request #3005 (2022-07-14 10:02:01)

Always use Kyber raw encoding for internal public key hashes
This addresses #2993.

Problem in a nutshell: Kyber's internal FO-transform relies on the hash of the Kyber public key. To obtain this hash, we used `public_key_bits()` whose output depends on the `Kyber_PublicKey::set_binary_encoding()` setting (i.e. `Raw`, or `Full`). If the key objects used for encap and decap used incompatible binary encodings, the resulting shared secret is different.

Solution: always use `Raw` for the FO-transform's public key encoding.


Patch:
diff --git a/src/lib/pubkey/kyber/kyber_common/kyber.cpp b/src/lib/pubkey/kyber/kyber_common/kyber.cpp
index b7035b6c3..0c12932ef 100644
--- a/src/lib/pubkey/kyber/kyber_common/kyber.cpp
+++ b/src/lib/pubkey/kyber/kyber_common/kyber.cpp
@@ -25,6 +25,7 @@
 #include <botan/internal/kyber_symmetric_primitives.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/ct_utils.h>
+#include <botan/internal/stl_util.h>
 
 #if defined(BOTAN_HAS_KYBER)
    #include <botan/internal/kyber_modern.h>
@@ -1201,7 +1202,7 @@ class Kyber_KEM_Encryptor final : public PK_Ops::KEM_Encryption_with_KDF,
 
          // Multitarget countermeasure for coins + contributory KEM
          G->update(shared_secret);
-         G->update(H->process(m_key.public_key_bits()));
+         G->update(H->process(m_key.public_key_bits_raw()));
          const auto g_out = G->final();
 
          const auto middle = G->output_length() / 2;
@@ -1241,7 +1242,7 @@ class Kyber_KEM_Decryptor final : public PK_Ops::KEM_Decryption_with_KDF,
 
          // Multitarget countermeasure for coins + contributory KEM
          G->update(shared_secret);
-         G->update(H->process(m_key.public_key_bits()));
+         G->update(H->process(m_key.public_key_bits_raw()));
 
          const auto g_out = G->final();
 
@@ -1352,23 +1353,33 @@ Kyber_PublicKey::Kyber_PublicKey(const Kyber_PublicKey& other)
 
 std::vector<uint8_t> Kyber_PublicKey::public_key_bits() const
    {
-   std::vector<uint8_t> output;
-   DER_Encoder der(output);
-
    switch(m_key_encoding)
       {
       case KyberKeyEncoding::Full:
-         der.start_sequence()
-         .encode(m_public->polynomials().to_bytes<std::vector<uint8_t>>(), ASN1_Type::OctetString)
-         .encode(m_public->seed(), ASN1_Type::OctetString)
-         .end_cons();
-         break;
+         return public_key_bits_der();
       case KyberKeyEncoding::Raw:
-         output = m_public->polynomials().to_bytes<std::vector<uint8_t>>();
-         output.insert(output.end(), m_public->seed().begin(), m_public->seed().end());
-         break;
+         return public_key_bits_raw();
       }
 
+   Botan::unreachable();
+   }
+
+std::vector<uint8_t> Kyber_PublicKey::public_key_bits_raw() const
+   {
+   return concat(m_public->polynomials().to_bytes<std::vector<uint8_t>>(),
+                 m_public->seed());
+   }
+
+std::vector<uint8_t> Kyber_PublicKey::public_key_bits_der() const
+   {
+   std::vector<uint8_t> output;
+   DER_Encoder der(output);
+
+   der.start_sequence()
+      .encode(m_public->polynomials().to_bytes<std::vector<uint8_t>>(), ASN1_Type::OctetString)
+      .encode(m_public->seed(), ASN1_Type::OctetString)
+      .end_cons();
+
    return output;
    }
 
@@ -1485,30 +1496,44 @@ std::unique_ptr<Public_Key> Kyber_PrivateKey::public_key() const
 
 secure_vector<uint8_t> Kyber_PrivateKey::private_key_bits() const
    {
-   secure_vector<uint8_t> output;
-   DER_Encoder der(output);
-   const auto pub_key = public_key_bits();
-   const auto pub_key_hash = m_private->mode().H()->process(pub_key);
-
    switch(m_key_encoding)
       {
       case KyberKeyEncoding::Full:
-         der.start_sequence()
-         .encode(size_t(0), ASN1_Type::Integer, ASN1_Class::Universal)
-         .encode(m_private->z(), ASN1_Type::OctetString)
-         .encode(m_private->polynomials().to_bytes<secure_vector<uint8_t>>(), ASN1_Type::OctetString)
-         .raw_bytes(pub_key)
-         .encode(pub_key_hash, ASN1_Type::OctetString)
-         .end_cons();
-         break;
+         return private_key_bits_der();
       case KyberKeyEncoding::Raw:
-         output = m_private->polynomials().to_bytes<secure_vector<uint8_t>>();
-         output.insert(output.end(), pub_key.begin(), pub_key.end());
-         output.insert(output.end(), pub_key_hash.begin(), pub_key_hash.end());
-         output.insert(output.end(), m_private->z().begin(), m_private->z().end());
-         break;
+         return private_key_bits_raw();
       }
 
+   Botan::unreachable();
+   }
+
+secure_vector<uint8_t> Kyber_PrivateKey::private_key_bits_raw() const
+   {
+   const auto pub_key = public_key_bits_raw();
+   const auto pub_key_sv = secure_vector<uint8_t>(pub_key.begin(), pub_key.end());
+   const auto pub_key_hash = m_private->mode().H()->process(pub_key);
+
+   return concat(m_private->polynomials().to_bytes<secure_vector<uint8_t>>(),
+                 pub_key_sv, pub_key_hash,
+                 m_private->z());
+   }
+
+secure_vector<uint8_t> Kyber_PrivateKey::private_key_bits_der() const
+   {
+   secure_vector<uint8_t> output;
+   DER_Encoder der(output);
+
+   const auto pub_key = public_key_bits_der();
+   const auto pub_key_hash = m_private->mode().H()->process(pub_key);
+
+   der.start_sequence()
+      .encode(size_t(0), ASN1_Type::Integer, ASN1_Class::Universal)
+      .encode(m_private->z(), ASN1_Type::OctetString)
+      .encode(m_private->polynomials().to_bytes<secure_vector<uint8_t>>(), ASN1_Type::OctetString)
+      .raw_bytes(pub_key)
+      .encode(pub_key_hash, ASN1_Type::OctetString)
+      .end_cons();
+
    return output;
    }
 
diff --git a/src/lib/pubkey/kyber/kyber_common/kyber.h b/src/lib/pubkey/kyber/kyber_common/kyber.h
index 30440819a..8aafc48f3 100644
--- a/src/lib/pubkey/kyber/kyber_common/kyber.h
+++ b/src/lib/pubkey/kyber/kyber_common/kyber.h
@@ -110,6 +110,9 @@ class BOTAN_PUBLIC_API(3, 0) Kyber_PublicKey : public virtual Public_Key
 
       void initialize_from_encoding(std::vector<uint8_t> pub_key, KyberMode m, KyberKeyEncoding encoding);
 
+      std::vector<uint8_t> public_key_bits_raw() const;
+      std::vector<uint8_t> public_key_bits_der() const;
+
    protected:
       friend class Kyber_KEM_Encryptor;
       friend class Kyber_KEM_Decryptor;
@@ -133,6 +136,10 @@ class BOTAN_PUBLIC_API(3, 0) Kyber_PrivateKey final : public virtual Kyber_Publi
             const std::string& params,
             const std::string& provider) const override;
 
+   private:
+      secure_vector<uint8_t> private_key_bits_raw() const;
+      secure_vector<uint8_t> private_key_bits_der() const;
+
    private:
       friend class Kyber_KEM_Decryptor;
 


Test patch:
diff --git a/src/tests/test_kyber.cpp b/src/tests/test_kyber.cpp
index 459d6bb44..927814ba6 100644
--- a/src/tests/test_kyber.cpp
+++ b/src/tests/test_kyber.cpp
@@ -32,6 +32,70 @@ namespace Botan_Tests {
 class KYBER_Tests final : public Test
    {
    public:
+      // Regression test for GH #2993: https://github.com/randombit/botan/issues/2993
+      //
+      // The resulting shared secrets did not match when the encapsulating public-
+      // key used a different encoding (Kyber_PublicKey::set_binary_encoding())
+      // from the private key decapsulating the ciphertext.
+      //
+      // The public key encoding used in Kyber's internal Fujisaki-Okamoto
+      // transform depended on that setting. I.e. if the encoding settings for
+      // encapsulation and decapsulation did not match, the resulting shared
+      // secret did not match either.
+      static void regression_gh2993(Test::Result &result, Botan::KyberMode mode)
+         {
+         auto sk = std::make_unique<Botan::Kyber_PrivateKey>(Test::rng(), mode);
+
+         sk->set_binary_encoding(Botan::KyberKeyEncoding::Raw);
+         auto sk_codec_raw = std::make_unique<Botan::Kyber_PrivateKey>(sk->private_key_bits(), mode, Botan::KyberKeyEncoding::Raw);
+         auto pk_raw = sk->public_key();
+         auto pk_codec_raw = std::make_unique<Botan::Kyber_PublicKey>(pk_raw->public_key_bits(), mode, Botan::KyberKeyEncoding::Raw);
+
+         sk->set_binary_encoding(Botan::KyberKeyEncoding::Full);
+         auto sk_codec_full = std::make_unique<Botan::Kyber_PrivateKey>(sk->private_key_bits(), mode, Botan::KyberKeyEncoding::Full);
+         auto pk_full = sk->public_key();
+         auto pk_codec_full = std::make_unique<Botan::Kyber_PublicKey>(pk_full->public_key_bits(), mode, Botan::KyberKeyEncoding::Full);
+
+         auto roundtrip = [&] (const auto& pkey, const auto& skey, const std::string context, const std::string kdf)
+            {
+            auto e = Botan::PK_KEM_Encryptor(*pkey, Test::rng(), kdf, "base");
+            Botan::secure_vector<uint8_t> ct, shared_key;
+            e.encrypt(ct, shared_key, 64, Test::rng());
+
+            auto d = Botan::PK_KEM_Decryptor(*skey, Test::rng(), kdf, "base");
+            const auto shared_key2 = d.decrypt(ct.data(), ct.size(), 64);
+
+            result.confirm("shared secrets are equal, when " + context + ", using " + kdf, shared_key == shared_key2);
+            };
+
+   #if defined(BOTAN_HAS_HKDF) && defined(BOTAN_HAS_SHA2_32)
+         sk->set_binary_encoding(Botan::KyberKeyEncoding::Raw);
+         roundtrip(pk_raw, sk, "both keys are in-memory", "HKDF(SHA-256)");
+         roundtrip(pk_codec_raw, sk, "pubkey is encoded/decoded as 'raw'", "HKDF(SHA-256)");
+         roundtrip(pk_raw, sk_codec_raw, "privkey is encoded/decoded as 'raw'", "HKDF(SHA-256)");
+         roundtrip(pk_codec_raw, sk_codec_raw, "both keys are encoded/decoded as 'raw'", "HKDF(SHA-256)");
+
+         sk->set_binary_encoding(Botan::KyberKeyEncoding::Full);
+         roundtrip(pk_full, sk, "both keys are in-memory", "HKDF(SHA-256)");
+         roundtrip(pk_codec_full, sk, "pubkey is encoded/decoded as 'full'", "HKDF(SHA-256)");
+         roundtrip(pk_full, sk_codec_full, "privkey is encoded/decoded as 'full'", "HKDF(SHA-256)");
+         roundtrip(pk_codec_full, sk_codec_full, "both keys are encoded/decoded as 'full'", "HKDF(SHA-256)");
+   #endif
+
+         sk->set_binary_encoding(Botan::KyberKeyEncoding::Raw);
+         roundtrip(pk_raw, sk, "both keys are in-memory", "Raw");
+         roundtrip(pk_codec_raw, sk, "pubkey is encoded/decoded as 'raw'", "Raw");
+         roundtrip(pk_raw, sk_codec_raw, "privkey is encoded/decoded as 'raw'", "Raw");
+         roundtrip(pk_codec_raw, sk_codec_raw, "both keys are encoded/decoded as 'raw'", "Raw");
+
+         sk->set_binary_encoding(Botan::KyberKeyEncoding::Full);
+         roundtrip(pk_full, sk, "both keys are in-memory", "Raw");
+         roundtrip(pk_codec_full, sk, "pubkey is encoded/decoded as 'full'", "Raw");
+         roundtrip(pk_full, sk_codec_full, "privkey is encoded/decoded as 'full'", "Raw");
+         roundtrip(pk_codec_full, sk_codec_full, "both keys are encoded/decoded as 'full'", "Raw");
+
+         }
+
       static Test::Result run_kyber_test(const char* test_name, Botan::KyberMode mode, size_t strength)
          {
          Test::Result result(test_name);
@@ -79,6 +143,11 @@ class KYBER_Tests final : public Test
             dec.decrypt(reverse_cipher_text, 0, std::vector<uint8_t>());
          result.confirm("shared secrets are not equal", key_alice != key_alice2);
 
+         //
+         // regression tests
+         //
+         regression_gh2993(result, mode);
+
          return result;
          }