addrman: change internal id counting to int64

mzumsande commented at 5:01 pm on August 1, 2024: contributor

With nIdCount being incremented for each addr received, an attacker could cause an overflow in the past, see https://bitcoincore.org/en/2024/07/31/disclose-addrman-int-overflow/ Even though that attack was made infeasible indirectly by addr rate-limiting (PR #22387), to be on the safe side and prevent any regressions change the nIds used internally to int64_t. This is being done by first introducing a user-defined type for nIds in the first commit, and then updating it to int64_t (thanks sipa for help with this!).

Note that nId is only used internally, it is not part of the serialization, so peers.dat should not be affected by this.

I assume that the only reason this was not done in the past is to not draw attention to this previously undisclosed issue.

DrahtBot commented at 5:01 pm on August 1, 2024: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	naumenkogs, stratospher, achow101
Concept ACK	dergoegge, brunoerg, BrandonOdiwuor, hebasto, Christewart
Approach ACK	tdb3

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#29536 (fuzz: fuzz connman with non-empty addrman + ASMap by brunoerg)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label P2P on Aug 1, 2024

in src/addrman_impl.h:184 in a11a6d033c outdated

177@@ -178,8 +178,10 @@ class AddrManImpl
178     //! @note Don't increment this. Increment `lowest_compatible` in `Serialize()` instead.
179     static constexpr uint8_t INCOMPATIBILITY_BASE = 32;
180 
181-    //! last used nId
182-    int nIdCount GUARDED_BY(cs){0};
183+    //! last used nId.
184+    //! This used to be an int, making it feasible for attackers to cause an overflow,
185+    //! see https://bitcoincore.org/en/2024/07/31/disclose-addrman-int-overflow/
186+    uint64_t nIdCount GUARDED_BY(cs){0};

hebasto commented at 5:09 pm on August 1, 2024:

Amend the pnId parameter type in AddrManImpl::Create respectively?

mzumsande commented at 5:14 pm on August 1, 2024:

true. It also needs more changes (mapInfo), everywhere where nId is used. I wil put the PR to draft until I have addressed these.

mzumsande commented at 9:59 pm on August 1, 2024:

Should be addressed now.

mzumsande marked this as a draft on Aug 1, 2024

dergoegge commented at 6:17 pm on August 1, 2024: member

Concept ACK

mzumsande force-pushed on Aug 1, 2024

mzumsande renamed this:
~~addrman: change counter to uint64_t~~
addrman: change internal id counting to int64_t
on Aug 1, 2024

mzumsande force-pushed on Aug 1, 2024

DrahtBot added the label CI failed on Aug 1, 2024

brunoerg commented at 7:38 pm on August 1, 2024: contributor

Concept ACK

DrahtBot removed the label CI failed on Aug 1, 2024

mzumsande force-pushed on Aug 1, 2024

mzumsande commented at 9:57 pm on August 1, 2024: contributor

Updated the PR to have a refactor-only commit that introduces a user-defined type for all spots that use nId as an int, and then change that to int64_t in the second commit.

mzumsande marked this as ready for review on Aug 1, 2024

BrandonOdiwuor commented at 12:39 pm on August 2, 2024: contributor

Concept ACK

glozow added the label Refactoring on Aug 2, 2024

in src/addrman_impl.h:40 in e5c7744a98 outdated

31@@ -32,6 +32,13 @@ static constexpr int ADDRMAN_NEW_BUCKET_COUNT{1 << ADDRMAN_NEW_BUCKET_COUNT_LOG2
32 static constexpr int32_t ADDRMAN_BUCKET_SIZE_LOG2{6};
33 static constexpr int ADDRMAN_BUCKET_SIZE{1 << ADDRMAN_BUCKET_SIZE_LOG2};
34 
35+/**
36+ * User-defined type for the internally used nIds
37+ * This used to be int, making it feasible for attackers to cause an overflow,
38+ * see https://bitcoincore.org/en/2024/07/31/disclose-addrman-int-overflow/
39+ */
40+using nid_type = int64_t;

hebasto commented at 4:23 pm on August 2, 2024:

Good to see that a signed type is used, rather than an unsigned one in the initial version of this PR.

mzumsande commented at 4:52 pm on August 2, 2024:

interesting pdf, thanks! In this particular case there was no choice because nIds in vvNew and vvTried are initialised to -1.

hebasto commented at 4:23 pm on August 2, 2024: member

Concept ACK.

in src/addrman.cpp:191 in 9170e28c8c outdated

187@@ -188,7 +188,7 @@ void AddrManImpl::Serialize(Stream& s_) const
188 
189     int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT ^ (1 << 30);
190     s << nUBuckets;
191-    std::unordered_map<int, int> mapUnkIds;
192+    std::unordered_map<nid_type, int> mapUnkIds;

sipa commented at 8:29 pm on August 2, 2024:

I think you’ll want std::vector<std::pair<int, nid_type>> bucket_entries; as well in the serializer below (not strictly necessary as the number can’t actually overflow an int, but morally, the second pair element is an id). Same with const nid_type entry_index{bucket_entry.second}; that’s derived from it (and possibly other places).

mzumsande commented at 9:34 pm on August 5, 2024:

Hmm, can you explain the “morally” part a bit more?

mapUnkIds maps nid_type to an int, let’s call that counter ser_count. ser_count is part of the serialization and is bounded by the limited slots of the addrman tables - even if the internal id would overflow an int, ser_count wouldn’t be affected by that.

During deserialization, ser_count is read into int entry_index (which must be int), and then makes it into bucket_entries and later into vvNew. But I’m unsure when is the best step to convert it into an int64_t - why is it better to already do that in the step entry_index -> bucket_entries rather than the way it is now?

naumenkogs commented at 12:22 pm on September 10, 2024:

I assume this is about the introduced index mismatch at AddrInfo& info = mapInfo[entry_index];, specifically the keys of mapInfo.

It is technically safe because we always go from a narrower type to the wide one… but that’s what is immoral i guess :)

I think it’s fine they way this commit works, at most we could add a comment explaining this mismatch.

stratospher commented at 8:41 am on September 17, 2024:

I’m fine with the version on the branch now because Serialise() and Unserialise() are symmetrical. nIndex is written as int into peers.dat in Serialise() and read as int from peers.dat in Unserialise().

stratospher commented at 6:05 pm on August 10, 2024: contributor

Concept ACK. if you retouch, there’s also: https://github.com/bitcoin/bitcoin/blob/c2d15d993ef06d97d4c117012bda6efa3dcbac45/src/test/fuzz/addrman.cpp#L189

mzumsande force-pushed on Aug 12, 2024

mzumsande commented at 3:29 pm on August 12, 2024: contributor

Concept ACK. if you retouch, there’s also:

Good catch, fixed!

tdb3 commented at 11:46 am on August 15, 2024: contributor

Concept ACK. Briefly reviewed, and will return to review in more detail. Love the approach to introduce nid_type. Makes things safer moving forward.

Christewart commented at 12:44 pm on August 17, 2024: contributor

Concept ACK

So presumably test cases are in #22387 to directly test the vuln?

I had a hard time deciphering what is meant to test the new rate limiting logic in #22387 and what test cases were intended to prevent a regression for being introduced in the future that re-introduces this vulnerability.

stratospher commented at 2:53 pm on August 17, 2024: contributor

I had a hard time deciphering what is meant to test the new rate limiting logic in #22387 and what test cases were intended to prevent a regression for being introduced in the future that re-introduces this vulnerability.

Main thing is to make sure that nId values are distinct. #22387 limits the nId which the addrman can possibly construct(functional tests which test this behaviour). This PR makes the nId space so large (64 bits) that the values are distinct. so even in the absence of the rate limiting mechanism, with this PR the attacker would need to insert > 2**64 addresses to make the node crash.

(you could change the type of nIdCount to int8_t to see the undesirable effects of duplicate nId in action!)

I looked into the assertion crash since I was confused how it happened. Sharing details in case it’s helpful to anyone.

32 bit nIdCount could overflow and wrap around if addr messages were spammed (nIdCount would go from 0 to INT32_MAX, then become negative and go from INT32_MIN to 0 and loop again). So nId’s aren’t distinct anymore. Create() is written with an assumption that every nId it receives is distinct. This line ends up overwriting the nId-> AddrInfo map without checking if it exists. This can lead to corruptions and assertion failures.

An example scenario:

suppose AddrInfo1 with nId=36 is inserted into a bucket-position in vvNew(new table) and mapInfo now contains nId=36 -> AddrInfo1 mapping
when nId=36 happens again (because nId wraps around due to overflow) and another address AddrInfo2 is inserted into the new table, there is no clean deletion of existing nId in vvNew /mapAddr and the nId=36 in vvNew means AddrInfo2 now.
It’s also possible that we don’t want to insert AddrInfo2 into new table and nId=36 address can get deleted later.
when the same bucket-position happens again, and we want to rewrite it’s contents(nId=36) which meant the overwritten old address -> that info isn’t present in mapInfo and nRefCount = 0 (because it got deleted!)
this will cause an assertion failure like the one below and the node crashes.

