Repository: randombit/botan
Pull request #2780 (2021-07-12 12:48:31)

FIX: Certificate Store might not find certificates where SHA1(pubkey) != key_id
This fixes [GH #2779](https://github.com/randombit/botan/issues/2779). It implements a fallback exhaustive search in `Certificate_Store_Windows::find_cert_by_pubkey_sha1()` that enumerates all available certificates, hashes their public keys and compares them to the requested key hash. Unfortunately, the Windows API doesn't seem to provide a built-in option to query for SHA-1(pubkey). It only provides MD5.

The fallback is invoked only if the existing query comes back with empty hands. The first query result is cached (both positive and negative outcome). This is meant to speed up repetitive searches of the same key hash. That seems particularly important for the negative case, where repetitive queries would otherwise always pay the price of the O(n)-fallback.

Furthermore, I added a regression test that now successfully finds `D-TRUST Root Class 3 CA 2 2009` which wouldn't be found without the proposed fix. On my machine, this exhaustive search fallback test runs for less than 10 milliseconds, FWIW.

I'm happy to provide a backport of that fix to the Botan2 branch if you find it worth the effort.


Patch:
diff --git a/src/lib/x509/certstor_system_windows/certstor_windows.cpp b/src/lib/x509/certstor_system_windows/certstor_windows.cpp
index d112047db..bc4e12abc 100644
--- a/src/lib/x509/certstor_system_windows/certstor_windows.cpp
+++ b/src/lib/x509/certstor_system_windows/certstor_windows.cpp
@@ -1,16 +1,18 @@
 /*
 * Certificate Store
-* (C) 1999-2019 Jack Lloyd
+* (C) 1999-2021 Jack Lloyd
 * (C) 2018-2019 Patrik Fiedler, Tim Oesterreich
+* (C) 2021      René Meusel
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
 #include <botan/certstor_windows.h>
+#include <botan/hash.h>
 #include <botan/pkix_types.h>
-#include <functional>
 
 #include <array>
+#include <functional>
 #include <vector>
 
 #define NOMINMAX 1
@@ -185,6 +187,7 @@ std::vector<X509_Certificate> find_cert_by_dn_and_key_id(const Botan::X509_DN& s
 
    return search_cert_stores(blob, find_type, filter, return_on_first_found);
    }
+
 } // namespace
 
 Certificate_Store_Windows::Certificate_Store_Windows() {}
@@ -241,11 +244,16 @@ Certificate_Store_Windows::find_cert_by_pubkey_sha1(const std::vector<uint8_t>&
 
    auto filter = [&](const std::vector<X509_Certificate>&, const X509_Certificate&) { return true; };
 
+   // This assumes that the to-be-found certificate adheres to RFC 3280 (Section 4.2.1.2), because
+   // the windows API does not allow to search for the SHA-1 of the certificate's public key directly.
+   // Most certificates adhere to the above mentioned convention...
    const auto certs = search_cert_stores(blob, CERT_FIND_KEY_IDENTIFIER, filter, true);
-   if(certs.empty())
-      return std::nullopt;
-   else
+   if(!certs.empty())
       return certs.front();
+
+   // ... for certificates that don't adhere to RFC 3280 (Section 4.2.1.2), we will need to use a
+   // fallback implementation that does an exhaustive search of all available certificates.
+   return find_cert_by_pubkey_sha1_via_exhaustive_search(key_hash);
    }
 
 std::optional<X509_Certificate>
@@ -262,4 +270,41 @@ std::optional<X509_CRL> Certificate_Store_Windows::find_crl_for(const X509_Certi
    BOTAN_UNUSED(subject);
    return std::nullopt;
    }
+
+std::optional<X509_Certificate>
+Certificate_Store_Windows::find_cert_by_pubkey_sha1_via_exhaustive_search(const std::vector<uint8_t> &key_hash) const
+   {
+   if(const auto cache_hit = m_non_rfc3289_certs.find(key_hash); cache_hit != m_non_rfc3289_certs.end())
+      {
+      return cache_hit->second;
+      }
+
+   auto sha1 = HashFunction::create_or_throw("SHA-1");
+   for(const auto store_name : cert_store_names)
+      {
+      Handle_Guard<HCERTSTORE> windows_cert_store = open_cert_store(store_name);
+      Handle_Guard<PCCERT_CONTEXT> cert_context = nullptr;
+
+      // Handle_Guard::assign exchanges the underlying pointer. No RAII is needed here, because the Windows API takes care of
+      // freeing the previous context.
+      while(cert_context.assign(CertEnumCertificatesInStore(windows_cert_store.get(), cert_context.get())))
+         {
+         const auto pubkey_blob = cert_context->pCertInfo->SubjectPublicKeyInfo.PublicKey;
+         const auto key_hash_candidate = sha1->process(static_cast<uint8_t*>(pubkey_blob.pbData),
+                                                       pubkey_blob.cbData);
+
+         if (std::equal(key_hash.begin(), key_hash.end(), key_hash_candidate.begin()))
+            {
+            X509_Certificate result(cert_context->pbCertEncoded, cert_context->cbCertEncoded);
+            m_non_rfc3289_certs[key_hash] = result;
+            return result;
+            }
+         }
+      }
+
+   // insert a negative query result into the cache
+   m_non_rfc3289_certs[key_hash] = std::nullopt;
+   return std::nullopt;
+   }
+
 }
diff --git a/src/lib/x509/certstor_system_windows/certstor_windows.h b/src/lib/x509/certstor_system_windows/certstor_windows.h
index 890920ac9..da2af6b34 100644
--- a/src/lib/x509/certstor_system_windows/certstor_windows.h
+++ b/src/lib/x509/certstor_system_windows/certstor_windows.h
@@ -2,6 +2,7 @@
 * Certificate Store
 * (C) 1999-2019 Jack Lloyd
 * (C) 2019      Patrick Schmidt
+* (C) 2021      René Meusel
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -11,6 +12,8 @@
 
 #include <botan/certstor.h>
 
+#include <map>
+
 namespace Botan {
 /**
 * Certificate Store that is backed by the system trust store on Windows.
@@ -64,6 +67,22 @@ class BOTAN_PUBLIC_API(2, 11) Certificate_Store_Windows final : public Certifica
        * @return nullptr;
        */
       std::optional<X509_CRL> find_crl_for(const X509_Certificate& subject) const override;
+
+   private:
+      /**
+       * Handle certificates that do not adhere to RFC 3280 using a subject key identifier
+       * that is not equal to the SHA-1 of the public key (w/o algorithm identifier)
+       *
+       * This method lazily builds a cache of certificates found in previous queries as well
+       * as negative results for @p key_hash queries that didn't find a certificate.
+       *
+       * See here for further details: https://github.com/randombit/botan/issues/2779
+       */
+      std::optional<X509_Certificate> find_cert_by_pubkey_sha1_via_exhaustive_search(
+               const std::vector<uint8_t> &key_hash) const;
+
+   private:
+      mutable std::map<std::vector<uint8_t>, std::optional<X509_Certificate>> m_non_rfc3289_certs;
    };
 }
 
