11972552403

Committed 22 Nov 2024 12:26PM UTC coverage: 91.244% (+0.004%) from 91.24%

Build # 11972552403

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #4436 from randombit/jack/cleanup-curvegfp

Cleanups relating to CurveGFp

Run Details

93250 of 102198 relevant lines covered (91.24%)

11237819.31 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

91.61

/src/lib/pubkey/ec_group/ec_group.cpp

/*
* ECC Domain Parameters
*
* (C) 2007 Falko Strenzke, FlexSecure GmbH
* (C) 2008,2018,2024 Jack Lloyd
* (C) 2018 Tobias Niemann
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/ec_group.h>

#include <botan/ber_dec.h>
#include <botan/der_enc.h>
#include <botan/mutex.h>
#include <botan/pem.h>
#include <botan/reducer.h>
#include <botan/rng.h>
#include <botan/internal/ec_inner_data.h>
#include <botan/internal/fmt.h>
#include <botan/internal/primality.h>
#include <vector>

namespace Botan {

class EC_Group_Data_Map final {
   public:
      EC_Group_Data_Map() = default;

      size_t clear() {
         lock_guard_type<mutex_type> lock(m_mutex);
         size_t count = m_registered_curves.size();
         m_registered_curves.clear();
         return count;
      }

      std::shared_ptr<EC_Group_Data> lookup(const OID& oid) {
         lock_guard_type<mutex_type> lock(m_mutex);

         for(auto i : m_registered_curves) {
            if(i->oid() == oid) {
               return i;
            }
         }

         // Not found, check hardcoded data
         std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid);

         if(data) {
            for(auto curve : m_registered_curves) {
               if(curve->oid().empty() == true && curve->params_match(*data)) {
                  curve->set_oid(oid);
                  return curve;
               }
            }

            m_registered_curves.push_back(data);
            return data;
         }

         // Nope, unknown curve
         return std::shared_ptr<EC_Group_Data>();
      }

      std::shared_ptr<EC_Group_Data> lookup_or_create(const BigInt& p,
                                                      const BigInt& a,
                                                      const BigInt& b,
                                                      const BigInt& g_x,
                                                      const BigInt& g_y,
                                                      const BigInt& order,
                                                      const BigInt& cofactor,
                                                      const OID& oid,
                                                      EC_Group_Source source) {
         lock_guard_type<mutex_type> lock(m_mutex);

         for(auto i : m_registered_curves) {
            /*
            * The params may be the same but you are trying to register under a
            * different OID than the one we are using, so using a different
            * group, since EC_Group's model assumes a single OID per group.
            */
            if(!oid.empty() && !i->oid().empty() && i->oid() != oid) {
               continue;
            }

            const bool same_oid = !oid.empty() && i->oid() == oid;
            const bool same_params = i->params_match(p, a, b, g_x, g_y, order, cofactor);

            /*
            * If the params and OID are the same then we are done, just return
            * the already registered curve obj.
            */
            if(same_params && same_oid) {
               return i;
            }

            /*
            * If same params and the new OID is empty, then that's ok too
            */
            if(same_params && oid.empty()) {
               return i;
            }

            /*
            * Check for someone trying to reuse an already in-use OID
            */
            if(same_oid && !same_params) {
               throw Invalid_Argument("Attempting to register a curve using OID " + oid.to_string() +
                                      " but a distinct curve is already registered using that OID");
            }

            /*
            * If the same curve was previously created without an OID but is now
            * being registered again using an OID, save that OID.
            */
            if(same_params && i->oid().empty() && !oid.empty()) {
               i->set_oid(oid);
               return i;
            }
         }

         /*
         Not found in current list, so we need to create a new entry

         If an OID is set, try to look up relative our static tables to detect a duplicate
         registration under an OID
         */

         auto new_group = EC_Group_Data::create(p, a, b, g_x, g_y, order, cofactor, oid, source);

         if(oid.has_value()) {
            std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid);
            if(data != nullptr && !new_group->params_match(*data)) {
               throw Invalid_Argument("Attempting to register an EC group under OID of hardcoded group");
            }
         } else {
            // Here try to use the order as a hint to look up the group id, to identify common groups
            const OID oid_from_store = EC_Group::EC_group_identity_from_order(order);
            if(oid_from_store.has_value()) {
               std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid_from_store);

               /*
               If EC_group_identity_from_order returned an OID then looking up that OID
               must always return a result.
               */
               BOTAN_ASSERT_NOMSG(data != nullptr);

               /*
               It is possible (if unlikely) that someone is registering another group
               that happens to have an order equal to that of a well known group -
               so verify all values before assigning the OID.
               */
               if(new_group->params_match(*data)) {
                  new_group->set_oid(oid_from_store);
               }
            }
         }

         m_registered_curves.push_back(new_group);
         return new_group;
      }

   private:
      mutex_type m_mutex;
      std::vector<std::shared_ptr<EC_Group_Data>> m_registered_curves;
};

//static
EC_Group_Data_Map& EC_Group::ec_group_data() {
   /*
   * This exists purely to ensure the allocator is constructed before g_ec_data,
   * which ensures that its destructor runs after ~g_ec_data is complete.
   */

   static Allocator_Initializer g_init_allocator;
   static EC_Group_Data_Map g_ec_data;
   return g_ec_data;
}

//static
size_t EC_Group::clear_registered_curve_data() {
   return ec_group_data().clear();
}

//static
std::shared_ptr<EC_Group_Data> EC_Group::load_EC_group_info(const char* p_str,
                                                            const char* a_str,
                                                            const char* b_str,
                                                            const char* g_x_str,
                                                            const char* g_y_str,
                                                            const char* order_str,
                                                            const OID& oid) {
   const BigInt p(p_str);
   const BigInt a(a_str);
   const BigInt b(b_str);
   const BigInt g_x(g_x_str);
   const BigInt g_y(g_y_str);
   const BigInt order(order_str);
   const BigInt cofactor(1);  // implicit

   return EC_Group_Data::create(p, a, b, g_x, g_y, order, cofactor, oid, EC_Group_Source::Builtin);
}

