diff options
| author | Peter Todd <pete@petertodd.org> | 2014-11-06 16:32:15 -0500 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2014-11-06 21:32:23 +0000 |
| commit | f552013ac1411cde48fefd357260f0b29e322b17 (patch) | |
| tree | 84fb04bd9802b7fa5308aeb26c88c6c6f2a10294 | |
| parent | b24594363fe44af02bf31567bef047a93fe613ac (diff) | |
| download | pi-bitcoindev-f552013ac1411cde48fefd357260f0b29e322b17.tar.gz pi-bitcoindev-f552013ac1411cde48fefd357260f0b29e322b17.zip | |
[Bitcoin-development] The difficulty of writing consensus critical code: the SIGHASH_SINGLE bug
| -rw-r--r-- | 77/e723a8ed161c2df409fd6f69e86314015fbd2f | 315 |
1 files changed, 315 insertions, 0 deletions
diff --git a/77/e723a8ed161c2df409fd6f69e86314015fbd2f b/77/e723a8ed161c2df409fd6f69e86314015fbd2f new file mode 100644 index 000000000..0c0696fe5 --- /dev/null +++ b/77/e723a8ed161c2df409fd6f69e86314015fbd2f @@ -0,0 +1,315 @@ +Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] + helo=mx.sourceforge.net) + by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) + (envelope-from <pete@petertodd.org>) id 1XmUfH-0002pa-Ln + for bitcoin-development@lists.sourceforge.net; + Thu, 06 Nov 2014 21:32:23 +0000 +Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of petertodd.org + designates 62.13.149.95 as permitted sender) + client-ip=62.13.149.95; envelope-from=pete@petertodd.org; + helo=outmail149095.authsmtp.com; +Received: from outmail149095.authsmtp.com ([62.13.149.95]) + by sog-mx-3.v43.ch3.sourceforge.com with esmtp (Exim 4.76) + id 1XmUfF-0006ti-Ma for bitcoin-development@lists.sourceforge.net; + Thu, 06 Nov 2014 21:32:23 +0000 +Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) + by punt15.authsmtp.com (8.14.2/8.14.2/) with ESMTP id sA6LWFrG012292 + for <bitcoin-development@lists.sourceforge.net>; + Thu, 6 Nov 2014 21:32:15 GMT +Received: from savin.petertodd.org (75-119-251-161.dsl.teksavvy.com + [75.119.251.161]) (authenticated bits=128) + by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id sA6LWCgg009787 + (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO) + for <bitcoin-development@lists.sourceforge.net>; + Thu, 6 Nov 2014 21:32:14 GMT +Date: Thu, 6 Nov 2014 16:32:15 -0500 +From: Peter Todd <pete@petertodd.org> +To: Bitcoin Dev <bitcoin-development@lists.sourceforge.net> +Message-ID: <20141106213215.GA12918@savin.petertodd.org> +MIME-Version: 1.0 +Content-Type: multipart/signed; micalg=pgp-sha256; + protocol="application/pgp-signature"; boundary="d6Gm4EdcadzBjdND" +Content-Disposition: inline +User-Agent: Mutt/1.5.21 (2010-09-15) +X-Server-Quench: 604db169-65fc-11e4-b396-002590a15da7 +X-AuthReport-Spam: If SPAM / abuse - report it at: + http://www.authsmtp.com/abuse +X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd + P1hXKl1LNVAaWXld WiVPGEoXDxgzCjYj NEgGOBsDNw4AXwN1 + LhcPXVBSFQF4Ax0L BRwUUx08cABYeX95 e0RnX25aWkVlcE56 + XU8aVhwAGQATPzcf UElffwQacQtIeB0L bFB7ACEMZ2waYH82 + FEpqZj1teD8EeXoQ GllXcANKSB9WEjdj USwCEH0jHEMLRi4u + KwA3YlkSVFkLM1kz N1RpUlUeKBIUERBF V0pXATNYLFAFDyEs + AQ4IFVIeHV8VegZz IjQTAihzIxp9fgcQ DlZKIwAA +X-Authentic-SMTP: 61633532353630.1023:706 +X-AuthFastPath: 0 (Was 255) +X-AuthSMTP-Origin: 75.119.251.161/587 +X-AuthVirus-Status: No virus detected - but ensure you scan with your own + anti-virus system. +X-Spam-Score: -1.5 (-) +X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. + See http://spamassassin.org/tag/ for more details. + -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for + sender-domain + -0.0 SPF_PASS SPF: sender matches SPF record +X-Headers-End: 1XmUfF-0006ti-Ma +Subject: [Bitcoin-development] The difficulty of writing consensus critical + code: the SIGHASH_SINGLE bug +X-BeenThere: bitcoin-development@lists.sourceforge.net +X-Mailman-Version: 2.1.9 +Precedence: list +List-Id: <bitcoin-development.lists.sourceforge.net> +List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>, + <mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe> +List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development> +List-Post: <mailto:bitcoin-development@lists.sourceforge.net> +List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help> +List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>, + <mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe> +X-List-Received-Date: Thu, 06 Nov 2014 21:32:23 -0000 + + +--d6Gm4EdcadzBjdND +Content-Type: text/plain; charset=utf-8 +Content-Disposition: inline +Content-Transfer-Encoding: quoted-printable + +Recently wrote the following for a friend and thought others might learn +=66rom it. + + +> Nope, never heard that term. By "bug-for-bug" compatibility, do you mean +> that, for each version which has a bug, each bug must behave in the *same* +> buggy way? + +Exactly. tl;dr: if you accept a block as valid due to a bug that others rej= +ect, +you're forked and the world ends. + +Long answer... well you reminded me I've never actually written up a good +example for others, and a few people have asked me for one. A great example= + of +this is the SIGHASH_SINGLE bug in the SignatureHash() function: + + uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, uns= +igned int nIn, int nHashType) + { + +<snip> + + else if ((nHashType & 0x1f) =3D=3D SIGHASH_SINGLE) + { + // Only lock-in the txout payee at same index as txin + unsigned int nOut =3D nIn; + if (nOut >=3D txTmp.vout.size()) + { + printf("ERROR: SignatureHash() : nOut=3D%d out of range\n",= + nOut); + return 1; + } +<snip> + + } + +<snip> + + // Serialize and hash + CHashWriter ss(SER_GETHASH, 0); + ss << txTmp << nHashType; + return ss.GetHash(); + } + +So that error condition results in SignatureHash() returning 1 rather than = +the +actual hash. But the consensus-critical code that implements the CHECKSIG +operators doesn't check for that condition! Thus as long as you use the +SIGHASH_SINGLE hashtype and the txin index is >=3D the number of txouts any= + valid +signature for the hash of the number 1 is considered valid! + +When I found this bug=C2=B9 I used it to fork bitcoin-ruby, among others. +(I'm not the first; I found it independently after Matt Corallo) Those +alt-implementations handled this edge-case as an exception, which in +turn caused the script to fail. Thus they'd reject blocks containing +transactions using such scripts, and be forked off the network. + +You can also use this bug for something even more subtle. So the +CHECKSIG* opcode evaluation does this: + + // Drop the signature, since there's no way for a signature to sign its= +elf + scriptCode.FindAndDelete(CScript(vchSig)); + +and CHECKMULTISIG* opcode: + + // Drop the signatures, since there's no way for a signature to sign it= +self + for (int k =3D 0; k < nSigsCount; k++) + { + valtype& vchSig =3D stacktop(-isig-k); + scriptCode.FindAndDelete(CScript(vchSig)); + } + +We used to think that code could never be triggered by a scriptPubKey or +redeemScript, basically because there was no way to get a signature into a +transaction in the right place without the signature depending on the txid = +of +the transaction it was to be included in. (long story) But SIGHASH_SINGLE m= +akes +that a non-issue, as you can now calculate the signature that signs '1' ahe= +ad +of time! In a CHECKMULTISIG that signature is valid, so is included in the = +list +of signatures being dropped, and thus the other signatures must take that +removal into account or they're invalid. Again, you've got a fork. + +However this isn't the end of it! So the way FindAndDelete() works is as +follows: + + int CScript::FindAndDelete(const CScript& b) + { + int nFound =3D 0; + if (b.empty()) + return nFound; + iterator pc =3D begin(); + opcodetype opcode; + do + { + while (end() - pc >=3D (long)b.size() && memcmp(&pc[0], &b[0], = +b.size()) =3D=3D 0) + { + pc =3D erase(pc, pc + b.size()); + ++nFound; + } + } + while (GetOp(pc, opcode)); + return nFound; + } + +So that's pretty ugly, but basically what's happening is the loop iterates +though all the opcodes in the script. Every opcode is compared at the *byte* +level to the bytes in the argument. If they match those bytes are removed f= +rom +the script and iteration continues. The resulting script, with chunks sliced +out of it at the byte level, is what gets hashed as part of the signature +checking algorithm. + +As FindAndDelete() is always called with CScript(vchSig) the signature +being found and deleted is reserialized. Serialization of bytes isn't +unique; there are multiple valid encodings for PUSHDATA operations. The +way CScript() is called the most compact encoding is used, however this +means that if the script being hashed used a different encoding those +bytes are *not* removed and thus the signature is different. + +Again, if you don't get every last one of those details exactly right, you'= +ll +get forked. + +=2E..and I'm still not done! So when you call CScript(vchSig) the relevant = +code +is the following: + + class CScript : public std::vector<unsigned char> + { + +<snip> + + explicit CScript(const CScriptNum& b) { operator<<(b); } + +<snip> + + CScript& operator<<(const std::vector<unsigned char>& b) + { + if (b.size() < OP_PUSHDATA1) + { + insert(end(), (unsigned char)b.size()); + } + else if (b.size() <=3D 0xff) + { + insert(end(), OP_PUSHDATA1); + insert(end(), (unsigned char)b.size()); + } + else if (b.size() <=3D 0xffff) + { + insert(end(), OP_PUSHDATA2); + unsigned short nSize =3D b.size(); + insert(end(), (unsigned char*)&nSize, (unsigned char*)&nSiz= +e + sizeof(nSize)); + } + else + { + insert(end(), OP_PUSHDATA4); + unsigned int nSize =3D b.size(); + insert(end(), (unsigned char*)&nSize, (unsigned char*)&nSiz= +e + sizeof(nSize)); + } + insert(end(), b.begin(), b.end()); + return *this; + } + +<snip, rest of class definition> + + } + +Recently as part of BIP62 we added the concept of a 'minimal' PUSHDATA +operation. Using the minimum-sized PUSHDATA opcode is obvious; not so obvio= +us +is that there are few "push number to stack" opcodes that push the numbers 0 +through 16 and -1 to the stack, bignum encoded. If you are pushing data that +happens to match the latter, you're supposed to use those OP_1...OP_16 and +OP_1NEGATE opcodes rather than a PUSHDATA. + +This means that calling CScript(b'\x81') will result in a non-standard +script. I know an unmerged pull-req=C2=B2 related to sipa's BIP62 work has +code in the CScript() class to automatically do that conversion; had +that code shipped we'd have a potential forking bug between new and old +versions of Bitcoin as the exact encoding of CScript() is consensus +critical by virtue of being called by the FindAndDelete() code! + +Even had we made that mistake, I'm not sure how to actually exploit it... +FindAndDelete() is only ever called in a consensus-critical way with valid +signatures; the byte arrays 01, 02, ..., 81 are all totally invalid signatu= +res. + +The best I could think of would be to exploit the script verification +flag SCRIPT_VERIFY_STRICTENC by using the little-known hybrid-pubkey +encoding=C2=B3, which I spent the past two hours looking at. However it isn= +'t +even soft-fork safe in the current implementation! All I could find was +a new DoS attack=E2=81=B4, and it's not exploitable in an actual release du= +e to +the pre-v0.10 IsStandard() rules. :( + + +[=C2=B9]: https://bitcointalk.org/index.php?topic=3D260595.0 +[=C2=B2]: https://github.com/bitcoin/bitcoin/pull/5091 +[=C2=B3]: https://github.com/bitcoin/bitcoin/blob/cd9114e5136ecc1f60baa43ff= +feeb632782f2353/src/test/data/script_valid.json#L739 +[=E2=81=B4]: http://www.mail-archive.com/bitcoin-development@lists.sourcefo= +rge.net/msg06458.html + +--=20 +'peter'[:-1]@petertodd.org +000000000000000019121d8632bcba14de98125e8a9affc7d07c760706ba3879 + +--d6Gm4EdcadzBjdND +Content-Type: application/pgp-signature; name="signature.asc" +Content-Description: Digital signature + +-----BEGIN PGP SIGNATURE----- + +iQGrBAEBCACVBQJUW+jbXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw +MDAwMDAwMDAwMDAwMDAxOTEyMWQ4NjMyYmNiYTE0ZGU5ODEyNWU4YTlhZmZjN2Qw +N2M3NjA3MDZiYTM4NzkvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0 +ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfsPgQgAv2S88Cl4BF+5lgagGZJw3Cur +H4oBozEViF7WxnoqExeRKpQ15Pvku7EDsTd/lkSEqzQrPZYEqiA6CLtooX5wAfd6 +5wBKPgk0hAWAkeXFpgiFRL/EW5oM9Bl7P/h/Dcywa/Akg+RdWFqW2o4n6xo4XKT0 +qtIbb0LC8AQ86n75/hELpRJd97l+R4vBxVW3FXeiLLefUPSorbYNMrgXSHGZAopM +MNlKMZS3+yXcp+BUfdeEWf1vuH5SVibbXJLom31M8Vr4uSnK/skWCUx1qNUB2mV0 +4PIRxiWSXXok9LftZnNcAGujoRtkQWvKIQQfn9EEVUqz1gGh5ZrWKDG+IEwqnA== +=83lm +-----END PGP SIGNATURE----- + +--d6Gm4EdcadzBjdND-- + + |