Fix X509_DN comparison

An issue in #1936 indicated that X509_DN operator< was not
behaving correctly. Indeed, DNs could compare in such a way
that DN1 < DN2 && DN2 < DN1. STL containers do not like this.

8 files changed, 147 insertions, 13 deletions

diff --git a/src/fuzzer/x509_dn.cpp b/src/fuzzer/x509_dn.cpp
new file mode 100644
index 000000000..dca6352e9
--- /dev/null
+++ b/src/fuzzer/x509_dn.cpp
@@ -0,0 +1,46 @@
+/*
+* (C) 2019 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include "fuzzers.h"
+#include <botan/x509_dn.h>
+#include <botan/ber_dec.h>
+#include <botan/hex.h>
+
+void fuzz(const uint8_t in[], size_t len)
+   {
+   const size_t half = len / 2;
+   Botan::X509_DN dn1;
+   Botan::X509_DN dn2;
+
+   try
+      {
+      Botan::BER_Decoder ber1(in, half);
+      dn1.decode_from(ber1);
+      ber1.verify_end();
+
+      Botan::BER_Decoder ber2(in + half, half);
+      dn2.decode_from(ber2);
+      ber2.verify_end();
+      }
+   catch(...) { return; }
+
+   const bool eq = dn1 == dn2;
+   const bool lt1 = dn1 < dn2;
+   const bool lt2 = dn2 < dn1;
+
+   if(lt1 == false && lt2 == false)
+      {
+      FUZZER_ASSERT_TRUE(eq);
+      }
+   else
+      {
+      // one is less than the other
+      FUZZER_ASSERT_TRUE(lt1 || lt2);
+
+      // it is not the case that both are less than the other
+      FUZZER_ASSERT_TRUE(!lt1 || !lt2);
+      }
+   }
diff --git a/src/lib/asn1/asn1_obj.cpp b/src/lib/asn1/asn1_obj.cpp
index 815bc4ef8..824355264 100644
--- a/src/lib/asn1/asn1_obj.cpp
+++ b/src/lib/asn1/asn1_obj.cpp
@@ -136,6 +136,9 @@ std::string asn1_tag_to_string(ASN1_Tag type)
       case Botan::BMP_STRING:
          return "BMP STRING";
 
+      case Botan::UNIVERSAL_STRING:
+         return "UNIVERSAL STRING";
+
       case Botan::UTC_TIME:
          return "UTC TIME";
 
diff --git a/src/lib/asn1/asn1_oid.h b/src/lib/asn1/asn1_oid.h
index f3ff36ce2..1c8959d99 100644
--- a/src/lib/asn1/asn1_oid.h
+++ b/src/lib/asn1/asn1_oid.h
@@ -78,7 +78,7 @@ class BOTAN_PUBLIC_API(2,0) OID final : public ASN1_Object
       * Construct an OID from a string.
       * @param str a string in the form "a.b.c" etc., where a,b,c are numbers
       */
-      OID(const std::string& str = "");
+      explicit OID(const std::string& str = "");
 
       explicit OID(std::initializer_list<uint32_t> init) : m_id(init) {}
    private:
diff --git a/src/lib/asn1/oids.cpp b/src/lib/asn1/oids.cpp
index 80f079395..844cdff79 100644
--- a/src/lib/asn1/oids.cpp
+++ b/src/lib/asn1/oids.cpp
@@ -28,7 +28,7 @@ class OID_Map final
          lock_guard_type<mutex_type> lock(m_mutex);
          auto i = m_str2oid.find(str);
          if(i == m_str2oid.end())
-            m_str2oid.insert(std::make_pair(str, oid.to_string()));
+            m_str2oid.insert(std::make_pair(str, oid));
          }
 
       void add_oid2str(const OID& oid, const std::string& str)
