net: remove is{Empty,Full} flags from CBloomFilter, clarify CVE fix

theStack commented at 6:01 pm on April 28, 2020: member

The BIP37 bloom filter class CBloomFilter contains two flags isEmpty/isFull together with an update method with the purpose to, according to the comments, “avoid wasting cpu”, i.e. the mechanism should serve as an optimization for the trivial cases of empty (all bits zero) or full (all bits one) filters. However, the real reason of adding those flags (introduced with commit https://github.com/bitcoin/bitcoin/commit/37c6389c5a0ca63ae3573440ecdfe95d28ad8f07 by gmaxwell) was a covert fix of CVE-2013-5700, a vulnerability that allowed a divide-by-zero remote node crash. According to gmaxwell himself (https://github.com/bitcoin/bitcoin/pull/9060#issuecomment-257749165):

the IsEmpty/IsFull optimizations were largely a pretextual optimization intended to make unexploitable a remote crash vulnerability (integer division by zero) that existed in the original bloom filtering code without disclosing it. I’m doubtful that they are all that useful. :)

For more information on how to trigger this crash, see PR #18515 which contains a detailled description and a regression test. It has also been discussed on a recent PR club meeting on fuzzing.

The covert fix code already led to issues and PR based on the wrong assumption that the flags are there for optimization reasons (see #16886 and #16922). This PR gets rid of the flags and the update method and just focuses on the CVE fix itself, i.e. it can be seen as a revert of the covert fix commit modulo the actual fix.

net: remove is{Empty,Full} flags from CBloomFilter, clarify CVE fix 1ad8ea2b73

DrahtBot added the label P2P on Apr 28, 2020

DrahtBot added the label Tests on Apr 28, 2020

MarcoFalke removed the label Tests on Apr 28, 2020

laanwj commented at 9:27 am on April 29, 2020: member

Concept and code review ACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8 Simpler code is better here, and absolutely, the “pretend” reasoning has caused a few people to do unnecessary work here.

MarcoFalke commented at 1:31 pm on April 29, 2020: member

ACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8

in src/test/fuzz/bloom_filter.cpp:28 in 1ad8ea2b73

24@@ -25,7 +25,7 @@ void test_one_input(const std::vector<uint8_t>& buffer)
25         fuzzed_data_provider.ConsumeIntegral<unsigned int>(),
26         static_cast<unsigned char>(fuzzed_data_provider.PickValueInArray({BLOOM_UPDATE_NONE, BLOOM_UPDATE_ALL, BLOOM_UPDATE_P2PUBKEY_ONLY, BLOOM_UPDATE_MASK}))};
27     while (fuzzed_data_provider.remaining_bytes() > 0) {
28-        switch (fuzzed_data_provider.ConsumeIntegralInRange(0, 4)) {
29+        switch (fuzzed_data_provider.ConsumeIntegralInRange(0, 3)) {

practicalswift commented at 6:28 pm on April 29, 2020:

Please keep fuzzed_data_provider.ConsumeIntegralInRange(0, 4) in order to not invalidate the existing seed corpus :)

Edit: Please take this as a nit: not something blocking merge.

MarcoFalke commented at 6:30 pm on April 29, 2020:

I think this is fine. Running the fuzz engine over the existing seeds for a minute or two will adjust the seeds to the new format.

No strong opinion, though.

laanwj commented at 8:24 am on April 30, 2020:

I don’t think we should hold back code changes just to not ‘invalidate the seed corpus’. This is putting the horse behind the cart.

MarcoFalke commented at 11:23 am on April 30, 2020:

And to go even further: Any code change to master is invalidating some seeds. So with the logic applied that we shouldn’t invalidate the existing seeds, we wouldn’t be allowed to do any changes to master anymore.

practicalswift commented at 12:55 pm on April 30, 2020:

The point here is the only effect of from changing 4 to 3 is that it invalidates the existing seed corpus. Not a big deal of course: treat it as a nit :)

Of course no one is suggesting that we should hold back necessary changes to the fuzzers (or to master generally!) in order not to invalidate the seed corpus - that would be silly :)

laanwj commented at 3:17 pm on April 30, 2020:

Okay, yes, I understand your point now.

practicalswift commented at 6:29 pm on April 29, 2020: contributor

Concept ACK ~~but please don’t invalidate the existing seed corpus :)~~

jnewbery added the label Review club on May 1, 2020

jnewbery commented at 9:12 pm on May 1, 2020: member

We’ll cover this in review club next Wednesday: https://bitcoincore.reviews/18806.html

meshcollider commented at 10:48 pm on May 1, 2020: contributor

utACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8

fjahr commented at 10:44 pm on May 5, 2020: member

Code review ACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8

Thanks for clarifying this code!

jkczyz commented at 6:47 am on May 6, 2020: contributor

ACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8

Reviewed and verified tests pass (including p2p_filter functional test which exercises this behavior).

fanquake merged this on May 6, 2020

fanquake closed this on May 6, 2020

rajarshimaitra commented at 7:48 am on May 6, 2020: contributor

Unit tests and functional tests passing (including p2p_filter). Code Review ACK.

Question: It seems this PR reverts almost all the changes of PR 2914 to fix the bug. Why the bug fix was done using is{Empty,Full} flags if it could have been fixed with a simple vData.empty() check in the insert and contains functions?

