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 ) 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 ; 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 ; Thu, 6 Nov 2014 21:32:14 GMT Date: Thu, 6 Nov 2014 16:32:15 -0500 From: Peter Todd To: Bitcoin Dev 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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) { 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; } } // 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 { explicit CScript(const CScriptNum& b) { operator<<(b); } CScript& operator<<(const std::vector& 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; } } 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--