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; 
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)
Subject: [Bitcoin-development] The difficulty of writing consensus critical
 code: the SIGHASH_SINGLE bug
Precedence: list


--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--