//static
std::pair<std::shared_ptr<EC_Group_Data>, bool> EC_Group::BER_decode_EC_group(std::span<const uint8_t> bits,
                                                                              EC_Group_Source source) {
   BER_Decoder ber(bits);
   BER_Object obj = ber.get_next_object();

   if(obj.type() == ASN1_Type::ObjectId) {
      OID oid;
      BER_Decoder(bits).decode(oid);

      auto data = ec_group_data().lookup(oid);
      if(!data) {
         throw Decoding_Error(fmt("Unknown namedCurve OID '{}'", oid.to_string()));
      }

      return std::make_pair(data, false);
   }

   if(obj.type() == ASN1_Type::Sequence) {
      BigInt p, a, b, order, cofactor;
      std::vector<uint8_t> base_pt;
      std::vector<uint8_t> seed;

      BER_Decoder(bits)
         .start_sequence()
         .decode_and_check<size_t>(1, "Unknown ECC param version code")
         .start_sequence()
         .decode_and_check(OID("1.2.840.10045.1.1"), "Only prime ECC fields supported")
         .decode(p)
         .end_cons()
         .start_sequence()
         .decode_octet_string_bigint(a)
         .decode_octet_string_bigint(b)
         .decode_optional_string(seed, ASN1_Type::BitString, ASN1_Type::BitString)
         .end_cons()
         .decode(base_pt, ASN1_Type::OctetString)
         .decode(order)
         .decode(cofactor)
         .end_cons()
         .verify_end();

      if(p.bits() < 112 || p.bits() > 521) {
         throw Decoding_Error("ECC p parameter is invalid size");
      }

      if(p.is_negative() || !is_bailie_psw_probable_prime(p)) {
         throw Decoding_Error("ECC p parameter is not a prime");
      }

      if(a.is_negative() || a >= p) {
         throw Decoding_Error("Invalid ECC a parameter");
      }

      if(b <= 0 || b >= p) {
         throw Decoding_Error("Invalid ECC b parameter");
      }

      if(order <= 0 || !is_bailie_psw_probable_prime(order)) {
         throw Decoding_Error("Invalid ECC order parameter");
      }

      if(cofactor <= 0 || cofactor >= 16) {
         throw Decoding_Error("Invalid ECC cofactor parameter");
      }

      const auto [g_x, g_y] = Botan::OS2ECP(base_pt.data(), base_pt.size(), p, a, b);

      auto data = ec_group_data().lookup_or_create(p, a, b, g_x, g_y, order, cofactor, OID(), source);
      return std::make_pair(data, true);
   }

   if(obj.type() == ASN1_Type::Null) {
      throw Decoding_Error("Cannot handle ImplicitCA ECC parameters");
   } else {
      throw Decoding_Error(fmt("Unexpected tag {} while decoding ECC domain params", asn1_tag_to_string(obj.type())));
   }
}

EC_Group::EC_Group() = default;

EC_Group::~EC_Group() = default;

EC_Group::EC_Group(const EC_Group&) = default;

EC_Group& EC_Group::operator=(const EC_Group&) = default;

// Internal constructor
EC_Group::EC_Group(std::shared_ptr<EC_Group_Data>&& data) : m_data(std::move(data)) {}

//static
EC_Group EC_Group::from_OID(const OID& oid) {
   auto data = ec_group_data().lookup(oid);

   if(!data) {
      throw Invalid_Argument(fmt("No EC_Group associated with OID '{}'", oid.to_string()));
   }

   return EC_Group(std::move(data));
}

//static
EC_Group EC_Group::from_name(std::string_view name) {
   std::shared_ptr<EC_Group_Data> data;

   if(auto oid = OID::from_name(name)) {
      data = ec_group_data().lookup(oid.value());
   }

   if(!data) {
      throw Invalid_Argument(fmt("Unknown EC_Group '{}'", name));
   }

   return EC_Group(std::move(data));
}

EC_Group::EC_Group(std::string_view str) {
   if(str.empty()) {
      return;  // no initialization / uninitialized
   }

   try {
      const OID oid = OID::from_string(str);
      if(oid.has_value()) {
         m_data = ec_group_data().lookup(oid);
      }
   } catch(...) {}

   if(m_data == nullptr) {
      if(str.size() > 30 && str.substr(0, 29) == "-----BEGIN EC PARAMETERS-----") {
         // OK try it as PEM ...
         const auto ber = PEM_Code::decode_check_label(str, "EC PARAMETERS");

         auto data = BER_decode_EC_group(ber, EC_Group_Source::ExternalSource);
         this->m_data = data.first;
         this->m_explicit_encoding = data.second;
      }
   }

   if(m_data == nullptr) {
      throw Invalid_Argument(fmt("Unknown ECC group '{}'", str));
   }
}

//static
EC_Group EC_Group::from_PEM(std::string_view pem) {
   const auto ber = PEM_Code::decode_check_label(pem, "EC PARAMETERS");
   return EC_Group(ber);
}

EC_Group::EC_Group(const BigInt& p,
                   const BigInt& a,
                   const BigInt& b,
                   const BigInt& base_x,
                   const BigInt& base_y,
                   const BigInt& order,
                   const BigInt& cofactor,
                   const OID& oid) {
   m_data =
      ec_group_data().lookup_or_create(p, a, b, base_x, base_y, order, cofactor, oid, EC_Group_Source::ExternalSource);
}

