Merge #18991: Cache responses to GETADDR to prevent topology leaks

3bd67ba5a4ef3c20ef1f873b63c9f53a6c8608b6 Test addr response caching (Gleb Naumenko)
cf1569e074505dbbb9d29422803dd31bb62072d4 Add addr permission flag enabling non-cached addr sharing (Gleb Naumenko)
acd6135b43941fa51d52f5fcdb2ce944280ad01e Cache responses to addr requests (Gleb Naumenko)
7cc0e8101f01891aa8be093a00d993bb7579c385 Remove useless 2500 limit on AddrMan queries (Gleb Naumenko)
ded742bc5b96e3215d69c11fb3628d224e7ae034 Move filtering banned addrs inside GetAddresses() (Gleb Naumenko)

Pull request description:

  This is a very simple code change with a big p2p privacy benefit.

  It’s currently trivial to scrape any reachable node’s AddrMan (a database of all nodes known to them along with the timestamps).
  We do have a limit of one GETADDR per connection, but a spy can disconnect and reconnect even from the same IP, and send GETADDR again and again.

  Since we respond with 1,000 random records at most, depending on the AddrMan size it takes probably up to 100 requests for an spy to make sure they scraped (almost) everything.
  I even have a script for that. It is totally doable within couple minutes.

  Then, with some extra protocol knowledge a spy can infer the direct peers of the victim, and other topological stuff.

  I suggest to cache responses to GETADDR on a daily basis, so that an attacker gets at most 1,000 records per day, and can’t track the changes in real time. I will be following up with more improvements to addr relay privacy, but this one alone is a very effective. And simple!

  I doubt any of the real software does *reconnect to get new addrs from a given peer*, so we shouldn’t be cutting anyone.
  I also believe it doesn’t have any negative implications on the overall topology quality. And the records being “outdated” for at most a day doesn’t break any honest assumptions either.

ACKs for top commit:
  jnewbery:
    reACK 3bd67ba5a4ef3c20ef1f873b63c9f53a6c8608b6
  promag:
    Code review ACK 3bd67ba5a4ef3c20ef1f873b63c9f53a6c8608b6.
  ariard:
    Code Review ACK 3bd67ba

Tree-SHA512: dfa5d03205c2424e40a3f8a41af9306227e1ca18beead3b3dda44aa2a082175bb1c6d929dbc7ea8e48e01aed0d50f0d54491caa1147471a2b72a46c3ca06b66f

11 files changed, 183 insertions, 13 deletions

diff --git a/src/addrman.h b/src/addrman.h
index 8e82020df0..9e742339db 100644
--- a/src/addrman.h
+++ b/src/addrman.h
@@ -157,7 +157,7 @@ public:
 #define ADDRMAN_GETADDR_MAX_PCT 23
 
 //! the maximum number of nodes to return in a getaddr call
-#define ADDRMAN_GETADDR_MAX 2500
+#define ADDRMAN_GETADDR_MAX 1000
 
 //! Convenience
 #define ADDRMAN_TRIED_BUCKET_COUNT (1 << ADDRMAN_TRIED_BUCKET_COUNT_LOG2)
