test: add BIP37 remote crash bug [CVE-2013-5700] test to p2p_filter.py #18515

theStack · 2020-04-03T14:44:04Z

Integrates the missing message type filteradd to the test framework and checks that the BIP37 implementation is not vulnerable to the "remote crash bug" CVE-2013-5700 anymore. Prior to v.0.8.4, it was possible to trigger a division-by-zero error on the following line in the function CBloomFilter::Hash():

bitcoin/src/bloom.cpp

Line 45 in f0d6487

    
           return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8);

By setting a zero-length filter via filterload, vData.size() is 0, so the modulo operation above, called on any .insert() or .contains() operation then crashed the node. The test uses the approach of just sending an arbitrary filteradd message after, which calls CBloomFilter::insert() (and in turn CBloomFilter::Hash()) on the node. The vulnerability was fixed by commit 37c6389 (an intentional covert fix, according to gmaxwell), which introduced flags isEmpty/isFull that wouldn't call the Hash() member function if isFull is true (set to true by default constructor).

To validate that the test fails if the implementation is vulnerable, one can simply set the flags to false in the member function UpdateEmptyFull() (that is called after a filter received via filterload is constructed), which activates the vulnerable code path calling Hash in any case on adding or testing for data in the filter:

diff --git a/src/bloom.cpp b/src/bloom.cpp
index bd6069b..ef294a3 100644
--- a/src/bloom.cpp
+++ b/src/bloom.cpp
@@ -199,8 +199,8 @@ void CBloomFilter::UpdateEmptyFull()
         full &= vData[i] == 0xff;
         empty &= vData[i] == 0;
     }
-    isFull = full;
-    isEmpty = empty;
+    isFull = false;
+    isEmpty = false;
 }

Resulting in:

$ ./p2p_filter.py
[...]
2020-04-03T14:38:59.593000Z TestFramework (INFO): Check that division-by-zero remote crash bug [CVE-2013-5700] is fixed
2020-04-03T14:38:59.695000Z TestFramework (ERROR): Assertion failed
[...]
[... some exceptions following ...]

naumenkogs · 2020-04-03T14:56:57Z

utACK 0ed2d8e

sipa · 2020-04-03T17:04:40Z

Code review ACK. I think this is exactly right.

practicalswift · 2020-04-04T14:13:06Z

Concept ACK

Regression testing is good. Regression testing CVE bugs is great :)

If you have time: please add more CVE regression tests like this :)

maflcko · 2020-04-05T13:16:36Z

ACK. I've also written a fuzz test that can find this issue in less than a week of CPU time: #18521

theStack · 2020-04-06T10:05:23Z