EC_Group::EC_Group(const OID& oid,
                   const BigInt& p,
                   const BigInt& a,
                   const BigInt& b,
                   const BigInt& base_x,
                   const BigInt& base_y,
                   const BigInt& order) {
   BOTAN_ARG_CHECK(oid.has_value(), "An OID is required for creating an EC_Group");
   BOTAN_ARG_CHECK(p.bits() >= 128, "EC_Group p too small");
   BOTAN_ARG_CHECK(p.bits() <= 521, "EC_Group p too large");

   if(p.bits() == 521) {
      BOTAN_ARG_CHECK(p == BigInt::power_of_2(521) - 1, "EC_Group with p of 521 bits must be 2**521-1");
   } else {
      BOTAN_ARG_CHECK(p.bits() % 32 == 0, "EC_Group p must be a multiple of 32 bits");
   }

   BOTAN_ARG_CHECK(p % 4 == 3, "EC_Group p must be congruent to 3 modulo 4");

   BOTAN_ARG_CHECK(a >= 0 && a < p, "EC_Group a is invalid");
   BOTAN_ARG_CHECK(b > 0 && b < p, "EC_Group b is invalid");
   BOTAN_ARG_CHECK(base_x >= 0 && base_x < p, "EC_Group base_x is invalid");
   BOTAN_ARG_CHECK(base_y >= 0 && base_y < p, "EC_Group base_y is invalid");
   BOTAN_ARG_CHECK(p.bits() == order.bits(), "EC_Group p and order must have the same number of bits");

   BOTAN_ARG_CHECK(is_bailie_psw_probable_prime(p), "EC_Group p is not prime");
   BOTAN_ARG_CHECK(is_bailie_psw_probable_prime(order), "EC_Group order is not prime");

   // This catches someone "ignoring" a cofactor and just trying to
   // provide the subgroup order
   BOTAN_ARG_CHECK((p - order).abs().bits() <= (p.bits() / 2) + 1, "Hasse bound invalid");

   BigInt cofactor(1);

   m_data =
      ec_group_data().lookup_or_create(p, a, b, base_x, base_y, order, cofactor, oid, EC_Group_Source::ExternalSource);
}

EC_Group::EC_Group(std::span<const uint8_t> ber) {
   auto data = BER_decode_EC_group(ber, EC_Group_Source::ExternalSource);
   m_data = data.first;
   m_explicit_encoding = data.second;
}

const EC_Group_Data& EC_Group::data() const {
   if(m_data == nullptr) {
      throw Invalid_State("EC_Group uninitialized");
   }
   return *m_data;
}

size_t EC_Group::get_p_bits() const {
   return data().p_bits();
}

size_t EC_Group::get_p_bytes() const {
   return data().p_bytes();
}

size_t EC_Group::get_order_bits() const {
   return data().order_bits();
}

size_t EC_Group::get_order_bytes() const {
   return data().order_bytes();
}

const BigInt& EC_Group::get_p() const {
   return data().p();
}

const BigInt& EC_Group::get_a() const {
   return data().a();
}

const BigInt& EC_Group::get_b() const {
   return data().b();
}

const EC_Point& EC_Group::get_base_point() const {
   return data().base_point();
}

const EC_Point& EC_Group::generator() const {
   return data().base_point();
}

const BigInt& EC_Group::get_order() const {
   return data().order();
}

const BigInt& EC_Group::get_g_x() const {
   return data().g_x();
}

const BigInt& EC_Group::get_g_y() const {
   return data().g_y();
}

const BigInt& EC_Group::get_cofactor() const {
   return data().cofactor();
}

bool EC_Group::has_cofactor() const {
   return data().has_cofactor();
}

BigInt EC_Group::mod_order(const BigInt& k) const {
   return data().mod_order(k);
}

const OID& EC_Group::get_curve_oid() const {
   return data().oid();
}

EC_Group_Source EC_Group::source() const {
   return data().source();
}

std::vector<uint8_t> EC_Group::DER_encode() const {
   const auto& der_named_curve = data().der_named_curve();
   // TODO(Botan4) this can be removed because an OID will always be defined
   if(der_named_curve.empty()) {
      throw Encoding_Error("Cannot encode EC_Group as OID because OID not set");
   }

   return der_named_curve;
}

std::vector<uint8_t> EC_Group::DER_encode(EC_Group_Encoding form) const {
   if(form == EC_Group_Encoding::Explicit) {
      std::vector<uint8_t> output;
      DER_Encoder der(output);
      const size_t ecpVers1 = 1;
      const OID curve_type("1.2.840.10045.1.1");  // prime field

      const size_t p_bytes = get_p_bytes();

      der.start_sequence()
         .encode(ecpVers1)
         .start_sequence()
         .encode(curve_type)
         .encode(get_p())
         .end_cons()
         .start_sequence()
         .encode(get_a().serialize(p_bytes), ASN1_Type::OctetString)
         .encode(get_b().serialize(p_bytes), ASN1_Type::OctetString)
         .end_cons()
         .encode(get_base_point().encode(EC_Point_Format::Uncompressed), ASN1_Type::OctetString)
         .encode(get_order())
         .encode(get_cofactor())
         .end_cons();
      return output;
   } else if(form == EC_Group_Encoding::NamedCurve) {
      return this->DER_encode();
   } else if(form == EC_Group_Encoding::ImplicitCA) {
      return {0x00, 0x05};
   } else {
      throw Internal_Error("EC_Group::DER_encode: Unknown encoding");
   }
}

std::string EC_Group::PEM_encode() const {
   const std::vector<uint8_t> der = DER_encode(EC_Group_Encoding::Explicit);
   return PEM_Code::encode(der, "EC PARAMETERS");
}

bool EC_Group::operator==(const EC_Group& other) const {
   if(m_data == other.m_data) {
      return true;  // same shared rep
   }

   return (get_p() == other.get_p() && get_a() == other.get_a() && get_b() == other.get_b() &&
           get_g_x() == other.get_g_x() && get_g_y() == other.get_g_y() && get_order() == other.get_order() &&
           get_cofactor() == other.get_cofactor());
}

bool EC_Group::verify_public_element(const EC_Point& point) const {
   //check that public point is not at infinity
   if(point.is_zero()) {
      return false;
   }

   //check that public point is on the curve
   if(point.on_the_curve() == false) {
      return false;
   }

   //check that public point has order q
   if((point * get_order()).is_zero() == false) {
      return false;
   }

   if(has_cofactor()) {
      if((point * get_cofactor()).is_zero()) {
         return false;
      }
   }

   return true;
}

