crypto/secp256k1: update to github.com/bitcoin-core/secp256k1 @ 9d560f9 (#3544)

- Use defined constants instead of hard-coding their integer value.
- Allocate secp256k1 structs on the C stack instead of converting []byte
- Remove dead code

1 files changed, 131 insertions, 80 deletions

diff --git a/crypto/secp256k1/libsecp256k1/src/ecdsa_impl.h b/crypto/secp256k1/libsecp256k1/src/ecdsa_impl.h
index 4a172b3c5..453bb1188 100644
--- a/crypto/secp256k1/libsecp256k1/src/ecdsa_impl.h
+++ b/crypto/secp256k1/libsecp256k1/src/ecdsa_impl.h
@@ -1,5 +1,5 @@
 /**********************************************************************
- * Copyright (c) 2013, 2014 Pieter Wuille                               *
+ * Copyright (c) 2013-2015 Pieter Wuille                              *
  * Distributed under the MIT software license, see the accompanying   *
  * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
  **********************************************************************/
@@ -46,66 +46,133 @@ static const secp256k1_fe secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CON
     0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL
 );
 
-static int secp256k1_ecdsa_sig_parse(secp256k1_scalar *rr, secp256k1_scalar *rs, const unsigned char *sig, size_t size) {
-    unsigned char ra[32] = {0}, sa[32] = {0};
-    const unsigned char *rp;
-    const unsigned char *sp;
-    size_t lenr;
-    size_t lens;
-    int overflow;
-    if (sig[0] != 0x30) {
-        return 0;
+static int secp256k1_der_read_len(const unsigned char **sigp, const unsigned char *sigend) {
+    int lenleft, b1;
+    size_t ret = 0;
+    if (*sigp >= sigend) {
+        return -1;
     }
-    lenr = sig[3];
-    if (5+lenr >= size) {
-        return 0;
+    b1 = *((*sigp)++);
+    if (b1 == 0xFF) {
+        /* X.690-0207 8.1.3.5.c the value 0xFF shall not be used. */
+        return -1;
     }
-    lens = sig[lenr+5];
-    if (sig[1] != lenr+lens+4) {
-        return 0;
+    if ((b1 & 0x80) == 0) {
+        /* X.690-0207 8.1.3.4 short form length octets */
+        return b1;
     }
-    if (lenr+lens+6 > size) {
-        return 0;
+    if (b1 == 0x80) {
+        /* Indefinite length is not allowed in DER. */
+        return -1;
+    }
+    /* X.690-207 8.1.3.5 long form length octets */
+    lenleft = b1 & 0x7F;
+    if (lenleft > sigend - *sigp) {
+        return -1;
+    }
+    if (**sigp == 0) {
+        /* Not the shortest possible length encoding. */
+        return -1;
     }
-    if (sig[2] != 0x02) {
+    if ((size_t)lenleft > sizeof(size_t)) {
+        /* The resulting length would exceed the range of a size_t, so
+         * certainly longer than the passed array size.
+         */
+        return -1;
+    }
+    while (lenleft > 0) {
+        if ((ret >> ((sizeof(size_t) - 1) * 8)) != 0) {
+        }
+        ret = (ret << 8) | **sigp;
+        if (ret + lenleft > (size_t)(sigend - *sigp)) {
+            /* Result exceeds the length of the passed array. */
+            return -1;
+        }
+        (*sigp)++;
+        lenleft--;
+    }
+    if (ret < 128) {
+        /* Not the shortest possible length encoding. */
+        return -1;
+    }
+    return ret;
+}
+
+static int secp256k1_der_parse_integer(secp256k1_scalar *r, const unsigned char **sig, const unsigned char *sigend) {
+    int overflow = 0;
+    unsigned char ra[32] = {0};
+    int rlen;
+
+    if (*sig == sigend || **sig != 0x02) {
+        /* Not a primitive integer (X.690-0207 8.3.1). */
         return 0;
     }
-    if (lenr == 0) {
+    (*sig)++;
+    rlen = secp256k1_der_read_len(sig, sigend);
+    if (rlen <= 0 || (*sig) + rlen > sigend) {
+        /* Exceeds bounds or not at least length 1 (X.690-0207 8.3.1).  */
         return 0;
     }
-    if (sig[lenr+4] != 0x02) {
+    if (**sig == 0x00 && rlen > 1 && (((*sig)[1]) & 0x80) == 0x00) {
+        /* Excessive 0x00 padding. */
         return 0;
     }
-    if (lens == 0) {
+    if (**sig == 0xFF && rlen > 1 && (((*sig)[1]) & 0x80) == 0x80) {
+        /* Excessive 0xFF padding. */
         return 0;
     }
-    sp = sig + 6 + lenr;
-    while (lens > 0 && sp[0] == 0) {
-        lens--;
-        sp++;
+    if ((**sig & 0x80) == 0x80) {
+        /* Negative. */
+        overflow = 1;
+    }
+    while (rlen > 0 && **sig == 0) {
+        /* Skip leading zero bytes */
+        rlen--;
+        (*sig)++;
+    }
+    if (rlen > 32) {
+        overflow = 1;
+    }
+    if (!overflow) {
+        memcpy(ra + 32 - rlen, *sig, rlen);
+        secp256k1_scalar_set_b32(r, ra, &overflow);
+    }
+    if (overflow) {
+        secp256k1_scalar_set_int(r, 0);
+    }
+    (*sig) += rlen;
+    return 1;
+}
+
+static int secp256k1_ecdsa_sig_parse(secp256k1_scalar *rr, secp256k1_scalar *rs, const unsigned char *sig, size_t size) {
+    const unsigned char *sigend = sig + size;
+    int rlen;
+    if (sig == sigend || *(sig++) != 0x30) {
+        /* The encoding doesn't start with a constructed sequence (X.690-0207 8.9.1). */
+        return 0;
     }
-    if (lens > 32) {
+    rlen = secp256k1_der_read_len(&sig, sigend);
+    if (rlen < 0 || sig + rlen > sigend) {
+        /* Tuple exceeds bounds */
         return 0;
     }
-    rp = sig + 4;
-    while (lenr > 0 && rp[0] == 0) {
-        lenr--;
-        rp++;
+    if (sig + rlen != sigend) {
+        /* Garbage after tuple. */
+        return 0;
     }
-    if (lenr > 32) {
+
+    if (!secp256k1_der_parse_integer(rr, &sig, sigend)) {
         return 0;
     }
-    memcpy(ra + 32 - lenr, rp, lenr);
-    memcpy(sa + 32 - lens, sp, lens);
-    overflow = 0;
-    secp256k1_scalar_set_b32(rr, ra, &overflow);
-    if (overflow) {
+    if (!secp256k1_der_parse_integer(rs, &sig, sigend)) {
         return 0;
     }
-    secp256k1_scalar_set_b32(rs, sa, &overflow);
-    if (overflow) {
+
+    if (sig != sigend) {
+        /* Trailing garbage inside tuple. */
         return 0;
     }
+
     return 1;
 }
 
@@ -136,7 +203,9 @@ static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, size_t *size, const
 static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context *ctx, const secp256k1_scalar *sigr, const secp256k1_scalar *sigs, const secp256k1_ge *pubkey, const secp256k1_scalar *message) {
     unsigned char c[32];
     secp256k1_scalar sn, u1, u2;
+#if !defined(EXHAUSTIVE_TEST_ORDER)
     secp256k1_fe xr;
+#endif
     secp256k1_gej pubkeyj;
     secp256k1_gej pr;
 
@@ -152,6 +221,19 @@ static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context *ctx, const
     if (secp256k1_gej_is_infinity(&pr)) {
         return 0;
     }
+
+#if defined(EXHAUSTIVE_TEST_ORDER)
+{
+    secp256k1_scalar computed_r;
+    secp256k1_ge pr_ge;
+    secp256k1_ge_set_gej(&pr_ge, &pr);
+    secp256k1_fe_normalize(&pr_ge.x);
+
+    secp256k1_fe_get_b32(c, &pr_ge.x);
+    secp256k1_scalar_set_b32(&computed_r, c, NULL);
+    return secp256k1_scalar_eq(sigr, &computed_r);
+}
+#else
     secp256k1_scalar_get_b32(c, sigr);
     secp256k1_fe_set_b32(&xr, c);
 
@@ -172,11 +254,11 @@ static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context *ctx, const
      *  secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
      */
     if (secp256k1_gej_eq_x_var(&xr, &pr)) {
-        /* xr.x == xr * xr.z^2 mod p, so the signature is valid. */
+        /* xr * pr.z^2 mod p == pr.x, so the signature is valid. */
         return 1;
     }
     if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
-        /* xr + p >= n, so we can skip testing the second case. */
+        /* xr + n >= p, so we can skip testing the second case. */
         return 0;
     }
     secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
@@ -185,39 +267,7 @@ static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context *ctx, const
         return 1;
     }
     return 0;
-}
-
-static int secp256k1_ecdsa_sig_recover(const secp256k1_ecmult_context *ctx, const secp256k1_scalar *sigr, const secp256k1_scalar* sigs, secp256k1_ge *pubkey, const secp256k1_scalar *message, int recid) {
-    unsigned char brx[32];
-    secp256k1_fe fx;
-    secp256k1_ge x;
-    secp256k1_gej xj;
-    secp256k1_scalar rn, u1, u2;
-    secp256k1_gej qj;
-
-    if (secp256k1_scalar_is_zero(sigr) || secp256k1_scalar_is_zero(sigs)) {
-        return 0;
-    }
-
-    secp256k1_scalar_get_b32(brx, sigr);
-    VERIFY_CHECK(secp256k1_fe_set_b32(&fx, brx)); /* brx comes from a scalar, so is less than the order; certainly less than p */
-    if (recid & 2) {
-        if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
-            return 0;
-        }
-        secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
-    }
-    if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1)) {
-        return 0;
-    }
-    secp256k1_gej_set_ge(&xj, &x);
-    secp256k1_scalar_inverse_var(&rn, sigr);
-    secp256k1_scalar_mul(&u1, &rn, message);
-    secp256k1_scalar_negate(&u1, &u1);
-    secp256k1_scalar_mul(&u2, &rn, sigs);
-    secp256k1_ecmult(ctx, &qj, &xj, &u2, &u1);
-    secp256k1_ge_set_gej_var(pubkey, &qj);
-    return !secp256k1_gej_is_infinity(&qj);
+#endif
 }
 
 static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, secp256k1_scalar *sigr, secp256k1_scalar *sigs, const secp256k1_scalar *seckey, const secp256k1_scalar *message, const secp256k1_scalar *nonce, int *recid) {
@@ -233,13 +283,14 @@ static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, sec
     secp256k1_fe_normalize(&r.y);
     secp256k1_fe_get_b32(b, &r.x);
     secp256k1_scalar_set_b32(sigr, b, &overflow);
-    if (secp256k1_scalar_is_zero(sigr)) {
-        /* P.x = order is on the curve, so technically sig->r could end up zero, which would be an invalid signature. */
-        secp256k1_gej_clear(&rp);
-        secp256k1_ge_clear(&r);
-        return 0;
-    }
+    /* These two conditions should be checked before calling */
+    VERIFY_CHECK(!secp256k1_scalar_is_zero(sigr));
+    VERIFY_CHECK(overflow == 0);
+
     if (recid) {
+        /* The overflow condition is cryptographically unreachable as hitting it requires finding the discrete log
+         * of some P where P.x >= order, and only 1 in about 2^127 points meet this criteria.
+         */
         *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
     }
     secp256k1_scalar_mul(&n, sigr, seckey);