@practicalswift: Thanks, my plan is indeed to analyze other CVEs as well and see if regression tests can be added (my assumption is that it's unlikely that others can triggered as simple as sending a pair of messages, but anyway it will be an interesting lesson, digging in the history of Bitcoin Core ;-))
@MarcoFalke: That's interesting, I guess I'm still underestimating how powerful fuzzing can be!

…rload'..'filterclear') a9ecbdf test: add more inactive filter tests to p2p_filter.py (Sebastian Falbesoner) 5eae034 net: limit BIP37 filter lifespan (active between 'filterload' and 'filterclear') (Sebastian Falbesoner) Pull request description: This PR fixes #18483. On the master branch, there is currently _always_ a BIP37 filter set for every peer: if not a specific filter is set through a `filterload` message, a default match-everything filter is instanciated and pointed to via the `CBloomFilter` default constructor; that happens both initially, when the containing structure `TxRelay` is constructed: https://github.com/bitcoin/bitcoin/blob/c0b389b33516fb3eaaad7c30bd11dba768882a7e/src/net.h#L812 and after a loaded filter is removed again through a `filterclear` message: https://github.com/bitcoin/bitcoin/blob/c0b389b33516fb3eaaad7c30bd11dba768882a7e/src/net_processing.cpp#L3201 The behaviour was introduced by commit 37c6389 (an intentional covert fix for [CVE-2013-5700](#18515), according to gmaxwell). This default match-everything filter leads to some unintended side-effects: 1. `getdata` request for filtered blocks (i.e. type `MSG_FILTERED_BLOCK`) are always responded to with `merkleblock`s, even if no filter was set by the peer, see issue #18483 (strictly speaking, this is a violation of BIP37) https://github.com/bitcoin/bitcoin/blob/c0b389b33516fb3eaaad7c30bd11dba768882a7e/src/net_processing.cpp#L1504-L1507 2. if a peer sends a `filteradd` message without having loaded a filter via `filterload` before, the intended increasing of the banscore never happens (triggered if `bad` is set to true, a few lines below) https://github.com/bitcoin/bitcoin/blob/c0b389b33516fb3eaaad7c30bd11dba768882a7e/src/net_processing.cpp#L3182-L3186 This PR basically activates the `else`-branch code paths for all checks of `pfilter` again (on the master branch, they are dead code) by limiting the pointer's lifespan: instead of always having a filter set, the `pfilter` is only pointing to a `CBloomFilter`-instance after receiving a `filterload` message and the instance is destroyed again (and the pointer nullified) after receiving a `filterclear` message. Here is a before/after comparison in behaviour: | code part / scenario | master branch | PR branch | | --------------------------------------------- | ---------------------------------- | ---------------------------------------------------- | | `getdata` processing for `MSG_FILTERED_BLOCK` | always responds with `merkleblock` | only responds if filter was set via `filterload` | | `filteradd` processing, no filter was loaded | nothing | peer's banscore increases by 100 (i.e. disconnect) | On the other code parts where `pfilter` is checked there is no change in the logic behaviour (except that `CBloomFilter::IsRelevantAndUpdate()` is unnecessarily called and immediately returned in the master branch). Note that the default constructor of `CBloomFilter` is only used for deserializing the received `filterload` message and nowhere else. The PR also contains a functional test checking that sending `getdata` for filtered blocks is ignored by the node if no bloom filter is set. ACKs for top commit: MarcoFalke: re-ACK a9ecbdf, only change is in test code 🕙 Tree-SHA512: 1a656a6d74ccaf628e7fdca063ba63fbab2089e0b6d0a11be9bbd387c2ee6d3230706ff8ffc1a55711481df3d4547137dd7c9d9184d89eaa43ade4927792d0b6

… 'filterload'..'filterclear') a9ecbdf test: add more inactive filter tests to p2p_filter.py (Sebastian Falbesoner) 5eae034 net: limit BIP37 filter lifespan (active between 'filterload' and 'filterclear') (Sebastian Falbesoner) Pull request description: This PR fixes bitcoin#18483. On the master branch, there is currently _always_ a BIP37 filter set for every peer: if not a specific filter is set through a `filterload` message, a default match-everything filter is instanciated and pointed to via the `CBloomFilter` default constructor; that happens both initially, when the containing structure `TxRelay` is constructed: https://github.com/bitcoin/bitcoin/blob/c0b389b33516fb3eaaad7c30bd11dba768882a7e/src/net.h#L812 and after a loaded filter is removed again through a `filterclear` message: https://github.com/bitcoin/bitcoin/blob/c0b389b33516fb3eaaad7c30bd11dba768882a7e/src/net_processing.cpp#L3201 The behaviour was introduced by commit bitcoin@37c6389 (an intentional covert fix for [CVE-2013-5700](bitcoin#18515), according to gmaxwell). This default match-everything filter leads to some unintended side-effects: 1. `getdata` request for filtered blocks (i.e. type `MSG_FILTERED_BLOCK`) are always responded to with `merkleblock`s, even if no filter was set by the peer, see issue bitcoin#18483 (strictly speaking, this is a violation of BIP37) https://github.com/bitcoin/bitcoin/blob/c0b389b33516fb3eaaad7c30bd11dba768882a7e/src/net_processing.cpp#L1504-L1507 2. if a peer sends a `filteradd` message without having loaded a filter via `filterload` before, the intended increasing of the banscore never happens (triggered if `bad` is set to true, a few lines below) https://github.com/bitcoin/bitcoin/blob/c0b389b33516fb3eaaad7c30bd11dba768882a7e/src/net_processing.cpp#L3182-L3186 This PR basically activates the `else`-branch code paths for all checks of `pfilter` again (on the master branch, they are dead code) by limiting the pointer's lifespan: instead of always having a filter set, the `pfilter` is only pointing to a `CBloomFilter`-instance after receiving a `filterload` message and the instance is destroyed again (and the pointer nullified) after receiving a `filterclear` message. Here is a before/after comparison in behaviour: | code part / scenario | master branch | PR branch | | --------------------------------------------- | ---------------------------------- | ---------------------------------------------------- | | `getdata` processing for `MSG_FILTERED_BLOCK` | always responds with `merkleblock` | only responds if filter was set via `filterload` | | `filteradd` processing, no filter was loaded | nothing | peer's banscore increases by 100 (i.e. disconnect) | On the other code parts where `pfilter` is checked there is no change in the logic behaviour (except that `CBloomFilter::IsRelevantAndUpdate()` is unnecessarily called and immediately returned in the master branch). Note that the default constructor of `CBloomFilter` is only used for deserializing the received `filterload` message and nowhere else. The PR also contains a functional test checking that sending `getdata` for filtered blocks is ignored by the node if no bloom filter is set. ACKs for top commit: MarcoFalke: re-ACK a9ecbdf, only change is in test code 🕙 Tree-SHA512: 1a656a6d74ccaf628e7fdca063ba63fbab2089e0b6d0a11be9bbd387c2ee6d3230706ff8ffc1a55711481df3d4547137dd7c9d9184d89eaa43ade4927792d0b6