bool EC_Group::verify_group(RandomNumberGenerator& rng, bool strong) const {
   const bool is_builtin = source() == EC_Group_Source::Builtin;

   if(is_builtin && !strong) {
      return true;
   }

   const BigInt& p = get_p();
   const BigInt& a = get_a();
   const BigInt& b = get_b();
   const BigInt& order = get_order();
   const EC_Point& base_point = get_base_point();

   if(p <= 3 || order <= 0) {
      return false;
   }
   if(a < 0 || a >= p) {
      return false;
   }
   if(b <= 0 || b >= p) {
      return false;
   }

   const size_t test_prob = 128;
   const bool is_randomly_generated = is_builtin;

   //check if field modulus is prime
   if(!is_prime(p, rng, test_prob, is_randomly_generated)) {
      return false;
   }

   //check if order is prime
   if(!is_prime(order, rng, test_prob, is_randomly_generated)) {
      return false;
   }

   //compute the discriminant: 4*a^3 + 27*b^2 which must be nonzero
   const Modular_Reducer mod_p(p);

   const BigInt discriminant = mod_p.reduce(mod_p.multiply(4, mod_p.cube(a)) + mod_p.multiply(27, mod_p.square(b)));

   if(discriminant == 0) {
      return false;
   }

   //check for valid cofactor
   if(get_cofactor() < 1) {
      return false;
   }

   //check if the base point is on the curve
   if(!base_point.on_the_curve()) {
      return false;
   }
   if((base_point * get_cofactor()).is_zero()) {
      return false;
   }
   //check if order of the base point is correct
   if(!(base_point * order).is_zero()) {
      return false;
   }

   // check the Hasse bound (roughly)
   if((p - get_cofactor() * order).abs().bits() > (p.bits() / 2) + 1) {
      return false;
   }

   return true;
}

EC_Group::Mul2Table::Mul2Table(const EC_AffinePoint& h) : m_tbl(h._group()->make_mul2_table(h._inner())) {}

EC_Group::Mul2Table::~Mul2Table() = default;

std::optional<EC_AffinePoint> EC_Group::Mul2Table::mul2_vartime(const EC_Scalar& x, const EC_Scalar& y) const {
   auto pt = m_tbl->mul2_vartime(x._inner(), y._inner());
   if(pt) {
      return EC_AffinePoint::_from_inner(std::move(pt));
   } else {
      return {};
   }
}

bool EC_Group::Mul2Table::mul2_vartime_x_mod_order_eq(const EC_Scalar& v,
                                                      const EC_Scalar& x,
                                                      const EC_Scalar& y) const {
   return m_tbl->mul2_vartime_x_mod_order_eq(v._inner(), x._inner(), y._inner());
}

bool EC_Group::Mul2Table::mul2_vartime_x_mod_order_eq(const EC_Scalar& v,
                                                      const EC_Scalar& c,
                                                      const EC_Scalar& x,
                                                      const EC_Scalar& y) const {
   return this->mul2_vartime_x_mod_order_eq(v, c * x, c * y);
}

}  // namespace Botan

