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

theStack · 2020-04-28T18:01:56Z

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

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.

laanwj · 2020-04-29T09:27:31Z

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

maflcko · 2020-04-29T13:31:18Z

ACK 1ad8ea2

src/test/fuzz/bloom_filter.cpp

practicalswift · 2020-04-29T18:29:16Z

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

jnewbery · 2020-05-01T21:12:56Z

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

meshcollider · 2020-05-01T22:48:08Z

utACK 1ad8ea2

fjahr · 2020-05-05T22:44:04Z

Code review ACK 1ad8ea2

Thanks for clarifying this code!

jkczyz · 2020-05-06T06:47:59Z

ACK 1ad8ea2

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

rajarshimaitra · 2020-05-06T07:48:42Z

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 · 2020-05-06T08:38:03Z

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 · 2020-05-06T09:54:52Z

utACK 1ad8ea2

eriknylund · 2020-05-06T16:49:39Z

ACK 1ad8ea2 reviewed changes, built and ran tests.

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

$ test/functional/p2p_filter.py 
2020-05-06T16:50:58.370000Z TestFramework (INFO): Initializing test directory /var/folders/tx/4h1x765x05xd4mkbqgj507dw0000gn/T/bitcoin_func_test_922swrck
2020-05-06T16:51:00.727000Z TestFramework (INFO): Check that too large filter is rejected
2020-05-06T16:51:00.838000Z TestFramework (INFO): Check that too large data element to add to the filter is rejected
2020-05-06T16:51:00.889000Z TestFramework (INFO): Add filtered P2P connection to the node
2020-05-06T16:51:00.942000Z TestFramework (INFO): Check that we receive merkleblock and tx if the filter matches a tx in a block
2020-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
2020-05-06T16:51:01.150000Z TestFramework (INFO): Check that we not receive a tx if the filter does not match a mempool tx
2020-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
2020-05-06T16:51:01.656000Z TestFramework (INFO): Check that after deleting filter all txs get relayed again
2020-05-06T16:51:03.128000Z TestFramework (INFO): Check that request for filtered blocks is ignored if no filter is set
2020-05-06T16:51:03.326000Z TestFramework (INFO): Check that sending "filteradd" if no filter is set is treated as misbehavior
2020-05-06T16:51:03.379000Z TestFramework (INFO): Check that division-by-zero remote crash bug [CVE-2013-5700] is fixed
2020-05-06T16:51:03.543000Z TestFramework (INFO): Stopping nodes
2020-05-06T16:51:03.910000Z TestFramework (INFO): Cleaning up /var/folders/tx/4h1x765x05xd4mkbqgj507dw0000gn/T/bitcoin_func_test_922swrck on exit
2020-05-06T16:51:03.910000Z TestFramework (INFO): Tests successful

eriknylund

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 · 2020-05-06T19:09:50Z

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

practicalswift · 2020-05-06T20:08:31Z

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

jnewbery · 2020-05-06T20:39:42Z

utACK 1ad8ea2

Concept ACK adding the assert, to document the expectations.

theStack · 2020-05-07T10:11:10Z

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 · 2020-05-07T14:27:57Z

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 · 2020-05-07T16:01:18Z

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 · 2020-05-11T16:45:08Z

All three test suites passed here.

…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: ``` 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, 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. 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. ``` Backport of core [[bitcoin/bitcoin#18806 | PR18806]]. Test Plan: ninja all check-all ninja bitcoin-fuzzers ./src/test/fuzz/bloom_filter <path_to_corpus> Reviewers: #bitcoin_abc, PiRK Reviewed By: #bitcoin_abc, PiRK Differential Revision: https://reviews.bitcoinabc.org/D9051

Backport bloom filter improvements Cherry-picked from the following upstream PRs: - bitcoin/bitcoin#7113 - bitcoin/bitcoin#7818 - Only the second commit (to resolve conflicts). - bitcoin/bitcoin#7934 - bitcoin/bitcoin#8655 - Partial backport to help resolve conflicts. - bitcoin/bitcoin#9060 - bitcoin/bitcoin#9223 - bitcoin/bitcoin#9644 - Partial backport to help resolve conflicts. - bitcoin/bitcoin#9916 - bitcoin/bitcoin#9750 - bitcoin/bitcoin#13176 - bitcoin/bitcoin#13948 - bitcoin/bitcoin#16073 - bitcoin/bitcoin#18670 - bitcoin/bitcoin#18806 - Reveals upstream's covert fix for CVE-2013-5700. - bitcoin/bitcoin#19968

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

1ad8ea2

DrahtBot added P2P Tests labels Apr 28, 2020

maflcko removed the Tests label Apr 28, 2020

practicalswift reviewed Apr 29, 2020

View reviewed changes

src/test/fuzz/bloom_filter.cpp Show resolved Hide resolved

jnewbery added the Review club label May 1, 2020

fanquake merged commit 551dc7f into bitcoin:master May 6, 2020

eriknylund reviewed May 6, 2020

View reviewed changes

theStack deleted the 20200428-net-clarify-divide-by-zero-fix branch December 1, 2020 09:55

str4d mentioned this pull request Mar 5, 2021

Backport bloom filter improvements zcash/zcash#5026

Merged

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

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

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

Uh oh!

Conversation

theStack commented Apr 28, 2020

Uh oh!

laanwj commented Apr 29, 2020

Uh oh!

maflcko commented Apr 29, 2020

Uh oh!

Uh oh!

practicalswift commented Apr 29, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jnewbery commented May 1, 2020

Uh oh!

meshcollider commented May 1, 2020

Uh oh!

fjahr commented May 5, 2020

Uh oh!

jkczyz commented May 6, 2020

Uh oh!

rajarshimaitra commented May 6, 2020

Uh oh!

fjahr commented May 6, 2020

Uh oh!

vasild commented May 6, 2020

Uh oh!

eriknylund commented May 6, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

eriknylund left a comment

Choose a reason for hiding this comment

Uh oh!

vasild commented May 6, 2020

Uh oh!

practicalswift commented May 6, 2020

Uh oh!

jnewbery commented May 6, 2020

Uh oh!

theStack commented May 7, 2020

Uh oh!

eriknylund commented May 7, 2020

Uh oh!

sipa commented May 7, 2020

Uh oh!

ThomasBucaioni commented May 11, 2020

Uh oh!

Uh oh!

practicalswift commented Apr 29, 2020 •

edited

Loading

eriknylund commented May 6, 2020 •

edited

Loading