Merge GH #2057 OID cleanups

51 files changed, 386 insertions, 366 deletions

diff --git a/src/build-data/oids.txt b/src/build-data/oids.txt
index cb4ea5456..063f52069 100644
--- a/src/build-data/oids.txt
+++ b/src/build-data/oids.txt
@@ -103,12 +103,11 @@
 # Hash functions
 1.2.840.113549.2.5 = MD5
 1.3.6.1.4.1.11591.12.2 = Tiger(24,3)
-
 1.2.156.10197.1.401 = SM3
-
 1.3.14.3.2.26 = SHA-160
-
 1.3.36.3.2.1 = RIPEMD-160
+1.2.643.7.1.1.2.2 = Streebog-256
+1.2.643.7.1.1.2.3 = Streebog-512
 
 # From NIST:
 2.16.840.1.101.3.4.2.1 = SHA-256
@@ -198,8 +197,6 @@
 1.2.410.200004.1.100.4.5 = ECKCDSA/EMSA1(SHA-256)
 
 1.2.643.2.2.3 = GOST-34.10/EMSA1(GOST-R-34.11-94)
-1.2.643.7.1.1.2.2 = Streebog-256
-1.2.643.7.1.1.2.3 = Streebog-512
 
 1.2.643.7.1.1.3.2 = GOST-34.10-2012-256/EMSA1(Streebog-256)
 1.2.643.7.1.1.3.3 = GOST-34.10-2012-512/EMSA1(Streebog-512)
diff --git a/src/cli/pk_crypt.cpp b/src/cli/pk_crypt.cpp
index b7fd62ac1..38b16bb82 100644
--- a/src/cli/pk_crypt.cpp
+++ b/src/cli/pk_crypt.cpp
@@ -59,7 +59,7 @@ class PK_Encrypt final : public Command
          if(!aead)
             throw CLI_Usage_Error("The AEAD '" + aead_algo + "' is not available");
 
-         const Botan::OID aead_oid = Botan::OIDS::lookup(aead_algo);
+         const Botan::OID aead_oid = Botan::OID::from_string(aead_algo);
          if(aead_oid.empty())
             throw CLI_Usage_Error("No OID defined for AEAD '" + aead_algo + "'");
 
@@ -159,14 +159,14 @@ class PK_Decrypt final : public Command
             return set_return_code(1);
             }
 
-         const std::string aead_algo = Botan::OIDS::lookup(aead_oid);
+         const std::string aead_algo = Botan::OIDS::oid2str_or_empty(aead_oid);
          if(aead_algo == "")
             {
             error_output() << "Ciphertext was encrypted with an unknown algorithm";
             return set_return_code(1);
             }
 