1	/*
2	* ECC Domain Parameters
3	*
4	* (C) 2007 Falko Strenzke, FlexSecure GmbH
5	* (C) 2008,2018,2024 Jack Lloyd
6	* (C) 2018 Tobias Niemann
7	*
8	* Botan is released under the Simplified BSD License (see license.txt)
9	*/
10
11	#include <botan/ec_group.h>
12
13	#include <botan/ber_dec.h>
14	#include <botan/der_enc.h>
15	#include <botan/mutex.h>
16	#include <botan/pem.h>
17	#include <botan/reducer.h>
18	#include <botan/rng.h>
19	#include <botan/internal/ec_inner_data.h>
20	#include <botan/internal/fmt.h>
21	#include <botan/internal/primality.h>
22	#include <vector>
23
24	namespace Botan {
25
26	class EC_Group_Data_Map final {
27	public:
28	EC_Group_Data_Map() = default;
29
30	size_t clear() {	1,769✔
31	lock_guard_type<mutex_type> lock(m_mutex);	1,769✔
32	size_t count = m_registered_curves.size();	1,769✔
33	m_registered_curves.clear();	1,769✔
34	return count;	1,769✔
35	}	1,769✔
36
37	std::shared_ptr<EC_Group_Data> lookup(const OID& oid) {	20,473✔
38	lock_guard_type<mutex_type> lock(m_mutex);	20,473✔
39
40	for(auto i : m_registered_curves) {	160,244✔
41	if(i->oid() == oid) {	159,050✔
42	return i;	19,279✔
43	}
44	}	159,050✔
45
46	// Not found, check hardcoded data
47	std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid);	1,194✔
48
49	if(data) {	1,194✔
50	for(auto curve : m_registered_curves) {	2,273✔
51	if(curve->oid().empty() == true && curve->params_match(*data)) {	1,132✔
52	curve->set_oid(oid);	×
53	return curve;	×
54	}
55	}	1,132✔
56
57	m_registered_curves.push_back(data);	1,141✔
58	return data;	1,141✔
59	}
60
61	// Nope, unknown curve
62	return std::shared_ptr<EC_Group_Data>();	53✔
63	}	21,667✔
64
65	std::shared_ptr<EC_Group_Data> lookup_or_create(const BigInt& p,	97✔
66	const BigInt& a,
67	const BigInt& b,
68	const BigInt& g_x,
69	const BigInt& g_y,
70	const BigInt& order,
71	const BigInt& cofactor,
72	const OID& oid,
73	EC_Group_Source source) {
74	lock_guard_type<mutex_type> lock(m_mutex);	97✔
75
76	for(auto i : m_registered_curves) {	1,627✔
77	/*
78	* The params may be the same but you are trying to register under a
79	* different OID than the one we are using, so using a different
80	* group, since EC_Group's model assumes a single OID per group.
81	*/
82	if(!oid.empty() && !i->oid().empty() && i->oid() != oid) {	1,608✔
83	continue;	695✔
84	}
85
86	const bool same_oid = !oid.empty() && i->oid() == oid;	913✔
87	const bool same_params = i->params_match(p, a, b, g_x, g_y, order, cofactor);	913✔
88
89	/*
90	* If the params and OID are the same then we are done, just return
91	* the already registered curve obj.
92	*/
93	if(same_params && same_oid) {	913✔
94	return i;	33✔
95	}
96
97	/*
98	* If same params and the new OID is empty, then that's ok too
99	*/
100	if(same_params && oid.empty()) {	880✔
101	return i;	45✔
102	}
103
104	/*
105	* Check for someone trying to reuse an already in-use OID
106	*/
107	if(same_oid && !same_params) {	835✔
108	throw Invalid_Argument("Attempting to register a curve using OID " + oid.to_string() +	×
109	" but a distinct curve is already registered using that OID");	×
110	}
111
112	/*
113	* If the same curve was previously created without an OID but is now
114	* being registered again using an OID, save that OID.
115	*/
116	if(same_params && i->oid().empty() && !oid.empty()) {	835✔
117	i->set_oid(oid);	×
118	return i;	×
119	}
120	}	1,608✔
121
122	/*
123	Not found in current list, so we need to create a new entry
124
125	If an OID is set, try to look up relative our static tables to detect a duplicate
126	registration under an OID
127	*/
128
129	auto new_group = EC_Group_Data::create(p, a, b, g_x, g_y, order, cofactor, oid, source);	19✔
130
131	if(oid.has_value()) {	19✔
132	std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid);	7✔
133	if(data != nullptr && !new_group->params_match(*data)) {	7✔
134	throw Invalid_Argument("Attempting to register an EC group under OID of hardcoded group");	1✔
135	}
136	} else {	7✔
137	// Here try to use the order as a hint to look up the group id, to identify common groups
138	const OID oid_from_store = EC_Group::EC_group_identity_from_order(order);	12✔
139	if(oid_from_store.has_value()) {	12✔
140	std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid_from_store);	8✔
141
142	/*
143	If EC_group_identity_from_order returned an OID then looking up that OID
144	must always return a result.
145	*/
146	BOTAN_ASSERT_NOMSG(data != nullptr);	8✔
147
148	/*
149	It is possible (if unlikely) that someone is registering another group
150	that happens to have an order equal to that of a well known group -
151	so verify all values before assigning the OID.
152	*/
153	if(new_group->params_match(*data)) {	8✔
154	new_group->set_oid(oid_from_store);	6✔
155	}
156	}	8✔
157	}	12✔
158
159	m_registered_curves.push_back(new_group);	18✔
160	return new_group;	18✔
161	}	115✔
162
163	private:
164	mutex_type m_mutex;
165	std::vector<std::shared_ptr<EC_Group_Data>> m_registered_curves;
166	};
167
168	//static
169	EC_Group_Data_Map& EC_Group::ec_group_data() {	22,339✔
170	/*
171	* This exists purely to ensure the allocator is constructed before g_ec_data,
172	* which ensures that its destructor runs after ~g_ec_data is complete.
173	*/
174
175	static Allocator_Initializer g_init_allocator;	22,339✔
176	static EC_Group_Data_Map g_ec_data;	22,339✔
177	return g_ec_data;	22,339✔
178	}
179
180	//static
181	size_t EC_Group::clear_registered_curve_data() {	1,769✔
182	return ec_group_data().clear();	1,769✔
183	}
184
185	//static
186	std::shared_ptr<EC_Group_Data> EC_Group::load_EC_group_info(const char* p_str,	1,150✔
187	const char* a_str,
188	const char* b_str,
189	const char* g_x_str,
190	const char* g_y_str,
191	const char* order_str,
192	const OID& oid) {
193	const BigInt p(p_str);	1,150✔
194	const BigInt a(a_str);	1,150✔
195	const BigInt b(b_str);	1,150✔
196	const BigInt g_x(g_x_str);	1,150✔
197	const BigInt g_y(g_y_str);	1,150✔
198	const BigInt order(order_str);	1,150✔
199	const BigInt cofactor(1); // implicit	1,150✔
200
201	return EC_Group_Data::create(p, a, b, g_x, g_y, order, cofactor, oid, EC_Group_Source::Builtin);	1,150✔
202	}	8,050✔
203
204	//static
205	std::pair<std::shared_ptr<EC_Group_Data>, bool> EC_Group::BER_decode_EC_group(std::span<const uint8_t> bits,	5,251✔
206	EC_Group_Source source) {
207	BER_Decoder ber(bits);	5,251✔
208	BER_Object obj = ber.get_next_object();	5,251✔
209
210	if(obj.type() == ASN1_Type::ObjectId) {	5,243✔
211	OID oid;	4,911✔
212	BER_Decoder(bits).decode(oid);	5,006✔
213
214	auto data = ec_group_data().lookup(oid);	4,869✔
215	if(!data) {	4,869✔
216	throw Decoding_Error(fmt("Unknown namedCurve OID '{}'", oid.to_string()));	106✔
217	}
218
219	return std::make_pair(data, false);	4,816✔
220	}	4,964✔
221
222	if(obj.type() == ASN1_Type::Sequence) {	332✔
223	BigInt p, a, b, order, cofactor;	329✔
224	std::vector<uint8_t> base_pt;	329✔
225	std::vector<uint8_t> seed;	329✔
226
227	BER_Decoder(bits)	657✔
228	.start_sequence()	328✔
229	.decode_and_check<size_t>(1, "Unknown ECC param version code")	635✔
230	.start_sequence()	307✔
231	.decode_and_check(OID("1.2.840.10045.1.1"), "Only prime ECC fields supported")	614✔
232	.decode(p)	306✔
233	.end_cons()	306✔
234	.start_sequence()	580✔
235	.decode_octet_string_bigint(a)	306✔
236	.decode_octet_string_bigint(b)	305✔
237	.decode_optional_string(seed, ASN1_Type::BitString, ASN1_Type::BitString)	303✔
238	.end_cons()	303✔
239	.decode(base_pt, ASN1_Type::OctetString)	300✔
240	.decode(order)	293✔
241	.decode(cofactor)	292✔
242	.end_cons()	292✔
243	.verify_end();	291✔
244
245	if(p.bits() < 112 \|\| p.bits() > 521) {	291✔
246	throw Decoding_Error("ECC p parameter is invalid size");	132✔
247	}
248
249	if(p.is_negative() \|\| !is_bailie_psw_probable_prime(p)) {	159✔
250	throw Decoding_Error("ECC p parameter is not a prime");	34✔
251	}
252
253	if(a.is_negative() \|\| a >= p) {	250✔
254	throw Decoding_Error("Invalid ECC a parameter");	9✔
255	}
256
257	if(b <= 0 \|\| b >= p) {	232✔
258	throw Decoding_Error("Invalid ECC b parameter");	55✔
259	}
260
261	if(order <= 0 \|\| !is_bailie_psw_probable_prime(order)) {	61✔
262	throw Decoding_Error("Invalid ECC order parameter");	2✔
263	}
264
265	if(cofactor <= 0 \|\| cofactor >= 16) {	116✔
266	throw Decoding_Error("Invalid ECC cofactor parameter");	3✔
267	}
268
269	const auto [g_x, g_y] = Botan::OS2ECP(base_pt.data(), base_pt.size(), p, a, b);	56✔
270
271	auto data = ec_group_data().lookup_or_create(p, a, b, g_x, g_y, order, cofactor, OID(), source);	55✔
272	return std::make_pair(data, true);	55✔
273	}	2,303✔
274
275	if(obj.type() == ASN1_Type::Null) {	3✔
276	throw Decoding_Error("Cannot handle ImplicitCA ECC parameters");	1✔
277	} else {
278	throw Decoding_Error(fmt("Unexpected tag {} while decoding ECC domain params", asn1_tag_to_string(obj.type())));	4✔
279	}
280	}	5,251✔
281
282	EC_Group::EC_Group() = default;	15✔
283
284	EC_Group::~EC_Group() = default;	126,334✔
285
286	EC_Group::EC_Group(const EC_Group&) = default;	45,618✔
287
288	EC_Group& EC_Group::operator=(const EC_Group&) = default;	×
289
290	// Internal constructor
291	EC_Group::EC_Group(std::shared_ptr<EC_Group_Data>&& data) : m_data(std::move(data)) {}	15,548✔
292
293	//static
294	EC_Group EC_Group::from_OID(const OID& oid) {	69✔
295	auto data = ec_group_data().lookup(oid);	69✔
296
297	if(!data) {	69✔
298	throw Invalid_Argument(fmt("No EC_Group associated with OID '{}'", oid.to_string()));	×
299	}
300
301	return EC_Group(std::move(data));	69✔
302	}	69✔
303
304	//static
305	EC_Group EC_Group::from_name(std::string_view name) {	15,479✔
306	std::shared_ptr<EC_Group_Data> data;	15,479✔
307
308	if(auto oid = OID::from_name(name)) {	15,479✔
309	data = ec_group_data().lookup(oid.value());	30,958✔
310	}	×
311
312	if(!data) {	15,479✔
313	throw Invalid_Argument(fmt("Unknown EC_Group '{}'", name));	×
314	}
315
316	return EC_Group(std::move(data));	15,479✔
317	}	15,479✔
318
319	EC_Group::EC_Group(std::string_view str) {	61✔
320	if(str.empty()) {	61✔
321	return; // no initialization / uninitialized
322	}
323
324	try {	61✔
325	const OID oid = OID::from_string(str);	61✔
326	if(oid.has_value()) {	56✔
327	m_data = ec_group_data().lookup(oid);	56✔
328	}
329	} catch(...) {}	61✔
330
331	if(m_data == nullptr) {	61✔
332	if(str.size() > 30 && str.substr(0, 29) == "-----BEGIN EC PARAMETERS-----") {	5✔
333	// OK try it as PEM ...
334	const auto ber = PEM_Code::decode_check_label(str, "EC PARAMETERS");	5✔
335
336	auto data = BER_decode_EC_group(ber, EC_Group_Source::ExternalSource);	5✔
337	this->m_data = data.first;	5✔
338	this->m_explicit_encoding = data.second;	5✔
339	}	10✔
340	}
341
342	if(m_data == nullptr) {	61✔
343	throw Invalid_Argument(fmt("Unknown ECC group '{}'", str));	×
344	}
345	}	×
346
347	//static
348	EC_Group EC_Group::from_PEM(std::string_view pem) {	1✔
349	const auto ber = PEM_Code::decode_check_label(pem, "EC PARAMETERS");	1✔
350	return EC_Group(ber);	1✔
351	}	1✔
352
353	EC_Group::EC_Group(const BigInt& p,	4✔
354	const BigInt& a,
355	const BigInt& b,
356	const BigInt& base_x,
357	const BigInt& base_y,
358	const BigInt& order,
359	const BigInt& cofactor,
360	const OID& oid) {	4✔
361	m_data =	4✔
362	ec_group_data().lookup_or_create(p, a, b, base_x, base_y, order, cofactor, oid, EC_Group_Source::ExternalSource);	4✔
363	}	4✔
364
365	EC_Group::EC_Group(const OID& oid,	46✔
366	const BigInt& p,
367	const BigInt& a,
368	const BigInt& b,
369	const BigInt& base_x,
370	const BigInt& base_y,
371	const BigInt& order) {	46✔
372	BOTAN_ARG_CHECK(oid.has_value(), "An OID is required for creating an EC_Group");	46✔
373	BOTAN_ARG_CHECK(p.bits() >= 128, "EC_Group p too small");	46✔
374	BOTAN_ARG_CHECK(p.bits() <= 521, "EC_Group p too large");	46✔
375
376	if(p.bits() == 521) {	46✔
377	BOTAN_ARG_CHECK(p == BigInt::power_of_2(521) - 1, "EC_Group with p of 521 bits must be 2**521-1");	4✔
378	} else {
379	BOTAN_ARG_CHECK(p.bits() % 32 == 0, "EC_Group p must be a multiple of 32 bits");	45✔
380	}
381
382	BOTAN_ARG_CHECK(p % 4 == 3, "EC_Group p must be congruent to 3 modulo 4");	43✔
383
384	BOTAN_ARG_CHECK(a >= 0 && a < p, "EC_Group a is invalid");	82✔
385	BOTAN_ARG_CHECK(b > 0 && b < p, "EC_Group b is invalid");	82✔
386	BOTAN_ARG_CHECK(base_x >= 0 && base_x < p, "EC_Group base_x is invalid");	82✔
387	BOTAN_ARG_CHECK(base_y >= 0 && base_y < p, "EC_Group base_y is invalid");	82✔
388	BOTAN_ARG_CHECK(p.bits() == order.bits(), "EC_Group p and order must have the same number of bits");	41✔
389
390	BOTAN_ARG_CHECK(is_bailie_psw_probable_prime(p), "EC_Group p is not prime");	38✔
391	BOTAN_ARG_CHECK(is_bailie_psw_probable_prime(order), "EC_Group order is not prime");	38✔
392
393	// This catches someone "ignoring" a cofactor and just trying to
394	// provide the subgroup order
395	BOTAN_ARG_CHECK((p - order).abs().bits() <= (p.bits() / 2) + 1, "Hasse bound invalid");	114✔
396
397	BigInt cofactor(1);	38✔
398
399	m_data =	38✔
400	ec_group_data().lookup_or_create(p, a, b, base_x, base_y, order, cofactor, oid, EC_Group_Source::ExternalSource);	38✔
401	}	46✔
402
403	EC_Group::EC_Group(std::span<const uint8_t> ber) {	5,246✔
404	auto data = BER_decode_EC_group(ber, EC_Group_Source::ExternalSource);	5,246✔
405	m_data = data.first;	4,866✔
406	m_explicit_encoding = data.second;	4,866✔
407	}	5,246✔
408
409	const EC_Group_Data& EC_Group::data() const {	98,492✔
410	if(m_data == nullptr) {	98,492✔
411	throw Invalid_State("EC_Group uninitialized");	×
412	}
413	return *m_data;	98,492✔
414	}
415
416	size_t EC_Group::get_p_bits() const {	1,278✔
417	return data().p_bits();	1,278✔
418	}
419
420	size_t EC_Group::get_p_bytes() const {	12,814✔
421	return data().p_bytes();	12,814✔
422	}
423
424	size_t EC_Group::get_order_bits() const {	1,145✔
425	return data().order_bits();	1,145✔
426	}
427
428	size_t EC_Group::get_order_bytes() const {	17,077✔
429	return data().order_bytes();	17,077✔
430	}
431
432	const BigInt& EC_Group::get_p() const {	25,361✔
433	return data().p();	25,361✔
434	}
435
436	const BigInt& EC_Group::get_a() const {	717✔
437	return data().a();	717✔
438	}
439
440	const BigInt& EC_Group::get_b() const {	605✔
441	return data().b();	605✔
442	}
443
444	const EC_Point& EC_Group::get_base_point() const {	717✔
445	return data().base_point();	717✔
446	}
447
448	const EC_Point& EC_Group::generator() const {	×
449	return data().base_point();	×
450	}
451
452	const BigInt& EC_Group::get_order() const {	840✔
453	return data().order();	840✔
454	}
455
456	const BigInt& EC_Group::get_g_x() const {	57✔
457	return data().g_x();	57✔
458	}
459
460	const BigInt& EC_Group::get_g_y() const {	57✔
461	return data().g_y();	57✔
462	}
463
464	const BigInt& EC_Group::get_cofactor() const {	244✔
465	return data().cofactor();	244✔
466	}
467
468	bool EC_Group::has_cofactor() const {	11,875✔
469	return data().has_cofactor();	11,875✔
470	}
471
472	BigInt EC_Group::mod_order(const BigInt& k) const {	1,093✔
473	return data().mod_order(k);	1,093✔
474	}
475
476	const OID& EC_Group::get_curve_oid() const {	23,157✔
477	return data().oid();	23,157✔
478	}
479
480	EC_Group_Source EC_Group::source() const {	134✔
481	return data().source();	134✔
482	}
483
484	std::vector<uint8_t> EC_Group::DER_encode() const {	1,321✔
485	const auto& der_named_curve = data().der_named_curve();	1,321✔
486	// TODO(Botan4) this can be removed because an OID will always be defined
487	if(der_named_curve.empty()) {	1,321✔
488	throw Encoding_Error("Cannot encode EC_Group as OID because OID not set");	×
489	}
490
491	return der_named_curve;	1,321✔
492	}
493
494	std::vector<uint8_t> EC_Group::DER_encode(EC_Group_Encoding form) const {	1,263✔
495	if(form == EC_Group_Encoding::Explicit) {	1,263✔
496	std::vector<uint8_t> output;	31✔
497	DER_Encoder der(output);	31✔
498	const size_t ecpVers1 = 1;	31✔
499	const OID curve_type("1.2.840.10045.1.1"); // prime field	31✔
500
501	const size_t p_bytes = get_p_bytes();	31✔
502
503	der.start_sequence()	31✔
504	.encode(ecpVers1)	31✔
505	.start_sequence()	31✔
506	.encode(curve_type)	31✔
507	.encode(get_p())	31✔
508	.end_cons()	31✔
509	.start_sequence()	31✔
510	.encode(get_a().serialize(p_bytes), ASN1_Type::OctetString)	31✔
511	.encode(get_b().serialize(p_bytes), ASN1_Type::OctetString)	62✔
512	.end_cons()	31✔
513	.encode(get_base_point().encode(EC_Point_Format::Uncompressed), ASN1_Type::OctetString)	62✔
514	.encode(get_order())	31✔
515	.encode(get_cofactor())	31✔
516	.end_cons();	31✔
517	return output;	31✔
518	} else if(form == EC_Group_Encoding::NamedCurve) {	1,263✔
519	return this->DER_encode();	1,232✔
520	} else if(form == EC_Group_Encoding::ImplicitCA) {	×
521	return {0x00, 0x05};	×
522	} else {
523	throw Internal_Error("EC_Group::DER_encode: Unknown encoding");	×
524	}
525	}
526
527	std::string EC_Group::PEM_encode() const {	1✔
528	const std::vector<uint8_t> der = DER_encode(EC_Group_Encoding::Explicit);	1✔
529	return PEM_Code::encode(der, "EC PARAMETERS");	1✔
530	}	1✔
531
532	bool EC_Group::operator==(const EC_Group& other) const {	48✔
533	if(m_data == other.m_data) {	48✔
534	return true; // same shared rep
535	}
536
537	return (get_p() == other.get_p() && get_a() == other.get_a() && get_b() == other.get_b() &&	×
538	get_g_x() == other.get_g_x() && get_g_y() == other.get_g_y() && get_order() == other.get_order() &&	×
539	get_cofactor() == other.get_cofactor());	×
540	}
541
542	bool EC_Group::verify_public_element(const EC_Point& point) const {	106✔
543	//check that public point is not at infinity
544	if(point.is_zero()) {	106✔
545	return false;
546	}
547
548	//check that public point is on the curve
549	if(point.on_the_curve() == false) {	106✔
550	return false;
551	}
552
553	//check that public point has order q
554	if((point * get_order()).is_zero() == false) {	106✔
555	return false;
556	}
557
558	if(has_cofactor()) {	106✔
559	if((point * get_cofactor()).is_zero()) {	×
560	return false;
561	}
562	}
563
564	return true;
565	}
566
567	bool EC_Group::verify_group(RandomNumberGenerator& rng, bool strong) const {	134✔
568	const bool is_builtin = source() == EC_Group_Source::Builtin;	134✔
569
570	if(is_builtin && !strong) {	134✔
571	return true;
572	}
573
574	const BigInt& p = get_p();	28✔
575	const BigInt& a = get_a();	28✔
576	const BigInt& b = get_b();	28✔
577	const BigInt& order = get_order();	28✔
578	const EC_Point& base_point = get_base_point();	28✔
579
580	if(p <= 3 \|\| order <= 0) {	56✔
581	return false;	×
582	}
583	if(a < 0 \|\| a >= p) {	56✔
584	return false;	×
585	}
586	if(b <= 0 \|\| b >= p) {	56✔
587	return false;	×
588	}
589
590	const size_t test_prob = 128;	28✔
591	const bool is_randomly_generated = is_builtin;	28✔
592
593	//check if field modulus is prime
594	if(!is_prime(p, rng, test_prob, is_randomly_generated)) {	28✔
595	return false;
596	}
597
598	//check if order is prime
599	if(!is_prime(order, rng, test_prob, is_randomly_generated)) {	28✔
600	return false;
601	}
602
603	//compute the discriminant: 4a^3 + 27b^2 which must be nonzero
604	const Modular_Reducer mod_p(p);	28✔
605
606	const BigInt discriminant = mod_p.reduce(mod_p.multiply(4, mod_p.cube(a)) + mod_p.multiply(27, mod_p.square(b)));	196✔
607
608	if(discriminant == 0) {	28✔
609	return false;
610	}
611
612	//check for valid cofactor
613	if(get_cofactor() < 1) {	28✔
614	return false;
615	}
616
617	//check if the base point is on the curve
618	if(!base_point.on_the_curve()) {	28✔
619	return false;
620	}
621	if((base_point * get_cofactor()).is_zero()) {	56✔
622	return false;
623	}
624	//check if order of the base point is correct
625	if(!(base_point * order).is_zero()) {	28✔
626	return false;
627	}
628
629	// check the Hasse bound (roughly)
630	if((p - get_cofactor() * order).abs().bits() > (p.bits() / 2) + 1) {	112✔
631	return false;
632	}
633
634	return true;
635	}	28✔
636
637	EC_Group::Mul2Table::Mul2Table(const EC_AffinePoint& h) : m_tbl(h._group()->make_mul2_table(h._inner())) {}	11,458✔
638
639	EC_Group::Mul2Table::~Mul2Table() = default;	11,458✔
640
641	std::optional<EC_AffinePoint> EC_Group::Mul2Table::mul2_vartime(const EC_Scalar& x, const EC_Scalar& y) const {	333✔
642	auto pt = m_tbl->mul2_vartime(x._inner(), y._inner());	333✔
643	if(pt) {	333✔
644	return EC_AffinePoint::_from_inner(std::move(pt));	666✔
645	} else {
646	return {};	×
647	}
648	}	333✔
649
650	bool EC_Group::Mul2Table::mul2_vartime_x_mod_order_eq(const EC_Scalar& v,	22,988✔
651	const EC_Scalar& x,
652	const EC_Scalar& y) const {
653	return m_tbl->mul2_vartime_x_mod_order_eq(v._inner(), x._inner(), y._inner());	22,988✔
654	}
655
656	bool EC_Group::Mul2Table::mul2_vartime_x_mod_order_eq(const EC_Scalar& v,	22,816✔
657	const EC_Scalar& c,
658	const EC_Scalar& x,
659	const EC_Scalar& y) const {
660	return this->mul2_vartime_x_mod_order_eq(v, c * x, c * y);	22,816✔
661	}
662
663	} // namespace Botan

randombit / botan / 11972552403

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous