Add Public_Key::estimated_strength which gives an approximation of how

hard that key is to break.

Use it in cert path validation, rejecting keys with estimated strength
less than 80 bits.

12 files changed, 99 insertions, 14 deletions

diff --git a/doc/relnotes/1_11_1.rst b/doc/relnotes/1_11_1.rst
new file mode 100644
index 000000000..07b1fc62e
--- /dev/null
+++ b/doc/relnotes/1_11_1.rst
@@ -0,0 +1,13 @@
+Version 1.11.1, Not Yet Released
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+A new function :cpp:func:`Public_Key::estimated_strength` returns
+an estimate for the upper bound of the strength of the key. For
+instance for an RSA key, it will return an estimate of how many
+operations GNFS would take to factor the key.
+
+A new :cpp:class:`Path_Validation_Result` code has been added
+``SIGNATURE_METHOD_TOO_WEAK``. By default signatures created with keys
+below 80 bits of strength (as estimated by ``estimated_strength``) are
+rejected. This level can be modified using a parameter to the
+:cpp:class:`Path_Validation_Restrictions` constructor.
diff --git a/doc/relnotes/index.rst b/doc/relnotes/index.rst
index bb4902824..775f4ce2d 100644
--- a/doc/relnotes/index.rst
+++ b/doc/relnotes/index.rst
@@ -1,4 +1,3 @@
-.. toctree::
 
 Release Notes
 ========================================
@@ -7,7 +6,9 @@ Series 1.11
 ----------------------------------------
 
 .. toctree::
+   :maxdepth: 1
 
+   1_11_1
    1_11_0
 
 Series 1.10
diff --git a/doc/x509.rst b/doc/x509.rst
index c7f871898..be93c604c 100644
--- a/doc/x509.rst
+++ b/doc/x509.rst
@@ -219,6 +219,22 @@ The process of validating a certfificate chain up to a trusted root is
 called `path validation`, and in botan that operation is handled by a
 set of functions in ``x509path.h`` named ``x509_path_validate``.
 
+.. cpp:class:: Path_Validation_Result
+
+   Specifies the result of the validation
+
+.. cpp:class:: Path_Validation_Restrictions
+
+   Specifies restrictions on the validation operation
+
+.. cpp:function:: Path_Validation_Result \
+     x509_path_validate(const X509_Certificate& end_cert, \
+     const Path_Validation_Restrictions& restrictions, \
+     const Certificate_Store& store)
+
+    Validates a path
+
+
 Certificate Authorities
 ---------------------------------
 
diff --git a/src/cert/x509/x509path.cpp b/src/cert/x509/x509path.cpp
index 66ba142d0..7d6108ffa 100644
--- a/src/cert/x509/x509path.cpp
+++ b/src/cert/x509/x509path.cpp
@@ -72,8 +72,10 @@ std::vector<X509_CRL> find_crls_from(const X509_Certificate& cert,
 
 }
 
-Path_Validation_Restrictions::Path_Validation_Restrictions(bool require_rev) :
-   m_require_revocation_information(require_rev)
+Path_Validation_Restrictions::Path_Validation_Restrictions(bool require_rev,
+                                                           size_t key_strength) :
+   m_require_revocation_information(require_rev),
+   m_minimum_key_strength(key_strength)
    {
    m_trusted_hashes.insert("SHA-160");
    m_trusted_hashes.insert("SHA-224");
@@ -96,7 +98,7 @@ std::set<std::string> Path_Validation_Result::trusted_hashes() const
    }
 
 std::string Path_Validation_Result::result_string() const
-    {
+   {
    switch(m_result)
       {
       case VERIFIED:
@@ -109,6 +111,9 @@ std::string Path_Validation_Result::result_string() const
          return "certificate chain too long";
       case SIGNATURE_ERROR:
          return "signature error";
+      case SIGNATURE_METHOD_TOO_WEAK:
+         return "signature method too weak";
+
       case POLICY_ERROR:
          return "policy error";
       case INVALID_USAGE:
@@ -142,11 +147,11 @@ std::string Path_Validation_Result::result_string() const
          return "CA certificate not allowed to issue certs";
       case CA_CERT_NOT_FOR_CRL_ISSUER:
          return "CA certificate not allowed to issue CRLs";
-
-      default:
-         return "Unknown code " + std::to_string(m_result);
       }
-    }
+
+   // default case
+   return "Unknown code " + std::to_string(m_result);
+   }
 
 Path_Validation_Result x509_path_validate(
    const X509_Certificate& end_cert,
@@ -244,8 +249,13 @@ Path_Validation_Result x509_path_validate(
          if(issuer.path_limit() < i)
             throw PKIX_Validation_Failure(Path_Validation_Result::CERT_CHAIN_TOO_LONG);
 
-         if(subject.check_signature(issuer.subject_public_key()) == false)
+         std::unique_ptr<Public_Key> issuer_key(issuer.subject_public_key());
+
+         if(subject.check_signature(*issuer_key) == false)
             throw PKIX_Validation_Failure(Path_Validation_Result::SIGNATURE_ERROR);
+
+         if(issuer_key->estimated_strength() < restrictions.minimum_key_strength())
+            throw PKIX_Validation_Failure(Path_Validation_Result::SIGNATURE_METHOD_TOO_WEAK);
          }
 
       for(size_t i = 1; i != cert_path.size(); ++i)
diff --git a/src/cert/x509/x509path.h b/src/cert/x509/x509path.h
index 21b808073..ae28599b0 100644
--- a/src/cert/x509/x509path.h
+++ b/src/cert/x509/x509path.h
@@ -17,21 +17,29 @@ namespace Botan {
 class BOTAN_DLL Path_Validation_Restrictions
    {
    public:
-   Path_Validation_Restrictions(bool require_rev = false);
+      Path_Validation_Restrictions(bool require_rev = false,
+                                   size_t minimum_key_strength = 80);
 
-   Path_Validation_Restrictions(bool require_rev,
-                                const std::set<std::string>& trusted_hashes) :
-      m_require_revocation_information(require_rev),
-      m_trusted_hashes(trusted_hashes) {}
+      Path_Validation_Restrictions(bool require_rev,
+                                   size_t minimum_key_strength,
+                                   const std::set<std::string>& trusted_hashes) :
+         m_require_revocation_information(require_rev),
+         m_trusted_hashes(trusted_hashes),
+         m_minimum_key_strength(minimum_key_strength) {}
 
       bool require_revocation_information() const
          { return m_require_revocation_information; }
 
       const std::set<std::string>& trusted_hashes() const
          { return m_trusted_hashes; }
+
+      size_t minimum_key_strength() const
+         { return m_minimum_key_strength; }
+
    private:
       bool m_require_revocation_information;
       std::set<std::string> m_trusted_hashes;
+      size_t m_minimum_key_strength;
    };
 
 class BOTAN_DLL Path_Validation_Result
@@ -48,6 +56,8 @@ class BOTAN_DLL Path_Validation_Result
          SIGNATURE_ERROR,
          POLICY_ERROR,
          INVALID_USAGE,
+
+         SIGNATURE_METHOD_TOO_WEAK,
          UNTRUSTED_HASH,
 
          CERT_MULTIPLE_ISSUERS_FOUND,
diff --git a/src/pubkey/dl_algo/dl_algo.cpp b/src/pubkey/dl_algo/dl_algo.cpp
index c90e7651e..22c432108 100644
--- a/src/pubkey/dl_algo/dl_algo.cpp
+++ b/src/pubkey/dl_algo/dl_algo.cpp
@@ -7,11 +7,17 @@
 
 #include <botan/dl_algo.h>
 #include <botan/numthry.h>
+#include <botan/internal/workfactor.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
 
 namespace Botan {
 
+size_t DL_Scheme_PublicKey::estimated_strength() const
+   {
+   return dl_work_factor(group.get_p().bits());
+   }
+
 AlgorithmIdentifier DL_Scheme_PublicKey::algorithm_identifier() const
    {
    return AlgorithmIdentifier(get_oid(),
diff --git a/src/pubkey/dl_algo/dl_algo.h b/src/pubkey/dl_algo/dl_algo.h
index af2806b02..abd2acba4 100644
--- a/src/pubkey/dl_algo/dl_algo.h
+++ b/src/pubkey/dl_algo/dl_algo.h
@@ -61,6 +61,8 @@ class BOTAN_DLL DL_Scheme_PublicKey : public virtual Public_Key
       */
       virtual DL_Group::Format group_format() const = 0;
 
+      size_t estimated_strength() const override;
+
       DL_Scheme_PublicKey(const AlgorithmIdentifier& alg_id,
                           const secure_vector<byte>& key_bits,
                           DL_Group::Format group_format);
diff --git a/src/pubkey/ecc_key/ecc_key.cpp b/src/pubkey/ecc_key/ecc_key.cpp
index 367b27584..22bc41249 100644
--- a/src/pubkey/ecc_key/ecc_key.cpp
+++ b/src/pubkey/ecc_key/ecc_key.cpp
@@ -18,6 +18,11 @@
 
 namespace Botan {
 
+size_t EC_PublicKey::estimated_strength() const
+   {
+   return domain().get_curve().get_p().bits() / 2;
+   }
+
 EC_PublicKey::EC_PublicKey(const EC_Group& dom_par,
                            const PointGFp& pub_point) :
    domain_params(dom_par), public_key(pub_point),
diff --git a/src/pubkey/ecc_key/ecc_key.h b/src/pubkey/ecc_key/ecc_key.h
index 76a63a7e4..de980608a 100644
--- a/src/pubkey/ecc_key/ecc_key.h
+++ b/src/pubkey/ecc_key/ecc_key.h
@@ -78,6 +78,9 @@ class BOTAN_DLL EC_PublicKey : public virtual Public_Key
       */
       EC_Group_Encoding domain_format() const
          { return domain_encoding; }
+
+      size_t estimated_strength() const override;
+
    protected:
       EC_PublicKey() : domain_encoding(EC_DOMPAR_ENC_EXPLICIT) {}
 
diff --git a/src/pubkey/if_algo/if_algo.cpp b/src/pubkey/if_algo/if_algo.cpp
index f044afd03..56419bb03 100644
--- a/src/pubkey/if_algo/if_algo.cpp
+++ b/src/pubkey/if_algo/if_algo.cpp
@@ -7,11 +7,17 @@
 
 #include <botan/if_algo.h>
 #include <botan/numthry.h>
+#include <botan/internal/workfactor.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
 
 namespace Botan {
 
+size_t IF_Scheme_PublicKey::estimated_strength() const
+   {
+   return dl_work_factor(n.bits());
+   }
+
 AlgorithmIdentifier IF_Scheme_PublicKey::algorithm_identifier() const
    {
    return AlgorithmIdentifier(get_oid(),
diff --git a/src/pubkey/if_algo/if_algo.h b/src/pubkey/if_algo/if_algo.h
index 5c95aecd1..7dd6d19f0 100644
--- a/src/pubkey/if_algo/if_algo.h
+++ b/src/pubkey/if_algo/if_algo.h
@@ -45,6 +45,8 @@ class BOTAN_DLL IF_Scheme_PublicKey : public virtual Public_Key
 
       size_t max_input_bits() const { return (n.bits() - 1); }
 
+      size_t estimated_strength() const override;
+
    protected:
       IF_Scheme_PublicKey() {}
 
diff --git a/src/pubkey/pk_keys.h b/src/pubkey/pk_keys.h
index a3b693956..a8585c154 100644
--- a/src/pubkey/pk_keys.h
+++ b/src/pubkey/pk_keys.h
@@ -28,6 +28,17 @@ class BOTAN_DLL Public_Key
       virtual std::string algo_name() const = 0;
 
       /**
+      * Return the estimated strength of the underlying key against
+      * the best currently known attack. Note that this ignores anything
+      * but pure attacks against the key itself and do not take into
+      * account padding schemes, usage mistakes, etc which might reduce
+      * the strength. However it does suffice to provide an upper bound.
+      *
+      * @return estimated strength in bits
+      */
+      virtual size_t estimated_strength() const = 0;
+
+      /**
       * Get the OID of the underlying public key scheme.
       * @return OID of the public key scheme
       */