diff --git a/src/lib/x509/x509_dn.cpp b/src/lib/x509/x509_dn.cpp
index 106190011..6e2707673 100644
--- a/src/lib/x509/x509_dn.cpp
+++ b/src/lib/x509/x509_dn.cpp
@@ -184,16 +184,54 @@ bool operator<(const X509_DN& dn1, const X509_DN& dn2)
    auto attr1 = dn1.get_attributes();
    auto attr2 = dn2.get_attributes();
 
-   if(attr1.size() < attr2.size()) return true;
-   if(attr1.size() > attr2.size()) return false;
+   // If they are not the same size, choose the smaller as the "lessor"
+   if(attr1.size() < attr2.size())
+      return true;
+   if(attr1.size() > attr2.size())
+      return false;
 
-   for(auto p1 = attr1.begin(); p1 != attr1.end(); ++p1)
+   // We know they are the same # of elements, now compare the OIDs:
+   auto p1 = attr1.begin();
+   auto p2 = attr2.begin();
+
+   while(p1 != attr1.end() && p2 != attr2.end())
       {
-      auto p2 = attr2.find(p1->first);
-      if(p2 == attr2.end())       return false;
-      if(p1->second > p2->second) return false;
-      if(p1->second < p2->second) return true;
+      if(p1->first != p2->first)
+         {
+         return (p1->first < p2->first);
+         }
+
+      ++p1;
+      ++p2;
       }
+
+   // We know this is true because maps have the same size
+   BOTAN_ASSERT_NOMSG(p1 == attr1.end());
+   BOTAN_ASSERT_NOMSG(p2 == attr2.end());
+
+   // Now we know all elements have the same OIDs, compare
+   // their string values:
+
+   p1 = attr1.begin();
+   p2 = attr2.begin();
+   while(p1 != attr1.end() && p2 != attr2.end())
+      {
+      BOTAN_DEBUG_ASSERT(p1->first == p2->first);
+
+      // They may be binary different but same by X.500 rules, check this
+      if(!x500_name_cmp(p1->second, p2->second))
+         {
+         // If they are not (by X.500) the same string, pick the
+         // lexicographic first as the lessor
+         return (p1->second < p2->second);
+         }
+
+      ++p1;
+      ++p2;
+      }
+
+   // if we reach here, then the DNs should be identical
+   BOTAN_DEBUG_ASSERT(dn1 == dn2);
    return false;
    }
 
@@ -250,7 +288,10 @@ void X509_DN::decode_from(BER_Decoder& source)
          OID oid;
          ASN1_String str;
 
-         rdn.start_cons(SEQUENCE).decode(oid).decode(str).end_cons();
+         rdn.start_cons(SEQUENCE)
+            .decode(oid)
+            .decode(str) // TODO support Any
+            .end_cons().verify_end("Invalid X509_DN, data follows RDN");
 
          add_attribute(oid, str);
          }
diff --git a/src/lib/x509/x509_dn.h b/src/lib/x509/x509_dn.h
index f47099c9a..db608ff26 100644
--- a/src/lib/x509/x509_dn.h
+++ b/src/lib/x509/x509_dn.h
@@ -87,9 +87,14 @@ class BOTAN_PUBLIC_API(2,0) X509_DN final : public ASN1_Object
       std::vector<uint8_t> m_dn_bits;
    };
 
-bool BOTAN_PUBLIC_API(2,0) operator==(const X509_DN&, const X509_DN&);
-bool BOTAN_PUBLIC_API(2,0) operator!=(const X509_DN&, const X509_DN&);
-bool BOTAN_PUBLIC_API(2,0) operator<(const X509_DN&, const X509_DN&);
+bool BOTAN_PUBLIC_API(2,0) operator==(const X509_DN& dn1, const X509_DN& dn2);
+bool BOTAN_PUBLIC_API(2,0) operator!=(const X509_DN& dn1, const X509_DN& dn2);
+
+/*
+The ordering here is arbitrary and may change from release to release.
+It is intended for allowing DNs as keys in std::map and similiar containers
+*/
+bool BOTAN_PUBLIC_API(2,0) operator<(const X509_DN& dn1, const X509_DN& dn2);
 
 BOTAN_PUBLIC_API(2,0) std::ostream& operator<<(std::ostream& out, const X509_DN& dn);
 BOTAN_PUBLIC_API(2,0) std::istream& operator>>(std::istream& in, X509_DN& dn);
