Also switch the (unused) verification code to low-s instead of even-s.

a81cd968 introduced a malleability breaker for signatures
(using an even value for S). In e0e14e43 this was changed to
the lower of two potential values, rather than the even one.
Only the signing code was changed though, the (for now unused)
verification code wasn't adapted.

5 files changed, 78 insertions, 25 deletions

diff --git a/src/key.cpp b/src/key.cpp
index b57b7c506c..2199996cf3 100644
--- a/src/key.cpp
+++ b/src/key.cpp
@@ -332,30 +332,60 @@ public:
     }
 };
 
+int CompareBigEndian(const unsigned char *c1, size_t c1len, const unsigned char *c2, size_t c2len) {
+    while (c1len > c2len) {
+        if (*c1)
+            return 1;
+        c1++;
+        c1len--;
+    }
+    while (c2len > c1len) {
+        if (*c2)
+            return -1;
+        c2++;
+        c2len--;
+    }
+    while (c1len > 0) {
+        if (*c1 > *c2)
+            return 1;
+        if (*c2 > *c1)
+            return -1;
+        c1++;
+        c2++;
+        c1len--;
+    }
+    return 0;
+}
+
+// Order of secp256k1's generator minus 1.
+const unsigned char vchMaxModOrder[32] = {
+    0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
+    0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
+    0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
+    0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x40
+};
+
+// Half of the order of secp256k1's generator minus 1.
+const unsigned char vchMaxModHalfOrder[32] = {
+    0x7F,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
+    0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
+    0x5D,0x57,0x6E,0x73,0x57,0xA4,0x50,0x1D,
+    0xDF,0xE9,0x2F,0x46,0x68,0x1B,0x20,0xA0
+};
+
+const unsigned char vchZero[0] = {};
+
+
 }; // end of anonymous namespace
 
 bool CKey::Check(const unsigned char *vch) {
-    // Do not convert to OpenSSL's data structures for range-checking keys,
-    // it's easy enough to do directly.
-    static const unsigned char vchMax[32] = {
-        0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
-        0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
-        0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
-        0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x40
-    };
-    bool fIsZero = true;
-    for (int i=0; i<32 && fIsZero; i++)
-        if (vch[i] != 0)
-            fIsZero = false;
-    if (fIsZero)
-        return false;
-    for (int i=0; i<32; i++) {
-        if (vch[i] < vchMax[i])
-            return true;
-        if (vch[i] > vchMax[i])
-            return false;
-    }
-    return true;
+    return CompareBigEndian(vch, 32, vchZero, 0) > 0 &&
+           CompareBigEndian(vch, 32, vchMaxModOrder, 32) <= 0;
+}
+
+bool CKey::CheckSignatureElement(const unsigned char *vch, int len, bool half) {
+    return CompareBigEndian(vch, len, vchZero, 0) > 0 &&
+           CompareBigEndian(vch, len, half ? vchMaxModHalfOrder : vchMaxModOrder, 32) <= 0;
 }
 
 void CKey::MakeNewKey(bool fCompressedIn) {
diff --git a/src/key.h b/src/key.h
index cf1165d3d0..37a06810b4 100644
--- a/src/key.h
+++ b/src/key.h
@@ -269,6 +269,9 @@ public:
 
     // Load private key and check that public key matches.
     bool Load(CPrivKey &privkey, CPubKey &vchPubKey, bool fSkipCheck);
+
+    // Check whether an element of a signature (r or s) is valid.
+    static bool CheckSignatureElement(const unsigned char *vch, int len, bool half);
 };
 
 struct CExtPubKey {
diff --git a/src/script.cpp b/src/script.cpp
index 810ba16d28..84a2a629e8 100644
--- a/src/script.cpp
+++ b/src/script.cpp
@@ -296,9 +296,12 @@ bool IsCanonicalSignature(const valtype &vchSig, unsigned int flags) {
     if (nLenS > 1 && (S[0] == 0x00) && !(S[1] & 0x80))
         return error("Non-canonical signature: S value excessively padded");
 
-    if (flags & SCRIPT_VERIFY_EVEN_S) {
-        if (S[nLenS-1] & 1)
-            return error("Non-canonical signature: S value odd");
+    if (flags & SCRIPT_VERIFY_LOW_S) {
+        // If the S value is above the order of the curve divided by two, its
+        // complement modulo the order could have been used instead, which is
+        // one byte shorter when encoded correctly.
+        if (!CKey::CheckSignatureElement(S, nLenS, true))
+            return error("Non-canonical signature: S value is unnecessarily high");
     }
 
     return true;
diff --git a/src/script.h b/src/script.h
index 657ac0b388..b96bbc45c3 100644
--- a/src/script.h
+++ b/src/script.h
@@ -40,7 +40,7 @@ enum
     SCRIPT_VERIFY_NONE      = 0,
     SCRIPT_VERIFY_P2SH      = (1U << 0), // evaluate P2SH (BIP16) subscripts
     SCRIPT_VERIFY_STRICTENC = (1U << 1), // enforce strict conformance to DER and SEC2 for signatures and pubkeys
-    SCRIPT_VERIFY_EVEN_S    = (1U << 2), // enforce even S values in signatures (depends on STRICTENC)
+    SCRIPT_VERIFY_LOW_S     = (1U << 2), // enforce low S values (<n/2) in signatures (depends on STRICTENC)
     SCRIPT_VERIFY_NOCACHE   = (1U << 3), // do not store results in signature cache (but do query it)
 };
 
diff --git a/src/test/canonical_tests.cpp b/src/test/canonical_tests.cpp
index c521f2cf9c..c38d9db57a 100644
--- a/src/test/canonical_tests.cpp
+++ b/src/test/canonical_tests.cpp
@@ -89,4 +89,21 @@ BOOST_AUTO_TEST_CASE(script_noncanon)
     }
 }
 
+BOOST_AUTO_TEST_CASE(script_signstrict)
+{
+    for (int i=0; i<100; i++) {
+        CKey key;
+        key.MakeNewKey(i & 1);
+        std::vector<unsigned char> sig;
+        uint256 hash = GetRandHash();
+
+        BOOST_CHECK(key.Sign(hash, sig)); // Generate a random signature.
+        BOOST_CHECK(key.GetPubKey().Verify(hash, sig)); // Check it.
+        sig.push_back(0x01); // Append a sighash type.
+
+        BOOST_CHECK(IsCanonicalSignature(sig, SCRIPT_VERIFY_STRICTENC | SCRIPT_VERIFY_LOW_S));
+        BOOST_CHECK(IsCanonicalSignature_OpenSSL(sig));
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()