diff --git a/src/lib/x509/certstor_system_windows/info.txt b/src/lib/x509/certstor_system_windows/info.txt
index 6d70de8bf..c0a55d2cb 100644
--- a/src/lib/x509/certstor_system_windows/info.txt
+++ b/src/lib/x509/certstor_system_windows/info.txt
@@ -10,6 +10,10 @@ win32,certificate_store
 certstor_windows.h
 </header:public>
 
+<requires>
+sha1
+</requires>
+
 <libs>
 windows -> crypt32
 mingw -> crypt32


Test patch:
diff --git a/src/tests/test_certstor_system.cpp b/src/tests/test_certstor_system.cpp
index b0cd80b03..d84b3cf2b 100644
--- a/src/tests/test_certstor_system.cpp
+++ b/src/tests/test_certstor_system.cpp
@@ -1,6 +1,6 @@
 /*
-* (C) 1999-2019 Jack Lloyd
-* (C) 2019      René Meusel
+* (C) 1999-2021 Jack Lloyd
+* (C) 2019,2021 René Meusel
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -49,6 +49,37 @@ Test::Result find_certificate_by_pubkey_sha1(Botan::Certificate_Store& certstore
    return result;
    }
 
+Test::Result find_certificate_by_pubkey_sha1_with_unmatching_key_id(Botan::Certificate_Store& certstore)
+   {
+   Test::Result result("System Certificate Store - Find Certificate by SHA1(pubkey) - regression test for GH #2779");
+
+   if(!certstore.find_cert(get_dn_of_cert_with_different_key_id(), {}).has_value())
+      {
+      result.note_missing("OS does not trust the certificate used for this regression test, skipping");
+      return result;
+      }
+
+   try
+      {
+      result.start_timer();
+      auto cert = certstore.find_cert_by_pubkey_sha1(get_pubkey_sha1_of_cert_with_different_key_id());
+      result.end_timer();
+
+      if(result.test_not_nullopt("found certificate", cert))
+         {
+         auto cns = cert->subject_dn().get_attribute("CN");
+         result.test_is_eq("exactly one CN", cns.size(), size_t(1));
+         result.test_eq("CN", cns.front(), "SecureTrust CA");
+         }
+      }
+   catch(std::exception& e)
+      {
+      result.test_failure(e.what());
+      }
+
+   return result;
+   }
+
 Test::Result find_cert_by_subject_dn(Botan::Certificate_Store& certstore)
    {
    Test::Result result("System Certificate Store - Find Certificate by subject DN");
@@ -328,6 +359,7 @@ class Certstor_System_Tests final : public Test
          results.push_back(open_result);
 
          results.push_back(find_certificate_by_pubkey_sha1(*system));
+         results.push_back(find_certificate_by_pubkey_sha1_with_unmatching_key_id(*system));
          results.push_back(find_cert_by_subject_dn(*system));
          results.push_back(find_cert_by_subject_dn_and_key_id(*system));
          results.push_back(find_all_certs_by_subject_dn(*system));
diff --git a/src/tests/test_certstor_utils.cpp b/src/tests/test_certstor_utils.cpp
index 68b0f8010..509959650 100644
--- a/src/tests/test_certstor_utils.cpp
+++ b/src/tests/test_certstor_utils.cpp
@@ -1,6 +1,6 @@
 /*
-* (C) 1999-2019 Jack Lloyd
-* (C) 2019      René Meusel
+* (C) 1999-2021 Jack Lloyd
+* (C) 2019,2021 René Meusel
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -49,6 +49,26 @@ std::vector<uint8_t> get_key_id()
    return Botan::hex_decode("c4a7b1a47b2c71fadbe14b9075ffc41560858910");
    }
 
+
+std::vector<uint8_t> get_pubkey_sha1_of_cert_with_different_key_id()
+   {
+   // see https://github.com/randombit/botan/issues/2779 for details
+   //
+   // SHA-1(Public Key) of:   SecureTrust CA
+   // Valid Until:            Dec 31 19:40:55 2029 GMT
+   // Subject Key Identifier: 4232b616fa04fdfe5d4b7ac3fdf74c401d5a43af
+   return Botan::hex_decode("ca4edd5b273529d9f6eec3e553efa4c019961daf");
+   }
+
+Botan::X509_DN get_dn_of_cert_with_different_key_id()
+   {
+   // This is the DN of the 'SecureTrust CA' whose SHA-1(pubkey) differs
+   // from its Subject Key Identifier
+   return read_dn("3048310b30090603550406130255533120301e060355040a131753656375"
+                  "7265547275737420436f72706f726174696f6e311730150603550403130e"
+                  "5365637572655472757374204341");
+   }
+
 Botan::X509_DN get_unknown_dn()
    {
    // thats a D-Trust "Test Certificate". It should be fairly likely that
diff --git a/src/tests/test_certstor_utils.h b/src/tests/test_certstor_utils.h
index ca25f4687..d1c46111d 100644
--- a/src/tests/test_certstor_utils.h
+++ b/src/tests/test_certstor_utils.h
@@ -1,6 +1,6 @@
 /*
-* (C) 1999-2019 Jack Lloyd
-* (C) 2019      René Meusel
+* (C) 1999-2021 Jack Lloyd
+* (C) 2019,2021 René Meusel
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -27,6 +27,9 @@ Botan::X509_DN get_utf8_dn();
 
 std::vector<uint8_t> get_key_id();
 
+std::vector<uint8_t> get_pubkey_sha1_of_cert_with_different_key_id();
+Botan::X509_DN       get_dn_of_cert_with_different_key_id();
+
 Botan::X509_DN get_unknown_dn();
 
 Botan::X509_DN get_skewed_dn();