-         if(pk_alg_id.get_oid() != Botan::OIDS::lookup("RSA/OAEP"))
+         if(pk_alg_id.get_oid() != Botan::OID::from_string("RSA/OAEP"))
             {
             error_output() << "Ciphertext was encrypted with something other than RSA/OAEP";
             return set_return_code(1);
@@ -175,7 +175,7 @@ class PK_Decrypt final : public Command
          Botan::AlgorithmIdentifier oaep_hash_id;
          Botan::BER_Decoder(pk_alg_id.get_parameters()).decode(oaep_hash_id);
 
-         const std::string oaep_hash = Botan::OIDS::lookup(oaep_hash_id.get_oid());
+         const std::string oaep_hash = Botan::OIDS::oid2str_or_empty(oaep_hash_id.get_oid());
 
          if(oaep_hash.empty())
             {
diff --git a/src/lib/asn1/alg_id.cpp b/src/lib/asn1/alg_id.cpp
index 0637a8f8d..4839303db 100644
--- a/src/lib/asn1/alg_id.cpp
+++ b/src/lib/asn1/alg_id.cpp
@@ -26,8 +26,7 @@ AlgorithmIdentifier::AlgorithmIdentifier(const OID& alg_id,
 */
 AlgorithmIdentifier::AlgorithmIdentifier(const std::string& alg_id,
                                          const std::vector<uint8_t>& param) :
-   oid(OIDS::lookup(alg_id)),
-   parameters(param)
+   AlgorithmIdentifier(OID::from_string(alg_id), param)
    {}
 
 /*
@@ -49,7 +48,7 @@ AlgorithmIdentifier::AlgorithmIdentifier(const OID& alg_id,
 */
 AlgorithmIdentifier::AlgorithmIdentifier(const std::string& alg_id,
                                          Encoding_Option option) :
-   oid(OIDS::lookup(alg_id)),
+   oid(OID::from_string(alg_id)),
    parameters()
    {
    const uint8_t DER_NULL[] = { 0x05, 0x00 };
diff --git a/src/lib/asn1/asn1_attribute.cpp b/src/lib/asn1/asn1_attribute.cpp
index 8ecd8fd5f..3106dda70 100644
--- a/src/lib/asn1/asn1_attribute.cpp
+++ b/src/lib/asn1/asn1_attribute.cpp
@@ -25,7 +25,7 @@ Attribute::Attribute(const OID& attr_oid, const std::vector<uint8_t>& attr_value
 */
 Attribute::Attribute(const std::string& attr_oid,
                      const std::vector<uint8_t>& attr_value) :
-   oid(OIDS::lookup(attr_oid)),
+   oid(OID::from_string(attr_oid)),
    parameters(attr_value)
    {}
 
diff --git a/src/lib/asn1/asn1_oid.cpp b/src/lib/asn1/asn1_oid.cpp
index c94f7c8b5..f1f229eee 100644
--- a/src/lib/asn1/asn1_oid.cpp
+++ b/src/lib/asn1/asn1_oid.cpp
@@ -10,9 +10,72 @@
 #include <botan/ber_dec.h>
 #include <botan/internal/bit_ops.h>
 #include <botan/parsing.h>
+#include <botan/oids.h>
+#include <algorithm>
+#include <sstream>
 
 namespace Botan {
 
+namespace {
+
+// returns empty on invalid
+std::vector<uint32_t> parse_oid_str(const std::string& oid)
+   {
+   try
+      {
+      std::string elem;
+      std::vector<uint32_t> oid_elems;
+
+      for(char c : oid)
+         {
+         if(c == '.')
+            {
+            if(elem.empty())
+               return std::vector<uint32_t>();
+            oid_elems.push_back(to_u32bit(elem));
+            elem.clear();
+            }
+         else
+            {
+            elem += c;
+            }
+         }
+
+      if(elem.empty())
+         return std::vector<uint32_t>();
+      oid_elems.push_back(to_u32bit(elem));
+
+      if(oid_elems.size() < 2)
+         return std::vector<uint32_t>();
+
+      return oid_elems;
+      }
+   catch(Invalid_Argument&) // thrown by to_u32bit
+      {
+      return std::vector<uint32_t>();
+      }
+   }
+
+}
+
+//static
+OID OID::from_string(const std::string& str)
+   {
+   if(str.empty())
+      throw Invalid_Argument("OID::from_string argument must be non-empty");
+
+   // first try as a dotted decimal OID string:
+   std::vector<uint32_t> raw = parse_oid_str(str);
+
+   if(raw.size() > 0)
+      return OID(std::move(raw));
+
+   const OID o = OIDS::str2oid_or_empty(str);
+   if(o.empty())
+      throw Lookup_Error("No OID associated with name " + str);
+   return o;
+   }
+
 /*
 * ASN.1 OID Constructor
 */
@@ -20,14 +83,7 @@ OID::OID(const std::string& oid_str)
    {
    if(!oid_str.empty())
       {
-      try
-         {
-         m_id = parse_asn1_oid(oid_str);
-         }
-      catch(...)
-         {
-         throw Invalid_OID(oid_str);
-         }
+      m_id = parse_oid_str(oid_str);
 
       if(m_id.size() < 2 || m_id[0] > 2)
          throw Invalid_OID(oid_str);
@@ -37,66 +93,36 @@ OID::OID(const std::string& oid_str)
    }
 
 /*
-* Clear the current OID
-*/
-void OID::clear()
-   {
-   m_id.clear();
-   }
-
-/*
 * Return this OID as a string
 */
 std::string OID::to_string() const
    {
-   std::string oid_str;
+   std::ostringstream oss;
    for(size_t i = 0; i != m_id.size(); ++i)
       {
-      oid_str += std::to_string(m_id[i]);
+      oss << m_id[i];
       if(i != m_id.size() - 1)
-         oid_str += ".";
+         oss << ".";
       }
-   return oid_str;
+   return oss.str();
    }
 
-/*
-* OID equality comparison
-*/
-bool OID::operator==(const OID& oid) const
+std::string OID::to_formatted_string() const
    {
-   if(m_id.size() != oid.m_id.size())
-      return false;
-   for(size_t i = 0; i != m_id.size(); ++i)
-      if(m_id[i] != oid.m_id[i])
-         return false;
-   return true;
+   const std::string s = OIDS::oid2str_or_empty(*this);
+   if(!s.empty())
+      return s;
+   return this->to_string();
    }
 
 /*
 * Append another component to the OID
 */
-OID& OID::operator+=(uint32_t component)
+OID operator+(const OID& oid, uint32_t new_component)
    {
-   m_id.push_back(component);
-   return (*this);
-   }
-
-/*
-* Append another component to the OID
-*/
-OID operator+(const OID& oid, uint32_t component)
-   {
-   OID new_oid(oid);
-   new_oid += component;
-   return new_oid;
-   }
-
-/*
-* OID inequality comparison
-*/
-bool operator!=(const OID& a, const OID& b)
-   {
-   return !(a == b);
+   std::vector<uint32_t> val = oid.get_components();
+   val.push_back(new_component);
+   return OID(std::move(val));
    }
 
 /*
@@ -104,21 +130,11 @@ bool operator!=(const OID& a, const OID& b)
 */
 bool operator<(const OID& a, const OID& b)
    {
-   const std::vector<uint32_t>& oid1 = a.get_id();
-   const std::vector<uint32_t>& oid2 = b.get_id();
-
-   if(oid1.size() < oid2.size())
-      return true;
-   if(oid1.size() > oid2.size())
-      return false;
-   for(size_t i = 0; i != oid1.size(); ++i)
-      {
-      if(oid1[i] < oid2[i])
-         return true;
-      if(oid1[i] > oid2[i])
-         return false;
-      }
-   return false;
+   const std::vector<uint32_t>& oid1 = a.get_components();
+   const std::vector<uint32_t>& oid2 = b.get_components();
+
+   return std::lexicographical_compare(oid1.begin(), oid1.end(),
+                                       oid2.begin(), oid2.end());
    }
 
 /*
@@ -172,7 +188,7 @@ void OID::decode_from(BER_Decoder& decoder)
       throw BER_Decoding_Error("OID encoding is too short");
       }
 
-   clear();
+   m_id.clear();
    m_id.push_back(bits[0] / 40);
    m_id.push_back(bits[0] % 40);
 
diff --git a/src/lib/asn1/asn1_oid.h b/src/lib/asn1/asn1_oid.h
index 1c8959d99..5ce7a0c73 100644
--- a/src/lib/asn1/asn1_oid.h
+++ b/src/lib/asn1/asn1_oid.h
@@ -1,6 +1,6 @@
 /*
 * ASN.1 OID
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2007,2019 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -20,6 +20,35 @@ namespace Botan {
 class BOTAN_PUBLIC_API(2,0) OID final : public ASN1_Object
    {
    public:
+
+      /**
+      * Create an uninitialied OID object
+      */
+      explicit OID() {}
+
+      /**
+      * Construct an OID from a string.
+      * @param str a string in the form "a.b.c" etc., where a,b,c are numbers
+      */
+      explicit OID(const std::string& str);
+
+      /**
+      * Initialize an OID from a sequence of integer values
+      */
+      explicit OID(std::initializer_list<uint32_t> init) : m_id(init) {}
+
+      /**
+      * Initialize an OID from a vector of integer values
+      */
+      explicit OID(std::vector<uint32_t>&& init) : m_id(init) {}
+
+      /**
+      * Construct an OID from a string.
+      * @param str a string in the form "a.b.c" etc., where a,b,c are numbers
+      *        or any known OID name (for example "RSA" or "X509v3.SubjectKeyIdentifier")
+      */
+      static OID from_string(const std::string& str);
+
       void encode_into(class DER_Encoder&) const override;
       void decode_from(class BER_Decoder&) override;
 
@@ -39,7 +68,9 @@ class BOTAN_PUBLIC_API(2,0) OID final : public ASN1_Object
       * Get this OID as list (vector) of its components.
       * @return vector representing this OID
       */
-      const std::vector<uint32_t>& get_id() const { return m_id; }
+      const std::vector<uint32_t>& get_components() const { return m_id; }
+
+      //const std::vector<uint32_t>& get_id() const { return get_components(); }
 
       /**
       * Get this OID as a string
@@ -51,36 +82,42 @@ class BOTAN_PUBLIC_API(2,0) OID final : public ASN1_Object
          }
 
       /**
-      * Get this OID as a string
+      * Get this OID as a dotted-decimal string
       * @return string representing this OID
       */
       std::string to_string() const;
 
       /**
+      * If there is a known name associated with this OID, return that.
+      * Otherwise return the result of to_string
+      */
+      std::string to_formatted_string() const;
+
+      /**
       * Compare two OIDs.
       * @return true if they are equal, false otherwise
       */
-      bool operator==(const OID&) const;
+      bool operator==(const OID& other) const
+         {
+         return m_id == other.m_id;
+         }
 
       /**
       * Reset this instance to an empty OID.
       */
-      void clear();
+      void BOTAN_DEPRECATED("Avoid mutation of OIDs") clear() { m_id.clear(); }
 
       /**
       * Add a component to this OID.
       * @param new_comp the new component to add to the end of this OID
       * @return reference to *this
       */
-      OID& operator+=(uint32_t new_comp);
-
-      /**
-      * Construct an OID from a string.
-      * @param str a string in the form "a.b.c" etc., where a,b,c are numbers
-      */
-      explicit OID(const std::string& str = "");
+      OID& BOTAN_DEPRECATED("Avoid mutation of OIDs") operator+=(uint32_t new_comp)
+         {
+         m_id.push_back(new_comp);
+         return (*this);
+         }
 
-      explicit OID(std::initializer_list<uint32_t> init) : m_id(init) {}
    private:
       std::vector<uint32_t> m_id;
    };
@@ -98,7 +135,10 @@ OID BOTAN_PUBLIC_API(2,0) operator+(const OID& oid, uint32_t new_comp);
 * @param b the second OID
 * @return true if a is not equal to b
 */
-bool BOTAN_PUBLIC_API(2,0) operator!=(const OID& a, const OID& b);
+inline bool operator!=(const OID& a, const OID& b)
+   {
+   return !(a == b);
+   }
 
 /**
 * Compare two OIDs.
diff --git a/src/lib/asn1/asn1_print.cpp b/src/lib/asn1/asn1_print.cpp
index 14f5b71a9..5b22c1d3a 100644
--- a/src/lib/asn1/asn1_print.cpp
+++ b/src/lib/asn1/asn1_print.cpp
@@ -149,7 +149,7 @@ void ASN1_Formatter::decode(std::ostream& output,
          OID oid;
          data.decode(oid);
 
-         std::string out = OIDS::lookup(oid);
+         std::string out = OIDS::oid2str_or_empty(oid);
          if(out.empty())
             {
             out = oid.to_string();
diff --git a/src/lib/asn1/oids.cpp b/src/lib/asn1/oids.cpp
index 844cdff79..bece7a9b4 100644
--- a/src/lib/asn1/oids.cpp
+++ b/src/lib/asn1/oids.cpp
@@ -10,8 +10,6 @@
 
 namespace Botan {
 
-namespace OIDS {
-
 namespace {
 
 class OID_Map final
@@ -40,7 +38,7 @@ class OID_Map final
             m_oid2str.insert(std::make_pair(oid_str, str));
          }
 
-      std::string lookup(const OID& oid)
+      std::string oid2str(const OID& oid)
          {
          const std::string oid_str = oid.to_string();
 
@@ -53,7 +51,7 @@ class OID_Map final
          return "";
          }
 
-      OID lookup(const std::string& str)
+      OID str2oid(const std::string& str)
          {
          lock_guard_type<mutex_type> lock(m_mutex);
          auto i = m_str2oid.find(str);
@@ -79,8 +77,8 @@ class OID_Map final
 
       OID_Map()
          {
-         m_str2oid = load_str2oid_map();
-         m_oid2str = load_oid2str_map();
+         m_str2oid = OIDS::load_str2oid_map();
+         m_oid2str = OIDS::load_oid2str_map();
          }
 
       mutex_type m_mutex;
@@ -90,46 +88,47 @@ class OID_Map final
 
 }
 
-void add_oid(const OID& oid, const std::string& name)
+void OIDS::add_oid(const OID& oid, const std::string& name)
    {
    OID_Map::global_registry().add_oid(oid, name);
    }
 
-void add_oidstr(const char* oidstr, const char* name)
+void OIDS::add_oidstr(const char* oidstr, const char* name)
    {
    add_oid(OID(oidstr), name);
    }
 
-void add_oid2str(const OID& oid, const std::string& name)
+void OIDS::add_oid2str(const OID& oid, const std::string& name)
    {
    OID_Map::global_registry().add_oid2str(oid, name);
    }
 
-void add_str2oid(const OID& oid, const std::string& name)
+void OIDS::add_str2oid(const OID& oid, const std::string& name)
    {
    OID_Map::global_registry().add_str2oid(oid, name);
    }
 
-std::string lookup(const OID& oid)
+std::string OIDS::oid2str_or_empty(const OID& oid)
    {
-   return OID_Map::global_registry().lookup(oid);
+   return OID_Map::global_registry().oid2str(oid);
    }
 
-OID lookup(const std::string& name)
+OID OIDS::str2oid_or_empty(const std::string& name)
    {
-   return OID_Map::global_registry().lookup(name);
+   return OID_Map::global_registry().str2oid(name);
    }
 
-bool have_oid(const std::string& name)
+std::string OIDS::oid2str_or_throw(const OID& oid)
    {
-   return OID_Map::global_registry().have_oid(name);
+   const std::string s = OIDS::oid2str_or_empty(oid);
+   if(s.empty())
+      throw Lookup_Error("No name associated with OID " + oid.to_string());
+   return s;
    }
 
-bool name_of(const OID& oid, const std::string& name)
+bool OIDS::have_oid(const std::string& name)
    {
-   return (oid == lookup(name));
+   return OID_Map::global_registry().have_oid(name);
    }
 
 }
-
-}
diff --git a/src/lib/asn1/oids.h b/src/lib/asn1/oids.h
index 7b87b5eaf..480e4f982 100644
--- a/src/lib/asn1/oids.h
+++ b/src/lib/asn1/oids.h
@@ -33,9 +33,9 @@ std::unordered_map<std::string, OID> load_str2oid_map();
 /**
 * Resolve an OID
 * @param oid the OID to look up
-* @return name associated with this OID
+* @return name associated with this OID, or an empty string
 */
-BOTAN_PUBLIC_API(2,0) std::string lookup(const OID& oid);
+BOTAN_UNSTABLE_API std::string oid2str_or_empty(const OID& oid);
 
 /**
 * Find the OID to a name. The lookup will be performed in the
@@ -43,24 +43,16 @@ BOTAN_PUBLIC_API(2,0) std::string lookup(const OID& oid);
 * @param name the name to resolve
 * @return OID associated with the specified name
 */
-BOTAN_PUBLIC_API(2,0) OID lookup(const std::string& name);
+BOTAN_UNSTABLE_API OID str2oid_or_empty(const std::string& name);
 
-inline std::string oid2str(const OID& oid)
-   {
-   return lookup(oid);
-   }
-
-inline OID str2oid(const std::string& name)
-   {
-   return lookup(name);
-   }
+BOTAN_UNSTABLE_API std::string oid2str_or_throw(const OID& oid);
 
 /**
 * See if an OID exists in the internal table.
 * @param oid the oid to check for
 * @return true if the oid is registered
 */
-BOTAN_UNSTABLE_API bool have_oid(const std::string& oid);
+BOTAN_UNSTABLE_API bool BOTAN_DEPRECATED("Just lookup the value instead") have_oid(const std::string& oid);
 
 /**
 * Tests whether the specified OID stands for the specified name.
@@ -68,7 +60,31 @@ BOTAN_UNSTABLE_API bool have_oid(const std::string& oid);
 * @param name the name to check
 * @return true if the specified OID stands for the specified name
 */
-BOTAN_UNSTABLE_API bool name_of(const OID& oid, const std::string& name);
+inline bool BOTAN_DEPRECATED("Use oid == OID::from_string(name)") name_of(const OID& oid, const std::string& name)
+   {
+   return (oid == str2oid_or_empty(name));
+   }
+
+inline std::string BOTAN_DEPRECATED("Use oid2str_or_empty") lookup(const OID& oid)
+   {
+   return oid2str_or_empty(oid);
+   }
+
+inline OID BOTAN_DEPRECATED("Use str2oid_or_empty") lookup(const std::string& name)
+   {
+   return str2oid_or_empty(name);
+   }
+
+inline std::string BOTAN_DEPRECATED("Use oid2str_or_empty") oid2str(const OID& oid)
+   {
+   return oid2str_or_empty(oid);
+   }
+
+inline OID BOTAN_DEPRECATED("Use str2oid_or_empty") str2oid(const std::string& name)
+   {
+   return str2oid_or_empty(name);
+   }
+
 }
 
 }
diff --git a/src/lib/kdf/prf_x942/prf_x942.cpp b/src/lib/kdf/prf_x942/prf_x942.cpp
index 1e520ab18..f4437b10b 100644
--- a/src/lib/kdf/prf_x942/prf_x942.cpp
+++ b/src/lib/kdf/prf_x942/prf_x942.cpp
@@ -7,7 +7,6 @@
 
 #include <botan/prf_x942.h>
 #include <botan/der_enc.h>
-#include <botan/oids.h>
 #include <botan/hash.h>
 #include <botan/loadstor.h>
 #include <algorithm>
@@ -37,7 +36,6 @@ size_t X942_PRF::kdf(uint8_t key[], size_t key_len,
                      const uint8_t label[], size_t label_len) const
    {
    std::unique_ptr<HashFunction> hash(HashFunction::create("SHA-160"));
-   const OID kek_algo(m_key_wrap_oid);
 
    secure_vector<uint8_t> h;
    secure_vector<uint8_t> in;
@@ -56,7 +54,7 @@ size_t X942_PRF::kdf(uint8_t key[], size_t key_len,
          DER_Encoder().start_cons(SEQUENCE)
 
             .start_cons(SEQUENCE)
-               .encode(kek_algo)
+               .encode(m_key_wrap_oid)
                .raw_bytes(encode_x942_int(counter))
             .end_cons()
 
@@ -85,15 +83,9 @@ size_t X942_PRF::kdf(uint8_t key[], size_t key_len,
    return offset;
    }
 
-/*
-* X9.42 Constructor
-*/
-X942_PRF::X942_PRF(const std::string& oid)
+std::string X942_PRF::name() const
    {
-   if(OIDS::have_oid(oid))
-      m_key_wrap_oid = OIDS::lookup(oid).to_string();
-   else
-      m_key_wrap_oid = oid;
+   return "X9.42-PRF(" + m_key_wrap_oid.to_formatted_string() + ")";
    }
 
 }
diff --git a/src/lib/kdf/prf_x942/prf_x942.h b/src/lib/kdf/prf_x942/prf_x942.h
index ebf9839f5..4b93d5966 100644
--- a/src/lib/kdf/prf_x942/prf_x942.h
+++ b/src/lib/kdf/prf_x942/prf_x942.h
@@ -9,6 +9,7 @@
 #define BOTAN_ANSI_X942_PRF_H_
 
 #include <botan/kdf.h>
+#include <botan/asn1_oid.h>
 
 namespace Botan {
 
@@ -18,7 +19,7 @@ namespace Botan {
 class BOTAN_PUBLIC_API(2,0) X942_PRF final : public KDF
    {
    public:
-      std::string name() const override { return "X9.42-PRF(" + m_key_wrap_oid + ")"; }
+      std::string name() const override;
 
       KDF* clone() const override { return new X942_PRF(m_key_wrap_oid); }
 
@@ -27,9 +28,11 @@ class BOTAN_PUBLIC_API(2,0) X942_PRF final : public KDF
                  const uint8_t salt[], size_t salt_len,
                  const uint8_t label[], size_t label_len) const override;
 
-      explicit X942_PRF(const std::string& oid);
+      explicit X942_PRF(const std::string& oid) : m_key_wrap_oid(OID::from_string(oid)) {}
+
+      explicit X942_PRF(const OID& oid) : m_key_wrap_oid(oid) {}
    private:
-      std::string m_key_wrap_oid;
+      OID m_key_wrap_oid;
    };
 
 }
diff --git a/src/lib/pk_pad/emsa1/emsa1.cpp b/src/lib/pk_pad/emsa1/emsa1.cpp
index e1bc8db6e..f7293db27 100644
--- a/src/lib/pk_pad/emsa1/emsa1.cpp
+++ b/src/lib/pk_pad/emsa1/emsa1.cpp
@@ -7,7 +7,6 @@
 
 #include <botan/emsa1.h>
 #include <botan/exceptn.h>
-#include <botan/oids.h>
 #include <botan/pk_keys.h>
 #include <botan/internal/padding.h>
 
@@ -109,13 +108,10 @@ AlgorithmIdentifier EMSA1::config_for_x509(const Private_Key& key,
          " not supported for signature algorithm " + key.algo_name());
       }
 
-   const std::string sig_name = key.algo_name() + "/" + name();
-   AlgorithmIdentifier sig_algo;
-   sig_algo.oid = OIDS::lookup(sig_name);
-   if(sig_algo.oid.empty())
-      throw Lookup_Error("No OID defined for " + sig_name);
+   const OID oid = OID::from_string(key.algo_name() + "/" + name());
 
-   std::string algo_name = key.algo_name();
+   const std::string algo_name = key.algo_name();
+   std::vector<uint8_t> parameters;
    if(algo_name == "DSA" ||
       algo_name == "ECDSA" ||
       algo_name == "ECGDSA" ||
@@ -125,14 +121,13 @@ AlgorithmIdentifier EMSA1::config_for_x509(const Private_Key& key,
       algo_name == "GOST-34.10-2012-512")
       {
       // for DSA, ECDSA, GOST parameters "SHALL" be empty
-      sig_algo.parameters = {};
       }
    else
       {
-      sig_algo.parameters = key.algorithm_identifier().parameters;
+      parameters = key.algorithm_identifier().get_parameters();
       }
 
-   return sig_algo;
+   return AlgorithmIdentifier(oid, parameters);
    }
 
 }
diff --git a/src/lib/pk_pad/emsa_pkcs1/emsa_pkcs1.cpp b/src/lib/pk_pad/emsa_pkcs1/emsa_pkcs1.cpp
index ddc1e6b27..85556a39e 100644
--- a/src/lib/pk_pad/emsa_pkcs1/emsa_pkcs1.cpp
+++ b/src/lib/pk_pad/emsa_pkcs1/emsa_pkcs1.cpp
@@ -8,7 +8,6 @@
 #include <botan/emsa_pkcs1.h>
 #include <botan/hash_id.h>
 #include <botan/exceptn.h>
-#include <botan/oids.h>
 #include <botan/pk_keys.h>
 #include <botan/internal/padding.h>
 
@@ -97,13 +96,10 @@ AlgorithmIdentifier EMSA_PKCS1v15::config_for_x509(const Private_Key& key,
          " not supported for signature algorithm " + key.algo_name());
       }
 
+   // for RSA PKCSv1.5 parameters "SHALL" be NULL
 
-   AlgorithmIdentifier sig_algo;
-   sig_algo.oid = OIDS::lookup( key.algo_name() + "/" + name() );
-   // for RSA PKCSv1.5 parameters "SHALL" be NULL as configured by
-   // RSA_PublicKey::algorithm_identifier()
-   sig_algo.parameters = key.algorithm_identifier().parameters;
-   return sig_algo;
+   const OID oid = OID::from_string(key.algo_name() + "/" + name());
+   return AlgorithmIdentifier(oid, AlgorithmIdentifier::USE_NULL_PARAM);
    }
 
 EMSA_PKCS1v15::EMSA_PKCS1v15(HashFunction* hash) : m_hash(hash)
diff --git a/src/lib/pk_pad/emsa_pssr/pssr.cpp b/src/lib/pk_pad/emsa_pssr/pssr.cpp
index 25c0a191f..652a7628b 100644
--- a/src/lib/pk_pad/emsa_pssr/pssr.cpp
+++ b/src/lib/pk_pad/emsa_pssr/pssr.cpp
@@ -10,7 +10,6 @@
 #include <botan/rng.h>
 #include <botan/mgf1.h>
 #include <botan/internal/bit_ops.h>
-#include <botan/oids.h>
 #include <botan/der_enc.h>
 #include <botan/pk_keys.h>
 #include <botan/internal/padding.h>
@@ -203,14 +202,11 @@ AlgorithmIdentifier PSSR::config_for_x509(const Private_Key& key,
          " not supported for signature algorithm " + key.algo_name());
       }
 
