aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJack Lloyd <[email protected]>2020-10-20 19:17:28 -0400
committerJack Lloyd <[email protected]>2020-10-20 19:17:28 -0400
commit54ccb865195aeecd40d6081dca0dab157b9f8fa5 (patch)
tree1b2a52a81097bdbe92136a56f831d9b9f31103a6
parentf33f00e5d0add6b17c3a51407720710a58bacd0b (diff)
Fix ECC multiexponentiation when two points are related
If the points are related by x = -{1,2,3}y then an infinity was silently produced, causing validation failures. Fixes #2424
-rw-r--r--src/lib/pubkey/ec_group/point_gfp.cpp6
-rw-r--r--src/lib/pubkey/ec_group/point_mul.cpp20
-rw-r--r--src/lib/pubkey/ec_group/point_mul.h1
-rw-r--r--src/tests/data/pubkey/ecdsa_verify.vec8
4 files changed, 33 insertions, 2 deletions
diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp
index c78763829..6c2302bd6 100644
--- a/src/lib/pubkey/ec_group/point_gfp.cpp
+++ b/src/lib/pubkey/ec_group/point_gfp.cpp
@@ -427,6 +427,12 @@ void PointGFp::force_all_affine(std::vector<PointGFp>& points,
return;
}
+ for(size_t i = 0; i != points.size(); ++i)
+ {
+ if(points[i].is_zero())
+ throw Invalid_State("Cannot convert zero ECC point to affine");
+ }
+
/*
For >= 2 points use Montgomery's trick
diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp
index d4a0b6ee6..2dff959d7 100644
--- a/src/lib/pubkey/ec_group/point_mul.cpp
+++ b/src/lib/pubkey/ec_group/point_mul.cpp
@@ -9,6 +9,7 @@
#include <botan/reducer.h>
#include <botan/internal/rounding.h>
#include <botan/internal/ct_utils.h>
+#include <iostream>
namespace Botan {
@@ -375,7 +376,19 @@ PointGFp_Multi_Point_Precompute::PointGFp_Multi_Point_Precompute(const PointGFp&
m_M.push_back(y3.plus(x2, ws));
m_M.push_back(y3.plus(x3, ws));
- PointGFp::force_all_affine(m_M, ws[0].get_word_vector());
+ bool no_infinity = true;
+ for(auto& pt : m_M)
+ {
+ if(pt.is_zero())
+ no_infinity = false;
+ }
+
+ if(no_infinity)
+ {
+ PointGFp::force_all_affine(m_M, ws[0].get_word_vector());
+ }
+
+ m_no_infinity = no_infinity;
}
PointGFp PointGFp_Multi_Point_Precompute::multi_exp(const BigInt& z1,
@@ -402,7 +415,10 @@ PointGFp PointGFp_Multi_Point_Precompute::multi_exp(const BigInt& z1,
// This function is not intended to be const time
if(z12)
{
- H.add_affine(m_M[z12-1], ws);
+ if(m_no_infinity)
+ H.add_affine(m_M[z12-1], ws);
+ else
+ H.add(m_M[z12-1], ws);
}
}
diff --git a/src/lib/pubkey/ec_group/point_mul.h b/src/lib/pubkey/ec_group/point_mul.h
index d503f4bee..095620428 100644
--- a/src/lib/pubkey/ec_group/point_mul.h
+++ b/src/lib/pubkey/ec_group/point_mul.h
@@ -77,6 +77,7 @@ class PointGFp_Multi_Point_Precompute final
const BigInt& k2) const;
private:
std::vector<PointGFp> m_M;
+ bool m_no_infinity;
};
}
diff --git a/src/tests/data/pubkey/ecdsa_verify.vec b/src/tests/data/pubkey/ecdsa_verify.vec
index 2bdf3299b..df3b2a41c 100644
--- a/src/tests/data/pubkey/ecdsa_verify.vec
+++ b/src/tests/data/pubkey/ecdsa_verify.vec
@@ -54,3 +54,11 @@ Px = 0x6564C83962A17949120C5E0E65290527A02CC7B635A829B33C083A09AAF67A12
Py = 0xBFECD7CD5956512DF2A051356B2DF592D93C739128828405E1F37F84B7E27CF9
Msg = 04FEFDFCFBFAF9F8F7F6F5F4F3F2F1F0EFEEEDECEBEAE9E8E7E6E5E4E3E2E1E0DFDEDDDCDBDAD9D8
Signature = 264A27F175848F0A110B2E7B03886B94777FB5ECBE2E8CD674AE196A6C80D8FFC8B5C6C00EACB1C76A3BAD03F8FFD4B58784BF35E104E721FF8F3F81AC9E6E91
+
+# https://github.com/randombit/botan/issues/2424
+
+Group = secp256k1
+Px = 55066263022277343669578718895168534326250603453777594175500187360389116729240
+Py = 83121579216557378445487899878180864668798711284981320763518679672151497189239
+Msg = 1111111111111111111111111111111111111111111111111111111111111111
+Signature = f490078fed0f0ca058fba78375f0e42678b25242238a664d4ed6784f7c284ec77cf9b997a778f8fe101f480d3c75cde95c5d712935fa5b9a4edf8e6654379b9c