diff --git a/src/net.cpp b/src/net.cpp
index 0c56cddbdc..bf29d928a1 100644
--- a/src/net.cpp
+++ b/src/net.cpp
@@ -2530,7 +2530,24 @@ void CConnman::AddNewAddresses(const std::vector<CAddress>& vAddr, const CAddres
 
 std::vector<CAddress> CConnman::GetAddresses()
 {
-    return addrman.GetAddr();
+    std::vector<CAddress> addresses = addrman.GetAddr();
+    if (m_banman) {
+        addresses.erase(std::remove_if(addresses.begin(), addresses.end(),
+                        [this](const CAddress& addr){return m_banman->IsDiscouraged(addr) || m_banman->IsBanned(addr);}),
+                        addresses.end());
+    }
+    return addresses;
+}
+
+std::vector<CAddress> CConnman::GetAddresses(Network requestor_network)
+{
+    const auto current_time = GetTime<std::chrono::microseconds>();
+    if (m_addr_response_caches.find(requestor_network) == m_addr_response_caches.end() ||
+        m_addr_response_caches[requestor_network].m_update_addr_response < current_time) {
+        m_addr_response_caches[requestor_network].m_addrs_response_cache = GetAddresses();
+        m_addr_response_caches[requestor_network].m_update_addr_response = current_time + std::chrono::hours(21) + GetRandMillis(std::chrono::hours(6));
+    }
+    return m_addr_response_caches[requestor_network].m_addrs_response_cache;
 }
 
 bool CConnman::AddNode(const std::string& strNode)
diff --git a/src/net.h b/src/net.h
index 17d8fda372..1c558ee810 100644
--- a/src/net.h
+++ b/src/net.h
@@ -27,6 +27,7 @@
 #include <atomic>
 #include <cstdint>
 #include <deque>
+#include <map>
 #include <thread>
 #include <memory>
 #include <condition_variable>
@@ -52,6 +53,9 @@ static const int TIMEOUT_INTERVAL = 20 * 60;
 static const int FEELER_INTERVAL = 120;
 /** The maximum number of new addresses to accumulate before announcing. */
 static const unsigned int MAX_ADDR_TO_SEND = 1000;
+// TODO: remove ADDRMAN_GETADDR_MAX and let the caller specify this limit with MAX_ADDR_TO_SEND.
+static_assert(MAX_ADDR_TO_SEND == ADDRMAN_GETADDR_MAX,
+    "Max allowed ADDR message size should be equal to the max number of records returned from AddrMan.");
 /** Maximum length of incoming protocol messages (no message over 4 MB is currently acceptable). */
 static const unsigned int MAX_PROTOCOL_MESSAGE_LENGTH = 4 * 1000 * 1000;
 /** Maximum length of the user agent string in `version` message */
@@ -251,6 +255,13 @@ public:
     void MarkAddressGood(const CAddress& addr);
     void AddNewAddresses(const std::vector<CAddress>& vAddr, const CAddress& addrFrom, int64_t nTimePenalty = 0);
     std::vector<CAddress> GetAddresses();
+    /**
+     * Cache is used to minimize topology leaks, so it should
+     * be used for all non-trusted calls, for example, p2p.
+     * A non-malicious call (from RPC or a peer with addr permission) should
+     * call the function without a parameter to avoid using the cache.
+     */
+    std::vector<CAddress> GetAddresses(Network requestor_network);
 
     // This allows temporarily exceeding m_max_outbound_full_relay, with the goal of finding
     // a peer that is better than all our current peers.
@@ -416,6 +427,29 @@ private:
     unsigned int nPrevNodeCount{0};
 
     /**
+     * Cache responses to addr requests to minimize privacy leak.
+     * Attack example: scraping addrs in real-time may allow an attacker
+     * to infer new connections of the victim by detecting new records
+     * with fresh timestamps (per self-announcement).
+     */
+    struct CachedAddrResponse {
+        std::vector<CAddress> m_addrs_response_cache;
+        std::chrono::microseconds m_update_addr_response{0};
+    };
+
+    /**
+     * Addr responses stored in different caches
+     * per network prevent cross-network node identification.
+     * If a node for example is multi-homed under Tor and IPv6,
+     * a single cache (or no cache at all) would let an attacker
+     * to easily detect that it is the same node by comparing responses.
+     * The used memory equals to 1000 CAddress records (or around 32 bytes) per
+     * distinct Network (up to 5) we have/had an inbound peer from,
+     * resulting in at most ~160 KB.
+     */
+    std::map<Network, CachedAddrResponse> m_addr_response_caches;
+
+    /**
      * Services this instance offers.
      *
      * This data is replicated in each CNode instance we create during peer
diff --git a/src/net_permissions.cpp b/src/net_permissions.cpp
index a75838307c..53648deb40 100644
--- a/src/net_permissions.cpp
+++ b/src/net_permissions.cpp
@@ -15,6 +15,7 @@ const std::vector<std::string> NET_PERMISSIONS_DOC{
     "relay (relay even in -blocksonly mode)",
     "mempool (allow requesting BIP35 mempool contents)",
     "download (allow getheaders during IBD, no disconnect after maxuploadtarget limit)",
+    "addr (responses to GETADDR avoid hitting the cache and contain random records with the most up-to-date info)"
 };
 
 namespace {
@@ -50,6 +51,7 @@ bool TryParsePermissionFlags(const std::string str, NetPermissionFlags& output,
             else if (permission == "download") NetPermissions::AddFlag(flags, PF_DOWNLOAD);
             else if (permission == "all") NetPermissions::AddFlag(flags, PF_ALL);
             else if (permission == "relay") NetPermissions::AddFlag(flags, PF_RELAY);
+            else if (permission == "addr") NetPermissions::AddFlag(flags, PF_ADDR);
             else if (permission.length() == 0); // Allow empty entries
             else {
                 error = strprintf(_("Invalid P2P permission: '%s'"), permission);
@@ -75,6 +77,7 @@ std::vector<std::string> NetPermissions::ToStrings(NetPermissionFlags flags)
     if (NetPermissions::HasFlag(flags, PF_RELAY)) strings.push_back("relay");
     if (NetPermissions::HasFlag(flags, PF_MEMPOOL)) strings.push_back("mempool");
     if (NetPermissions::HasFlag(flags, PF_DOWNLOAD)) strings.push_back("download");
+    if (NetPermissions::HasFlag(flags, PF_ADDR)) strings.push_back("addr");
     return strings;
 }
 
diff --git a/src/net_permissions.h b/src/net_permissions.h
index a9633ee2ae..5b68f635a7 100644
--- a/src/net_permissions.h
+++ b/src/net_permissions.h
@@ -29,10 +29,12 @@ enum NetPermissionFlags {
     PF_NOBAN = (1U << 4) | PF_DOWNLOAD,
     // Can query the mempool
     PF_MEMPOOL = (1U << 5),
+    // Can request addrs without hitting a privacy-preserving cache
+    PF_ADDR = (1U << 7),
 
     // True if the user did not specifically set fine grained permissions
     PF_ISIMPLICIT = (1U << 31),
-    PF_ALL = PF_BLOOMFILTER | PF_FORCERELAY | PF_RELAY | PF_NOBAN | PF_MEMPOOL | PF_DOWNLOAD,
+    PF_ALL = PF_BLOOMFILTER | PF_FORCERELAY | PF_RELAY | PF_NOBAN | PF_MEMPOOL | PF_DOWNLOAD | PF_ADDR,
 };
 
 class NetPermissions
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
index 88e73cd804..c503a97be5 100644
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -2541,7 +2541,7 @@ void ProcessMessage(
         if (!pfrom.IsAddrRelayPeer()) {
             return;
         }
-        if (vAddr.size() > 1000)
+        if (vAddr.size() > MAX_ADDR_TO_SEND)
         {
             LOCK(cs_main);
             Misbehaving(pfrom.GetId(), 20, strprintf("addr message size = %u", vAddr.size()));
@@ -3474,13 +3474,15 @@ void ProcessMessage(
         pfrom.fSentAddr = true;
 
         pfrom.vAddrToSend.clear();
-        std::vector<CAddress> vAddr = connman.GetAddresses();
+        std::vector<CAddress> vAddr;
+        if (pfrom.HasPermission(PF_ADDR)) {
+            vAddr = connman.GetAddresses();
+        } else {
+            vAddr = connman.GetAddresses(pfrom.addr.GetNetwork());
+        }
         FastRandomContext insecure_rand;
         for (const CAddress &addr : vAddr) {
-            bool banned_or_discouraged = banman && (banman->IsDiscouraged(addr) || banman->IsBanned(addr));
-            if (!banned_or_discouraged) {
-                pfrom.PushAddress(addr, insecure_rand);
-            }
+            pfrom.PushAddress(addr, insecure_rand);
         }
         return;
     }
@@ -4079,8 +4081,8 @@ bool PeerLogicValidation::SendMessages(CNode* pto)
                 {
                     pto->m_addr_known->insert(addr.GetKey());
                     vAddr.push_back(addr);
-                    // receiver rejects addr messages larger than 1000
-                    if (vAddr.size() >= 1000)
+                    // receiver rejects addr messages larger than MAX_ADDR_TO_SEND
+                    if (vAddr.size() >= MAX_ADDR_TO_SEND)
                     {
                         connman->PushMessage(pto, msgMaker.Make(NetMsgType::ADDR, vAddr));
                         vAddr.clear();
diff --git a/src/test/fuzz/net_permissions.cpp b/src/test/fuzz/net_permissions.cpp
index ae531f4462..8a674ac1e9 100644
--- a/src/test/fuzz/net_permissions.cpp
+++ b/src/test/fuzz/net_permissions.cpp
@@ -24,6 +24,7 @@ void test_one_input(const std::vector<uint8_t>& buffer)
                                                                                              NetPermissionFlags::PF_FORCERELAY,
                                                                                              NetPermissionFlags::PF_NOBAN,
                                                                                              NetPermissionFlags::PF_MEMPOOL,
+                                                                                             NetPermissionFlags::PF_ADDR,
                                                                                              NetPermissionFlags::PF_ISIMPLICIT,
                                                                                              NetPermissionFlags::PF_ALL,
                                                                                          }) :
diff --git a/src/test/netbase_tests.cpp b/src/test/netbase_tests.cpp
index 591b4ce49a..49073ea657 100644
--- a/src/test/netbase_tests.cpp
+++ b/src/test/netbase_tests.cpp
@@ -406,13 +406,14 @@ BOOST_AUTO_TEST_CASE(netpermissions_test)
     BOOST_CHECK(NetWhitelistPermissions::TryParse("bloom,forcerelay,noban,relay,mempool@1.2.3.4/32", whitelistPermissions, error));
 
     const auto strings = NetPermissions::ToStrings(PF_ALL);
-    BOOST_CHECK_EQUAL(strings.size(), 6U);
+    BOOST_CHECK_EQUAL(strings.size(), 7U);
     BOOST_CHECK(std::find(strings.begin(), strings.end(), "bloomfilter") != strings.end());
     BOOST_CHECK(std::find(strings.begin(), strings.end(), "forcerelay") != strings.end());
     BOOST_CHECK(std::find(strings.begin(), strings.end(), "relay") != strings.end());
     BOOST_CHECK(std::find(strings.begin(), strings.end(), "noban") != strings.end());
     BOOST_CHECK(std::find(strings.begin(), strings.end(), "mempool") != strings.end());
     BOOST_CHECK(std::find(strings.begin(), strings.end(), "download") != strings.end());
+    BOOST_CHECK(std::find(strings.begin(), strings.end(), "addr") != strings.end());
 }
 
 BOOST_AUTO_TEST_CASE(netbase_dont_resolve_strings_with_embedded_nul_characters)
diff --git a/test/functional/p2p_getaddr_caching.py b/test/functional/p2p_getaddr_caching.py
new file mode 100755
index 0000000000..c9278eab92
--- /dev/null
+++ b/test/functional/p2p_getaddr_caching.py
@@ -0,0 +1,109 @@
+#!/usr/bin/env python3
+# Copyright (c) 2020 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+"""Test addr response caching"""
+
+import time
+from test_framework.messages import (
+    CAddress,
+    NODE_NETWORK,
+    NODE_WITNESS,
+    msg_addr,
+    msg_getaddr,
+)
+from test_framework.mininode import (
+    P2PInterface,
+    mininode_lock
+)
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import (
+    assert_equal,
+)
+
+MAX_ADDR_TO_SEND = 1000
+
+def gen_addrs(n):
+    addrs = []
+    for i in range(n):
+        addr = CAddress()
+        addr.time = int(time.time())
+        addr.nServices = NODE_NETWORK | NODE_WITNESS
+        # Use first octets to occupy different AddrMan buckets
+        first_octet = i >> 8
+        second_octet = i % 256
+        addr.ip = "{}.{}.1.1".format(first_octet, second_octet)
+        addr.port = 8333
+        addrs.append(addr)
+    return addrs
+
+class AddrReceiver(P2PInterface):
+
+    def __init__(self):
+        super().__init__()
+        self.received_addrs = None
+
+    def get_received_addrs(self):
+        with mininode_lock:
+            return self.received_addrs
+
+    def on_addr(self, message):
+        self.received_addrs = []
+        for addr in message.addrs:
+            self.received_addrs.append(addr.ip)
+
+    def addr_received(self):
+        return self.received_addrs is not None
+
+
+class AddrTest(BitcoinTestFramework):
+    def set_test_params(self):
+        self.setup_clean_chain = False
+        self.num_nodes = 1
+
+    def run_test(self):
+        self.log.info('Create connection that sends and requests addr messages')
+        addr_source = self.nodes[0].add_p2p_connection(P2PInterface())
+
+        msg_send_addrs = msg_addr()
+        self.log.info('Fill peer AddrMan with a lot of records')
+        # Since these addrs are sent from the same source, not all of them will be stored,
+        # because we allocate a limited number of AddrMan buckets per addr source.
+        total_addrs = 10000
+        addrs = gen_addrs(total_addrs)
+        for i in range(int(total_addrs/MAX_ADDR_TO_SEND)):
+            msg_send_addrs.addrs = addrs[i * MAX_ADDR_TO_SEND:(i + 1) * MAX_ADDR_TO_SEND]
+            addr_source.send_and_ping(msg_send_addrs)
+
+        responses = []
+        self.log.info('Send many addr requests within short time to receive same response')
+        N = 5
+        cur_mock_time = int(time.time())
+        for i in range(N):
+            addr_receiver = self.nodes[0].add_p2p_connection(AddrReceiver())
+            addr_receiver.send_and_ping(msg_getaddr())
+            # Trigger response
+            cur_mock_time += 5 * 60
+            self.nodes[0].setmocktime(cur_mock_time)
+            addr_receiver.wait_until(addr_receiver.addr_received)
+            responses.append(addr_receiver.get_received_addrs())
+        for response in responses[1:]:
+            assert_equal(response, responses[0])
+        assert(len(response) < MAX_ADDR_TO_SEND)
+
+        cur_mock_time += 3 * 24 * 60 * 60
+        self.nodes[0].setmocktime(cur_mock_time)
+
+        self.log.info('After time passed, see a new response to addr request')
+        last_addr_receiver = self.nodes[0].add_p2p_connection(AddrReceiver())
+        last_addr_receiver.send_and_ping(msg_getaddr())
+        # Trigger response
+        cur_mock_time += 5 * 60
+        self.nodes[0].setmocktime(cur_mock_time)
+        last_addr_receiver.wait_until(last_addr_receiver.addr_received)
+        # new response is different
+        assert(set(responses[0]) != set(last_addr_receiver.get_received_addrs()))
+
+
+if __name__ == '__main__':
+    AddrTest().main()
diff --git a/test/functional/p2p_permissions.py b/test/functional/p2p_permissions.py
index 32a795e345..254352c816 100755
--- a/test/functional/p2p_permissions.py
+++ b/test/functional/p2p_permissions.py
@@ -96,7 +96,7 @@ class P2PPermissionsTests(BitcoinTestFramework):
         self.checkpermission(
             # all permission added
             ["-whitelist=all@127.0.0.1"],
-            ["forcerelay", "noban", "mempool", "bloomfilter", "relay", "download"],
+            ["forcerelay", "noban", "mempool", "bloomfilter", "relay", "download", "addr"],
             False)
 
         self.stop_node(1)
diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py
index 95c2b7c5ec..b090e93394 100755
--- a/test/functional/test_runner.py
+++ b/test/functional/test_runner.py
@@ -159,6 +159,7 @@ BASE_SCRIPTS = [
     'rpc_deprecated.py',
     'wallet_disable.py',
     'p2p_addr_relay.py',
+    'p2p_getaddr_caching.py',
     'p2p_getdata.py',
     'rpc_net.py',
     'wallet_keypool.py',