Reject non-canonically-encoded CompactSize #2884

gavinandresen commented at 5:16 AM on August 7, 2013: contributor

The length of vectors, maps, sets, etc are serialized using Write/ReadCompactSize -- which, unfortunately, do not use a unique encoding.

So deserializing and then re-serializing a transaction (for example) can give you different bits than you started with. That doesn't cause any problems that we are aware of, but it is exactly the type of subtle mismatch that can lead to exploits.

With this pull, reading a non-canonical CompactSize throws an exception, which means nodes will ignore 'tx' or 'block' or other messages that are not properly encoded.

Please check my logic... but this change is safe with respect to causing a network split. Old clients that receive non-canonically-encoded transactions or blocks deserialize them into CTransaction/CBlock structures in memory, and then re-serialize them before relaying them to peers.

And please check my logic with respect to causing a blockchain split: there are no CompactSize fields in the block header, so the block hash is always canonical. The merkle root in the block header is computed on a vector<CTransaction>, so any non-canonical encoding of the transactions in 'tx' or 'block' messages is erased as they are read into memory by old clients, and does not affect the block hash. And, as noted above, old clients re-serialize (with canonical encoding) 'tx' and 'block' messages before relaying to peers.

petertodd commented at 2:27 PM on August 8, 2013: contributor

@SergioDemianLerner +1

"Old clients that receive non-canonically-encoded transactions or blocks deserialize them into CTransaction/CBlock structures in memory, and then re-serialize them before relaying them to peers."

What do you mean by "old" here?

gavinandresen commented at 8:54 PM on August 8, 2013: contributor

@petertodd : for "block" messages, old means "previous versions of the reference implementation." For "tx" messages, old means "versions that have commit 'Simplify storage of orphan transactions'".

Rejecting non-canonically-encoded "tx" messages should have no ill effects-- well, beyond creating Yet Another Way to craft 0-confirmation transactions that are accepted by un-upgraded nodes and rejected by newer nodes.

I'll make the CHECK_THROW for the unit tests message specific.

Reject non-canonically-encoded sizes

The length of vectors, maps, sets, etc are serialized using
Write/ReadCompactSize -- which, unfortunately, do not use a
unique encoding.

So deserializing and then re-serializing a transaction (for example)
can give you different bits than you started with. That doesn't
cause any problems that we are aware of, but it is exactly the type
of subtle mismatch that can lead to exploits.

With this pull, reading a non-canonical CompactSize throws an
exception, which means nodes will ignore 'tx' or 'block' or
other messages that are not properly encoded.

Please check my logic... but this change is safe with respect to
causing a network split. Old clients that receive
non-canonically-encoded transactions or blocks deserialize
them into CTransaction/CBlock structures in memory, and then
re-serialize them before relaying them to peers.

And please check my logic with respect to causing a blockchain
split: there are no CompactSize fields in the block header, so
the block hash is always canonical. The merkle root in the block
header is computed on a vector<CTransaction>, so
any non-canonical encoding of the transactions in 'tx' or 'block'
messages is erased as they are read into memory by old clients,
and does not affect the block hash. And, as noted above, old
clients re-serialize (with canonical encoding) 'tx' and 'block'
messages before relaying to peers.

8dc206a1e2

sipa commented at 9:51 PM on August 15, 2013: member

Strange that pull tester succeeds - IIRC there was a test that used an incorrectly-encoded vtx size in a block, to push it over the 1 MB limit?

jgarzik commented at 2:42 AM on August 25, 2013: contributor

ACK

sipa commented at 4:07 PM on August 25, 2013: member

ACK. In a later version we probably want to make it a DoSable offence to use these non-canonical encodings, but right now that would cause network fork risk for pre-0.8.3 nodes.

petertodd commented at 4:57 PM on August 25, 2013: contributor

ACK

FWIW if anyone wants to see it in action, here's block 100 with the compact int for the length of the transaction list changed to non-canonical format:

0100000095194b8567fe2e8bbda931afd01a7acd399b9325cb54683e64129bcd00000000660802c98f18fd34fd16d61c63cf447568370124ac5f3be626c2e1c3c9f0052d19a76949ffff001d33f3c25dfd010001000000010000000000000000000000000000000000000000000000000000000000000000ffffffff0704ffff001d014dffffffff0100f2052a01000000434104e70a02f5af48a1989bf630d92523c9d14c45c75f7d1b998e962bff6ff9995fc5bdb44f1793b37495d80324acba7c8f537caaf8432b8d47987313060cc82d8a93ac00000000

petertodd commented at 4:58 PM on August 25, 2013: contributor

@sipa With the pull-tester I suspect what happened was it just expected the block to fail, so this patch just makes it fail for a different reason.

gavinandresen commented at 11:55 PM on August 25, 2013: contributor

@sip @petertodd : Sipa is right, this should have made the blockchain tester fail at block b64:

        // Check that a block which is (when properly encoded) <= MAX_BLOCK_SIZE is accepted
        // Even when it is encoded with varints that make its encoded size actually > MAX_BLOCK_SIZE
        // -> b39 (11) -> b42 (12) -> b43 (13) -> b53 (14) -> b55 (15) -> b57 (16) -> b60 (17) -> b64 (18)
        //

gavinandresen commented at 12:52 AM on August 27, 2013: contributor

There is a bug in the blockchain tester code; running under the debugger, I'm getting:

02:47:47 10 BitcoindComparisonTool.<init>: Block "b63" completed processing
... I had a conditional breakpoint set to trip with messages > 900,000 bytes, and
on b64 I get:
(gdb) p nMessageSize
$6 = 999999

@TheBlueMatt : I'll need help figuring out how to fix and then recompile the .jar.

TheBlueMatt commented at 1:50 AM on August 29, 2013: member

@gavinandresen My usual method is to import bitcoinj into eclipse and use the export menu from there. It would be easier if it worked in IntelliJ but I have yet to get IntelliJ's jar export to work.

TheBlueMatt commented at 4:49 PM on September 5, 2013: member

@gavinandresen oh, Read the next comment, the signature size is non-deterministic, so try running it again and see if you get it over 1m (I believe you've got a 1/3 shot IIRC).

BitcoinPullTester commented at 12:20 PM on September 7, 2013: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/8dc206a1e2715be83912e039465a049b708b94c1 for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

sipa commented at 2:36 PM on September 29, 2013: member

This still needs some work to understand the pulltester output, I guess?

gavinandresen commented at 10:13 PM on September 30, 2013: contributor

@sipa : I still think there is a bug in pull-tester. I'm torn on whether or not that bug should be fixed before this change goes in, because accepting this pull would just mean removing that pull-tester test (since the purpose of this pull is for the network to reject the thing pull-tester is testing).

gavinandresen referenced this in commit f90b690a0d on Oct 20, 2013

gavinandresen merged this on Oct 20, 2013

gavinandresen closed this on Oct 20, 2013

gavinandresen deleted the branch on Nov 4, 2013

IntegralTeam referenced this in commit dd3977523a on Jun 4, 2019

DrahtBot locked this on Sep 8, 2021