1 // Copyright (c) 2009-2020 The Bitcoin Core developers
2 // Copyright (c) 2017 The Zcash developers
3 // Distributed under the MIT software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5
6 #include <pubkey.h>
7
8 #include <hash.h>
9 #include <secp256k1.h>
10 #include <secp256k1_extrakeys.h>
11 #include <secp256k1_recovery.h>
12 #include <secp256k1_schnorrsig.h>
13 #include <span.h>
14 #include <uint256.h>
15
16 #include <algorithm>
17 #include <cassert>
18
19 namespace
20 {
21 /* Global secp256k1_context object used for verification. */
22 secp256k1_context* secp256k1_context_verify = nullptr;
23 } // namespace
24
25 /** This function is taken from the libsecp256k1 distribution and implements
26 * DER parsing for ECDSA signatures, while supporting an arbitrary subset of
27 * format violations.
28 *
29 * Supported violations include negative integers, excessive padding, garbage
30 * at the end, and overly long length descriptors. This is safe to use in
31 * Bitcoin because since the activation of BIP66, signatures are verified to be
32 * strict DER before being passed to this module, and we know it supports all
33 * violations present in the blockchain before that point.
34 */
ecdsa_signature_parse_der_lax(const secp256k1_context * ctx,secp256k1_ecdsa_signature * sig,const unsigned char * input,size_t inputlen)35 int ecdsa_signature_parse_der_lax(const secp256k1_context* ctx, secp256k1_ecdsa_signature* sig, const unsigned char *input, size_t inputlen) {
36 size_t rpos, rlen, spos, slen;
37 size_t pos = 0;
38 size_t lenbyte;
39 unsigned char tmpsig[64] = {0};
40 int overflow = 0;
41
42 /* Hack to initialize sig with a correctly-parsed but invalid signature. */
43 secp256k1_ecdsa_signature_parse_compact(ctx, sig, tmpsig);
44
45 /* Sequence tag byte */
46 if (pos == inputlen || input[pos] != 0x30) {
47 return 0;
48 }
49 pos++;
50
51 /* Sequence length bytes */
52 if (pos == inputlen) {
53 return 0;
54 }
55 lenbyte = input[pos++];
56 if (lenbyte & 0x80) {
57 lenbyte -= 0x80;
58 if (lenbyte > inputlen - pos) {
59 return 0;
60 }
61 pos += lenbyte;
62 }
63
64 /* Integer tag byte for R */
65 if (pos == inputlen || input[pos] != 0x02) {
66 return 0;
67 }
68 pos++;
69
70 /* Integer length for R */
71 if (pos == inputlen) {
72 return 0;
73 }
74 lenbyte = input[pos++];
75 if (lenbyte & 0x80) {
76 lenbyte -= 0x80;
77 if (lenbyte > inputlen - pos) {
78 return 0;
79 }
80 while (lenbyte > 0 && input[pos] == 0) {
81 pos++;
82 lenbyte--;
83 }
84 static_assert(sizeof(size_t) >= 4, "size_t too small");
85 if (lenbyte >= 4) {
86 return 0;
87 }
88 rlen = 0;
89 while (lenbyte > 0) {
90 rlen = (rlen << 8) + input[pos];
91 pos++;
92 lenbyte--;
93 }
94 } else {
95 rlen = lenbyte;
96 }
97 if (rlen > inputlen - pos) {
98 return 0;
99 }
100 rpos = pos;
101 pos += rlen;
102
103 /* Integer tag byte for S */
104 if (pos == inputlen || input[pos] != 0x02) {
105 return 0;
106 }
107 pos++;
108
109 /* Integer length for S */
110 if (pos == inputlen) {
111 return 0;
112 }
113 lenbyte = input[pos++];
114 if (lenbyte & 0x80) {
115 lenbyte -= 0x80;
116 if (lenbyte > inputlen - pos) {
117 return 0;
118 }
119 while (lenbyte > 0 && input[pos] == 0) {
120 pos++;
121 lenbyte--;
122 }
123 static_assert(sizeof(size_t) >= 4, "size_t too small");
124 if (lenbyte >= 4) {
125 return 0;
126 }
127 slen = 0;
128 while (lenbyte > 0) {
129 slen = (slen << 8) + input[pos];
130 pos++;
131 lenbyte--;
132 }
133 } else {
134 slen = lenbyte;
135 }
136 if (slen > inputlen - pos) {
137 return 0;
138 }
139 spos = pos;
140
141 /* Ignore leading zeroes in R */
142 while (rlen > 0 && input[rpos] == 0) {
143 rlen--;
144 rpos++;
145 }
146 /* Copy R value */
147 if (rlen > 32) {
148 overflow = 1;
149 } else {
150 memcpy(tmpsig + 32 - rlen, input + rpos, rlen);
151 }
152
153 /* Ignore leading zeroes in S */
154 while (slen > 0 && input[spos] == 0) {
155 slen--;
156 spos++;
157 }
158 /* Copy S value */
159 if (slen > 32) {
160 overflow = 1;
161 } else {
162 memcpy(tmpsig + 64 - slen, input + spos, slen);
163 }
164
165 if (!overflow) {
166 overflow = !secp256k1_ecdsa_signature_parse_compact(ctx, sig, tmpsig);
167 }
168 if (overflow) {
169 /* Overwrite the result again with a correctly-parsed but invalid
170 signature if parsing failed. */
171 memset(tmpsig, 0, 64);
172 secp256k1_ecdsa_signature_parse_compact(ctx, sig, tmpsig);
173 }
174 return 1;
175 }
176
XOnlyPubKey(Span<const unsigned char> bytes)177 XOnlyPubKey::XOnlyPubKey(Span<const unsigned char> bytes)
178 {
179 assert(bytes.size() == 32);
180 std::copy(bytes.begin(), bytes.end(), m_keydata.begin());
181 }
182
IsFullyValid() const183 bool XOnlyPubKey::IsFullyValid() const
184 {
185 secp256k1_xonly_pubkey pubkey;
186 return secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &pubkey, m_keydata.data());
187 }
188
VerifySchnorr(const uint256 & msg,Span<const unsigned char> sigbytes) const189 bool XOnlyPubKey::VerifySchnorr(const uint256& msg, Span<const unsigned char> sigbytes) const
190 {
191 assert(sigbytes.size() == 64);
192 secp256k1_xonly_pubkey pubkey;
193 if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &pubkey, m_keydata.data())) return false;
194 return secp256k1_schnorrsig_verify(secp256k1_context_verify, sigbytes.data(), msg.begin(), &pubkey);
195 }
196
197 static const CHashWriter HASHER_TAPTWEAK = TaggedHash("TapTweak");
198
ComputeTapTweakHash(const uint256 * merkle_root) const199 uint256 XOnlyPubKey::ComputeTapTweakHash(const uint256* merkle_root) const
200 {
201 if (merkle_root == nullptr) {
202 // We have no scripts. The actual tweak does not matter, but follow BIP341 here to
203 // allow for reproducible tweaking.
204 return (CHashWriter(HASHER_TAPTWEAK) << m_keydata).GetSHA256();
205 } else {
206 return (CHashWriter(HASHER_TAPTWEAK) << m_keydata << *merkle_root).GetSHA256();
207 }
208 }
209
CheckTapTweak(const XOnlyPubKey & internal,const uint256 & merkle_root,bool parity) const210 bool XOnlyPubKey::CheckTapTweak(const XOnlyPubKey& internal, const uint256& merkle_root, bool parity) const
211 {
212 secp256k1_xonly_pubkey internal_key;
213 if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &internal_key, internal.data())) return false;
214 uint256 tweak = internal.ComputeTapTweakHash(&merkle_root);
215 return secp256k1_xonly_pubkey_tweak_add_check(secp256k1_context_verify, m_keydata.begin(), parity, &internal_key, tweak.begin());
216 }
217
CreateTapTweak(const uint256 * merkle_root) const218 std::optional<std::pair<XOnlyPubKey, bool>> XOnlyPubKey::CreateTapTweak(const uint256* merkle_root) const
219 {
220 secp256k1_xonly_pubkey base_point;
221 if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &base_point, data())) return std::nullopt;
222 secp256k1_pubkey out;
223 uint256 tweak = ComputeTapTweakHash(merkle_root);
224 if (!secp256k1_xonly_pubkey_tweak_add(secp256k1_context_verify, &out, &base_point, tweak.data())) return std::nullopt;
225 int parity = -1;
226 std::pair<XOnlyPubKey, bool> ret;
227 secp256k1_xonly_pubkey out_xonly;
228 if (!secp256k1_xonly_pubkey_from_pubkey(secp256k1_context_verify, &out_xonly, &parity, &out)) return std::nullopt;
229 secp256k1_xonly_pubkey_serialize(secp256k1_context_verify, ret.first.begin(), &out_xonly);
230 assert(parity == 0 || parity == 1);
231 ret.second = parity;
232 return ret;
233 }
234
235
Verify(const uint256 & hash,const std::vector<unsigned char> & vchSig) const236 bool CPubKey::Verify(const uint256 &hash, const std::vector<unsigned char>& vchSig) const {
237 if (!IsValid())
238 return false;
239 secp256k1_pubkey pubkey;
240 secp256k1_ecdsa_signature sig;
241 assert(secp256k1_context_verify && "secp256k1_context_verify must be initialized to use CPubKey.");
242 if (!secp256k1_ec_pubkey_parse(secp256k1_context_verify, &pubkey, vch, size())) {
243 return false;
244 }
245 if (!ecdsa_signature_parse_der_lax(secp256k1_context_verify, &sig, vchSig.data(), vchSig.size())) {
246 return false;
247 }
248 /* libsecp256k1's ECDSA verification requires lower-S signatures, which have
249 * not historically been enforced in Bitcoin, so normalize them first. */
250 secp256k1_ecdsa_signature_normalize(secp256k1_context_verify, &sig, &sig);
251 return secp256k1_ecdsa_verify(secp256k1_context_verify, &sig, hash.begin(), &pubkey);
252 }
253
RecoverCompact(const uint256 & hash,const std::vector<unsigned char> & vchSig)254 bool CPubKey::RecoverCompact(const uint256 &hash, const std::vector<unsigned char>& vchSig) {
255 if (vchSig.size() != COMPACT_SIGNATURE_SIZE)
256 return false;
257 int recid = (vchSig[0] - 27) & 3;
258 bool fComp = ((vchSig[0] - 27) & 4) != 0;
259 secp256k1_pubkey pubkey;
260 secp256k1_ecdsa_recoverable_signature sig;
261 assert(secp256k1_context_verify && "secp256k1_context_verify must be initialized to use CPubKey.");
262 if (!secp256k1_ecdsa_recoverable_signature_parse_compact(secp256k1_context_verify, &sig, &vchSig[1], recid)) {
263 return false;
264 }
265 if (!secp256k1_ecdsa_recover(secp256k1_context_verify, &pubkey, &sig, hash.begin())) {
266 return false;
267 }
268 unsigned char pub[SIZE];
269 size_t publen = SIZE;
270 secp256k1_ec_pubkey_serialize(secp256k1_context_verify, pub, &publen, &pubkey, fComp ? SECP256K1_EC_COMPRESSED : SECP256K1_EC_UNCOMPRESSED);
271 Set(pub, pub + publen);
272 return true;
273 }
274
IsFullyValid() const275 bool CPubKey::IsFullyValid() const {
276 if (!IsValid())
277 return false;
278 secp256k1_pubkey pubkey;
279 assert(secp256k1_context_verify && "secp256k1_context_verify must be initialized to use CPubKey.");
280 return secp256k1_ec_pubkey_parse(secp256k1_context_verify, &pubkey, vch, size());
281 }
282
Decompress()283 bool CPubKey::Decompress() {
284 if (!IsValid())
285 return false;
286 secp256k1_pubkey pubkey;
287 assert(secp256k1_context_verify && "secp256k1_context_verify must be initialized to use CPubKey.");
288 if (!secp256k1_ec_pubkey_parse(secp256k1_context_verify, &pubkey, vch, size())) {
289 return false;
290 }
291 unsigned char pub[SIZE];
292 size_t publen = SIZE;
293 secp256k1_ec_pubkey_serialize(secp256k1_context_verify, pub, &publen, &pubkey, SECP256K1_EC_UNCOMPRESSED);
294 Set(pub, pub + publen);
295 return true;
296 }
297
Derive(CPubKey & pubkeyChild,ChainCode & ccChild,unsigned int nChild,const ChainCode & cc) const298 bool CPubKey::Derive(CPubKey& pubkeyChild, ChainCode &ccChild, unsigned int nChild, const ChainCode& cc) const {
299 assert(IsValid());
300 assert((nChild >> 31) == 0);
301 assert(size() == COMPRESSED_SIZE);
302 unsigned char out[64];
303 BIP32Hash(cc, nChild, *begin(), begin()+1, out);
304 memcpy(ccChild.begin(), out+32, 32);
305 secp256k1_pubkey pubkey;
306 assert(secp256k1_context_verify && "secp256k1_context_verify must be initialized to use CPubKey.");
307 if (!secp256k1_ec_pubkey_parse(secp256k1_context_verify, &pubkey, vch, size())) {
308 return false;
309 }
310 if (!secp256k1_ec_pubkey_tweak_add(secp256k1_context_verify, &pubkey, out)) {
311 return false;
312 }
313 unsigned char pub[COMPRESSED_SIZE];
314 size_t publen = COMPRESSED_SIZE;
315 secp256k1_ec_pubkey_serialize(secp256k1_context_verify, pub, &publen, &pubkey, SECP256K1_EC_COMPRESSED);
316 pubkeyChild.Set(pub, pub + publen);
317 return true;
318 }
319
Encode(unsigned char code[BIP32_EXTKEY_SIZE]) const320 void CExtPubKey::Encode(unsigned char code[BIP32_EXTKEY_SIZE]) const {
321 code[0] = nDepth;
322 memcpy(code+1, vchFingerprint, 4);
323 code[5] = (nChild >> 24) & 0xFF; code[6] = (nChild >> 16) & 0xFF;
324 code[7] = (nChild >> 8) & 0xFF; code[8] = (nChild >> 0) & 0xFF;
325 memcpy(code+9, chaincode.begin(), 32);
326 assert(pubkey.size() == CPubKey::COMPRESSED_SIZE);
327 memcpy(code+41, pubkey.begin(), CPubKey::COMPRESSED_SIZE);
328 }
329
Decode(const unsigned char code[BIP32_EXTKEY_SIZE])330 void CExtPubKey::Decode(const unsigned char code[BIP32_EXTKEY_SIZE]) {
331 nDepth = code[0];
332 memcpy(vchFingerprint, code+1, 4);
333 nChild = (code[5] << 24) | (code[6] << 16) | (code[7] << 8) | code[8];
334 memcpy(chaincode.begin(), code+9, 32);
335 pubkey.Set(code+41, code+BIP32_EXTKEY_SIZE);
336 }
337
Derive(CExtPubKey & out,unsigned int _nChild) const338 bool CExtPubKey::Derive(CExtPubKey &out, unsigned int _nChild) const {
339 out.nDepth = nDepth + 1;
340 CKeyID id = pubkey.GetID();
341 memcpy(out.vchFingerprint, &id, 4);
342 out.nChild = _nChild;
343 return pubkey.Derive(out.pubkey, out.chaincode, _nChild, chaincode);
344 }
345
CheckLowS(const std::vector<unsigned char> & vchSig)346 /* static */ bool CPubKey::CheckLowS(const std::vector<unsigned char>& vchSig) {
347 secp256k1_ecdsa_signature sig;
348 assert(secp256k1_context_verify && "secp256k1_context_verify must be initialized to use CPubKey.");
349 if (!ecdsa_signature_parse_der_lax(secp256k1_context_verify, &sig, vchSig.data(), vchSig.size())) {
350 return false;
351 }
352 return (!secp256k1_ecdsa_signature_normalize(secp256k1_context_verify, nullptr, &sig));
353 }
354
355 /* static */ int ECCVerifyHandle::refcount = 0;
356
ECCVerifyHandle()357 ECCVerifyHandle::ECCVerifyHandle()
358 {
359 if (refcount == 0) {
360 assert(secp256k1_context_verify == nullptr);
361 secp256k1_context_verify = secp256k1_context_create(SECP256K1_CONTEXT_VERIFY);
362 assert(secp256k1_context_verify != nullptr);
363 }
364 refcount++;
365 }
366
~ECCVerifyHandle()367 ECCVerifyHandle::~ECCVerifyHandle()
368 {
369 refcount--;
370 if (refcount == 0) {
371 assert(secp256k1_context_verify != nullptr);
372 secp256k1_context_destroy(secp256k1_context_verify);
373 secp256k1_context_verify = nullptr;
374 }
375 }
376
GetVerifyContext()377 const secp256k1_context* GetVerifyContext() {
378 return secp256k1_context_verify;
379 }
380