…rify CVE fix 1ad8ea2 net: remove is{Empty,Full} flags from CBloomFilter, clarify CVE fix (Sebastian Falbesoner) Pull request description: 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 37c6389 by gmaxwell) was a _covert fix_ of [CVE-2013-5700](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2013-5700), a vulnerability that allowed a divide-by-zero remote node crash. According to gmaxwell himself (#9060 (comment)): > 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](https://bitcoincore.reviews/18521.html). 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. ACKs for top commit: meshcollider: utACK 1ad8ea2 laanwj: Concept and code review ACK 1ad8ea2 jkczyz: ACK 1ad8ea2 MarcoFalke: ACK 1ad8ea2 fjahr: Code review ACK 1ad8ea2 Tree-SHA512: 29f7ff9faece0285e11e16c024851f5bcb772dec64118ccc3f9067ec256267ec8e1b1e3105c7de2a72fd122c3b085e8fc840ab8f4e49813f1cc7a444df1867f7

…er, clarify CVE fix 1ad8ea2 net: remove is{Empty,Full} flags from CBloomFilter, clarify CVE fix (Sebastian Falbesoner) Pull request description: 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 bitcoin@37c6389 by gmaxwell) was a _covert fix_ of [CVE-2013-5700](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2013-5700), a vulnerability that allowed a divide-by-zero remote node crash. According to gmaxwell himself (bitcoin#9060 (comment)): > 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 bitcoin#18515 which contains a detailled description and a regression test. It has also been discussed on a [recent PR club meeting on fuzzing](https://bitcoincore.reviews/18521.html). The covert fix code already led to issues and PR based on the wrong assumption that the flags are there for optimization reasons (see bitcoin#16886 and bitcoin#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. ACKs for top commit: meshcollider: utACK 1ad8ea2 laanwj: Concept and code review ACK 1ad8ea2 jkczyz: ACK 1ad8ea2 MarcoFalke: ACK 1ad8ea2 fjahr: Code review ACK 1ad8ea2 Tree-SHA512: 29f7ff9faece0285e11e16c024851f5bcb772dec64118ccc3f9067ec256267ec8e1b1e3105c7de2a72fd122c3b085e8fc840ab8f4e49813f1cc7a444df1867f7

Summary: Integrates the missing message type `filteradd` to the test framework and checks that the BIP37 implementation is not vulnerable to the "remote crash bug" CVE-2013-5700 anymore. This is a Backport of Bitcoin Core [[bitcoin/bitcoin#18515 | PR18515]] Test Plan: `ninja && ./test/functional/test_runner.py` Reviewers: O1 Bitcoin ABC, #bitcoin_abc, Fabien Reviewed By: O1 Bitcoin ABC, #bitcoin_abc, Fabien Differential Revision: https://reviews.bitcoinabc.org/D7546

test: add BIP37 remote crash bug [CVE-2013-5700] test to p2p_filter.py

0ed2d8e

fanquake added the Tests label Apr 3, 2020

maflcko merged commit cf21293 into bitcoin:master Apr 5, 2020

theStack mentioned this pull request Apr 6, 2020

net: limit BIP37 filter lifespan (active between 'filterload'..'filterclear') #18544

Merged

theStack mentioned this pull request Apr 28, 2020

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

Merged

theStack deleted the 20200403-test-check-for-CVE20135700-vuln-in-bip37-tests branch December 1, 2020 09:56

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

test: add BIP37 remote crash bug [CVE-2013-5700] test to p2p_filter.py #18515

test: add BIP37 remote crash bug [CVE-2013-5700] test to p2p_filter.py #18515

Uh oh!

theStack commented Apr 3, 2020

Uh oh!

naumenkogs commented Apr 3, 2020

Uh oh!

sipa commented Apr 3, 2020

Uh oh!

practicalswift commented Apr 4, 2020

Uh oh!

maflcko commented Apr 5, 2020

Uh oh!

theStack commented Apr 6, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

test: add BIP37 remote crash bug [CVE-2013-5700] test to p2p_filter.py #18515

test: add BIP37 remote crash bug [CVE-2013-5700] test to p2p_filter.py #18515

Uh oh!

Conversation

theStack commented Apr 3, 2020

Uh oh!

naumenkogs commented Apr 3, 2020

Uh oh!

sipa commented Apr 3, 2020

Uh oh!

practicalswift commented Apr 4, 2020

Uh oh!

maflcko commented Apr 5, 2020

Uh oh!

theStack commented Apr 6, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants