diff --git a/src/key.h b/src/key.h --- a/src/key.h +++ b/src/key.h @@ -113,7 +113,7 @@ * The test_case parameter tweaks the deterministic nonce. */ bool SignECDSA(const uint256 &hash, std::vector &vchSig, - uint32_t test_case = 0) const; + bool grind = true, uint32_t test_case = 0) const; /** * Create a Schnorr signature. diff --git a/src/key.cpp b/src/key.cpp --- a/src/key.cpp +++ b/src/key.cpp @@ -221,8 +221,24 @@ return result; } +// Check that the sig has a low R value and will be less than 71 bytes +static bool SigHasLowR(const secp256k1_ecdsa_signature *sig) { + uint8_t compact_sig[64]; + secp256k1_ecdsa_signature_serialize_compact(secp256k1_context_sign, + compact_sig, sig); + + // In DER serialization, all values are interpreted as big-endian, signed + // integers. The highest bit in the integer indicates its signed-ness; 0 is + // positive, 1 is negative. When the value is interpreted as a negative + // integer, it must be converted to a positive value by prepending a 0x00 + // byte so that the highest bit is 0. We can avoid this prepending by + // ensuring that our highest bit is always 0, and thus we must check that + // the first byte is less than 0x80. + return compact_sig[0] < 0x80; +} + bool CKey::SignECDSA(const uint256 &hash, std::vector &vchSig, - uint32_t test_case) const { + bool grind, uint32_t test_case) const { if (!fValid) { return false; } @@ -231,9 +247,19 @@ uint8_t extra_entropy[32] = {0}; WriteLE32(extra_entropy, test_case); secp256k1_ecdsa_signature sig; - int ret = secp256k1_ecdsa_sign(secp256k1_context_sign, &sig, hash.begin(), + uint32_t counter = 0; + int ret = + secp256k1_ecdsa_sign(secp256k1_context_sign, &sig, hash.begin(), + begin(), secp256k1_nonce_function_rfc6979, + (!grind && test_case) ? extra_entropy : nullptr); + + // Grind for low R + while (ret && !SigHasLowR(&sig) && grind) { + WriteLE32(extra_entropy, ++counter); + ret = secp256k1_ecdsa_sign(secp256k1_context_sign, &sig, hash.begin(), begin(), secp256k1_nonce_function_rfc6979, - test_case ? extra_entropy : nullptr); + extra_entropy); + } assert(ret); secp256k1_ecdsa_signature_serialize_der(secp256k1_context_sign, vchSig.data(), &nSigLen, &sig); diff --git a/src/test/key_tests.cpp b/src/test/key_tests.cpp --- a/src/test/key_tests.cpp +++ b/src/test/key_tests.cpp @@ -35,7 +35,7 @@ // get r value produced by ECDSA signing algorithm // (assumes ECDSA r is encoded in the canonical manner) -std::vector get_r_ECDSA(std::vector sigECDSA) { +static std::vector get_r_ECDSA(std::vector sigECDSA) { std::vector ret(32, 0); assert(sigECDSA[2] == 2); @@ -245,16 +245,16 @@ BOOST_CHECK(key1C.SignECDSA(hashMsg, detsigc)); BOOST_CHECK(detsig == detsigc); BOOST_CHECK(detsig == - ParseHex("3045022100c6ab5f8acfccc114da39dd5ad0b1ef4d39df6a721e8" - "24c22e00b7bc7944a1f7802206ff23df3802e241ee234a8b66c40" - "c82e56a6cc37f9b50463111c9f9229b8f3b3")); + ParseHex("304402200c648ad9936cae4006f0b0d7bcbacdcdf5a14260eb550" + "c31ddb1eb1a13b1b58602201b868673bb5926d1610a07cd03692d" + "fdcb98ed059314f66b457a794f2c4b8e79")); BOOST_CHECK(key2.SignECDSA(hashMsg, detsig)); BOOST_CHECK(key2C.SignECDSA(hashMsg, detsigc)); BOOST_CHECK(detsig == detsigc); BOOST_CHECK(detsig == - ParseHex("304502210094dc5a77b8d5db6b42b66c29d7033cd873fac7a1272" - "4a90373726f60bb9f852a02204eb4c98b9a2f5c017f9417ba7c43" - "279c20c84bb058dc05b3beeb9333016b15bb")); + ParseHex("304402205fb8ff5dbba6110d877169812f5cd939866d9487c6b62" + "5785c6876e4fb8ea69a0220711dc4ecff142f7f808905c04bbd41" + "89e3d2c689c4be396ed22883c463d6ad7a")); // Compact BOOST_CHECK(key1.SignCompact(hashMsg, detsig)); BOOST_CHECK(key1C.SignCompact(hashMsg, detsigc)); @@ -293,4 +293,41 @@ "6b4b1573c84da49a38405d")); } +BOOST_AUTO_TEST_CASE(key_signature_tests) { + // When entropy is specified, we should see at least one high R signature + // within 20 signatures + CKey key = DecodeSecret(strSecret1); + std::string msg = "A message to be signed"; + uint256 msg_hash = Hash(msg.begin(), msg.end()); + std::vector sig; + bool found = false; + + for (int i = 1; i <= 20; ++i) { + sig.clear(); + key.SignECDSA(msg_hash, sig, false, i); + found = sig[3] == 0x21 && sig[4] == 0x00; + if (found) { + break; + } + } + BOOST_CHECK(found); + + // When entropy is not specified, we should always see low R signatures that + // are less than 70 bytes in 256 tries We should see at least one signature + // that is less than 70 bytes. + found = true; + bool found_small = false; + for (int i = 0; i < 256; ++i) { + sig.clear(); + msg = "A message to be signed" + std::to_string(i); + msg_hash = Hash(msg.begin(), msg.end()); + key.SignECDSA(msg_hash, sig); + found = sig[3] == 0x20; + BOOST_CHECK(sig.size() <= 70); + found_small |= sig.size() < 70; + } + BOOST_CHECK(found); + BOOST_CHECK(found_small); +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp --- a/src/test/script_tests.cpp +++ b/src/test/script_tests.cpp @@ -273,7 +273,7 @@ std::vector vchSig, r, s; uint32_t iter = 0; do { - key.SignECDSA(hash, vchSig, iter++); + key.SignECDSA(hash, vchSig, false, iter++); if ((lenS == 33) != (vchSig[5 + vchSig[3]] == 33)) { NegateSignatureS(vchSig); } diff --git a/test/functional/data/rpc_psbt.json b/test/functional/data/rpc_psbt.json --- a/test/functional/data/rpc_psbt.json +++ b/test/functional/data/rpc_psbt.json @@ -53,14 +53,6 @@ ], "psbt" : "cHNidP8BAJoCAAAAAljoeiG1ba8MI76OcHBFbDNvfLqlyHV5JPVFiHuyq911AAAAAAD/////g40EJ9DsZQpoqka7CwmK6kQiwHGyyng1Kgd5WdB86h0BAAAAAP////8CcKrwCAAAAAAWABTYXCtx0AYLCcmIauuBXlCZHdoSTQDh9QUAAAAAFgAUAK6pouXw+HaliN9VRuh0LR2HAI8AAAAAAAEAIIDw+gIAAAAAF6kUD7lGNCFpa4LIM68kHHjBfdveSTSHAQMEQQAAAAEER1IhApWDvzmuCmCXR60Zmt3WNPphCFWdbFzTm0whg/GrluB/IQLath/0mhTban0CsM0fu3j8SxgxK1tOVNrk26L7/vU211KuIgYClYO/Oa4KYJdHrRma3dY0+mEIVZ1sXNObTCGD8auW4H8Q2QxqTwAAAIAAAACAAAAAgCIGAtq2H/SaFNtqfQKwzR+7ePxLGDErW05U2uTbovv+9TbXENkMak8AAACAAAAAgAEAAIAAAQAgAMLrCwAAAAAXqRT2U5MH46SNHgE20GH10f4Z4aJAiYcBAwRBAAAAAQRHUiEDCJ3BDHrG21T5EymvYXMz2ziM6tDCMfcjN50bmQMLAtwhAjrdkE89bc9Z3bkGsN7iNSm3/7ntUOXoYVGSaGAiHw5zUq4iBgI63ZBPPW3PWd25BrDe4jUpt/+57VDl6GFRkmhgIh8OcxDZDGpPAAAAgAAAAIADAACAIgYDCJ3BDHrG21T5EymvYXMz2ziM6tDCMfcjN50bmQMLAtwQ2QxqTwAAAIAAAACAAgAAgAEFR1IhAwidwQx6xttU+RMpr2FzM9s4jOrQwjH3IzedG5kDCwLcIQI63ZBPPW3PWd25BrDe4jUpt/+57VDl6GFRkmhgIh8Oc1KuACICA6mkw39ZltOqJdusa1cK8GUDlEkpQkYLNUdT7Z7spYdxENkMak8AAACAAAAAgAQAAIAAIgICf2OZdX0u/1WhNq0CxoSxg4tlVuXxtrNCgqlLa1AFEJYQ2QxqTwAAAIAAAACABQAAgAA=", "result" : "cHNidP8BAJoCAAAAAljoeiG1ba8MI76OcHBFbDNvfLqlyHV5JPVFiHuyq911AAAAAAD/////g40EJ9DsZQpoqka7CwmK6kQiwHGyyng1Kgd5WdB86h0BAAAAAP////8CcKrwCAAAAAAWABTYXCtx0AYLCcmIauuBXlCZHdoSTQDh9QUAAAAAFgAUAK6pouXw+HaliN9VRuh0LR2HAI8AAAAAAAEAIIDw+gIAAAAAF6kUD7lGNCFpa4LIM68kHHjBfdveSTSHIgIClYO/Oa4KYJdHrRma3dY0+mEIVZ1sXNObTCGD8auW4H9HMEQCIFeeX7PDIvPZfNrFqWNn0HYRnoT1rlK5Z6WDG3bEROr1AiB2sWDcIhR/xfSYYn09htmayTznOW5Qm2bPIpe3y5lN3EEBAwRBAAAAAQRHUiEClYO/Oa4KYJdHrRma3dY0+mEIVZ1sXNObTCGD8auW4H8hAtq2H/SaFNtqfQKwzR+7ePxLGDErW05U2uTbovv+9TbXUq4iBgKVg785rgpgl0etGZrd1jT6YQhVnWxc05tMIYPxq5bgfxDZDGpPAAAAgAAAAIAAAACAIgYC2rYf9JoU22p9ArDNH7t4/EsYMStbTlTa5Nui+/71NtcQ2QxqTwAAAIAAAACAAQAAgAABACAAwusLAAAAABepFPZTkwfjpI0eATbQYfXR/hnhokCJhyICAwidwQx6xttU+RMpr2FzM9s4jOrQwjH3IzedG5kDCwLcRzBEAiBnrEB7WcwLuWdisBpe6dVj/d3RTo0CCmRQJjnWVNBCDQIgH3K+5DYrjna1qu3uYVvW81W5g9tGDs9qfelLV5uyeTtBAQMEQQAAAAEER1IhAwidwQx6xttU+RMpr2FzM9s4jOrQwjH3IzedG5kDCwLcIQI63ZBPPW3PWd25BrDe4jUpt/+57VDl6GFRkmhgIh8Oc1KuIgYCOt2QTz1tz1nduQaw3uI1Kbf/ue1Q5ehhUZJoYCIfDnMQ2QxqTwAAAIAAAACAAwAAgCIGAwidwQx6xttU+RMpr2FzM9s4jOrQwjH3IzedG5kDCwLcENkMak8AAACAAAAAgAIAAIABBUdSIQMIncEMesbbVPkTKa9hczPbOIzq0MIx9yM3nRuZAwsC3CECOt2QTz1tz1nduQaw3uI1Kbf/ue1Q5ehhUZJoYCIfDnNSrgAiAgOppMN/WZbTqiXbrGtXCvBlA5RJKUJGCzVHU+2e7KWHcRDZDGpPAAAAgAAAAIAEAACAACICAn9jmXV9Lv9VoTatAsaEsYOLZVbl8bazQoKpS2tQBRCWENkMak8AAACAAAAAgAUAAIAA" - }, - { - "privkeys" : [ - "cT7J9YpCwY3AVRFSjN6ukeEeWY6mhpbJPxRaDaP5QTdygQRxP9Au", - "cNBc3SWUip9PPm1GjRoLEJT6T41iNzCYtD7qro84FMnM5zEqeJsE" - ], - "psbt" : "cHNidP8BAJoCAAAAAljoeiG1ba8MI76OcHBFbDNvfLqlyHV5JPVFiHuyq911AAAAAAD/////g40EJ9DsZQpoqka7CwmK6kQiwHGyyng1Kgd5WdB86h0BAAAAAP////8CcKrwCAAAAAAWABTYXCtx0AYLCcmIauuBXlCZHdoSTQDh9QUAAAAAFgAUAK6pouXw+HaliN9VRuh0LR2HAI8AAAAAAAEAIIDw+gIAAAAAF6kUD7lGNCFpa4LIM68kHHjBfdveSTSHAQMEQQAAAAEER1IhApWDvzmuCmCXR60Zmt3WNPphCFWdbFzTm0whg/GrluB/IQLath/0mhTban0CsM0fu3j8SxgxK1tOVNrk26L7/vU211KuIgYClYO/Oa4KYJdHrRma3dY0+mEIVZ1sXNObTCGD8auW4H8Q2QxqTwAAAIAAAACAAAAAgCIGAtq2H/SaFNtqfQKwzR+7ePxLGDErW05U2uTbovv+9TbXENkMak8AAACAAAAAgAEAAIAAAQAgAMLrCwAAAAAXqRT2U5MH46SNHgE20GH10f4Z4aJAiYcBAwRBAAAAAQRHUiEDCJ3BDHrG21T5EymvYXMz2ziM6tDCMfcjN50bmQMLAtwhAjrdkE89bc9Z3bkGsN7iNSm3/7ntUOXoYVGSaGAiHw5zUq4iBgI63ZBPPW3PWd25BrDe4jUpt/+57VDl6GFRkmhgIh8OcxDZDGpPAAAAgAAAAIADAACAIgYDCJ3BDHrG21T5EymvYXMz2ziM6tDCMfcjN50bmQMLAtwQ2QxqTwAAAIAAAACAAgAAgAEFR1IhAwidwQx6xttU+RMpr2FzM9s4jOrQwjH3IzedG5kDCwLcIQI63ZBPPW3PWd25BrDe4jUpt/+57VDl6GFRkmhgIh8Oc1KuACICA6mkw39ZltOqJdusa1cK8GUDlEkpQkYLNUdT7Z7spYdxENkMak8AAACAAAAAgAQAAIAAIgICf2OZdX0u/1WhNq0CxoSxg4tlVuXxtrNCgqlLa1AFEJYQ2QxqTwAAAIAAAACABQAAgAA=", - "result" : "cHNidP8BAJoCAAAAAljoeiG1ba8MI76OcHBFbDNvfLqlyHV5JPVFiHuyq911AAAAAAD/////g40EJ9DsZQpoqka7CwmK6kQiwHGyyng1Kgd5WdB86h0BAAAAAP////8CcKrwCAAAAAAWABTYXCtx0AYLCcmIauuBXlCZHdoSTQDh9QUAAAAAFgAUAK6pouXw+HaliN9VRuh0LR2HAI8AAAAAAAEAIIDw+gIAAAAAF6kUD7lGNCFpa4LIM68kHHjBfdveSTSHIgIC2rYf9JoU22p9ArDNH7t4/EsYMStbTlTa5Nui+/71NtdIMEUCIQC4KZqvFEgiBXP/DSl7MJWuNK4jWoaSxkV49PQymsSmXQIgZEJJTLiXqYesRIJn+5rpHOzzEc+UvVyBhl4iRJDa/lZBAQMEQQAAAAEER1IhApWDvzmuCmCXR60Zmt3WNPphCFWdbFzTm0whg/GrluB/IQLath/0mhTban0CsM0fu3j8SxgxK1tOVNrk26L7/vU211KuIgYClYO/Oa4KYJdHrRma3dY0+mEIVZ1sXNObTCGD8auW4H8Q2QxqTwAAAIAAAACAAAAAgCIGAtq2H/SaFNtqfQKwzR+7ePxLGDErW05U2uTbovv+9TbXENkMak8AAACAAAAAgAEAAIAAAQAgAMLrCwAAAAAXqRT2U5MH46SNHgE20GH10f4Z4aJAiYciAgI63ZBPPW3PWd25BrDe4jUpt/+57VDl6GFRkmhgIh8Oc0gwRQIhAPnp+xxMInl3CosPo889LXOd7tusAnUZQYscGdNuJAZrAiBResVBqwycuwTarMk8X4focnvDwzVFrdydyZ2mfIus0UEBAwRBAAAAAQRHUiEDCJ3BDHrG21T5EymvYXMz2ziM6tDCMfcjN50bmQMLAtwhAjrdkE89bc9Z3bkGsN7iNSm3/7ntUOXoYVGSaGAiHw5zUq4iBgI63ZBPPW3PWd25BrDe4jUpt/+57VDl6GFRkmhgIh8OcxDZDGpPAAAAgAAAAIADAACAIgYDCJ3BDHrG21T5EymvYXMz2ziM6tDCMfcjN50bmQMLAtwQ2QxqTwAAAIAAAACAAgAAgAEFR1IhAwidwQx6xttU+RMpr2FzM9s4jOrQwjH3IzedG5kDCwLcIQI63ZBPPW3PWd25BrDe4jUpt/+57VDl6GFRkmhgIh8Oc1KuACICA6mkw39ZltOqJdusa1cK8GUDlEkpQkYLNUdT7Z7spYdxENkMak8AAACAAAAAgAQAAIAAIgICf2OZdX0u/1WhNq0CxoSxg4tlVuXxtrNCgqlLa1AFEJYQ2QxqTwAAAIAAAACABQAAgAA=" } ], "combiner" : [ diff --git a/test/util/data/txcreatesignv2.hex b/test/util/data/txcreatesignv2.hex --- a/test/util/data/txcreatesignv2.hex +++ b/test/util/data/txcreatesignv2.hex @@ -1 +1 @@ -02000000018594c5bdcaec8f06b78b596f31cd292a294fd031e24eec716f43dac91ea7494d000000008b483045022100c8409b51f558d853f862a88a50f8c0a45f8d0689b339f518ceb16fc38146d85c02202e703515d1c5cce477fd3e51de7f18d31884b57900cf09018163e3257a63517b01410479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8ffffffff01a0860100000000001976a9145834479edbbe0539b31ffd3a8f8ebadc2165ed0188ac00000000 +02000000018594c5bdcaec8f06b78b596f31cd292a294fd031e24eec716f43dac91ea7494d000000008a47304402205338be788a5c8ec16624f60c244927054e7b07bc8e540b14b1f4a16842ddefd102204e4db3e867caa416a6ec592addc30ba379c1e899913caf97214ed3e0aa3c866a01410479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8ffffffff01a0860100000000001976a9145834479edbbe0539b31ffd3a8f8ebadc2165ed0188ac00000000