Repository: randombit/botan (cpp)

Issue:
PointGFp_Multi_Point_Precompute gives wrong result when an infinity point occurs in the precomputation
We were recently contacted by @guidovranken, who alerted us that our signature verification function in https://github.com/trezor/trezor-firmware/tree/master/crypto accepts the following signature as valid whereas Botan does not:

```
ecc curve: secp256k1
public key X: 55066263022277343669578718895168534326250603453777594175500187360389116729240
public key Y: 83121579216557378445487899878180864668798711284981320763518679672151497189239
msg_digest: {0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11} (32 bytes)
signature R: 110618813224107091100351766566588261013518646361399424304146461958647130377927
signature S: 56528019055117870811188539769759161932852696818058491284544029456598522370972
```

I believe that the signature is valid and the bug is in Botan's `PointGFp_Multi_Point_Precompute` class. What's special about the given example is that the public key is -G (the negation of the base point). So when you use `PointGFp_Multi_Point_Precompute` in the `ECDSA_Verification_Operation` class, the input to its constructor is G and -G. Thus the precomputation of the 15 values for Shamir's trick results in several infinity points. However, the class does not take this possibility into account because it's written to work with the affine point representation. When you call `PointGFp::force_all_affine()` on these points in the constructor, the function finishes without throwing any exceptions, but all the precomputed points are now zeroed. As a result, when you compute the value of `R` in `ECDSA_Verification_Operation::verify()`, it comes out to be the infinity point and signature validation inevitably fails.

At the very least this scenario should result in an exception being thrown by `PointGFp::force_all_affine()`, just like `PointGFp::force_affine()` does. But to be fair, -G is a valid public key, so `PointGFp_Multi_Point_Precompute` should be fixed to accommodate this scenario.

Pull request:
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

Patch:
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;
    };
 
 }


Test patch:
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