fjahr commented at 8:38 am on May 6, 2020: member

It seems this PR reverts almost all the changes of PR 2914 to fix the bug. Why the bug fix was done using is{Empty,Full} flags if it could have been fixed with a simple vData.empty() check in the insert and contains functions?

That is the covert part of the fix (together with a misleading commit message and merge process). It made it harder to understand that there was a vulnerability so that attackers don’t find it and use it before most of the network has updated to a version that includes the fix. Once that is the case the vulnerability is made public. This post about a more recent vulnerability should give you more insight into the process: https://bitcoincore.org/en/2019/11/08/CVE-2017-18350/

vasild commented at 9:54 am on May 6, 2020: member

utACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8

eriknylund commented at 4:49 pm on May 6, 2020: contributor

ACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8 reviewed changes, built and ran tests.

Ran functional test p2p_filter which includes test for CVE-2013-5700 fix:

 0$ test/functional/p2p_filter.py 
 12020-05-06T16:50:58.370000Z TestFramework (INFO): Initializing test directory /var/folders/tx/4h1x765x05xd4mkbqgj507dw0000gn/T/bitcoin_func_test_922swrck
 22020-05-06T16:51:00.727000Z TestFramework (INFO): Check that too large filter is rejected
 32020-05-06T16:51:00.838000Z TestFramework (INFO): Check that too large data element to add to the filter is rejected
 42020-05-06T16:51:00.889000Z TestFramework (INFO): Add filtered P2P connection to the node
 52020-05-06T16:51:00.942000Z TestFramework (INFO): Check that we receive merkleblock and tx if the filter matches a tx in a block
 62020-05-06T16:51:01.002000Z TestFramework (INFO): Check that we only receive a merkleblock if the filter does not match a tx in a block
 72020-05-06T16:51:01.150000Z TestFramework (INFO): Check that we not receive a tx if the filter does not match a mempool tx
 82020-05-06T16:51:01.451000Z TestFramework (INFO): Check that we receive a tx in reply to a mempool msg if the filter matches a mempool tx
 92020-05-06T16:51:01.656000Z TestFramework (INFO): Check that after deleting filter all txs get relayed again
102020-05-06T16:51:03.128000Z TestFramework (INFO): Check that request for filtered blocks is ignored if no filter is set
112020-05-06T16:51:03.326000Z TestFramework (INFO): Check that sending "filteradd" if no filter is set is treated as misbehavior
122020-05-06T16:51:03.379000Z TestFramework (INFO): Check that division-by-zero remote crash bug [CVE-2013-5700] is fixed
132020-05-06T16:51:03.543000Z TestFramework (INFO): Stopping nodes
142020-05-06T16:51:03.910000Z TestFramework (INFO): Cleaning up /var/folders/tx/4h1x765x05xd4mkbqgj507dw0000gn/T/bitcoin_func_test_922swrck on exit
152020-05-06T16:51:03.910000Z TestFramework (INFO): Tests successful

eriknylund commented at 5:58 pm on May 6, 2020: contributor

Feedback from nehan and others during the PR review club was to consider adding an assert() in the Hash() method to make sure any caller is informed that a vData.empty() check has been done to make sure vData.size() is not 0.

vasild commented at 7:09 pm on May 6, 2020: member

@eriknylund an assertion failure is not much different than division by zero - both would terminate the program.

practicalswift commented at 8:08 pm on May 6, 2020: contributor

@vasild Division by zero is not guaranteed to terminate the program :)

jnewbery commented at 8:39 pm on May 6, 2020: member

utACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8

Concept ACK adding the assert, to document the expectations.

theStack commented at 10:11 am on May 7, 2020: member

I’m neutral on the idea of adding an assert to Hash() – on one hand it documents expectations, on the other hand there is no point in ever calling the hash function outside of the two operations insert and contains in a bloom filter. Also the performance could decrease a bit if on every single hash calculated (up to 50 per insert/contains operation) an additional assertion condition has to be checked.

eriknylund commented at 2:27 pm on May 7, 2020: contributor

I’m neutral on the idea of adding an assert to Hash() – on one hand it documents expectations, on the other hand there is no point in ever calling the hash function outside of the two operations insert and contains in a bloom filter. Also the performance could decrease a bit if on every single hash calculated (up to 50 per insert/contains operation) an additional assertion condition has to be checked.

I see. Would a simple comment be better suited in this case?

sipa commented at 4:01 pm on May 7, 2020: member

Just a comment/assertion on Hash is arguably insufficient. The code vData[nIndex >> 3] is always invalid when vData is empty, for any value of nIndex - which happens to exactly match the conditions in which Hash is allowed to be called.

ThomasBucaioni commented at 4:45 pm on May 11, 2020: none

All three test suites passed here.

sidhujag referenced this in commit e9d4768e75 on May 12, 2020

theStack deleted the branch on Dec 1, 2020

Fabcien referenced this in commit f614ca7395 on Jan 26, 2021

zkbot referenced this in commit be459619a8 on Mar 5, 2021

zkbot referenced this in commit 78de0cdf46 on Apr 15, 2021

DrahtBot locked this on Feb 15, 2022

net: remove is{Empty,Full} flags from CBloomFilter, clarify CVE fix #18806