0bitcoind: addrman.cpp:494: void AddrManImpl::ClearNew(int, int): Assertion `infoDelete.nRefCount > 0' failed.
1Aborted (core dumped)

in src/addrman_impl.h:266 in 1ded29db12 outdated

264@@ -258,7 +265,7 @@ class AddrManImpl
265      *
266      *  @return  int The nid of the entry. If the addrman position is empty or not found, returns -1.

tdb3 commented at 8:28 pm on August 18, 2024:

nit: The return type in the Doxygen content could be adjusted.

0-     * [@return](/bitcoin-bitcoin/contributor/return/)  int The nid of the entry. If the addrman position is empty or not found, returns -1.
1+     * [@return](/bitcoin-bitcoin/contributor/return/)  nid_type The nid of the entry. If the addrman position is empty or not found, returns -1.
2      * */
3     nid_type GetEntry(bool use_tried, size_t bucket, size_t position) const EXCLUSIVE_LOCKS_REQUIRED(cs);

nit / thinking out loud: Returning -1 is a remnant of the previous type being a plain int. To keep with the theme of using the user-defined nid_type, would it be worth creating a macro (or constexpr, or similar) to name the invalid case (e.g. INVALID_NID = -1)? Not sure, as I’m not seeing a need to adjust nid_type to anything more complicated than int64_t, and GetEntry() in this case is just indicating empty/not found.

mzumsande commented at 3:03 pm on August 30, 2024:

Fixed the return type.

Yes, also not sure about INVALID_NID - I don’t really see why we would want to change it from -1 to another value, but happy to add it if others like it… I’ll keep this thread open for a while.

tdb3 commented at 8:56 pm on August 18, 2024: contributor

Approach ACK Reviewed a bit more. Just nits.

addrman, refactor: introduce user-defined type for internal nId

This makes it easier to track which spots refer to an nId
(as opposed to, for example, bucket index etc. which also use int)

Co-authored-by: Pieter Wuille <pieter@wuille.net>

051ba3290e

addrman: change nid_type from int to int64_t

With nId being incremented for each addr received,
an attacker could cause an overflow in the past.
(https://bitcoincore.org/en/2024/07/31/disclose-addrman-int-overflow/)
Even though that attack was made infeasible by
rate-limiting (PR #22387), to be on the safe side change the
type to an int64_t.

51f7668d31

mzumsande force-pushed on Aug 30, 2024

mzumsande commented at 3:06 pm on August 30, 2024: contributor

1ded29d to 51f7668: Rebased and fixed doxygen comment.

So presumably test cases are in #22387 to directly test the vuln?

No, there is no test case that directly tests the vulnerability. For that, we’d need to add approximately 2 * INT_MAX addrs to addrman (see the explanation by @stratospher above) - which I think would be too slow to be practical for the test suite. However, one simple way to recreate the vulnerability (with this branch) is to locally change nid_type to int8_t - if you then run a node, it will crash quickly.

DrahtBot added the label CI failed on Sep 8, 2024

DrahtBot removed the label CI failed on Sep 9, 2024

naumenkogs commented at 12:33 pm on September 10, 2024: member

ACK 51f7668d31e2624e41c7ce77fe33162802808f3f

The reasoning in the original post makes sense, this is an improvement. I reviewed the code visually.

DrahtBot requested review from brunoerg on Sep 10, 2024

DrahtBot requested review from stratospher on Sep 10, 2024

DrahtBot requested review from hebasto on Sep 10, 2024

DrahtBot requested review from dergoegge on Sep 10, 2024

DrahtBot requested review from BrandonOdiwuor on Sep 10, 2024

DrahtBot requested review from tdb3 on Sep 10, 2024

stratospher commented at 8:43 am on September 17, 2024: contributor

ACK 51f7668d31e2624e41c7ce77fe33162802808f3f. I think it’s a good change to make the nId space large(64 bits) so that the nId values are distinct.

achow101 commented at 4:48 pm on September 20, 2024: member

ACK 51f7668d31e2624e41c7ce77fe33162802808f3f

achow101 merged this on Sep 20, 2024

achow101 closed this on Sep 20, 2024

mzumsande deleted the branch on Oct 1, 2024

addrman: change internal id counting to int64_t #30568

Code Coverage

Reviews

Conflicts