Fully working path validation. Even fixes the cases in PKITS where we

got the answer wrong before. Still no policy or name constraints
support, though.

11 files changed, 299 insertions, 60 deletions

diff --git a/src/cert/certstore/certstor.cpp b/src/cert/certstore/certstor.cpp
index 3cba2f39e..7aa528d04 100644
--- a/src/cert/certstore/certstor.cpp
+++ b/src/cert/certstore/certstor.cpp
@@ -9,12 +9,7 @@
 
 namespace Botan {
 
-Certificate_Store* Certificate_Store_Memory::clone() const
-   {
-   return new Certificate_Store_Memory(*this);
-   }
-
-void Certificate_Store_Memory::add_certificate(const X509_Certificate& cert)
+void Certificate_Store_In_Memory::add_certificate(const X509_Certificate& cert)
    {
    for(size_t i = 0; i != certs.size(); ++i)
       {
@@ -26,7 +21,7 @@ void Certificate_Store_Memory::add_certificate(const X509_Certificate& cert)
    }
 
 std::vector<X509_Certificate>
-Certificate_Store_Memory::find_cert_by_subject_and_key_id(
+Certificate_Store_In_Memory::find_cert_by_subject_and_key_id(
    const X509_DN& subject_dn,
    const MemoryRegion<byte>& key_id) const
    {
@@ -50,7 +45,7 @@ Certificate_Store_Memory::find_cert_by_subject_and_key_id(
    return result;
    }
 
-void Certificate_Store_Memory::add_crl(const X509_CRL& crl)
+void Certificate_Store_In_Memory::add_crl(const X509_CRL& crl)
    {
    X509_DN crl_issuer = crl.issuer_dn();
 
@@ -59,11 +54,9 @@ void Certificate_Store_Memory::add_crl(const X509_CRL& crl)
       // Found an update of a previously existing one; replace it
       if(crls[i].issuer_dn() == crl_issuer)
          {
-         if(crls[i].this_update() < crl.this_update())
-            {
+         if(crls[i].this_update() <= crl.this_update())
             crls[i] = crl;
-            return;
-            }
+         return;
          }
       }
 
@@ -72,7 +65,7 @@ void Certificate_Store_Memory::add_crl(const X509_CRL& crl)
    }
 
 std::vector<X509_CRL>
-Certificate_Store_Memory::find_crl_by_subject_and_key_id(
+Certificate_Store_In_Memory::find_crl_by_issuer_and_key_id(
    const X509_DN& issuer_dn,
    const MemoryRegion<byte>& key_id) const
    {
diff --git a/src/cert/certstore/certstor.h b/src/cert/certstore/certstor.h
index 374013984..604541d52 100644
--- a/src/cert/certstore/certstor.h
+++ b/src/cert/certstore/certstor.h
@@ -21,8 +21,6 @@ class BOTAN_DLL Certificate_Store
    public:
       virtual ~Certificate_Store() {}
 
-      virtual Certificate_Store* clone() const = 0;
-
       /**
       * Add a certificate; this may fail if the store is write-only
       */
@@ -45,7 +43,7 @@ class BOTAN_DLL Certificate_Store
       * Find CRLs by the DN and key id of the issuer
       */
       virtual std::vector<X509_CRL>
-         find_crl_by_subject_and_key_id(
+         find_crl_by_issuer_and_key_id(
             const X509_DN& issuer_dn,
             const MemoryRegion<byte>& key_id) const = 0;
    };
@@ -53,11 +51,9 @@ class BOTAN_DLL Certificate_Store
 /**
 * In Memory Certificate Store
 */
-class BOTAN_DLL Certificate_Store_Memory : public Certificate_Store
+class BOTAN_DLL Certificate_Store_In_Memory : public Certificate_Store
    {
    public:
-      Certificate_Store* clone() const;
-
       void add_certificate(const X509_Certificate& cert);
 
       void add_crl(const X509_CRL& crl);
@@ -66,13 +62,13 @@ class BOTAN_DLL Certificate_Store_Memory : public Certificate_Store
          const X509_DN& subject_dn,
          const MemoryRegion<byte>& key_id) const;
 
-      std::vector<X509_CRL> find_crl_by_subject_and_key_id(
+      std::vector<X509_CRL> find_crl_by_issuer_and_key_id(
          const X509_DN& issuer_dn,
          const MemoryRegion<byte>& key_id) const;
 
-      Certificate_Store_Memory() {}
+      Certificate_Store_In_Memory() {}
    private:
-      // TODO: Add indexing on the DN and key id to avoid linear search?
+      // TODO: Add indexing on the DN and key id to avoid linear search
       std::vector<X509_Certificate> certs;
       std::vector<X509_CRL> crls;
    };
diff --git a/src/cert/x509cert/x509_ext.h b/src/cert/x509cert/x509_ext.h
index 8799c5921..714e29562 100644
--- a/src/cert/x509cert/x509_ext.h
+++ b/src/cert/x509cert/x509_ext.h
@@ -12,7 +12,7 @@
 #include <botan/asn1_oid.h>
 #include <botan/asn1_obj.h>
 #include <botan/datastor.h>
-#include <botan/pubkey_enums.h>
+#include <botan/crl_ent.h>
 
 namespace Botan {
 
diff --git a/src/cert/x509cert/x509_obj.cpp b/src/cert/x509cert/x509_obj.cpp
index 13193f09c..c58081225 100644
--- a/src/cert/x509cert/x509_obj.cpp
+++ b/src/cert/x509cert/x509_obj.cpp
@@ -16,6 +16,8 @@
 #include <algorithm>
 #include <memory>
 
+#include <stdio.h>
+
 namespace Botan {
 
 /*
@@ -192,8 +194,9 @@ bool X509_Object::check_signature(Public_Key& pub_key) const
 
       return verifier.verify_message(tbs_data(), signature());
       }
-   catch(...)
+   catch(std::exception& e)
       {
+      printf("Failure during validation %s\n", e.what());
       return false;
       }
    }
diff --git a/src/cert/x509cert/x509cert.cpp b/src/cert/x509cert/x509cert.cpp
index 7d9370f2a..52115a1a8 100644
--- a/src/cert/x509cert/x509cert.cpp
+++ b/src/cert/x509cert/x509cert.cpp
@@ -206,9 +206,15 @@ bool X509_Certificate::is_CA_cert() const
    {
    if(!subject.get1_u32bit("X509v3.BasicConstraints.is_ca"))
       return false;
-   if((constraints() & KEY_CERT_SIGN) || (constraints() == NO_CONSTRAINTS))
+
+   return allowed_usage(KEY_CERT_SIGN);
+   }
+
+bool X509_Certificate::allowed_usage(Key_Constraints restriction) const
+   {
+   if(constraints() == NO_CONSTRAINTS)
       return true;
-   return false;
+   return (constraints() & restriction);
    }
 
 /*
diff --git a/src/cert/x509cert/x509cert.h b/src/cert/x509cert/x509cert.h
index 8798ef1c2..d25b97694 100644
--- a/src/cert/x509cert/x509cert.h
+++ b/src/cert/x509cert/x509cert.h
@@ -23,10 +23,10 @@ namespace Botan {
 class BOTAN_DLL X509_Certificate : public X509_Object
    {
    public:
-     /**
-     * Get the public key associated with this certificate.
-     * @return subject public key of this certificate
-     */
+      /**
+      * Get the public key associated with this certificate.
+      * @return subject public key of this certificate
+      */
       Public_Key* subject_public_key() const;
 
       /**
@@ -111,6 +111,8 @@ class BOTAN_DLL X509_Certificate : public X509_Object
       */
       bool is_CA_cert() const;
 
+      bool allowed_usage(Key_Constraints restriction) const;
+
       /**
       * Get the path limit as defined in the BasicConstraints extension of
       * this certificate.
diff --git a/src/cert/x509crl/crl_ent.h b/src/cert/x509crl/crl_ent.h
index b3e696a86..ae9535484 100644
--- a/src/cert/x509crl/crl_ent.h
+++ b/src/cert/x509crl/crl_ent.h
@@ -13,6 +13,26 @@
 namespace Botan {
 
 /**
+* X.509v2 CRL Reason Code.
+*/
+enum CRL_Code {
+   UNSPECIFIED            = 0,
+   KEY_COMPROMISE         = 1,
+   CA_COMPROMISE          = 2,
+   AFFILIATION_CHANGED    = 3,
+   SUPERSEDED             = 4,
+   CESSATION_OF_OPERATION = 5,
+   CERTIFICATE_HOLD       = 6,
+   REMOVE_FROM_CRL        = 8,
+   PRIVLEDGE_WITHDRAWN    = 9,
+   AA_COMPROMISE          = 10,
+
+   DELETE_CRL_ENTRY       = 0xFF00,
+   OCSP_GOOD              = 0xFF01,
+   OCSP_UNKNOWN           = 0xFF02
+};
+
+/**
 * This class represents CRL entries
 */
 class BOTAN_DLL CRL_Entry : public ASN1_Object
diff --git a/src/cert/x509crl/x509_crl.cpp b/src/cert/x509crl/x509_crl.cpp
index 01fce4c52..9c6b891c7 100644
--- a/src/cert/x509crl/x509_crl.cpp
+++ b/src/cert/x509crl/x509_crl.cpp
@@ -7,6 +7,7 @@
 
 #include <botan/x509_crl.h>
 #include <botan/x509_ext.h>
+#include <botan/x509cert.h>
 #include <botan/ber_dec.h>
 #include <botan/parsing.h>
 #include <botan/bigint.h>
@@ -32,6 +33,43 @@ X509_CRL::X509_CRL(const std::string& in, bool touc) :
    do_decode();
    }
 
+/**
+* Check if this particular certificate is listed in the CRL
+*/
+bool X509_CRL::is_revoked(const X509_Certificate& cert) const
+   {
+   /*
+   If the cert wasn't issued by the CRL issuer, it's possible the cert
+   is revoked, but not by this CRL. Maybe throw an exception instead?
+   */
+   if(cert.issuer_dn() != issuer_dn())
+      return false;
+
+   MemoryVector<byte> crl_akid = authority_key_id();
+   MemoryVector<byte> cert_akid = cert.authority_key_id();
+
+   if(!crl_akid.empty() && !cert_akid.empty())
+      if(crl_akid != cert_akid)
+         return false;
+
+   MemoryVector<byte> cert_serial = cert.serial_number();
+
+   bool is_revoked = false;
+
+   for(size_t i = 0; i != revoked.size(); ++i)
+      {
+      if(cert_serial == revoked[i].serial_number())
+         {
+         if(revoked[i].reason_code() == REMOVE_FROM_CRL)
+            is_revoked = false;
+         else
+            is_revoked = true;
+         }
+      }
+
+   return is_revoked;
+   }
+
 /*
 * Decode the TBSCertList data
 */
diff --git a/src/cert/x509crl/x509_crl.h b/src/cert/x509crl/x509_crl.h
index c2b3c4f5c..55eb8424b 100644
--- a/src/cert/x509crl/x509_crl.h
+++ b/src/cert/x509crl/x509_crl.h
@@ -14,6 +14,8 @@
 
 namespace Botan {
 
+class X509_Certificate;
+
 /**
 * This class represents X.509 Certificate Revocation Lists (CRLs).
 */
@@ -30,6 +32,11 @@ class BOTAN_DLL X509_CRL : public X509_Object
          };
 
       /**
+      * Check if this particular certificate is listed in the CRL
+      */
+      bool is_revoked(const X509_Certificate& cert) const;
+
+      /**
       * Get the entries of this CRL in the form of a vector.
       * @return vector containing the entries of this CRL.
       */
diff --git a/src/cert/x509path/x509path.cpp b/src/cert/x509path/x509path.cpp
index d0153309c..e18c3b2f8 100644
--- a/src/cert/x509path/x509path.cpp
+++ b/src/cert/x509path/x509path.cpp
@@ -15,33 +15,193 @@
 
 namespace Botan {
 
-Path_Validation_Result x509_path_validate(
-   const X509_Certificate& cert,
-   const std::vector<Certificate_Store*>& certstores)
+namespace {
+
+class PKIX_Validation_Failure : public std::exception
+   {
+   public:
+      PKIX_Validation_Failure(X509_Path_Validation_Code code) : m_code(code) {}
+
+      X509_Path_Validation_Code code() const { return m_code; }
+
+      const char* what() { return "PKIX validation failed"; }
+   private:
+      X509_Path_Validation_Code m_code;
+   };
+
+X509_Certificate find_issuing_cert(const X509_Certificate& cert,
+                                   const std::vector<Certificate_Store*>& certstores)
    {
    const X509_DN issuer_dn = cert.issuer_dn();
    const MemoryVector<byte> auth_key_id = cert.authority_key_id();
 
-   Path_Validation_Result result;
+   for(size_t i = 0; i != certstores.size(); ++i)
+      {
+      std::vector<X509_Certificate> certs =
+         certstores[i]->find_cert_by_subject_and_key_id(issuer_dn, auth_key_id);
 
-   std::vector<X509_Certificate> cert_path;
+      if(certs.size() == 0)
+         throw PKIX_Validation_Failure(CERT_ISSUER_NOT_FOUND);
+      else if(certs.size() > 1)
+         throw PKIX_Validation_Failure(CERT_MULTIPLE_ISSUERS_FOUND);
 
-   cert_path.push_back(cert);
+      return certs[0];
+      }
+
+   throw PKIX_Validation_Failure(CERT_ISSUER_NOT_FOUND);
+   }
+
+std::vector<X509_CRL> find_crls_from(const X509_Certificate& cert,
+                                     const std::vector<Certificate_Store*>& certstores)
+   {
+   const X509_DN issuer_dn = cert.subject_dn();
+   const MemoryVector<byte> auth_key_id = cert.subject_key_id();
 
    for(size_t i = 0; i != certstores.size(); ++i)
       {
-      std::vector<X509_Certificate> got =
-         certstores[i]->find_cert_by_subject_and_key_id(issuer_dn, auth_key_id);
+      std::vector<X509_CRL> crl =
+         certstores[i]->find_crl_by_issuer_and_key_id(issuer_dn, auth_key_id);
+
+      if(!crl.empty())
+         return crl;
+      }
+
+   return std::vector<X509_CRL>();
+   }
+
+}
+
+std::set<std::string> Path_Validation_Result::trusted_hashes() const
+   {
+   std::set<std::string> hashes;
+   for(size_t i = 0; i != cert_path.size(); ++i)
+      hashes.insert(cert_path[i].hash_used_for_signature());
+   return hashes;
+   }
+
+Path_Validation_Result x509_path_validate(
+   const X509_Certificate& end_cert,
+   const std::vector<Certificate_Store*>& certstores)
+   {
+   std::vector<X509_Certificate> certs;
+   certs.push_back(end_cert);
+   return x509_path_validate(certs, certstores);
+   }
+
+Path_Validation_Result x509_path_validate(
+   const std::vector<X509_Certificate>& end_certs,
+   Certificate_Store& store)
+   {
+   std::vector<Certificate_Store*> certstores;
+   certstores.push_back(&store);
+
+   return x509_path_validate(end_certs, certstores);
+   }
+
+Path_Validation_Result x509_path_validate(
+   const X509_Certificate& end_cert,
+   Certificate_Store& store)
+   {
+   std::vector<X509_Certificate> certs;
+   certs.push_back(end_cert);
+
+   std::vector<Certificate_Store*> certstores;
+   certstores.push_back(&store);
+
+   return x509_path_validate(certs, certstores);
+   }
+
+Path_Validation_Result
+x509_path_validate(const std::vector<X509_Certificate>& end_certs,
+                   const std::vector<Certificate_Store*>& certstores)
+   {
+   Path_Validation_Result r;
+
+   r.cert_path = end_certs;
 
-      // What to do if it returns more than one match?
-      if(got.size() == 1)
+   try
+      {
+      // iterate until we reach a root or cannot find the issuer
+
+      while(!r.cert_path.back().is_self_signed())
          {
-         cert_path.push_back(got[0]);
-         break;
+         X509_Certificate cert = find_issuing_cert(r.cert_path.back(),
+                                                   certstores);
+
+         r.cert_path.push_back(cert);
          }
+
+      /*
+      for(size_t i = 0; i != r.cert_path.size(); ++i)
+         std::cout << "Cert " << i << " = " << r.cert_path[i].subject_dn() << "\n";
+      */
+
+      X509_Time current_time(system_time());
+
+      for(size_t i = 0; i != r.cert_path.size(); ++i)
+         {
+         const X509_Certificate& subject = r.cert_path[i];
+
+         // Check all certs for valid time range
+         if(current_time < X509_Time(subject.start_time()))
+            throw PKIX_Validation_Failure(CERT_NOT_YET_VALID);
+
+         if(current_time > X509_Time(subject.end_time()))
+            throw PKIX_Validation_Failure(CERT_HAS_EXPIRED);
+
+         const bool at_self_signed_root = (i == r.cert_path.size() - 1);
+
+         const X509_Certificate& issuer =
+            r.cert_path[at_self_signed_root ? (i) : (i + 1)];
+
+         // Check issuer constraints
+         if(!issuer.is_CA_cert()) // require this for self-signed end-entity?
+            throw PKIX_Validation_Failure(CA_CERT_NOT_FOR_CERT_ISSUER);
+
+         if(issuer.path_limit() < i)
+            throw PKIX_Validation_Failure(CERT_CHAIN_TOO_LONG);
+
+         if(subject.check_signature(issuer.subject_public_key()) == false)
+            throw PKIX_Validation_Failure(SIGNATURE_ERROR);
+         }
+
+      r.validation_result = VERIFIED;
+
+      for(size_t i = 1; i != r.cert_path.size(); ++i)
+         {
+         const X509_Certificate& subject = r.cert_path[i-1];
+         const X509_Certificate& ca = r.cert_path[i];
+
+         std::vector<X509_CRL> crls = find_crls_from(ca, certstores);
+
+         if(crls.empty())
+            throw PKIX_Validation_Failure(CRL_NOT_FOUND);
+
+         const X509_CRL& crl = crls[0];
+
+         if(!ca.allowed_usage(CRL_SIGN))
+            throw PKIX_Validation_Failure(CA_CERT_NOT_FOR_CRL_ISSUER);
+
+         if(current_time < X509_Time(crl.this_update()))
+            throw PKIX_Validation_Failure(CRL_NOT_YET_VALID);
+
+         if(current_time > X509_Time(crl.next_update()))
+            throw PKIX_Validation_Failure(CRL_HAS_EXPIRED);
+
+         if(crl.check_signature(ca.subject_public_key()) == false)
+            throw PKIX_Validation_Failure(SIGNATURE_ERROR);
+
+         if(crl.is_revoked(subject))
+            throw PKIX_Validation_Failure(CERT_IS_REVOKED);
+         }
+
+      }
+   catch(PKIX_Validation_Failure& e)
+      {
+      r.validation_result = e.code();
       }
 
-   return result;
+   return r;
    }
 
 }
diff --git a/src/cert/x509path/x509path.h b/src/cert/x509path/x509path.h
index 57e4764cc..b32a69162 100644
--- a/src/cert/x509path/x509path.h
+++ b/src/cert/x509path/x509path.h
@@ -34,6 +34,7 @@ enum X509_Path_Validation_Code {
    CERT_HAS_EXPIRED,
    CERT_IS_REVOKED,
 
+   CRL_NOT_FOUND,
    CRL_FORMAT_ERROR,
    CRL_ISSUER_NOT_FOUND,
    CRL_NOT_YET_VALID,
@@ -44,38 +45,51 @@ enum X509_Path_Validation_Code {
    CA_CERT_NOT_FOR_CRL_ISSUER
 };
 
-enum X509_Cert_Usage {
-   NO_RESTRICTIONS  = 0x00,
-   TLS_SERVER       = 0x01,
-   TLS_CLIENT       = 0x02,
-   CODE_SIGNING     = 0x04,
-   EMAIL_PROTECTION = 0x08,
-   TIME_STAMPING    = 0x10,
-   CRL_SIGNING      = 0x20
-};
+      enum Usage_Restrictions {
+         NO_RESTRICTIONS  = 0x00,
+         TLS_SERVER       = 0x01,
+         TLS_CLIENT       = 0x02,
+         CODE_SIGNING     = 0x04,
+         EMAIL_PROTECTION = 0x08,
+         TIME_STAMPING    = 0x10,
+         CRL_SIGNING      = 0x20
+      };
 
 class Path_Validation_Result
    {
    public:
+      Path_Validation_Result() :
+         validation_result(UNKNOWN_X509_ERROR),
+         allowed_usages(NO_RESTRICTIONS)
+         {}
+
       X509_Path_Validation_Code validation_result;
-      X509_Cert_Usage allowed_usages;
+      Usage_Restrictions allowed_usages;
+
       std::vector<X509_Certificate> cert_path;
 
+      /**
+      * Returns the set of hash functions you are implicitly
+      * trusting by trusting this result.
+      */
       std::set<std::string> trusted_hashes() const;
    };
 
 Path_Validation_Result BOTAN_DLL x509_path_validate(
+   const std::vector<X509_Certificate>& end_certs,
+   const std::vector<Certificate_Store*>& certstores);
+
+Path_Validation_Result BOTAN_DLL x509_path_validate(
    const X509_Certificate& end_cert,
    const std::vector<Certificate_Store*>& certstores);
 
-inline Path_Validation_Result x509_path_validate(
+Path_Validation_Result BOTAN_DLL x509_path_validate(
    const X509_Certificate& end_cert,
-   Certificate_Store& store)
-   {
-   std::vector<Certificate_Store*> store_vec;
-   store_vec.push_back(&store);
-   return x509_path_validate(end_cert, store_vec);
-   }
+   Certificate_Store& store);
+
+Path_Validation_Result BOTAN_DLL x509_path_validate(
+   const std::vector<X509_Certificate>& end_certs,
+   Certificate_Store& store);
 
 }