From 18dfea0dd082af18dfb02981b7ee1cd44d514388 Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Sat, 14 Jul 2018 16:03:28 -0700 Subject: Always create 70 byte signatures with low R values When extra entropy is not specified by the caller, CKey::Sign will now always create a signature that has a low R value and is at most 70 bytes. The resulting signature on the stack will be 71 bytes when the sighash byte is included. Using low R signatures means that the resulting DER encoded signature will never need to have additional padding to account for high R values. --- src/bench/verify_script.cpp | 2 +- src/key.cpp | 24 ++++++++++++++++++++++-- src/key.h | 2 +- src/test/key_tests.cpp | 36 ++++++++++++++++++++++++++++++++++++ src/test/script_tests.cpp | 2 +- 5 files changed, 61 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/bench/verify_script.cpp b/src/bench/verify_script.cpp index ae60588c2d..1d599b2685 100644 --- a/src/bench/verify_script.cpp +++ b/src/bench/verify_script.cpp @@ -76,7 +76,7 @@ static void VerifyScriptBench(benchmark::State& state) CMutableTransaction txSpend = BuildSpendingTransaction(scriptSig, txCredit); CScriptWitness& witness = txSpend.vin[0].scriptWitness; witness.stack.emplace_back(); - key.Sign(SignatureHash(witScriptPubkey, txSpend, 0, SIGHASH_ALL, txCredit.vout[0].nValue, SigVersion::WITNESS_V0), witness.stack.back(), 0); + key.Sign(SignatureHash(witScriptPubkey, txSpend, 0, SIGHASH_ALL, txCredit.vout[0].nValue, SigVersion::WITNESS_V0), witness.stack.back()); witness.stack.back().push_back(static_cast(SIGHASH_ALL)); witness.stack.push_back(ToByteVector(pubkey)); diff --git a/src/key.cpp b/src/key.cpp index 94be179bfb..69af255be6 100644 --- a/src/key.cpp +++ b/src/key.cpp @@ -189,7 +189,20 @@ CPubKey CKey::GetPubKey() const { return result; } -bool CKey::Sign(const uint256 &hash, std::vector& vchSig, uint32_t test_case) const { +// Check that the sig has a low R value and will be less than 71 bytes +bool SigHasLowR(const secp256k1_ecdsa_signature* sig) +{ + unsigned char 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::Sign(const uint256 &hash, std::vector& vchSig, bool grind, uint32_t test_case) const { if (!fValid) return false; vchSig.resize(CPubKey::SIGNATURE_SIZE); @@ -197,7 +210,14 @@ bool CKey::Sign(const uint256 &hash, std::vector& vchSig, uint32_ unsigned char extra_entropy[32] = {0}; WriteLE32(extra_entropy, test_case); secp256k1_ecdsa_signature sig; - int ret = secp256k1_ecdsa_sign(secp256k1_context_sign, &sig, hash.begin(), begin(), secp256k1_nonce_function_rfc6979, test_case ? extra_entropy : nullptr); + 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, extra_entropy); + } assert(ret); secp256k1_ecdsa_signature_serialize_der(secp256k1_context_sign, vchSig.data(), &nSigLen, &sig); vchSig.resize(nSigLen); diff --git a/src/key.h b/src/key.h index f573a18a4e..ce49b3df02 100644 --- a/src/key.h +++ b/src/key.h @@ -114,7 +114,7 @@ public: * Create a DER-serialized signature. * The test_case parameter tweaks the deterministic nonce. */ - bool Sign(const uint256& hash, std::vector& vchSig, uint32_t test_case = 0) const; + bool Sign(const uint256& hash, std::vector& vchSig, bool grind = true, uint32_t test_case = 0) const; /** * Create a compact signature (65 bytes), which allows reconstructing the used public key. diff --git a/src/test/key_tests.cpp b/src/test/key_tests.cpp index 64c57f0705..acd213dac2 100644 --- a/src/test/key_tests.cpp +++ b/src/test/key_tests.cpp @@ -152,4 +152,40 @@ BOOST_AUTO_TEST_CASE(key_test1) BOOST_CHECK(detsigc == ParseHex("2052d8a32079c11e79db95af63bb9600c5b04f21a9ca33dc129c2bfa8ac9dc1cd561d8ae5e0f6c1a16bde3719c64c2fd70e404b6428ab9a69566962e8771b5944d")); } +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.Sign(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(); + std::string msg = "A message to be signed" + std::to_string(i); + msg_hash = Hash(msg.begin(), msg.end()); + key.Sign(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 index 510910e149..63a9892821 100644 --- a/src/test/script_tests.cpp +++ b/src/test/script_tests.cpp @@ -369,7 +369,7 @@ public: std::vector vchSig, r, s; uint32_t iter = 0; do { - key.Sign(hash, vchSig, iter++); + key.Sign(hash, vchSig, false, iter++); if ((lenS == 33) != (vchSig[5 + vchSig[3]] == 33)) { NegateSignatureS(vchSig); } -- cgit v1.2.3