-   AlgorithmIdentifier sig_algo;
-   // hardcoded as RSA is the only valid algorithm for EMSA4 at the moment
-   sig_algo.oid = OIDS::lookup( "RSA/EMSA4" );
-
    const AlgorithmIdentifier hash_id(cert_hash_name, AlgorithmIdentifier::USE_NULL_PARAM);
    const AlgorithmIdentifier mgf_id("MGF1", hash_id.BER_encode());
 
-   DER_Encoder(sig_algo.parameters)
+   std::vector<uint8_t> parameters;
+   DER_Encoder(parameters)
       .start_cons(SEQUENCE)
       .start_cons(ASN1_Tag(0), CONTEXT_SPECIFIC).encode(hash_id).end_cons()
       .start_cons(ASN1_Tag(1), CONTEXT_SPECIFIC).encode(mgf_id).end_cons()
@@ -218,7 +214,8 @@ AlgorithmIdentifier PSSR::config_for_x509(const Private_Key& key,
       .start_cons(ASN1_Tag(3), CONTEXT_SPECIFIC).encode(size_t(1)).end_cons() // trailer field
       .end_cons();
 
-   return sig_algo;
+   // hardcoded as RSA is the only valid algorithm for EMSA4 at the moment
+   return AlgorithmIdentifier("RSA/EMSA4", parameters);
    }
 
 PSSR_Raw::PSSR_Raw(HashFunction* h) :
diff --git a/src/lib/prov/openssl/openssl_ec.cpp b/src/lib/prov/openssl/openssl_ec.cpp
index 53ed081a1..3f691f68a 100644
--- a/src/lib/prov/openssl/openssl_ec.cpp
+++ b/src/lib/prov/openssl/openssl_ec.cpp
@@ -10,7 +10,6 @@
 #if defined(BOTAN_HAS_ECC_PUBLIC_KEY_CRYPTO)
   #include <botan/der_enc.h>
   #include <botan/pkcs8.h>
-  #include <botan/oids.h>
   #include <botan/internal/pk_ops_impl.h>
 #endif
 
@@ -90,7 +89,7 @@ int OpenSSL_EC_nid_for(const OID& oid)
    if(oid.empty())
       return -1;
 
-   const std::string name = OIDS::lookup(oid);
+   const std::string name = oid.to_formatted_string();
 
    if(name == "secp192r1")
       return OpenSSL_EC_curve_builtin(NID_X9_62_prime192v1);
diff --git a/src/lib/pubkey/ec_group/ec_group.cpp b/src/lib/pubkey/ec_group/ec_group.cpp
index 2067d57c4..41b48790f 100644
--- a/src/lib/pubkey/ec_group/ec_group.cpp
+++ b/src/lib/pubkey/ec_group/ec_group.cpp
@@ -13,7 +13,6 @@
 #include <botan/internal/primality.h>
 #include <botan/ber_dec.h>
 #include <botan/der_enc.h>
-#include <botan/oids.h>
 #include <botan/pem.h>
 #include <botan/reducer.h>
 #include <botan/mutex.h>
@@ -361,11 +360,11 @@ EC_Group::EC_Group(const std::string& str)
 
    try
       {
-      OID oid = OIDS::lookup(str);
-      if(oid.empty() == false)
+      const OID oid = OID::from_string(str);
+      if(oid.has_value())
          m_data = ec_group_data().lookup(oid);
       }
-   catch(Invalid_OID&)
+   catch(...)
       {
       }
 
diff --git a/src/lib/pubkey/gost_3410/gost_3410.h b/src/lib/pubkey/gost_3410/gost_3410.h
index 3f475d434..28e8274de 100644
--- a/src/lib/pubkey/gost_3410/gost_3410.h
+++ b/src/lib/pubkey/gost_3410/gost_3410.h
@@ -53,7 +53,7 @@ class BOTAN_PUBLIC_API(2,0) GOST_3410_PublicKey : public virtual EC_PublicKey
       size_t message_part_size() const override
          { return domain().get_order().bytes(); }
 
-      Signature_Format default_x509_signature_format() const
+      Signature_Format default_x509_signature_format() const override
          { return IEEE_1363; }
 
       std::unique_ptr<PK_Ops::Verification>
