Repository: tlsfuzzer/python-ecdsa

Issue:
Some high "s" values in ECDSA signature not detected due to error in floating point arithmetic
In the functions such as  [sigencode_strings_canonize](https://github.com/tlsfuzzer/python-ecdsa/blob/ea9666903c109a8e88a37eb1c60d4e98f01f0299/src/ecdsa/util.py#L329), [sigencode_string_canonize](https://github.com/tlsfuzzer/python-ecdsa/blob/ea9666903c109a8e88a37eb1c60d4e98f01f0299/src/ecdsa/util.py#L353), and [sigencode_der_canonize](https://github.com/tlsfuzzer/python-ecdsa/blob/ea9666903c109a8e88a37eb1c60d4e98f01f0299/src/ecdsa/util.py#L384)
where canonicalization of the "s" value in an ECDSA signature is performed with the code :

```
if s > order / 2:
	s = order - s
```
which uses the Python 3 "true division" operator `/` producing a floating point type irrespective of the type of the operands (eg. as described in [1] p146), high "s" values in at least the range `[N // 2 + 1, N // 2 + 2**127]` are not detected, where `//` is the Python 3 "floor division" operator which discards the remainder and performs exact integer arithmetic for integer operands of arbitrary size (eg. see [1] p135)). (`N` = order of the elliptic curve).

This is because the exact value of `N / 2`, which should be `N // 2 + 0.5`, is considerably larger than this due to the floating point error:

```
>>> N/2 > N//2 + 2**127
True
>>> N/2 > N//2 + 2**128
False
```
(testing with Python interpreter v3.8.10).

In the test below in Python interpreter v3.8.10 we can see how `s = (N // 2) + 2**127` is not detected as high, whereas `s = (N // 2) + 2**128` is detected as high :

```
N = order of secp256k1 generator point G =
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

N // 2 = 
7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0        (exact)

>>> N / 2
5.78960446186581e+76            (approximate)

>>> s = (N // 2) + 2**127
>>> s > N / 2
False

>>> s = (N // 2) + 2**128
>>> s > N / 2
True
```

The fix is to simply use the exact integer floor division operator `//` instead of `/` :

```
if s > order // 2:
	s = order - s
```

and this will detect any s from the "midpoint" of odd prime `N` upwards, ie. the "high" values of s.

This problem is also discussed in [this question](https://bitcoin.stackexchange.com/q/125459/117559) on Bitcoin Stack Exchange.


[1] Mark Lutz (2013), Learning Python 5th Edition, O'Reilly



Discussion hints:

Solution patch:
diff --git a/src/ecdsa/util.py b/src/ecdsa/util.py
index 639bc0c..1aff5bf 100644
--- a/src/ecdsa/util.py
+++ b/src/ecdsa/util.py
@@ -304,6 +304,23 @@ def sigencode_der(r, s, order):
     return der.encode_sequence(der.encode_integer(r), der.encode_integer(s))
 
 
+def _canonize(s, order):
+    """
+    Internal function for ensuring that the ``s`` value of a signature is in
+    the "canonical" format.
+
+    :param int s: the second parameter of ECDSA signature
+    :param int order: the order of the curve over which the signatures was
+        computed
+
+    :return: canonical value of s
+    :rtype: int
+    """
+    if s > order // 2:
+        s = order - s
+    return s
+
+
 def sigencode_strings_canonize(r, s, order):
     """
     Encode the signature to a pair of strings in a tuple
@@ -326,8 +343,7 @@ def sigencode_strings_canonize(r, s, order):
     :return: raw encoding of ECDSA signature
     :rtype: tuple(bytes, bytes)
     """
-    if s > order / 2:
-        s = order - s
+    s = _canonize(s, order)
     return sigencode_strings(r, s, order)
 
 
@@ -350,8 +366,7 @@ def sigencode_string_canonize(r, s, order):
     :return: raw encoding of ECDSA signature
     :rtype: bytes
     """
-    if s > order / 2:
-        s = order - s
+    s = _canonize(s, order)
     return sigencode_string(r, s, order)
 
 
@@ -381,8 +396,7 @@ def sigencode_der_canonize(r, s, order):
     :return: DER encoding of ECDSA signature
     :rtype: bytes
     """
-    if s > order / 2:
-        s = order - s
+    s = _canonize(s, order)
     return sigencode_der(r, s, order)
 
 


Test patch:
diff --git a/src/ecdsa/test_pyecdsa.py b/src/ecdsa/test_pyecdsa.py
index 4187895..799e9b7 100644
--- a/src/ecdsa/test_pyecdsa.py
+++ b/src/ecdsa/test_pyecdsa.py
@@ -520,6 +520,23 @@ class ECDSA(unittest.TestCase):
         self.assertEqual(r, new_r)
         self.assertEqual(order - s, new_s)
 
+    def test_sigencode_der_canonize_with_close_to_half_order(self):
+        r = 13
+        order = SECP112r1.order
+        s = order // 2 + 1
+
+        regular_encode = sigencode_der(r, s, order)
+        canonical_encode = sigencode_der_canonize(r, s, order)
+
+        self.assertNotEqual(regular_encode, canonical_encode)
+
+        new_r, new_s = sigdecode_der(
+            sigencode_der_canonize(r, s, order), order
+        )
+
+        self.assertEqual(r, new_r)
+        self.assertEqual(order - s, new_s)
+
     def test_sig_decode_strings_with_invalid_count(self):
         with self.assertRaises(MalformedSignature):
             sigdecode_strings([b"one", b"two", b"three"], 0xFF)