addrman: change internal id counting to int64_t #30568

pull mzumsande wants to merge 2 commits into bitcoin:master from mzumsande:202408_addrman_int changing 3 files +45 −37
  1. 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.

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

  3. DrahtBot added the label P2P on Aug 1, 2024
  4. 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.
  5. mzumsande marked this as a draft on Aug 1, 2024
  6. dergoegge commented at 6:17 pm on August 1, 2024: member
    Concept ACK
  7. mzumsande force-pushed on Aug 1, 2024
  8. mzumsande renamed this:
    addrman: change counter to uint64_t
    addrman: change internal id counting to int64_t
    on Aug 1, 2024
  9. mzumsande force-pushed on Aug 1, 2024
  10. mzumsande force-pushed on Aug 1, 2024
  11. DrahtBot added the label CI failed on Aug 1, 2024
  12. brunoerg commented at 7:38 pm on August 1, 2024: contributor
    Concept ACK
  13. DrahtBot removed the label CI failed on Aug 1, 2024
  14. mzumsande force-pushed on Aug 1, 2024
  15. 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.
  16. mzumsande marked this as ready for review on Aug 1, 2024
  17. BrandonOdiwuor commented at 12:39 pm on August 2, 2024: contributor
    Concept ACK
  18. glozow added the label Refactoring on Aug 2, 2024
  19. 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.
  20. hebasto commented at 4:23 pm on August 2, 2024: member
    Concept ACK.
  21. 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().
  22. stratospher commented at 6:05 pm on August 10, 2024: contributor
  23. mzumsande force-pushed on Aug 12, 2024
  24. mzumsande commented at 3:29 pm on August 12, 2024: contributor

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

    Good catch, fixed!

  25. 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.
  26. 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.

  27. 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)
    
  28. 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.

  29. tdb3 commented at 8:56 pm on August 18, 2024: contributor
    Approach ACK Reviewed a bit more. Just nits.
  30. 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
  31. 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
  32. mzumsande force-pushed on Aug 30, 2024
  33. 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.

  34. DrahtBot added the label CI failed on Sep 8, 2024
  35. DrahtBot removed the label CI failed on Sep 9, 2024
  36. 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.

  37. DrahtBot requested review from brunoerg on Sep 10, 2024
  38. DrahtBot requested review from stratospher on Sep 10, 2024
  39. DrahtBot requested review from hebasto on Sep 10, 2024
  40. DrahtBot requested review from dergoegge on Sep 10, 2024
  41. DrahtBot requested review from BrandonOdiwuor on Sep 10, 2024
  42. DrahtBot requested review from tdb3 on Sep 10, 2024
  43. 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.
  44. achow101 commented at 4:48 pm on September 20, 2024: member
    ACK 51f7668d31e2624e41c7ce77fe33162802808f3f
  45. achow101 merged this on Sep 20, 2024
  46. achow101 closed this on Sep 20, 2024

  47. mzumsande deleted the branch on Oct 1, 2024

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-09 06:12 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me