diff --git a/src/lib/pubkey/pbes2/pbes2.cpp b/src/lib/pubkey/pbes2/pbes2.cpp
index ce540c932..d68bf184b 100644
--- a/src/lib/pubkey/pbes2/pbes2.cpp
+++ b/src/lib/pubkey/pbes2/pbes2.cpp
@@ -34,7 +34,7 @@ SymmetricKey derive_key(const std::string& passphrase,
                         const AlgorithmIdentifier& kdf_algo,
                         size_t default_key_size)
    {
-   if(kdf_algo.get_oid() == OIDS::lookup("PKCS5.PBKDF2"))
+   if(kdf_algo.get_oid() == OID::from_string("PKCS5.PBKDF2"))
       {
       secure_vector<uint8_t> salt;
       size_t iterations = 0, key_length = 0;
@@ -56,12 +56,12 @@ SymmetricKey derive_key(const std::string& passphrase,
       if(key_length == 0)
          key_length = default_key_size;
 
-      const std::string prf = OIDS::lookup(prf_algo.get_oid());
+      const std::string prf = OIDS::oid2str_or_throw(prf_algo.get_oid());
       std::unique_ptr<PBKDF> pbkdf(get_pbkdf("PBKDF2(" + prf + ")"));
       return pbkdf->pbkdf_iterations(key_length, passphrase, salt.data(), salt.size(), iterations);
       }
 #if defined(BOTAN_HAS_SCRYPT)
-   else if(kdf_algo.get_oid() == OIDS::lookup("Scrypt"))
+   else if(kdf_algo.get_oid() == OID::from_string("Scrypt"))
       {
       secure_vector<uint8_t> salt;
       size_t N = 0, r = 0, p = 0;
@@ -142,7 +142,7 @@ secure_vector<uint8_t> derive_key(const std::string& passphrase,
             .encode(key_length)
          .end_cons();
 
-      kdf_algo = AlgorithmIdentifier(OIDS::lookup("Scrypt"), scrypt_params);
+      kdf_algo = AlgorithmIdentifier(OID::from_string("Scrypt"), scrypt_params);
       return key;
 #else
       throw Not_Implemented("Scrypt is not available in this build");
@@ -214,7 +214,7 @@ pbes2_encrypt_shared(const secure_vector<uint8_t>& key_bits,
    if(!known_pbes_cipher_mode(cipher_spec[1]))
       throw Encoding_Error("PBE-PKCS5 v2.0: Don't know param format for " + cipher);
 
-   const OID cipher_oid = OIDS::lookup(cipher);
+   const OID cipher_oid = OIDS::str2oid_or_empty(cipher);
    if(cipher_oid.empty())
       throw Encoding_Error("PBE-PKCS5 v2.0: No OID assigned for " + cipher);
 
@@ -251,7 +251,7 @@ pbes2_encrypt_shared(const secure_vector<uint8_t>& key_bits,
          )
       .end_cons();
 
-   AlgorithmIdentifier id(OIDS::lookup("PBE-PKCS5v20"), pbes2_params);
+   AlgorithmIdentifier id(OID::from_string("PBE-PKCS5v20"), pbes2_params);
 
    return std::make_pair(id, unlock(ctext));
    }
@@ -315,7 +315,7 @@ pbes2_decrypt(const secure_vector<uint8_t>& key_bits,
          .decode(enc_algo)
       .end_cons();
 
-   const std::string cipher = OIDS::lookup(enc_algo.get_oid());
+   const std::string cipher = OIDS::oid2str_or_throw(enc_algo.get_oid());
    const std::vector<std::string> cipher_spec = split_on(cipher, '/');
    if(cipher_spec.size() != 2)
       throw Decoding_Error("PBE-PKCS5 v2.0: Invalid cipher spec " + cipher);
diff --git a/src/lib/pubkey/pk_algs.cpp b/src/lib/pubkey/pk_algs.cpp
index f59583e1f..fc8697585 100644
--- a/src/lib/pubkey/pk_algs.cpp
+++ b/src/lib/pubkey/pk_algs.cpp
@@ -6,7 +6,6 @@
 */
 
 #include <botan/pk_algs.h>
-#include <botan/oids.h>
 #include <botan/parsing.h>
 
 #if defined(BOTAN_HAS_RSA)
@@ -83,11 +82,8 @@ std::unique_ptr<Public_Key>
 load_public_key(const AlgorithmIdentifier& alg_id,
                 const std::vector<uint8_t>& key_bits)
    {
-   const std::vector<std::string> alg_info = split_on(OIDS::lookup(alg_id.get_oid()), '/');
-
-   if(alg_info.empty())
-      throw Decoding_Error("Unknown algorithm OID: " + alg_id.get_oid().to_string());
-
+   const std::string oid_str = alg_id.get_oid().to_formatted_string();
+   const std::vector<std::string> alg_info = split_on(oid_str, '/');
    const std::string alg_name = alg_info[0];
 
 #if defined(BOTAN_HAS_RSA)
@@ -160,16 +156,14 @@ load_public_key(const AlgorithmIdentifier& alg_id,
       return std::unique_ptr<Public_Key>(new XMSS_PublicKey(key_bits));
 #endif
 
-   throw Decoding_Error("Unhandled PK algorithm " + alg_name);
+   throw Decoding_Error("Unknown or unavailable public key algorithm " + alg_name);
    }
 
 std::unique_ptr<Private_Key>
 load_private_key(const AlgorithmIdentifier& alg_id,
                  const secure_vector<uint8_t>& key_bits)
    {
-   const std::string alg_name = OIDS::lookup(alg_id.get_oid());
-   if(alg_name == "")
-      throw Decoding_Error("Unknown algorithm OID: " + alg_id.get_oid().to_string());
+   const std::string alg_name = alg_id.get_oid().to_formatted_string();
 
 #if defined(BOTAN_HAS_RSA)
    if(alg_name == "RSA")
@@ -241,7 +235,7 @@ load_private_key(const AlgorithmIdentifier& alg_id,
       return std::unique_ptr<Private_Key>(new XMSS_PrivateKey(key_bits));
 #endif
 
-   throw Decoding_Error("Unhandled PK algorithm " + alg_name);
+   throw Decoding_Error("Unknown or unavailable public key algorithm " + alg_name);
    }
 
 #if defined(BOTAN_HAS_ECC_GROUP)
diff --git a/src/lib/pubkey/pk_keys.cpp b/src/lib/pubkey/pk_keys.cpp
index ce3eeeb7f..c5a98d72f 100644
--- a/src/lib/pubkey/pk_keys.cpp
+++ b/src/lib/pubkey/pk_keys.cpp
@@ -52,12 +52,10 @@ std::vector<uint8_t> Public_Key::subject_public_key() const
 */
 OID Public_Key::get_oid() const
    {
-   const OID oid = OIDS::lookup(algo_name());
-
-   if(oid.empty())
+   const OID o = OIDS::str2oid_or_empty(algo_name());
+   if(o.empty())
       throw Lookup_Error("PK algo " + algo_name() + " has no defined OIDs");
-
-   return oid;
+   return o;
    }
 
 secure_vector<uint8_t> Private_Key::private_key_info() const
diff --git a/src/lib/pubkey/pkcs8.cpp b/src/lib/pubkey/pkcs8.cpp
index 0929769df..0238491dc 100644
--- a/src/lib/pubkey/pkcs8.cpp
+++ b/src/lib/pubkey/pkcs8.cpp
@@ -104,7 +104,7 @@ secure_vector<uint8_t> PKCS8_decode(
       {
       if(is_encrypted)
          {
-         if(OIDS::lookup(pbe_alg_id.get_oid()) != "PBE-PKCS5v20")
+         if(OIDS::oid2str_or_throw(pbe_alg_id.get_oid()) != "PBE-PKCS5v20")
             throw PKCS8_Exception("Unknown PBE type " + pbe_alg_id.get_oid().to_string());
 #if defined(BOTAN_HAS_PKCS5_PBES2)
          key = pbes2_decrypt(key_data, get_passphrase(), pbe_alg_id.get_parameters());
@@ -350,8 +350,8 @@ load_key(DataSource& source,
    AlgorithmIdentifier alg_id;
    secure_vector<uint8_t> pkcs8_key = PKCS8_decode(source, get_pass, alg_id, is_encrypted);
 
-   const std::string alg_name = OIDS::lookup(alg_id.get_oid());
-   if(alg_name.empty() || alg_name == alg_id.get_oid().to_string())
+   const std::string alg_name = OIDS::oid2str_or_empty(alg_id.get_oid());
+   if(alg_name.empty())
       throw PKCS8_Exception("Unknown algorithm OID: " +
                             alg_id.get_oid().to_string());
 
diff --git a/src/lib/tls/tls_callbacks.cpp b/src/lib/tls/tls_callbacks.cpp
index 18868e0ef..0dd758b75 100644
--- a/src/lib/tls/tls_callbacks.cpp
+++ b/src/lib/tls/tls_callbacks.cpp
@@ -13,7 +13,6 @@
 #include <botan/ocsp.h>
 #include <botan/dh.h>
 #include <botan/ecdh.h>
-#include <botan/oids.h>
 #include <botan/tls_exceptn.h>
 #include <botan/internal/ct_utils.h>
 
@@ -177,7 +176,7 @@ std::pair<secure_vector<uint8_t>, std::vector<uint8_t>> TLS::Callbacks::tls_ecdh
       }
    else
       {
-      EC_Group group(OIDS::lookup(curve_name));
+      EC_Group group(OID::from_string(curve_name));
       ECDH_PublicKey peer_key(group, group.OS2ECP(peer_public_value));
       policy.check_peer_key_acceptable(peer_key);
       ECDH_PrivateKey priv_key(rng, group);
diff --git a/src/lib/utils/exceptn.h b/src/lib/utils/exceptn.h
index 61e7c7c1f..0259a225b 100644
--- a/src/lib/utils/exceptn.h
+++ b/src/lib/utils/exceptn.h
@@ -360,7 +360,8 @@ class BOTAN_PUBLIC_API(2,0) Not_Implemented final : public Exception
 
 /*
    The following exception types are still in use for compatability reasons,
-   but are deprecated and will be removed in a future major release
+   but are deprecated and will be removed in a future major release.
+   Instead catch the base class.
 */
 
 /**
diff --git a/src/lib/utils/parsing.cpp b/src/lib/utils/parsing.cpp
index 8e62c6e03..197f4a11c 100644
--- a/src/lib/utils/parsing.cpp
+++ b/src/lib/utils/parsing.cpp
@@ -16,6 +16,10 @@
 #include <limits>
 #include <set>
 
+#if defined(BOTAN_HAS_ASN1)
+  #include <botan/asn1_oid.h>
+#endif
+
 namespace Botan {
 
 uint16_t to_uint16(const std::string& str)
@@ -194,32 +198,11 @@ std::string string_join(const std::vector<std::string>& strs, char delim)
 */
 std::vector<uint32_t> parse_asn1_oid(const std::string& oid)
    {
-   std::string substring;
-   std::vector<uint32_t> oid_elems;
-
-   for(auto i = oid.begin(); i != oid.end(); ++i)
-      {
-      char c = *i;
-
-      if(c == '.')
-         {
-         if(substring.empty())
-            throw Invalid_OID(oid);
-         oid_elems.push_back(to_u32bit(substring));
-         substring.clear();
-         }
-      else
-         substring += c;
-      }
-
-   if(substring.empty())
-      throw Invalid_OID(oid);
-   oid_elems.push_back(to_u32bit(substring));
-
-   if(oid_elems.size() < 2)
-      throw Invalid_OID(oid);
-
-   return oid_elems;
+#if defined(BOTAN_HAS_ASN1)
+   return OID(oid).get_components();
+#else
+   throw Not_Supported("ASN1 support not available");
+#endif
    }
 
 /*
diff --git a/src/lib/utils/parsing.h b/src/lib/utils/parsing.h
index 12cb3fa34..ed42ea8f5 100644
--- a/src/lib/utils/parsing.h
+++ b/src/lib/utils/parsing.h
@@ -95,7 +95,8 @@ std::string string_join(const std::vector<std::string>& strs,
 * @param oid the OID in string form
 * @return OID components
 */
-BOTAN_PUBLIC_API(2,0) std::vector<uint32_t> parse_asn1_oid(const std::string& oid);
+BOTAN_PUBLIC_API(2,0) std::vector<uint32_t>
+BOTAN_DEPRECATED("Use OID::from_string(oid).get_components()") parse_asn1_oid(const std::string& oid);
 
 /**
 * Compare two names using the X.509 comparison algorithm
diff --git a/src/lib/x509/asn1_alt_name.cpp b/src/lib/x509/asn1_alt_name.cpp
index 4e052ca58..1e5611c8b 100644
--- a/src/lib/x509/asn1_alt_name.cpp
+++ b/src/lib/x509/asn1_alt_name.cpp
@@ -69,10 +69,14 @@ std::multimap<std::string, std::string> AlternativeName::contents() const
    std::multimap<std::string, std::string> names;
 
    for(auto i = m_alt_info.begin(); i != m_alt_info.end(); ++i)
+      {
       multimap_insert(names, i->first, i->second);
+      }
 
    for(auto i = m_othernames.begin(); i != m_othernames.end(); ++i)
-      multimap_insert(names, OIDS::lookup(i->first), i->second.value());
+      {
+      multimap_insert(names, i->first.to_formatted_string(), i->second.value());
+      }
 
    return names;
    }
diff --git a/src/lib/x509/ocsp.cpp b/src/lib/x509/ocsp.cpp
index 249ce7817..34cb1d4fa 100644
--- a/src/lib/x509/ocsp.cpp
+++ b/src/lib/x509/ocsp.cpp
@@ -164,7 +164,7 @@ Certificate_Status_Code Response::verify_signature(const X509_Certificate& issue
       std::unique_ptr<Public_Key> pub_key(issuer.subject_public_key());
 
       const std::vector<std::string> sig_info =
-         split_on(OIDS::lookup(m_sig_algo.get_oid()), '/');
+         split_on(m_sig_algo.get_oid().to_formatted_string(), '/');
 
       if(sig_info.size() != 2 || sig_info[0] != pub_key->algo_name())
          return Certificate_Status_Code::OCSP_RESPONSE_INVALID;
diff --git a/src/lib/x509/ocsp_types.cpp b/src/lib/x509/ocsp_types.cpp
index 3eda5c05b..9a0fbdf8d 100644
--- a/src/lib/x509/ocsp_types.cpp
+++ b/src/lib/x509/ocsp_types.cpp
@@ -10,7 +10,6 @@
 #include <botan/ber_dec.h>
 #include <botan/x509_ext.h>
 #include <botan/hash.h>
-#include <botan/oids.h>
 
 namespace Botan {
 
@@ -39,7 +38,8 @@ bool CertID::is_id_for(const X509_Certificate& issuer,
       if(BigInt::decode(subject.serial_number()) != m_subject_serial)
          return false;
 
-      std::unique_ptr<HashFunction> hash(HashFunction::create(OIDS::lookup(m_hash_id.get_oid())));
+      const std::string hash_algo = m_hash_id.get_oid().to_formatted_string();
+      std::unique_ptr<HashFunction> hash = HashFunction::create_or_throw(hash_algo);
 
       if(m_issuer_dn_hash != unlock(hash->process(subject.raw_issuer_dn())))
          return false;
diff --git a/src/lib/x509/pkcs10.cpp b/src/lib/x509/pkcs10.cpp
index 2da002cd1..5e40cb4c3 100644
--- a/src/lib/x509/pkcs10.cpp
+++ b/src/lib/x509/pkcs10.cpp
@@ -148,19 +148,19 @@ std::unique_ptr<PKCS10_Data> decode_pkcs10(const std::vector<uint8_t>& body)
          const OID& oid = attr.get_oid();
          BER_Decoder value(attr.get_parameters());
 
-         if(oid == OIDS::lookup("PKCS9.EmailAddress"))
+         if(oid == OID::from_string("PKCS9.EmailAddress"))
             {
             ASN1_String email;
             value.decode(email);
             pkcs9_email.insert(email.value());
             }
-         else if(oid == OIDS::lookup("PKCS9.ChallengePassword"))
+         else if(oid == OID::from_string("PKCS9.ChallengePassword"))
             {
             ASN1_String challenge_password;
             value.decode(challenge_password);
             data->m_challenge = challenge_password.value();
             }
-         else if(oid == OIDS::lookup("PKCS9.ExtensionRequest"))
+         else if(oid == OID::from_string("PKCS9.ExtensionRequest"))
             {
             value.decode(data->m_extensions).verify_end();
             }
@@ -260,7 +260,7 @@ const Extensions& PKCS10_Request::extensions() const
 */
 Key_Constraints PKCS10_Request::constraints() const
    {
-   if(auto ext = extensions().get(OIDS::lookup("X509v3.KeyUsage")))
+   if(auto ext = extensions().get(OID::from_string("X509v3.KeyUsage")))
       {
       return dynamic_cast<Cert_Extension::Key_Usage&>(*ext).get_constraints();
       }
@@ -273,7 +273,7 @@ Key_Constraints PKCS10_Request::constraints() const
 */
 std::vector<OID> PKCS10_Request::ex_constraints() const
    {
-   if(auto ext = extensions().get(OIDS::lookup("X509v3.ExtendedKeyUsage")))
+   if(auto ext = extensions().get(OID::from_string("X509v3.ExtendedKeyUsage")))
       {
       return dynamic_cast<Cert_Extension::Extended_Key_Usage&>(*ext).get_oids();
       }
@@ -286,7 +286,7 @@ std::vector<OID> PKCS10_Request::ex_constraints() const
 */
 bool PKCS10_Request::is_CA() const
    {
-   if(auto ext = extensions().get(OIDS::lookup("X509v3.BasicConstraints")))
+   if(auto ext = extensions().get(OID::from_string("X509v3.BasicConstraints")))
       {
       return dynamic_cast<Cert_Extension::Basic_Constraints&>(*ext).get_is_ca();
       }
@@ -299,7 +299,7 @@ bool PKCS10_Request::is_CA() const
 */
 size_t PKCS10_Request::path_limit() const
    {
-   if(auto ext = extensions().get(OIDS::lookup("X509v3.BasicConstraints")))
+   if(auto ext = extensions().get(OID::from_string("X509v3.BasicConstraints")))
       {
       Cert_Extension::Basic_Constraints& basic_constraints = dynamic_cast<Cert_Extension::Basic_Constraints&>(*ext);
       if(basic_constraints.get_is_ca())
diff --git a/src/lib/x509/x509_ca.cpp b/src/lib/x509/x509_ca.cpp
index 73eea4a95..59bc219b5 100644
--- a/src/lib/x509/x509_ca.cpp
+++ b/src/lib/x509/x509_ca.cpp
@@ -40,7 +40,7 @@ X509_CA::X509_CA(const X509_Certificate& c,
    // constructor without additional options: use the padding used in the CA certificate
    // sig_oid_str = <sig_alg>/<padding>, so padding with all its options will look
    // like a cipher mode to the scanner
-   std::string sig_oid_str = OIDS::lookup(c.signature_algorithm().oid);
+   std::string sig_oid_str = OIDS::oid2str_or_throw(c.signature_algorithm().get_oid());
    SCAN_Name scanner(sig_oid_str);
    std::string pad = scanner.cipher_mode();
    if(!pad.empty())
diff --git a/src/lib/x509/x509_dn.cpp b/src/lib/x509/x509_dn.cpp
index 6e2707673..bd8b60c40 100644
--- a/src/lib/x509/x509_dn.cpp
+++ b/src/lib/x509/x509_dn.cpp
@@ -23,7 +23,7 @@ namespace Botan {
 void X509_DN::add_attribute(const std::string& type,
                             const std::string& str)
    {
-   add_attribute(OIDS::lookup(type), str);
+   add_attribute(OID::from_string(type), str);
    }
 
 /*
@@ -59,18 +59,18 @@ std::multimap<std::string, std::string> X509_DN::contents() const
 
    for(auto& i : m_rdn)
       {
-      std::string str_value = OIDS::oid2str(i.first);
-
-      if(str_value.empty())
-         str_value = i.first.to_string();
-      multimap_insert(retval, str_value, i.second.value());
+      multimap_insert(retval, i.first.to_formatted_string(), i.second.value());
       }
    return retval;
    }
 
 bool X509_DN::has_field(const std::string& attr) const
    {
-   return has_field(OIDS::lookup(deref_info_field(attr)));
+   const OID o = OIDS::str2oid_or_empty(deref_info_field(attr));
+   if(o.has_value())
+      return has_field(o);
+   else
+      return false;
    }
 
 bool X509_DN::has_field(const OID& oid) const
@@ -86,7 +86,7 @@ bool X509_DN::has_field(const OID& oid) const
 
 std::string X509_DN::get_first_attribute(const std::string& attr) const
    {
-   const OID oid = OIDS::lookup(deref_info_field(attr));
+   const OID oid = OID::from_string(deref_info_field(attr));
    return get_first_attribute(oid).value();
    }
 
@@ -108,7 +108,7 @@ ASN1_String X509_DN::get_first_attribute(const OID& oid) const
 */
 std::vector<std::string> X509_DN::get_attribute(const std::string& attr) const
    {
-   const OID oid = OIDS::lookup(deref_info_field(attr));
+   const OID oid = OID::from_string(deref_info_field(attr));
 
    std::vector<std::string> values;
 
@@ -304,10 +304,7 @@ namespace {
 
 std::string to_short_form(const OID& oid)
    {
-   const std::string long_id = OIDS::oid2str(oid);
-
-   if(long_id.empty())
-      return oid.to_string();
+   const std::string long_id = oid.to_formatted_string();
 
    if(long_id == "X520.CommonName")
       return "CN";
diff --git a/src/lib/x509/x509_dn_ub.cpp b/src/lib/x509/x509_dn_ub.cpp
index cf8714320..d8663124e 100644
--- a/src/lib/x509/x509_dn_ub.cpp
+++ b/src/lib/x509/x509_dn_ub.cpp
@@ -1,7 +1,7 @@
 /*
 * DN_UB maps: Upper bounds on the length of DN strings
 *
-* This file was automatically generated by ./src/scripts/oids.py on 2017-12-23
+* This file was automatically generated by ./src/scripts/oids.py on 2019-08-04
 *
 * All manual edits to this file will be lost. Edit the script
 * then regenerate this source file.
@@ -14,6 +14,7 @@
 #include <map>
 
 namespace {
+
 /**
  * Upper bounds for the length of distinguished name fields as given in RFC 5280, Appendix A.
  * Only OIDS recognized by botan are considered, so far.
@@ -22,20 +23,21 @@ namespace {
  */
 static const std::map<Botan::OID, size_t> DN_UB =
    {
-   { Botan::OID("2.5.4.10"), 64 }, // X520.Organization
-   { Botan::OID("2.5.4.11"), 64 }, // X520.OrganizationalUnit
-   { Botan::OID("2.5.4.12"), 64 }, // X520.Title
-   { Botan::OID("2.5.4.3"), 64 }, // X520.CommonName
-   { Botan::OID("2.5.4.4"), 40 }, // X520.Surname
-   { Botan::OID("2.5.4.42"), 32768 }, // X520.GivenName
-   { Botan::OID("2.5.4.43"), 32768 }, // X520.Initials
-   { Botan::OID("2.5.4.44"), 32768 }, // X520.GenerationalQualifier
-   { Botan::OID("2.5.4.46"), 64 }, // X520.DNQualifier
-   { Botan::OID("2.5.4.5"), 64 }, // X520.SerialNumber
-   { Botan::OID("2.5.4.6"), 3 }, // X520.Country
-   { Botan::OID("2.5.4.65"), 128 }, // X520.Pseudonym
-   { Botan::OID("2.5.4.7"), 128 }, // X520.Locality
-   { Botan::OID("2.5.4.8"), 128 } // X520.State
+   { Botan::OID({2,5,4,10}), 64 }, // X520.Organization
+   { Botan::OID({2,5,4,11}), 64 }, // X520.OrganizationalUnit
+   { Botan::OID({2,5,4,12}), 64 }, // X520.Title
+   { Botan::OID({2,5,4,3}), 64 }, // X520.CommonName
+   { Botan::OID({2,5,4,4}), 40 }, // X520.Surname
+   { Botan::OID({2,5,4,42}), 32768 }, // X520.GivenName
+   { Botan::OID({2,5,4,43}), 32768 }, // X520.Initials
+   { Botan::OID({2,5,4,44}), 32768 }, // X520.GenerationalQualifier
+   { Botan::OID({2,5,4,46}), 64 }, // X520.DNQualifier
+   { Botan::OID({2,5,4,5}), 64 }, // X520.SerialNumber
+   { Botan::OID({2,5,4,6}), 3 }, // X520.Country
+   { Botan::OID({2,5,4,65}), 128 }, // X520.Pseudonym
+   { Botan::OID({2,5,4,7}), 128 }, // X520.Locality
+   { Botan::OID({2,5,4,8}), 128 }, // X520.State
+   { Botan::OID({2,5,4,9}), 128 } // X520.StreetAddress
    };
 }
 
diff --git a/src/lib/x509/x509_ext.cpp b/src/lib/x509/x509_ext.cpp
index 9b938f4d3..0bfc337c4 100644
--- a/src/lib/x509/x509_ext.cpp
+++ b/src/lib/x509/x509_ext.cpp
@@ -12,7 +12,6 @@
 #include <botan/datastor.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
-#include <botan/oids.h>
 #include <botan/hash.h>
 #include <botan/internal/bit_ops.h>
 #include <algorithm>
@@ -786,7 +785,7 @@ std::vector<uint8_t> Authority_Information_Access::encode_inner() const
    DER_Encoder(output)
       .start_cons(SEQUENCE)
       .start_cons(SEQUENCE)
-      .encode(OIDS::lookup("PKIX.OCSP"))
+      .encode(OID::from_string("PKIX.OCSP"))
       .add_object(ASN1_Tag(6), CONTEXT_SPECIFIC, url.value())
       .end_cons()
       .end_cons();
@@ -805,7 +804,7 @@ void Authority_Information_Access::decode_inner(const std::vector<uint8_t>& in)
 
       info.decode(oid);
 
-      if(oid == OIDS::lookup("PKIX.OCSP"))
+      if(oid == OID::from_string("PKIX.OCSP"))
          {
          BER_Object name = info.get_next_object();
 
@@ -815,7 +814,7 @@ void Authority_Information_Access::decode_inner(const std::vector<uint8_t>& in)
             }
 
          }
-      if(oid == OIDS::lookup("PKIX.CertificateAuthorityIssuers"))
+      if(oid == OID::from_string("PKIX.CertificateAuthorityIssuers"))
          {
          BER_Object name = info.get_next_object();
 
diff --git a/src/lib/x509/x509_ext.h b/src/lib/x509/x509_ext.h
index e8b21ef9b..2f818af63 100644
--- a/src/lib/x509/x509_ext.h
+++ b/src/lib/x509/x509_ext.h
@@ -36,7 +36,7 @@ class BOTAN_PUBLIC_API(2,0) Certificate_Extension
       /*
       * @return specific OID name
       * If possible OIDS table should match oid_name to OIDS, ie
-      * OIDS::lookup(ext->oid_name()) == ext->oid_of()
+      * OID::from_string(ext->oid_name()) == ext->oid_of()
       * Should return empty string if OID is not known
       */
       virtual std::string oid_name() const = 0;
diff --git a/src/lib/x509/x509_obj.cpp b/src/lib/x509/x509_obj.cpp
index dd1e51cd7..e6767ea98 100644
--- a/src/lib/x509/x509_obj.cpp
+++ b/src/lib/x509/x509_obj.cpp
@@ -7,7 +7,6 @@
 
 #include <botan/x509_obj.h>
 #include <botan/pubkey.h>
-#include <botan/oids.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
 #include <botan/parsing.h>
@@ -139,7 +138,7 @@ std::vector<uint8_t> X509_Object::tbs_data() const
 std::string X509_Object::hash_used_for_signature() const
    {
    const OID& oid = m_sig_algo.get_oid();
-   const std::vector<std::string> sig_info = split_on(OIDS::lookup(oid), '/');
+   const std::vector<std::string> sig_info = split_on(oid.to_formatted_string(), '/');
 
    if(sig_info.size() == 1 && sig_info[0] == "Ed25519")
       return "SHA-512";
@@ -148,7 +147,8 @@ std::string X509_Object::hash_used_for_signature() const
 
    if(sig_info[1] == "EMSA4")
       {
-      return OIDS::lookup(decode_pss_params(signature_algorithm().get_parameters()).hash_algo.get_oid());
+      const OID hash_oid = decode_pss_params(signature_algorithm().get_parameters()).hash_algo.get_oid();
+      return hash_oid.to_formatted_string();
       }
    else
       {
@@ -184,7 +184,7 @@ bool X509_Object::check_signature(const Public_Key& pub_key) const
 Certificate_Status_Code X509_Object::verify_signature(const Public_Key& pub_key) const
    {
    const std::vector<std::string> sig_info =
-      split_on(OIDS::lookup(m_sig_algo.get_oid()), '/');
+      split_on(m_sig_algo.get_oid().to_formatted_string(), '/');
 
    if(sig_info.size() < 1 || sig_info.size() > 2 || sig_info[0] != pub_key.algo_name())
       return Certificate_Status_Code::SIGNATURE_ALGO_BAD_PARAMS;
@@ -202,15 +202,15 @@ Certificate_Status_Code X509_Object::verify_signature(const Public_Key& pub_key)
    if(padding == "EMSA4")
       {
       // "MUST contain RSASSA-PSS-params"
-      if(signature_algorithm().parameters.empty())
+      if(signature_algorithm().get_parameters().empty())
          {
          return Certificate_Status_Code::SIGNATURE_ALGO_BAD_PARAMS;
          }
 
-      Pss_params pss_parameter = decode_pss_params(signature_algorithm().parameters);
+      Pss_params pss_parameter = decode_pss_params(signature_algorithm().get_parameters());
 
       // hash_algo must be SHA1, SHA2-224, SHA2-256, SHA2-384 or SHA2-512
-      const std::string hash_algo = OIDS::lookup(pss_parameter.hash_algo.oid);
+      const std::string hash_algo = pss_parameter.hash_algo.get_oid().to_formatted_string();
       if(hash_algo != "SHA-160" &&
          hash_algo != "SHA-224" &&
          hash_algo != "SHA-256" &&
@@ -220,7 +220,7 @@ Certificate_Status_Code X509_Object::verify_signature(const Public_Key& pub_key)
          return Certificate_Status_Code::UNTRUSTED_HASH;
          }
 
-      const std::string mgf_algo = OIDS::lookup(pss_parameter.mask_gen_algo.oid);
+      const std::string mgf_algo = pss_parameter.mask_gen_algo.get_oid().to_formatted_string();
       if(mgf_algo != "MGF1")
          {
          return Certificate_Status_Code::SIGNATURE_ALGO_BAD_PARAMS;
@@ -228,7 +228,7 @@ Certificate_Status_Code X509_Object::verify_signature(const Public_Key& pub_key)
 
       // For MGF1, it is strongly RECOMMENDED that the underlying hash function be the same as the one identified by hashAlgorithm
       // Must be SHA1, SHA2-224, SHA2-256, SHA2-384 or SHA2-512
-      if(pss_parameter.mask_gen_hash.oid != pss_parameter.hash_algo.oid)
+      if(pss_parameter.mask_gen_hash.get_oid() != pss_parameter.hash_algo.get_oid())
          {
          return Certificate_Status_Code::SIGNATURE_ALGO_BAD_PARAMS;
          }
@@ -238,7 +238,6 @@ Certificate_Status_Code X509_Object::verify_signature(const Public_Key& pub_key)
          return Certificate_Status_Code::SIGNATURE_ALGO_BAD_PARAMS;
          }
 
-      // salt_len is actually not used for verification. Length is inferred from the signature
       padding += "(" + hash_algo + "," + mgf_algo + "," + std::to_string(pss_parameter.salt_len) + ")";
       }
 
@@ -354,7 +353,7 @@ std::string choose_sig_algo(AlgorithmIdentifier& sig_algo,
       }
    else
       {
-      sig_algo = AlgorithmIdentifier(OIDS::lookup("Ed25519"), AlgorithmIdentifier::USE_EMPTY_PARAM);
+      sig_algo = AlgorithmIdentifier(OID::from_string("Ed25519"), AlgorithmIdentifier::USE_EMPTY_PARAM);
       return "Pure";
       }
    }
diff --git a/src/lib/x509/x509cert.cpp b/src/lib/x509/x509cert.cpp
index 0212267ec..96e66a5e0 100644
--- a/src/lib/x509/x509cert.cpp
+++ b/src/lib/x509/x509cert.cpp
@@ -147,8 +147,8 @@ std::unique_ptr<X509_Certificate_Data> parse_x509_cert_body(const X509_Object& o
    AlgorithmIdentifier public_key_alg_id;
    BER_Decoder(public_key).decode(public_key_alg_id).discard_remaining();
 
-   std::vector<std::string> public_key_info =
-      split_on(OIDS::oid2str(public_key_alg_id.get_oid()), '/');
+   const std::vector<std::string> public_key_info =
+      split_on(OIDS::oid2str_or_empty(public_key_alg_id.get_oid()), '/');
 
    if(!public_key_info.empty() && public_key_info[0] == "RSA")
       {
@@ -500,7 +500,7 @@ bool X509_Certificate::allowed_usage(Key_Constraints usage) const
 
 bool X509_Certificate::allowed_extended_usage(const std::string& usage) const
    {
-   return allowed_extended_usage(OIDS::str2oid(usage));
+   return allowed_extended_usage(OID::from_string(usage));
    }
 
 bool X509_Certificate::allowed_extended_usage(const OID& usage) const
@@ -552,7 +552,7 @@ bool X509_Certificate::has_constraints(Key_Constraints constraints) const
 
 bool X509_Certificate::has_ex_constraint(const std::string& ex_constraint) const
    {
-   return has_ex_constraint(OIDS::str2oid(ex_constraint));
+   return has_ex_constraint(OID::from_string(ex_constraint));
    }
 
 bool X509_Certificate::has_ex_constraint(const OID& usage) const
@@ -566,7 +566,7 @@ bool X509_Certificate::has_ex_constraint(const OID& usage) const
 */
 bool X509_Certificate::is_critical(const std::string& ex_name) const
    {
-   return v3_extensions().critical_extension_set(OIDS::str2oid(ex_name));
+   return v3_extensions().critical_extension_set(OID::from_string(ex_name));
    }
 
 std::string X509_Certificate::ocsp_responder() const
@@ -695,7 +695,7 @@ std::vector<std::string> lookup_oids(const std::vector<OID>& oids)
 
    for(const OID& oid : oids)
       {
-      out.push_back(OIDS::oid2str(oid));
+      out.push_back(oid.to_formatted_string());
       }
    return out;
    }
@@ -823,12 +823,7 @@ std::string X509_Certificate::to_string() const
       out << "Extended Constraints:\n";
       for(auto&& oid : ex_constraints)
          {
-         const std::string oid_str = OIDS::oid2str(oid);
-
-         if(oid_str.empty())
-            out << "   " << oid.to_string() << "\n";
-         else
-            out << "   " << oid_str << "\n";
+         out << "   " << oid.to_formatted_string() << "\n";
          }
       }
 
@@ -873,8 +868,7 @@ std::string X509_Certificate::to_string() const
    if(!crl_distribution_point().empty())
       out << "CRL " << crl_distribution_point() << "\n";
 
-   out << "Signature algorithm: " <<
-      OIDS::oid2str(this->signature_algorithm().get_oid()) << "\n";
+   out << "Signature algorithm: " << this->signature_algorithm().get_oid().to_formatted_string() << "\n";
 
    out << "Serial number: " << hex_encode(this->serial_number()) << "\n";
 
diff --git a/src/lib/x509/x509opt.cpp b/src/lib/x509/x509opt.cpp
index e31ead91f..f762acd7b 100644
--- a/src/lib/x509/x509opt.cpp
+++ b/src/lib/x509/x509opt.cpp
@@ -6,7 +6,6 @@
 */
 
 #include <botan/x509self.h>
-#include <botan/oids.h>
 #include <botan/parsing.h>
 #include <chrono>
 
@@ -49,7 +48,7 @@ void X509_Cert_Options::add_ex_constraint(const OID& oid)
 */
 void X509_Cert_Options::add_ex_constraint(const std::string& oid_str)
    {
-   ex_constraints.push_back(OIDS::lookup(oid_str));
+   ex_constraints.push_back(OID::from_string(oid_str));
    }
 
 /*
diff --git a/src/lib/x509/x509path.cpp b/src/lib/x509/x509path.cpp
index cecefcc79..95e9209e6 100644
--- a/src/lib/x509/x509path.cpp
+++ b/src/lib/x509/x509path.cpp
@@ -116,14 +116,14 @@ PKIX::check_chain(const std::vector<std::shared_ptr<const X509_Certificate>>& ce
 
       std::unique_ptr<Public_Key> issuer_key(issuer->subject_public_key());
 
-      // Check the signature algorithm
-      if(OIDS::lookup(subject->signature_algorithm().oid).empty())
+      // Check the signature algorithm is known
+      if(OIDS::oid2str_or_empty(subject->signature_algorithm().get_oid()).empty())
          {
          status.insert(Certificate_Status_Code::SIGNATURE_ALGO_UNKNOWN);
          }
-      // only perform the following checks if the signature algorithm is known
       else
          {
+         // only perform the following checks if the signature algorithm is known
          if(!issuer_key)
             {
             status.insert(Certificate_Status_Code::CERT_PUBKEY_INVALID);
@@ -298,8 +298,11 @@ PKIX::check_crl(const std::vector<std::shared_ptr<const X509_Certificate>>& cert
 
          for(const auto& extension : crls[i]->extensions().extensions())
             {
+            // XXX this is wrong - the OID might be defined but the extention not full parsed
+            // for example see #1652
+
             // is the extension critical and unknown?
-            if(extension.second && OIDS::lookup(extension.first->oid_of()) == "")
+            if(extension.second && OIDS::oid2str_or_empty(extension.first->oid_of()) == "")
                {
                /* NIST Certificate Path Valiadation Testing document: "When an implementation does not recognize a critical extension in the
                 * crlExtensions field, it shall assume that identified certificates have been revoked and are no longer valid"
diff --git a/src/lib/x509/x509self.cpp b/src/lib/x509/x509self.cpp
index d84544eff..dd4ed7e3f 100644
--- a/src/lib/x509/x509self.cpp
+++ b/src/lib/x509/x509self.cpp
@@ -10,7 +10,6 @@
 #include <botan/x509_ca.h>
 #include <botan/der_enc.h>
 #include <botan/pubkey.h>
-#include <botan/oids.h>
 #include <botan/hash.h>
 
 namespace Botan {
@@ -35,7 +34,7 @@ void load_info(const X509_Cert_Options& opts, X509_DN& subject_dn,
 
    subject_dn.add_attribute("X520.SerialNumber", opts.serial_number);
    subject_alt = AlternativeName(opts.email, opts.uri, opts.dns, opts.ip);
-   subject_alt.add_othername(OIDS::lookup("PKIX.XMPPAddr"),
+   subject_alt.add_othername(OID::from_string("PKIX.XMPPAddr"),
                              opts.xmpp, UTF8_STRING);
 
    for(auto dns : opts.more_dns)
diff --git a/src/scripts/oids.py b/src/scripts/oids.py
index f303f1f7e..7036dbab6 100755
--- a/src/scripts/oids.py
+++ b/src/scripts/oids.py
@@ -1,4 +1,4 @@
-#!/usr/bin/python2
+#!/usr/bin/python
 
 """
 (C) 2016 Jack Lloyd
@@ -129,7 +129,7 @@ def format_dn_ub_map(dn_ub, oid2str):
     for k in sorted(dn_ub.keys()):
         v = dn_ub[k]
 
-        s += '   { Botan::OID("%s"), %s }, // %s\n' % (k,v,oid2str[k])
+        s += '   { Botan::OID({%s}), %s }, // %s\n' % (k.replace('.',','),v,oid2str[k])
 
     # delete last ',' and \n
     idx = s.rfind(',')
@@ -156,6 +156,7 @@ def format_dn_ub_as_map(dn_ub, oid2str):
 #include <map>
 
 namespace {
+
 /**
  * Upper bounds for the length of distinguished name fields as given in RFC 5280, Appendix A.
  * Only OIDS recognized by botan are considered, so far.
@@ -219,30 +220,36 @@ def format_pads_as_map(sig_dict):
 */
 
 #include <botan/internal/padding.h>
-#include <map>
+#include <unordered_map>
 #include <vector>
 #include <string>
 #include <algorithm>
 
 namespace Botan {
 
-const std::map<const std::string, std::vector<std::string>> allowed_signature_paddings =
+namespace {
+
+const std::unordered_map<const std::string, std::vector<std::string>> allowed_signature_paddings =
    {
    %s
    };
 
-__attribute__((visibility("default"))) const std::vector<std::string> get_sig_paddings(const std::string algo)
+}
+
+const std::vector<std::string> get_sig_paddings(const std::string algo)
    {
-   if(allowed_signature_paddings.count(algo) > 0)
-      return allowed_signature_paddings.at(algo);
+   auto i = allowed_signature_paddings.find(algo);
+   if(i != allowed_signature_paddings.end())
+      return i->second;
    return {};
    }
 
 bool sig_algo_and_pad_ok(const std::string algo, std::string padding)
    {
-   std::vector<std::string> pads = get_sig_paddings(algo);
+   const std::vector<std::string> pads = get_sig_paddings(algo);
    return std::find(pads.begin(), pads.end(), padding) != pads.end();
    }
+
 }
 """ % (sys.argv[0], datetime.date.today().strftime("%Y-%m-%d"),
        format_set_map(sig_dict))
@@ -293,7 +300,7 @@ def main(args = None):
         nam = match.group(2)
 
         if oid in str2oid:
-            print "Duplicated OID", oid, name, oid2str[oid]
+            print("Duplicated OID", oid, name, oid2str[oid])
             sys.exit() # hard error
         else:
             oid2str[oid] = nam
@@ -310,18 +317,19 @@ def main(args = None):
                 sig2pads[pad_match.group(1)].add(pad_match.group(2))
 
         if nam in str2oid:
-            #print "Duplicated name", nam, oid, str2oid[nam]
             #str2oid[nam] = oid
             pass
         else:
             str2oid[nam] = oid
 
     if args[1] == "oids":
-        print format_as_map(oid2str, str2oid)
+        print(format_as_map(oid2str, str2oid))
     elif args[1] == "dn_ub":
-        print format_dn_ub_as_map(dn_ub,oid2str)
+        print(format_dn_ub_as_map(dn_ub,oid2str))
     elif args[1] == "pads":
-        print format_pads_as_map(sig2pads)
+        print(format_pads_as_map(sig2pads))
+    else:
+        print("Unknown command: try oids, dn_ub, or pads")
 
     return 0
 
diff --git a/src/tests/data/kdf/x942_prf.vec b/src/tests/data/kdf/x942_prf.vec
index 40dc2415d..f9c7e6bf5 100644
--- a/src/tests/data/kdf/x942_prf.vec
+++ b/src/tests/data/kdf/x942_prf.vec
@@ -1,5 +1,5 @@
 
-[X9.42-PRF(1.2.840.113549.1.9.16.3.6)]
+[X9.42-PRF(KeyWrap.TripleDES)]
 Secret = 000102030405060708090A0B0C0D0E0F10111213
 Salt = 
 Output = A09661392376F7044D9052A397883246B67F5F1EF63EB5FB
@@ -9,8 +9,3 @@ Secret = 000102030405060708090A0B0C0D0E0F10111213
 Salt = 0123456789ABCDEFFEDCBA98765432010123456789ABCDEFFEDCBA98765432010123456789ABCDEFFEDCBA98765432010123456789ABCDEFFEDCBA9876543201
 Output = 48950C46E0530075403CCE72889604E0
 
-[X9.42-PRF(1.2.840.113549.1.9.16.3.6)]
-Secret = 000102030405060708090A0B0C0D0E0F10111213
-Salt = 
-Output = A09661392376F7044D9052A397883246B67F5F1EF63EB5FB
-
diff --git a/src/tests/test_ecc_pointmul.cpp b/src/tests/test_ecc_pointmul.cpp
index 5c91f479b..460c43ee5 100644
--- a/src/tests/test_ecc_pointmul.cpp
+++ b/src/tests/test_ecc_pointmul.cpp
@@ -8,7 +8,6 @@
 
 #if defined(BOTAN_HAS_ECDSA)
    #include <botan/ecdsa.h>
-   #include <botan/oids.h>
 #endif
 
 namespace Botan_Tests {
@@ -29,7 +28,7 @@ class ECC_Pointmult_Tests final : public Text_Based_Test
          const Botan::BigInt X = vars.get_req_bn("X");
          const Botan::BigInt Y = vars.get_req_bn("Y");
 
-         Botan::EC_Group group(Botan::OIDS::lookup(group_id));
+         Botan::EC_Group group(Botan::OID::from_string(group_id));
 
          const Botan::PointGFp& base_point = group.get_base_point();
 
diff --git a/src/tests/test_ecdsa.cpp b/src/tests/test_ecdsa.cpp
index 296ae5175..860fe7e11 100644
--- a/src/tests/test_ecdsa.cpp
+++ b/src/tests/test_ecdsa.cpp
@@ -12,7 +12,6 @@
 #if defined(BOTAN_HAS_ECDSA)
    #include "test_pubkey.h"
    #include <botan/ecdsa.h>
-   #include <botan/oids.h>
 #endif
 
 namespace Botan_Tests {
@@ -39,7 +38,7 @@ class ECDSA_Verification_Tests final : public PK_Signature_Verification_Test
          const std::string group_id = vars.get_req_str("Group");
          const BigInt px = vars.get_req_bn("Px");
          const BigInt py = vars.get_req_bn("Py");
-         Botan::EC_Group group(Botan::OIDS::lookup(group_id));
+         Botan::EC_Group group(Botan::OID::from_string(group_id));
 
          const Botan::PointGFp public_point = group.point(px, py);
 
@@ -79,7 +78,7 @@ class ECDSA_Wycheproof_Verification_Tests final : public PK_Signature_Verificati
          const std::string group_id = vars.get_req_str("Group");
          const BigInt px = vars.get_req_bn("Px");
          const BigInt py = vars.get_req_bn("Py");
-         Botan::EC_Group group(Botan::OIDS::lookup(group_id));
+         Botan::EC_Group group(Botan::OID::from_string(group_id));
 
          const Botan::PointGFp public_point = group.point(px, py);
 
@@ -115,7 +114,7 @@ class ECDSA_Signature_KAT_Tests final : public PK_Signature_Generation_Test
          {
          const std::string group_id = vars.get_req_str("Group");
          const BigInt x = vars.get_req_bn("X");
-         Botan::EC_Group group(Botan::OIDS::lookup(group_id));
+         Botan::EC_Group group(Botan::OID::from_string(group_id));
 
          std::unique_ptr<Botan::Private_Key> key(new Botan::ECDSA_PrivateKey(Test::rng(), group, x));
          return key;
@@ -218,7 +217,7 @@ class ECDSA_Invalid_Key_Tests final : public Text_Based_Test
          Test::Result result("ECDSA invalid keys");
 
          const std::string group_id = vars.get_req_str("Group");
-         Botan::EC_Group group(Botan::OIDS::lookup(group_id));
+         Botan::EC_Group group(Botan::OID::from_string(group_id));
          const Botan::BigInt x = vars.get_req_bn("InvalidKeyX");
          const Botan::BigInt y = vars.get_req_bn("InvalidKeyY");
 
diff --git a/src/tests/test_ecgdsa.cpp b/src/tests/test_ecgdsa.cpp
index 5ddb5b9f8..4a39128fb 100644
--- a/src/tests/test_ecgdsa.cpp
+++ b/src/tests/test_ecgdsa.cpp
@@ -11,7 +11,6 @@
 #if defined(BOTAN_HAS_ECGDSA)
    #include "test_pubkey.h"
    #include <botan/ecgdsa.h>
-   #include <botan/oids.h>
 #endif
 
 namespace Botan_Tests {
@@ -37,7 +36,7 @@ class ECGDSA_Signature_KAT_Tests final : public PK_Signature_Generation_Test
          {
          const std::string group_id = vars.get_req_str("Group");
          const BigInt x = vars.get_req_bn("X");
-         Botan::EC_Group group(Botan::OIDS::lookup(group_id));
+         Botan::EC_Group group(Botan::OID::from_string(group_id));
 
          std::unique_ptr<Botan::Private_Key> key(new Botan::ECGDSA_PrivateKey(Test::rng(), group, x));
          return key;
diff --git a/src/tests/test_eckcdsa.cpp b/src/tests/test_eckcdsa.cpp
index c6a8cdd7b..b5a9ab97e 100644
--- a/src/tests/test_eckcdsa.cpp
+++ b/src/tests/test_eckcdsa.cpp
@@ -11,7 +11,6 @@
 #if defined(BOTAN_HAS_ECKCDSA)
    #include "test_pubkey.h"
    #include <botan/eckcdsa.h>
-   #include <botan/oids.h>
 #endif
 
 namespace Botan_Tests {
@@ -38,7 +37,7 @@ class ECKCDSA_Signature_KAT_Tests final : public PK_Signature_Generation_Test
          {
          const std::string group_id = vars.get_req_str("Group");
          const BigInt x = vars.get_req_bn("X");
-         Botan::EC_Group group(Botan::OIDS::lookup(group_id));
+         Botan::EC_Group group(Botan::OID::from_string(group_id));
 
          std::unique_ptr<Botan::Private_Key> key(new Botan::ECKCDSA_PrivateKey(Test::rng(), group, x));
          return key;
diff --git a/src/tests/test_gost_3410.cpp b/src/tests/test_gost_3410.cpp
index d99251075..99ee0fc80 100644
--- a/src/tests/test_gost_3410.cpp
+++ b/src/tests/test_gost_3410.cpp
@@ -8,7 +8,6 @@
 
 #if defined(BOTAN_HAS_GOST_34_10_2001)
    #include <botan/gost_3410.h>
-   #include <botan/oids.h>
    #include "test_pubkey.h"
 #endif
 
diff --git a/src/tests/test_hash_id.cpp b/src/tests/test_hash_id.cpp
index e58c0a5e7..c82139bc3 100644
--- a/src/tests/test_hash_id.cpp
+++ b/src/tests/test_hash_id.cpp
@@ -10,7 +10,6 @@
   #include <botan/hash_id.h>
   #include <botan/der_enc.h>
   #include <botan/alg_id.h>
-  #include <botan/oids.h>
 #endif
 
 namespace Botan_Tests {
@@ -52,7 +51,7 @@ class PKCS_HashID_Test final : public Test
                {
                const std::vector<uint8_t> pkcs_id = Botan::pkcs_hash_id(hash_fn);
 
-               const Botan::OID oid = Botan::OIDS::lookup(hash_fn);
+               const Botan::OID oid = Botan::OID::from_string(hash_fn);
                const Botan::AlgorithmIdentifier alg(oid, Botan::AlgorithmIdentifier::USE_NULL_PARAM);
                const std::vector<uint8_t> dummy_hash(hash_len);
 
diff --git a/src/tests/test_oid.cpp b/src/tests/test_oid.cpp
index 42da391e0..9ab1ad440 100644
--- a/src/tests/test_oid.cpp
+++ b/src/tests/test_oid.cpp
@@ -4,6 +4,8 @@
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
+#define BOTAN_NO_DEPRECATED_WARNINGS
+
 #include "tests.h"
 
 #if defined(BOTAN_HAS_ASN1)
@@ -26,8 +28,8 @@ Test::Result test_add_have_OID()
 
    result.test_eq("OID 'botan-test-oid1' added successfully", Botan::OIDS::have_oid("botan-test-oid1"), true);
 
-   result.test_eq("name of OID '1.2.345.6.666' is 'botan-test-oid1'", Botan::OIDS::name_of(Botan::OID("1.2.345.6.666"),
-                  "botan-test-oid1"), true);
+   result.test_eq("name of OID '1.2.345.6.666' is 'botan-test-oid1'",
+                  Botan::OIDS::oid2str_or_throw(Botan::OID("1.2.345.6.666")), "botan-test-oid1");
 
    return result;
    }
@@ -42,8 +44,8 @@ Test::Result test_add_have_OID_str()
 
    result.test_eq("OID 'botan-test-oid2' added successfully", Botan::OIDS::have_oid("botan-test-oid2"), true);
 
-   result.test_eq("name of OID '1.2.345.6.777' is 'botan-test-oid2'", Botan::OIDS::name_of(Botan::OID("1.2.345.6.777"),
-                  "botan-test-oid2"), true);
+   result.test_eq("name of OID '1.2.345.6.777' is 'botan-test-oid2'",
+                  Botan::OIDS::oid2str_or_throw(Botan::OID("1.2.345.6.777")), "botan-test-oid2");
    return result;
    }
 
@@ -51,21 +53,25 @@ Test::Result test_add_and_lookup()
    {
    Test::Result result("OID add and lookup");
 
-   result.test_eq("OIDS::lookup returns empty string for non-existent OID object",
-                  Botan::OIDS::lookup(Botan::OID("1.2.345.6.888")), std::string());
+   result.test_eq("OIDS::oid2str_or_empty returns empty string for non-existent OID object",
+                  Botan::OIDS::oid2str_or_empty(Botan::OID("1.2.345.6.888")), std::string());
 
-   result.test_eq("OIDS::lookup returns empty OID for non-existent OID name", Botan::OIDS::lookup("botan-test-oid3").to_string(), Botan::OID().to_string());
+   result.test_eq("OIDS::str2oid_or_empty returns empty OID for non-existent OID name",
+                  Botan::OIDS::str2oid_or_empty("botan-test-oid3").to_string(), Botan::OID().to_string());
 
    // add oid -> string mapping
    Botan::OIDS::add_oid2str(Botan::OID("1.2.345.6.888"), "botan-test-oid3");
-   result.test_eq("", Botan::OIDS::lookup(Botan::OID("1.2.345.6.888")), "botan-test-oid3");
+   result.test_eq("Lookup works after adding the OID",
+                  Botan::OIDS::oid2str_or_throw(Botan::OID("1.2.345.6.888")), "botan-test-oid3");
 
    // still returns empty OID
-   result.test_eq("OIDS::lookup still returns empty OID without adding name mapping", Botan::OIDS::lookup("botan-test-oid3").to_string(), Botan::OID().to_string());
+   result.test_eq("OIDS::str2oid_or_empty still returns empty OID without adding name mapping",
+                  Botan::OIDS::str2oid_or_empty("botan-test-oid3").to_string(), Botan::OID().to_string());
 
    // add string -> oid mapping
    Botan::OIDS::add_str2oid(Botan::OID("1.2.345.6.888"), "botan-test-oid3");
-   Botan::OIDS::lookup("botan-test-oid3");
+   result.test_eq("OIDS::str2oid_or_empty returns value after adding name mapping",
+                  Botan::OIDS::str2oid_or_empty("botan-test-oid3").to_string(), Botan::OID({1,2,345,6,888}).to_string());
 
    return result;
    }
diff --git a/src/tests/unit_ecc.cpp b/src/tests/unit_ecc.cpp
index 08d08b516..6a3a17367 100644
--- a/src/tests/unit_ecc.cpp
+++ b/src/tests/unit_ecc.cpp
@@ -19,7 +19,6 @@
   #include <botan/hex.h>
   #include <botan/data_src.h>
   #include <botan/x509_key.h>
-  #include <botan/oids.h>
 #endif
 
 namespace Botan_Tests {
@@ -274,7 +273,7 @@ class EC_Group_Tests : public Test
             {
             Test::Result result("EC_Group " + group_name);
 
-            const Botan::OID oid = Botan::OIDS::lookup(group_name);
+            const Botan::OID oid = Botan::OID::from_string(group_name);
 
             const Botan::EC_Group group(oid);
 
diff --git a/src/tests/unit_ecdsa.cpp b/src/tests/unit_ecdsa.cpp
index ee8ffc375..a103e67b0 100644
--- a/src/tests/unit_ecdsa.cpp
+++ b/src/tests/unit_ecdsa.cpp
@@ -82,7 +82,7 @@ Test::Result test_decode_ecdsa_X509()
    Test::Result result("ECDSA Unit");
    Botan::X509_Certificate cert(Test::data_file("x509/ecc/CSCA.CSCA.csca-germany.1.crt"));
 
-   result.test_eq("correct signature oid", Botan::OIDS::lookup(cert.signature_algorithm().get_oid()), "ECDSA/EMSA1(SHA-224)");
+   result.test_eq("correct signature oid", cert.signature_algorithm().get_oid().to_formatted_string(), "ECDSA/EMSA1(SHA-224)");
 
    result.test_eq("serial number", cert.serial_number(), Botan::hex_decode("01"));
    result.test_eq("authority key id", cert.authority_key_id(), cert.subject_key_id());
diff --git a/src/tests/unit_x509.cpp b/src/tests/unit_x509.cpp
index 69ffe3823..2b4b3f5de 100644
--- a/src/tests/unit_x509.cpp
+++ b/src/tests/unit_x509.cpp
@@ -8,7 +8,6 @@
 #include "tests.h"
 
 #if defined(BOTAN_HAS_X509_CERTIFICATES)
-
    #include <botan/calendar.h>
    #include <botan/pkcs10.h>
    #include <botan/pkcs8.h>
@@ -20,7 +19,6 @@
    #include <botan/der_enc.h>
    #include <botan/oids.h>
    #include <botan/internal/padding.h>
-
 #endif
 
 namespace Botan_Tests {
@@ -429,7 +427,7 @@ Test::Result test_rsa_oaep()
    result.test_not_null("Decoding RSA-OAEP worked", public_key.get());
    auto pk_info = cert.subject_public_key_algo();
 
-   result.test_eq("RSA-OAEP OID", pk_info.get_oid().to_string(), Botan::OIDS::lookup("RSA/OAEP").to_string());
+   result.test_eq("RSA-OAEP OID", pk_info.get_oid().to_string(), Botan::OID::from_string("RSA/OAEP").to_string());
 #endif
 
    return result;
@@ -604,13 +602,13 @@ Test::Result test_verify_gost2012_cert()
 
    Botan::X509_Certificate ca_cert_def = Botan::X509::create_self_signed_cert(opt, (*sk), "SHA-512", Test::rng());
    test_result.test_eq("CA certificate signature algorithm (default)",
-      Botan::OIDS::lookup(ca_cert_def.signature_algorithm().oid),"RSA/EMSA3(SHA-512)");
+      Botan::OIDS::oid2str_or_throw(ca_cert_def.signature_algorithm().get_oid()),"RSA/EMSA3(SHA-512)");
 
    // Create X509 CA certificate; RSA-PSS is explicitly set
    opt.set_padding_scheme("PSSR");
    Botan::X509_Certificate ca_cert_exp = Botan::X509::create_self_signed_cert(opt, (*sk), "SHA-512", Test::rng());
    test_result.test_eq("CA certificate signature algorithm (explicit)",
-      Botan::OIDS::lookup(ca_cert_exp.signature_algorithm().oid),"RSA/EMSA4");
+      Botan::OIDS::oid2str_or_throw(ca_cert_exp.signature_algorithm().get_oid()),"RSA/EMSA4");
 
 #if defined(BOTAN_HAS_EMSA1)
 
@@ -630,7 +628,7 @@ Test::Result test_verify_gost2012_cert()
 #endif
 
    test_result.test_eq("CA certificate signature algorithm (explicit)",
-      Botan::OIDS::lookup(ca_cert_exp.signature_algorithm().oid),"RSA/EMSA4");
+      Botan::OIDS::oid2str_or_throw(ca_cert_exp.signature_algorithm().get_oid()),"RSA/EMSA4");
 
    const Botan::X509_Time not_before = from_date(-1, 1, 1);
    const Botan::X509_Time not_after = from_date(2, 1, 2);
@@ -639,7 +637,7 @@ Test::Result test_verify_gost2012_cert()
    Botan::X509_Cert_Options req_opt("endpoint");
    req_opt.set_padding_scheme("EMSA4(SHA-512,MGF1,64)");
    Botan::PKCS10_Request end_req = Botan::X509::create_cert_req(req_opt, (*sk), "SHA-512", Test::rng());
-   test_result.test_eq("Certificate request signature algorithm", Botan::OIDS::lookup(end_req.signature_algorithm().oid),"RSA/EMSA4");
+   test_result.test_eq("Certificate request signature algorithm", Botan::OIDS::oid2str_or_throw(end_req.signature_algorithm().get_oid()),"RSA/EMSA4");
 
    // Create X509 CA object: will fail as the chosen hash functions differ
    try
@@ -657,21 +655,21 @@ Test::Result test_verify_gost2012_cert()
    // Create X509 CA object: its signer will use the padding scheme from the CA certificate, i.e. EMSA3
    Botan::X509_CA ca_def(ca_cert_def, (*sk), "SHA-512", Test::rng());
    Botan::X509_Certificate end_cert_emsa3 = ca_def.sign_request(end_req, Test::rng(), not_before, not_after);
-   test_result.test_eq("End certificate signature algorithm", Botan::OIDS::lookup(end_cert_emsa3.signature_algorithm().oid), "RSA/EMSA3(SHA-512)");
+   test_result.test_eq("End certificate signature algorithm", Botan::OIDS::oid2str_or_throw(end_cert_emsa3.signature_algorithm().get_oid()), "RSA/EMSA3(SHA-512)");
 
    // Create X509 CA object: its signer will use the explicitly configured padding scheme, which is different from the CA certificate's scheme
    Botan::X509_CA ca_diff(ca_cert_def, (*sk), {{"padding","EMSA-PSS"}}, "SHA-512", Test::rng());
    Botan::X509_Certificate end_cert_diff_emsa4 = ca_diff.sign_request(end_req, Test::rng(), not_before, not_after);
-   test_result.test_eq("End certificate signature algorithm", Botan::OIDS::lookup(end_cert_diff_emsa4.signature_algorithm().oid), "RSA/EMSA4");
+   test_result.test_eq("End certificate signature algorithm", Botan::OIDS::oid2str_or_throw(end_cert_diff_emsa4.signature_algorithm().get_oid()), "RSA/EMSA4");
 
    // Create X509 CA object: its signer will use the explicitly configured padding scheme, which is identical to the CA certificate's scheme
    Botan::X509_CA ca_exp(ca_cert_exp, (*sk), {{"padding","EMSA4(SHA-512,MGF1,64)"}},"SHA-512", Test::rng());
    Botan::X509_Certificate end_cert_emsa4= ca_exp.sign_request(end_req, Test::rng(), not_before, not_after);
-   test_result.test_eq("End certificate signature algorithm", Botan::OIDS::lookup(end_cert_emsa4.signature_algorithm().oid), "RSA/EMSA4");
+   test_result.test_eq("End certificate signature algorithm", Botan::OIDS::oid2str_or_throw(end_cert_emsa4.signature_algorithm().get_oid()), "RSA/EMSA4");
 
    // Check CRL signature algorithm
    Botan::X509_CRL crl = ca_exp.new_crl(Test::rng());
-   test_result.test_eq("CRL signature algorithm", Botan::OIDS::lookup(crl.signature_algorithm().oid), "RSA/EMSA4");
+   test_result.test_eq("CRL signature algorithm", Botan::OIDS::oid2str_or_throw(crl.signature_algorithm().get_oid()), "RSA/EMSA4");
 
    // sanity check for verification, the heavy lifting is done in the other unit tests
    const Botan::Certificate_Store_In_Memory trusted(ca_exp.ca_certificate());
@@ -1392,7 +1390,7 @@ Test::Result test_x509_extensions(const Botan::Private_Key& ca_key,
    // include a custom extension in the request
    Botan::Extensions req_extensions;
    const Botan::OID oid("1.2.3.4.5.6.7.8.9.1");
-   const Botan::OID ku_oid = Botan::OIDS::lookup("X509v3.KeyUsage");
+   const Botan::OID ku_oid = Botan::OID::from_string("X509v3.KeyUsage");
    req_extensions.add(new String_Extension("AAAAAAAAAAAAAABCDEF"), false);
    opts.extensions = req_extensions;
    opts.set_padding_scheme(sig_padding);