diff --git a/src/tests/data/x509_dn.vec b/src/tests/data/x509_dn.vec
index ab9e2dec3..e71510dbb 100644
--- a/src/tests/data/x509_dn.vec
+++ b/src/tests/data/x509_dn.vec
@@ -1,8 +1,29 @@
 
 [Equal]
+# Empty
+DN1 = 3000
+DN2 = 3000
+
+# Equal binary
 DN1 = 301C310B3009060355040613025654310D300B0603550403130454455354
 DN2 = 301C310B3009060355040613025654310D300B0603550403130454455354
 
+# Different string types, same contents
+DN1 = 302E3111300F06035504061C0800000056000000543119301706035504031C1000000054000000450000005300000054
+DN2 = 301C310B3009060355040613025654310D300B0603550403130454455354
+
+# Same contents, different casing (X.500 demands case-insensitive), different order
+DN1 = 301C310B3009060355040613025654310D300B0603550403130454455354
+DN2 = 301C310D300B0603550403130474457354310B3009060355040613027674
+
+# Empty, different encodings
+DN1 = 3000
+DN2 = 3080
+
+# Empty, one using EOC encoding
+DN1 = 0000308100
+DN2 = 3000
+
 [Unequal]
 DN1 = 301C310B3009060355040613025654310D300B0603550403130454450054
 DN2 = 301C310B3009060355040613025600310D300B0603550403130454455354
@@ -12,3 +33,6 @@ DN2 = 3019311730150603550403130E4141202020202020202020202020
 
 DN1 = 3018311630140603550403130D41412041414141414141414141
 DN2 = 3019311730150603550403130E4141202020202020202020202020
+
+DN1 = 3080318030800604307A7AFD1E808080300080208080800F0029000B800000000001000000D60680FF7FFFFF00040404040404040404040404230404040404040404040404040404040404040404040404040404040404040404040404040404040404040404040404000000
+DN2 = 000000000000000000000000000000000000000030803180308006047A7A30FD1E808080300080208080810F0000000B800000000001000000D60680FF7FFF040404040404040404040404040404040404040404040404000000000000000404040404040404040404890880
diff --git a/src/tests/test_x509_dn.cpp b/src/tests/test_x509_dn.cpp
index 662c11e74..7e93d2c24 100644
--- a/src/tests/test_x509_dn.cpp
+++ b/src/tests/test_x509_dn.cpp
@@ -23,6 +23,7 @@ class X509_DN_Comparisons_Tests final : public Text_Based_Test
          {
          const std::vector<uint8_t> dn_bits1 = vars.get_req_bin("DN1");
          const std::vector<uint8_t> dn_bits2 = vars.get_req_bin("DN2");
+
          const bool dn_same = (type == "Equal");
 
          Test::Result result("X509_DN comparisons");
@@ -38,6 +39,20 @@ class X509_DN_Comparisons_Tests final : public Text_Based_Test
 
             const bool compared_same = (dn1 == dn2);
             result.test_eq("Comparison matches expected", dn_same, compared_same);
+
+            const bool lt1 = (dn1 < dn2);
+            const bool lt2 = (dn2 < dn1);
+
+            if(dn_same)
+               {
+               result.test_eq("same means neither is less than", lt1, false);
+               result.test_eq("same means neither is less than", lt2, false);
+               }
+            else
+               {
+               result.test_eq("different means one is less than", lt1 || lt2, true);
+               result.test_eq("different means only one is less than", lt1 && lt2, false);
+               }
             }
          catch(Botan::Exception& e)
             {