diff --git a/src/pubkey.cpp b/src/pubkey.cpp index d4faf53247..9e5d3b06fd 100644 --- a/src/pubkey.cpp +++ b/src/pubkey.cpp @@ -1,323 +1,324 @@ // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "pubkey.h" #include #include namespace { /* Global secp256k1_context object used for verification. */ secp256k1_context *secp256k1_context_verify = nullptr; } // namespace /** * This function is taken from the libsecp256k1 distribution and implements DER * parsing for ECDSA signatures, while supporting an arbitrary subset of format * violations. * * Supported violations include negative integers, excessive padding, garbage at * the end, and overly long length descriptors. This is safe to use in Bitcoin * because since the activation of BIP66, signatures are verified to be strict * DER before being passed to this module, and we know it supports all * violations present in the blockchain before that point. */ static int ecdsa_signature_parse_der_lax(const secp256k1_context *ctx, secp256k1_ecdsa_signature *sig, const uint8_t *input, size_t inputlen) { size_t rpos, rlen, spos, slen; size_t pos = 0; size_t lenbyte; uint8_t tmpsig[64] = {0}; int overflow = 0; /* Hack to initialize sig with a correctly-parsed but invalid signature. */ secp256k1_ecdsa_signature_parse_compact(ctx, sig, tmpsig); /* Sequence tag byte */ if (pos == inputlen || input[pos] != 0x30) { return 0; } pos++; /* Sequence length bytes */ if (pos == inputlen) { return 0; } lenbyte = input[pos++]; if (lenbyte & 0x80) { lenbyte -= 0x80; if (pos + lenbyte > inputlen) { return 0; } pos += lenbyte; } /* Integer tag byte for R */ if (pos == inputlen || input[pos] != 0x02) { return 0; } pos++; /* Integer length for R */ if (pos == inputlen) { return 0; } lenbyte = input[pos++]; if (lenbyte & 0x80) { lenbyte -= 0x80; if (pos + lenbyte > inputlen) { return 0; } while (lenbyte > 0 && input[pos] == 0) { pos++; lenbyte--; } if (lenbyte >= sizeof(size_t)) { return 0; } rlen = 0; while (lenbyte > 0) { rlen = (rlen << 8) + input[pos]; pos++; lenbyte--; } } else { rlen = lenbyte; } if (rlen > inputlen - pos) { return 0; } rpos = pos; pos += rlen; /* Integer tag byte for S */ if (pos == inputlen || input[pos] != 0x02) { return 0; } pos++; /* Integer length for S */ if (pos == inputlen) { return 0; } lenbyte = input[pos++]; if (lenbyte & 0x80) { lenbyte -= 0x80; if (pos + lenbyte > inputlen) { return 0; } while (lenbyte > 0 && input[pos] == 0) { pos++; lenbyte--; } if (lenbyte >= sizeof(size_t)) { return 0; } slen = 0; while (lenbyte > 0) { slen = (slen << 8) + input[pos]; pos++; lenbyte--; } } else { slen = lenbyte; } if (slen > inputlen - pos) { return 0; } spos = pos; pos += slen; /* Ignore leading zeroes in R */ while (rlen > 0 && input[rpos] == 0) { rlen--; rpos++; } /* Copy R value */ if (rlen > 32) { overflow = 1; } else { memcpy(tmpsig + 32 - rlen, input + rpos, rlen); } /* Ignore leading zeroes in S */ while (slen > 0 && input[spos] == 0) { slen--; spos++; } /* Copy S value */ if (slen > 32) { overflow = 1; } else { memcpy(tmpsig + 64 - slen, input + spos, slen); } if (!overflow) { overflow = !secp256k1_ecdsa_signature_parse_compact(ctx, sig, tmpsig); } if (overflow) { /* Overwrite the result again with a correctly-parsed but invalid signature if parsing failed. */ memset(tmpsig, 0, 64); secp256k1_ecdsa_signature_parse_compact(ctx, sig, tmpsig); } return 1; } bool CPubKey::Verify(const uint256 &hash, const std::vector &vchSig) const { if (!IsValid()) return false; secp256k1_pubkey pubkey; secp256k1_ecdsa_signature sig; if (!secp256k1_ec_pubkey_parse(secp256k1_context_verify, &pubkey, &(*this)[0], size())) { return false; } if (vchSig.size() == 0) { return false; } if (!ecdsa_signature_parse_der_lax(secp256k1_context_verify, &sig, &vchSig[0], vchSig.size())) { return false; } /** * libsecp256k1's ECDSA verification requires lower-S signatures, which have * not historically been enforced in Bitcoin, so normalize them first. */ secp256k1_ecdsa_signature_normalize(secp256k1_context_verify, &sig, &sig); return secp256k1_ecdsa_verify(secp256k1_context_verify, &sig, hash.begin(), &pubkey); } bool CPubKey::RecoverCompact(const uint256 &hash, const std::vector &vchSig) { if (vchSig.size() != 65) return false; int recid = (vchSig[0] - 27) & 3; bool fComp = ((vchSig[0] - 27) & 4) != 0; secp256k1_pubkey pubkey; secp256k1_ecdsa_recoverable_signature sig; if (!secp256k1_ecdsa_recoverable_signature_parse_compact( secp256k1_context_verify, &sig, &vchSig[1], recid)) { return false; } if (!secp256k1_ecdsa_recover(secp256k1_context_verify, &pubkey, &sig, hash.begin())) { return false; } uint8_t pub[65]; size_t publen = 65; secp256k1_ec_pubkey_serialize( secp256k1_context_verify, pub, &publen, &pubkey, fComp ? SECP256K1_EC_COMPRESSED : SECP256K1_EC_UNCOMPRESSED); Set(pub, pub + publen); return true; } bool CPubKey::IsFullyValid() const { if (!IsValid()) return false; secp256k1_pubkey pubkey; return secp256k1_ec_pubkey_parse(secp256k1_context_verify, &pubkey, &(*this)[0], size()); } bool CPubKey::Decompress() { if (!IsValid()) return false; secp256k1_pubkey pubkey; if (!secp256k1_ec_pubkey_parse(secp256k1_context_verify, &pubkey, &(*this)[0], size())) { return false; } uint8_t pub[65]; size_t publen = 65; secp256k1_ec_pubkey_serialize(secp256k1_context_verify, pub, &publen, &pubkey, SECP256K1_EC_UNCOMPRESSED); Set(pub, pub + publen); return true; } bool CPubKey::Derive(CPubKey &pubkeyChild, ChainCode &ccChild, unsigned int nChild, const ChainCode &cc) const { assert(IsValid()); assert((nChild >> 31) == 0); assert(begin() + 33 == end()); uint8_t out[64]; BIP32Hash(cc, nChild, *begin(), begin() + 1, out); memcpy(ccChild.begin(), out + 32, 32); secp256k1_pubkey pubkey; if (!secp256k1_ec_pubkey_parse(secp256k1_context_verify, &pubkey, &(*this)[0], size())) { return false; } if (!secp256k1_ec_pubkey_tweak_add(secp256k1_context_verify, &pubkey, out)) { return false; } uint8_t pub[33]; size_t publen = 33; secp256k1_ec_pubkey_serialize(secp256k1_context_verify, pub, &publen, &pubkey, SECP256K1_EC_COMPRESSED); pubkeyChild.Set(pub, pub + publen); return true; } void CExtPubKey::Encode(uint8_t code[BIP32_EXTKEY_SIZE]) const { code[0] = nDepth; memcpy(code + 1, vchFingerprint, 4); code[5] = (nChild >> 24) & 0xFF; code[6] = (nChild >> 16) & 0xFF; code[7] = (nChild >> 8) & 0xFF; code[8] = (nChild >> 0) & 0xFF; memcpy(code + 9, chaincode.begin(), 32); assert(pubkey.size() == 33); memcpy(code + 41, pubkey.begin(), 33); } void CExtPubKey::Decode(const uint8_t code[BIP32_EXTKEY_SIZE]) { nDepth = code[0]; memcpy(vchFingerprint, code + 1, 4); nChild = (code[5] << 24) | (code[6] << 16) | (code[7] << 8) | code[8]; memcpy(chaincode.begin(), code + 9, 32); pubkey.Set(code + 41, code + BIP32_EXTKEY_SIZE); } bool CExtPubKey::Derive(CExtPubKey &out, unsigned int _nChild) const { out.nDepth = nDepth + 1; CKeyID id = pubkey.GetID(); memcpy(&out.vchFingerprint[0], &id, 4); out.nChild = _nChild; return pubkey.Derive(out.pubkey, out.chaincode, _nChild, chaincode); } -/* static */ bool CPubKey::CheckLowS(const std::vector &vchSig) { +bool CPubKey::CheckLowS( + const boost::sliced_range> &vchSig) { secp256k1_ecdsa_signature sig; if (!ecdsa_signature_parse_der_lax(secp256k1_context_verify, &sig, &vchSig[0], vchSig.size())) { return false; } return (!secp256k1_ecdsa_signature_normalize(secp256k1_context_verify, nullptr, &sig)); } /* static */ int ECCVerifyHandle::refcount = 0; ECCVerifyHandle::ECCVerifyHandle() { if (refcount == 0) { assert(secp256k1_context_verify == nullptr); secp256k1_context_verify = secp256k1_context_create(SECP256K1_CONTEXT_VERIFY); assert(secp256k1_context_verify != nullptr); } refcount++; } ECCVerifyHandle::~ECCVerifyHandle() { refcount--; if (refcount == 0) { assert(secp256k1_context_verify != nullptr); secp256k1_context_destroy(secp256k1_context_verify); secp256k1_context_verify = nullptr; } } diff --git a/src/pubkey.h b/src/pubkey.h index 8b1606a388..99b91c523e 100644 --- a/src/pubkey.h +++ b/src/pubkey.h @@ -1,210 +1,216 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_PUBKEY_H #define BITCOIN_PUBKEY_H #include "hash.h" #include "serialize.h" #include "uint256.h" +#include + #include #include /** * secp256k1: * const unsigned int PRIVATE_KEY_SIZE = 279; * const unsigned int PUBLIC_KEY_SIZE = 65; * const unsigned int SIGNATURE_SIZE = 72; * * see www.keylength.com * script supports up to 75 for single byte push */ const unsigned int BIP32_EXTKEY_SIZE = 74; /** A reference to a CKey: the Hash160 of its serialized public key */ class CKeyID : public uint160 { public: CKeyID() : uint160() {} CKeyID(const uint160 &in) : uint160(in) {} }; typedef uint256 ChainCode; /** An encapsulated public key. */ class CPubKey { private: /** * Just store the serialized data. * Its length can very cheaply be computed from the first byte. */ uint8_t vch[65]; //! Compute the length of a pubkey with a given first byte. static unsigned int GetLen(uint8_t chHeader) { if (chHeader == 2 || chHeader == 3) return 33; if (chHeader == 4 || chHeader == 6 || chHeader == 7) return 65; return 0; } //! Set this key data to be invalid void Invalidate() { vch[0] = 0xFF; } public: //! Construct an invalid public key. CPubKey() { Invalidate(); } //! Initialize a public key using begin/end iterators to byte data. template void Set(const T pbegin, const T pend) { int len = pend == pbegin ? 0 : GetLen(pbegin[0]); if (len && len == (pend - pbegin)) memcpy(vch, (uint8_t *)&pbegin[0], len); else Invalidate(); } //! Construct a public key using begin/end iterators to byte data. template CPubKey(const T pbegin, const T pend) { Set(pbegin, pend); } //! Construct a public key from a byte vector. CPubKey(const std::vector &_vch) { Set(_vch.begin(), _vch.end()); } //! Simple read-only vector-like interface to the pubkey data. unsigned int size() const { return GetLen(vch[0]); } const uint8_t *begin() const { return vch; } const uint8_t *end() const { return vch + size(); } const uint8_t &operator[](unsigned int pos) const { return vch[pos]; } //! Comparator implementation. friend bool operator==(const CPubKey &a, const CPubKey &b) { return a.vch[0] == b.vch[0] && memcmp(a.vch, b.vch, a.size()) == 0; } friend bool operator!=(const CPubKey &a, const CPubKey &b) { return !(a == b); } friend bool operator<(const CPubKey &a, const CPubKey &b) { return a.vch[0] < b.vch[0] || (a.vch[0] == b.vch[0] && memcmp(a.vch, b.vch, a.size()) < 0); } //! Implement serialization, as if this was a byte vector. template void Serialize(Stream &s) const { unsigned int len = size(); ::WriteCompactSize(s, len); s.write((char *)vch, len); } template void Unserialize(Stream &s) { unsigned int len = ::ReadCompactSize(s); if (len <= 65) { s.read((char *)vch, len); } else { // invalid pubkey, skip available data char dummy; while (len--) s.read(&dummy, 1); Invalidate(); } } //! Get the KeyID of this public key (hash of its serialization) CKeyID GetID() const { return CKeyID(Hash160(vch, vch + size())); } //! Get the 256-bit hash of this public key. uint256 GetHash() const { return Hash(vch, vch + size()); } /* * Check syntactic correctness. * * Note that this is consensus critical as CheckSig() calls it! */ bool IsValid() const { return size() > 0; } //! fully validate whether this is a valid public key (more expensive than //! IsValid()) bool IsFullyValid() const; //! Check whether this is a compressed public key. bool IsCompressed() const { return size() == 33; } /** * Verify a DER signature (~72 bytes). * If this public key is not fully valid, the return value will be false. */ bool Verify(const uint256 &hash, const std::vector &vchSig) const; /** * Check whether a signature is normalized (lower-S). */ - static bool CheckLowS(const std::vector &vchSig); + static bool + CheckLowS(const boost::sliced_range> &vchSig); + static bool CheckLowS(const std::vector &vchSig) { + return CheckLowS(vchSig | boost::adaptors::sliced(0, vchSig.size())); + } //! Recover a public key from a compact signature. bool RecoverCompact(const uint256 &hash, const std::vector &vchSig); //! Turn this public key into an uncompressed public key. bool Decompress(); //! Derive BIP32 child pubkey. bool Derive(CPubKey &pubkeyChild, ChainCode &ccChild, unsigned int nChild, const ChainCode &cc) const; }; struct CExtPubKey { uint8_t nDepth; uint8_t vchFingerprint[4]; unsigned int nChild; ChainCode chaincode; CPubKey pubkey; friend bool operator==(const CExtPubKey &a, const CExtPubKey &b) { return a.nDepth == b.nDepth && memcmp(&a.vchFingerprint[0], &b.vchFingerprint[0], sizeof(vchFingerprint)) == 0 && a.nChild == b.nChild && a.chaincode == b.chaincode && a.pubkey == b.pubkey; } void Encode(uint8_t code[BIP32_EXTKEY_SIZE]) const; void Decode(const uint8_t code[BIP32_EXTKEY_SIZE]); bool Derive(CExtPubKey &out, unsigned int nChild) const; void Serialize(CSizeComputer &s) const { // Optimized implementation for ::GetSerializeSize that avoids copying. // add one byte for the size (compact int) s.seek(BIP32_EXTKEY_SIZE + 1); } template void Serialize(Stream &s) const { unsigned int len = BIP32_EXTKEY_SIZE; ::WriteCompactSize(s, len); uint8_t code[BIP32_EXTKEY_SIZE]; Encode(code); s.write((const char *)&code[0], len); } template void Unserialize(Stream &s) { unsigned int len = ::ReadCompactSize(s); uint8_t code[BIP32_EXTKEY_SIZE]; if (len != BIP32_EXTKEY_SIZE) throw std::runtime_error("Invalid extended key size\n"); s.read((char *)&code[0], len); Decode(code); } }; /** * Users of this module must hold an ECCVerifyHandle. The constructor and * destructor of these are not allowed to run in parallel, though. */ class ECCVerifyHandle { static int refcount; public: ECCVerifyHandle(); ~ECCVerifyHandle(); }; #endif // BITCOIN_PUBKEY_H diff --git a/src/script/sigencoding.cpp b/src/script/sigencoding.cpp index d423926b7d..023f1d1e5f 100644 --- a/src/script/sigencoding.cpp +++ b/src/script/sigencoding.cpp @@ -1,178 +1,177 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Copyright (c) 2017-2018 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "sigencoding.h" #include "pubkey.h" #include "script_flags.h" +#include + /** * A canonical signature exists of: <30> <02> <02> , where R and S are not negative (their first byte has its * highest bit not set), and not excessively padded (do not start with a 0 byte, * unless an otherwise negative number follows, in which case a single 0 byte is * necessary and even required). * * See https://bitcointalk.org/index.php?topic=8392.msg127623#msg127623 * * This function is consensus-critical since BIP66. */ static bool IsValidSignatureEncoding(const valtype &sig) { // Format: 0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] // [sighash] // * total-length: 1-byte length descriptor of everything that follows, // excluding the sighash byte. // * R-length: 1-byte length descriptor of the R value that follows. // * R: arbitrary-length big-endian encoded R value. It must use the // shortest possible encoding for a positive integers (which means no null // bytes at the start, except a single one when the next byte has its // highest bit set). // * S-length: 1-byte length descriptor of the S value that follows. // * S: arbitrary-length big-endian encoded S value. The same rules apply. // * sighash: 1-byte value indicating what data is hashed (not part of the // DER signature) // Minimum and maximum size constraints. if (sig.size() < 9) return false; if (sig.size() > 73) return false; // A signature is of type 0x30 (compound). if (sig[0] != 0x30) return false; // Make sure the length covers the entire signature. if (sig[1] != sig.size() - 3) return false; // Extract the length of the R element. unsigned int lenR = sig[3]; // Make sure the length of the S element is still inside the signature. if (5 + lenR >= sig.size()) return false; // Extract the length of the S element. unsigned int lenS = sig[5 + lenR]; // Verify that the length of the signature matches the sum of the length // of the elements. if (size_t(lenR + lenS + 7) != sig.size()) return false; // Check whether the R element is an integer. if (sig[2] != 0x02) return false; // Zero-length integers are not allowed for R. if (lenR == 0) return false; // Negative numbers are not allowed for R. if (sig[4] & 0x80) return false; // Null bytes at the start of R are not allowed, unless R would otherwise be // interpreted as a negative number. if (lenR > 1 && (sig[4] == 0x00) && !(sig[5] & 0x80)) return false; // Check whether the S element is an integer. if (sig[lenR + 4] != 0x02) return false; // Zero-length integers are not allowed for S. if (lenS == 0) return false; // Negative numbers are not allowed for S. if (sig[lenR + 6] & 0x80) return false; // Null bytes at the start of S are not allowed, unless S would otherwise be // interpreted as a negative number. if (lenS > 1 && (sig[lenR + 6] == 0x00) && !(sig[lenR + 7] & 0x80)) { return false; } return true; } static bool IsLowDERSignature(const valtype &vchSig, ScriptError *serror) { - if (!IsValidSignatureEncoding(vchSig)) { - return set_error(serror, SCRIPT_ERR_SIG_DER); - } - std::vector vchSigCopy(vchSig.begin(), - vchSig.begin() + vchSig.size() - 1); - if (!CPubKey::CheckLowS(vchSigCopy)) { - return set_error(serror, SCRIPT_ERR_SIG_HIGH_S); + assert(vchSig.size() > 0); + if (CPubKey::CheckLowS(vchSig | + boost::adaptors::sliced(0, vchSig.size() - 1))) { + return true; } - return true; + return set_error(serror, SCRIPT_ERR_SIG_HIGH_S); } bool CheckSignatureEncoding(const valtype &vchSig, uint32_t flags, ScriptError *serror) { // Empty signature. Not strictly DER encoded, but allowed to provide a // compact way to provide an invalid signature for use with CHECK(MULTI)SIG if (vchSig.size() == 0) { return true; } if ((flags & (SCRIPT_VERIFY_DERSIG | SCRIPT_VERIFY_LOW_S | SCRIPT_VERIFY_STRICTENC)) != 0 && !IsValidSignatureEncoding(vchSig)) { return set_error(serror, SCRIPT_ERR_SIG_DER); } if ((flags & SCRIPT_VERIFY_LOW_S) != 0 && !IsLowDERSignature(vchSig, serror)) { // serror is set return false; } if ((flags & SCRIPT_VERIFY_STRICTENC) != 0) { if (!GetHashType(vchSig).isDefined()) { return set_error(serror, SCRIPT_ERR_SIG_HASHTYPE); } bool usesForkId = GetHashType(vchSig).hasForkId(); bool forkIdEnabled = flags & SCRIPT_ENABLE_SIGHASH_FORKID; if (!forkIdEnabled && usesForkId) { return set_error(serror, SCRIPT_ERR_ILLEGAL_FORKID); } if (forkIdEnabled && !usesForkId) { return set_error(serror, SCRIPT_ERR_MUST_USE_FORKID); } } return true; } static bool IsCompressedOrUncompressedPubKey(const valtype &vchPubKey) { switch (vchPubKey.size()) { case 33: // Compressed public key: must start with 0x02 or 0x03. return vchPubKey[0] == 0x02 || vchPubKey[0] == 0x03; case 65: // Non-compressed public key: must start with 0x04. return vchPubKey[0] == 0x04; default: // Non-canonical public key: invalid size. return false; } } static bool IsCompressedPubKey(const valtype &vchPubKey) { if (vchPubKey.size() != 33) { // Non-canonical public key: invalid length for compressed key return false; } if (vchPubKey[0] != 0x02 && vchPubKey[0] != 0x03) { // Non-canonical public key: invalid prefix for compressed key return false; } return true; } bool CheckPubKeyEncoding(const valtype &vchPubKey, uint32_t flags, ScriptError *serror) { if ((flags & SCRIPT_VERIFY_STRICTENC) && !IsCompressedOrUncompressedPubKey(vchPubKey)) { return set_error(serror, SCRIPT_ERR_PUBKEYTYPE); } // Only compressed keys are accepted when // SCRIPT_VERIFY_COMPRESSED_PUBKEYTYPE is enabled. if ((flags & SCRIPT_VERIFY_COMPRESSED_PUBKEYTYPE) && !IsCompressedPubKey(vchPubKey)) { return set_error(serror, SCRIPT_ERR_NONCOMPRESSED_PUBKEY); } return true; }