CVE-2024-31208: Insufficient Information (NVD-CWE-noinfo)
value: Synapse is an open-source Matrix homeserver. A remote Matrix user with malicious intent, sharing a room with Synapse instances before 1.105.1, can dispatch specially crafted events to exploit a weakness in the V2 state resolution algorithm. This can induce high CPU consumption and accumulate excessive data in the database of such instances, resulting in a denial of service. Servers in private federations, or those that do not federate, are not affected. Server administrators should upgrade to 1.105.1 or later. Some workarounds are available. One can ban the malicious users or ACL block servers from the rooms and/or leave the room and purge the room using the admin API.
CWE description: There is insufficient information about the issue to classify it; details are unkown or unspecified.
Published: 2024-04-23T18:15Z
Repository: https://github.com/element-hq/synapse
Language: Python
Files changed: changelog.d/17044.misc, synapse/storage/databases/main/events.py, synapse/storage/schema/__init__.py, tests/storage/test_event_chain.py
Commit date: 2024-04-23 15:25:49 +0100
Commit message: Fix GHSA-3h7q-rfh9-xm4v

Weakness in auth chain indexing allows DoS from remote room members
through disk fill and high CPU usage.

A remote Matrix user with malicious intent, sharing a room with Synapse
instances before 1.104.1, can dispatch specially crafted events to
exploit a weakness in how the auth chain cover index is calculated. This
can induce high CPU consumption and accumulate excessive data in the
database of such instances, resulting in a denial of service.

Servers in private federations, or those that do not federate, are not
affected.

Diff: diff --git a/changelog.d/17044.misc b/changelog.d/17044.misc
new file mode 100644
index 000000000..a1439752d
--- /dev/null
+++ b/changelog.d/17044.misc
@@ -0,0 +1 @@
+Refactor auth chain fetching to reduce duplication.
diff --git a/synapse/storage/databases/main/events.py b/synapse/storage/databases/main/events.py
index a6fda3f43..1e731d56b 100644
--- a/synapse/storage/databases/main/events.py
+++ b/synapse/storage/databases/main/events.py
@@ -17,10 +17,11 @@
 # <http://www.apache.org/licenses/LICENSE-2.0>.
 #
 # [This file includes modifications made by New Vector Limited]
 #
 #
+import collections
 import itertools
 import logging
 from collections import OrderedDict
 from typing import (
     TYPE_CHECKING,
@@ -51,10 +52,11 @@ from synapse.storage._base import db_to_json, make_in_list_sql_clause
 from synapse.storage.database import (
     DatabasePool,
     LoggingDatabaseConnection,
     LoggingTransaction,
 )
+from synapse.storage.databases.main.event_federation import EventFederationStore
 from synapse.storage.databases.main.events_worker import EventCacheEntry
 from synapse.storage.databases.main.search import SearchEntry
 from synapse.storage.engines import PostgresEngine
 from synapse.storage.util.id_generators import AbstractStreamIdGenerator
 from synapse.storage.util.sequence import SequenceGenerator
@@ -766,44 +768,30 @@ class PersistEventsStore:
         #   1. Fetch the chain ID/sequence numbers of its auth events,
         #      discarding any that are reachable by other auth events, or
         #      that have the same chain ID as the event.
         #   2. For each retained auth event we:
         #       a. Add a link from the event's to the auth event's chain
-        #          ID/sequence number; and
-        #       b. Add a link from the event to every chain reachable by the
-        #          auth event.
+        #          ID/sequence number
 
         # Step 1, fetch all existing links from all the chains we've seen
         # referenced.
         chain_links = _LinkMap()
-        auth_chain_rows = cast(
-            List[Tuple[int, int, int, int]],
-            db_pool.simple_select_many_txn(
-                txn,
-                table="event_auth_chain_links",
-                column="origin_chain_id",
-                iterable={chain_id for chain_id, _ in chain_map.values()},
-                keyvalues={},
-                retcols=(
-                    "origin_chain_id",
-                    "origin_sequence_number",
-                    "target_chain_id",
-                    "target_sequence_number",
-                ),
-            ),
-        )
-        for (
-            origin_chain_id,
-            origin_sequence_number,
-            target_chain_id,
-            target_sequence_number,
-        ) in auth_chain_rows:
-            chain_links.add_link(
-                (origin_chain_id, origin_sequence_number),
-                (target_chain_id, target_sequence_number),
-                new=False,
-            )
+
+        for links in EventFederationStore._get_chain_links(
+            txn, {chain_id for chain_id, _ in chain_map.values()}
+        ):
+            for origin_chain_id, inner_links in links.items():
+                for (
+                    origin_sequence_number,
+                    target_chain_id,
+                    target_sequence_number,
+                ) in inner_links:
+                    chain_links.add_link(
+                        (origin_chain_id, origin_sequence_number),
+                        (target_chain_id, target_sequence_number),
+                        new=False,
+                    )
 
         # We do this in toplogical order to avoid adding redundant links.
         for event_id in sorted_topologically(
             events_to_calc_chain_id_for, event_to_auth_chain
         ):
@@ -834,22 +822,10 @@ class PersistEventsStore:
                 # Step 2a, add link between the event and auth event
                 chain_links.add_link(
                     (chain_id, sequence_number), (auth_chain_id, auth_sequence_number)
                 )
 
-                # Step 2b, add a link to chains reachable from the auth
-                # event.
-                for target_id, target_seq in chain_links.get_links_from(
-                    (auth_chain_id, auth_sequence_number)
-                ):
-                    if target_id == chain_id:
-                        continue
-
-                    chain_links.add_link(
-                        (chain_id, sequence_number), (target_id, target_seq)
-                    )
-
         db_pool.simple_insert_many_txn(
             txn,
             table="event_auth_chain_links",
             keys=(
                 "origin_chain_id",
@@ -2449,35 +2425,10 @@ class _LinkMap:
             self.additions.add((src_chain, src_seq, target_chain, target_seq))
 
         current_links[src_seq] = target_seq
         return True
 
-    def get_links_from(
-        self, src_tuple: Tuple[int, int]
-    ) -> Generator[Tuple[int, int], None, None]:
-        """Gets the chains reachable from the given chain/sequence number.
-
-        Yields:
-            The chain ID and sequence number the link points to.
-        """
-        src_chain, src_seq = src_tuple
-        for target_id, sequence_numbers in self.maps.get(src_chain, {}).items():
-            for link_src_seq, target_seq in sequence_numbers.items():
-                if link_src_seq <= src_seq:
-                    yield target_id, target_seq
-
-    def get_links_between(
-        self, source_chain: int, target_chain: int
-    ) -> Generator[Tuple[int, int], None, None]:
-        """Gets the links between two chains.
-
-        Yields:
-            The source and target sequence numbers.
-        """
-
-        yield from self.maps.get(source_chain, {}).get(target_chain, {}).items()
-
     def get_additions(self) -> Generator[Tuple[int, int, int, int], None, None]:
         """Gets any newly added links.
 
         Yields:
             The source chain ID/sequence number and target chain ID/sequence number
@@ -2500,11 +2451,26 @@ class _LinkMap:
         target_chain, target_seq = target_tuple
 
         if src_chain == target_chain:
             return target_seq <= src_seq
 
-        links = self.get_links_between(src_chain, target_chain)
-        for link_start_seq, link_end_seq in links:
-            if link_start_seq <= src_seq and target_seq <= link_end_seq:
-                return True
+        # We have to graph traverse the links to check for indirect paths.
+        visited_chains = collections.Counter()
+        search = [(src_chain, src_seq)]
+        while search:
+            chain, seq = search.pop()
+            visited_chains[chain] = max(seq, visited_chains[chain])
+            for tc, links in self.maps.get(chain, {}).items():
+                for ss, ts in links.items():
+                    # Don't revisit chains we've already seen, unless the target
+                    # sequence number is higher than last time.
+                    if ts <= visited_chains.get(tc, 0):
+                        continue
+
+                    if ss <= seq:
+                        if tc == target_chain:
+                            if target_seq <= ts:
+                                return True
+                        else:
+                            search.append((tc, ts))
 
         return False
diff --git a/synapse/storage/schema/__init__.py b/synapse/storage/schema/__init__.py
index c0b925444..039aa91b9 100644
--- a/synapse/storage/schema/__init__.py
+++ b/synapse/storage/schema/__init__.py
@@ -130,16 +130,20 @@ Changes in SCHEMA_VERSION = 82
     - The insertion_events, insertion_event_extremities, insertion_event_edges, and
       batch_events tables are no longer purged in preparation for their removal.
 
 Changes in SCHEMA_VERSION = 83
     - The event_txn_id is no longer used.
+
+Changes in SCHEMA_VERSION = 84
+    - No longer assumes that `event_auth_chain_links` holds transitive links, and
+      so read operations must do graph traversal.
 """
 
 
 SCHEMA_COMPAT_VERSION = (
-    # The event_txn_id table and tables from MSC2716 no longer exist.
-    83
+    # Transitive links are no longer written to `event_auth_chain_links`
+    84
 )
 """Limit on how far the synapse codebase can be rolled back without breaking db compat
 
 This value is stored in the database, and checked on startup. If the value in the
 database is greater than SCHEMA_VERSION, then Synapse will refuse to start.
diff --git a/tests/storage/test_event_chain.py b/tests/storage/test_event_chain.py
index 9e4e73832..27d5b0125 100644
--- a/tests/storage/test_event_chain.py
+++ b/tests/storage/test_event_chain.py
@@ -19,10 +19,12 @@
 #
 #
 
 from typing import Dict, List, Set, Tuple, cast
 
+from parameterized import parameterized
+
 from twisted.test.proto_helpers import MemoryReactor
 from twisted.trial import unittest
 
 from synapse.api.constants import EventTypes
 from synapse.api.room_versions import RoomVersions
@@ -43,18 +45,20 @@ from tests.unittest import HomeserverTestCase
 class EventChainStoreTestCase(HomeserverTestCase):
     def prepare(self, reactor: MemoryReactor, clock: Clock, hs: HomeServer) -> None:
         self.store = hs.get_datastores().main
         self._next_stream_ordering = 1
 
-    def test_simple(self) -> None:
+    @parameterized.expand([(False,), (True,)])
+    def test_simple(self, batched: bool) -> None:
         """Test that the example in `docs/auth_chain_difference_algorithm.md`
         works.
         """
 
         event_factory = self.hs.get_event_builder_factory()
         bob = "@creator:test"
         alice = "@alice:test"
+        charlie = "@charlie:test"
         room_id = "!room:test"
 
         # Ensure that we have a rooms entry so that we generate the chain index.
         self.get_success(
             self.store.store_room(
@@ -189,46 +193,74 @@ class EventChainStoreTestCase(HomeserverTestCase):
                     power_2.event_id,
                 ],
             )
         )
 
+        charlie_invite = self.get_success(
+            event_factory.for_room_version(
+                RoomVersions.V6,
+                {
+                    "type": EventTypes.Member,
+                    "state_key": charlie,
+                    "sender": alice,
+                    "room_id": room_id,
+                    "content": {"tag": "charlie_invite"},
+                },
+            ).build(
+                prev_event_ids=[],
+                auth_event_ids=[
+                    create.event_id,
+                    alice_join2.event_id,
+                    power_2.event_id,
+                ],
+            )
+        )
+
         events = [
             create,
             bob_join,
             power,
             alice_invite,
             alice_join,
             bob_join_2,
             power_2,
             alice_join2,
+            charlie_invite,
         ]
 
         expected_links = [
             (bob_join, create),
-            (power, create),
             (power, bob_join),
-            (alice_invite, create),
             (alice_invite, power),
-            (alice_invite, bob_join),
             (bob_join_2, power),
             (alice_join2, power_2),
+            (charlie_invite, alice_join2),
         ]
 
-        self.persist(events)
+        # We either persist as a batch or one-by-one depending on test
+        # parameter.
+        if batched:
+            self.persist(events)
+        else:
+            for event in events:
+                self.persist([event])
+
         chain_map, link_map = self.fetch_chains(events)
 
         # Check that the expected links and only the expected links have been
         # added.
-        self.assertEqual(len(expected_links), len(list(link_map.get_additions())))
-
-        for start, end in expected_links:
-            start_id, start_seq = chain_map[start.event_id]
-            end_id, end_seq = chain_map[end.event_id]
+        event_map = {e.event_id: e for e in events}
+        reverse_chain_map = {v: event_map[k] for k, v in chain_map.items()}
 
-            self.assertIn(
-                (start_seq, end_seq), list(link_map.get_links_between(start_id, end_id))
-            )
+        self.maxDiff = None
+        self.assertCountEqual(
+            expected_links,
+            [
+                (reverse_chain_map[(s1, s2)], reverse_chain_map[(t1, t2)])
+                for s1, s2, t1, t2 in link_map.get_additions()
+            ],
+        )
 
         # Test that everything can reach the create event, but the create event
         # can't reach anything.
         for event in events[1:]:
             self.assertTrue(
@@ -366,28 +398,27 @@ class EventChainStoreTestCase(HomeserverTestCase):
 
         chain_map, link_map = self.fetch_chains(events)
 
         expected_links = [
             (bob_join, create),
-            (power, create),
             (power, bob_join),
-            (alice_invite, create),
             (alice_invite, power),
-            (alice_invite, bob_join),
         ]
 
         # Check that the expected links and only the expected links have been
         # added.
-        self.assertEqual(len(expected_links), len(list(link_map.get_additions())))
+        event_map = {e.event_id: e for e in events}
+        reverse_chain_map = {v: event_map[k] for k, v in chain_map.items()}
 
-        for start, end in expected_links:
-            start_id, start_seq = chain_map[start.event_id]
-            end_id, end_seq = chain_map[end.event_id]
-
-            self.assertIn(
-                (start_seq, end_seq), list(link_map.get_links_between(start_id, end_id))
-            )
+        self.maxDiff = None
+        self.assertCountEqual(
+            expected_links,
+            [
+                (reverse_chain_map[(s1, s2)], reverse_chain_map[(t1, t2)])
+                for s1, s2, t1, t2 in link_map.get_additions()
+            ],
+        )
 
     def persist(
         self,
         events: List[EventBase],
     ) -> None:
@@ -487,32 +518,43 @@ class LinkMapTestCase(unittest.TestCase):
     def test_simple(self) -> None:
         """Basic tests for the LinkMap."""
         link_map = _LinkMap()
 
         link_map.add_link((1, 1), (2, 1), new=False)
-        self.assertCountEqual(link_map.get_links_between(1, 2), [(1, 1)])
-        self.assertCountEqual(link_map.get_links_from((1, 1)), [(2, 1)])
         self.assertCountEqual(link_map.get_additions(), [])
         self.assertTrue(link_map.exists_path_from((1, 5), (2, 1)))
         self.assertFalse(link_map.exists_path_from((1, 5), (2, 2)))
         self.assertTrue(link_map.exists_path_from((1, 5), (1, 1)))
         self.assertFalse(link_map.exists_path_from((1, 1), (1, 5)))
 
         # Attempting to add a redundant link is ignored.
         self.assertFalse(link_map.add_link((1, 4), (2, 1)))
-        self.assertCountEqual(link_map.get_links_between(1, 2), [(1, 1)])
+        self.assertCountEqual(link_map.get_additions(), [])
 
         # Adding new non-redundant links works
         self.assertTrue(link_map.add_link((1, 3), (2, 3)))
-        self.assertCountEqual(link_map.get_links_between(1, 2), [(1, 1), (3, 3)])
+        self.assertCountEqual(link_map.get_additions(), [(1, 3, 2, 3)])
 
         self.assertTrue(link_map.add_link((2, 5), (1, 3)))
-        self.assertCountEqual(link_map.get_links_between(2, 1), [(5, 3)])
-        self.assertCountEqual(link_map.get_links_between(1, 2), [(1, 1), (3, 3)])
-
         self.assertCountEqual(link_map.get_additions(), [(1, 3, 2, 3), (2, 5, 1, 3)])
 
+    def test_exists_path_from(self) -> None:
+        "Check that `exists_path_from` can handle non-direct links"
+        link_map = _LinkMap()
+
+        link_map.add_link((1, 1), (2, 1), new=False)
+        link_map.add_link((2, 1), (3, 1), new=False)
+
+        self.assertTrue(link_map.exists_path_from((1, 4), (3, 1)))
+        self.assertFalse(link_map.exists_path_from((1, 4), (3, 2)))
+
+        link_map.add_link((1, 5), (2, 3), new=False)
+        link_map.add_link((2, 2), (3, 3), new=False)
+
+        self.assertTrue(link_map.exists_path_from((1, 6), (3, 2)))
+        self.assertFalse(link_map.exists_path_from((1, 4), (3, 2)))
+
 
 class EventChainBackgroundUpdateTestCase(HomeserverTestCase):
     servlets = [
         admin.register_servlets,
         room.register_servlets,

Vulnerable code:         #          ID/sequence number; and
        #       b. Add a link from the event to every chain reachable by the
        #          auth event.
        auth_chain_rows = cast(
            List[Tuple[int, int, int, int]],
            db_pool.simple_select_many_txn(
                txn,
                table="event_auth_chain_links",
                column="origin_chain_id",
                iterable={chain_id for chain_id, _ in chain_map.values()},
                keyvalues={},
                retcols=(
                    "origin_chain_id",
                    "origin_sequence_number",
                    "target_chain_id",
                    "target_sequence_number",
                ),
            ),
        )
        for (
            origin_chain_id,
            origin_sequence_number,
            target_chain_id,
            target_sequence_number,
        ) in auth_chain_rows:
            chain_links.add_link(
                (origin_chain_id, origin_sequence_number),
                (target_chain_id, target_sequence_number),
                new=False,
            )
                # Step 2b, add a link to chains reachable from the auth
                # event.
                for target_id, target_seq in chain_links.get_links_from(
                    (auth_chain_id, auth_sequence_number)
                ):
                    if target_id == chain_id:
                        continue

                    chain_links.add_link(
                        (chain_id, sequence_number), (target_id, target_seq)
                    )

    def get_links_from(
        self, src_tuple: Tuple[int, int]
    ) -> Generator[Tuple[int, int], None, None]:
        """Gets the chains reachable from the given chain/sequence number.

        Yields:
            The chain ID and sequence number the link points to.
        """
        src_chain, src_seq = src_tuple
        for target_id, sequence_numbers in self.maps.get(src_chain, {}).items():
            for link_src_seq, target_seq in sequence_numbers.items():
                if link_src_seq <= src_seq:
                    yield target_id, target_seq

    def get_links_between(
        self, source_chain: int, target_chain: int
    ) -> Generator[Tuple[int, int], None, None]:
        """Gets the links between two chains.

        Yields:
            The source and target sequence numbers.
        """

        yield from self.maps.get(source_chain, {}).get(target_chain, {}).items()

        links = self.get_links_between(src_chain, target_chain)
        for link_start_seq, link_end_seq in links:
            if link_start_seq <= src_seq and target_seq <= link_end_seq:
                return True
    # The event_txn_id table and tables from MSC2716 no longer exist.
    83
    def test_simple(self) -> None:
            (power, create),
            (alice_invite, create),
            (alice_invite, bob_join),
        self.persist(events)
        self.assertEqual(len(expected_links), len(list(link_map.get_additions())))

        for start, end in expected_links:
            start_id, start_seq = chain_map[start.event_id]
            end_id, end_seq = chain_map[end.event_id]
            self.assertIn(
                (start_seq, end_seq), list(link_map.get_links_between(start_id, end_id))
            )
            (power, create),
            (alice_invite, create),
            (alice_invite, bob_join),
        self.assertEqual(len(expected_links), len(list(link_map.get_additions())))
        for start, end in expected_links:
            start_id, start_seq = chain_map[start.event_id]
            end_id, end_seq = chain_map[end.event_id]

            self.assertIn(
                (start_seq, end_seq), list(link_map.get_links_between(start_id, end_id))
            )
        self.assertCountEqual(link_map.get_links_between(1, 2), [(1, 1)])
        self.assertCountEqual(link_map.get_links_from((1, 1)), [(2, 1)])
        self.assertCountEqual(link_map.get_links_between(1, 2), [(1, 1)])
        self.assertCountEqual(link_map.get_links_between(1, 2), [(1, 1), (3, 3)])
        self.assertCountEqual(link_map.get_links_between(2, 1), [(5, 3)])
        self.assertCountEqual(link_map.get_links_between(1, 2), [(1, 1), (3, 3)])

Fixed code: Refactor auth chain fetching to reduce duplication.
import collections
from synapse.storage.databases.main.event_federation import EventFederationStore
        #          ID/sequence number

        for links in EventFederationStore._get_chain_links(
            txn, {chain_id for chain_id, _ in chain_map.values()}
        ):
            for origin_chain_id, inner_links in links.items():
                for (
                    origin_sequence_number,
                    target_chain_id,
                    target_sequence_number,
                ) in inner_links:
                    chain_links.add_link(
                        (origin_chain_id, origin_sequence_number),
                        (target_chain_id, target_sequence_number),
                        new=False,
                    )
        # We have to graph traverse the links to check for indirect paths.
        visited_chains = collections.Counter()
        search = [(src_chain, src_seq)]
        while search:
            chain, seq = search.pop()
            visited_chains[chain] = max(seq, visited_chains[chain])
            for tc, links in self.maps.get(chain, {}).items():
                for ss, ts in links.items():
                    # Don't revisit chains we've already seen, unless the target
                    # sequence number is higher than last time.
                    if ts <= visited_chains.get(tc, 0):
                        continue

                    if ss <= seq:
                        if tc == target_chain:
                            if target_seq <= ts:
                                return True
                        else:
                            search.append((tc, ts))

Changes in SCHEMA_VERSION = 84
    - No longer assumes that `event_auth_chain_links` holds transitive links, and
      so read operations must do graph traversal.
    # Transitive links are no longer written to `event_auth_chain_links`
    84
from parameterized import parameterized

    @parameterized.expand([(False,), (True,)])
    def test_simple(self, batched: bool) -> None:
        charlie = "@charlie:test"
        charlie_invite = self.get_success(
            event_factory.for_room_version(
                RoomVersions.V6,
                {
                    "type": EventTypes.Member,
                    "state_key": charlie,
                    "sender": alice,
                    "room_id": room_id,
                    "content": {"tag": "charlie_invite"},
                },
            ).build(
                prev_event_ids=[],
                auth_event_ids=[
                    create.event_id,
                    alice_join2.event_id,
                    power_2.event_id,
                ],
            )
        )

            charlie_invite,
            (charlie_invite, alice_join2),
        # We either persist as a batch or one-by-one depending on test
        # parameter.
        if batched:
            self.persist(events)
        else:
            for event in events:
                self.persist([event])

        event_map = {e.event_id: e for e in events}
        reverse_chain_map = {v: event_map[k] for k, v in chain_map.items()}
        self.maxDiff = None
        self.assertCountEqual(
            expected_links,
            [
                (reverse_chain_map[(s1, s2)], reverse_chain_map[(t1, t2)])
                for s1, s2, t1, t2 in link_map.get_additions()
            ],
        )
        event_map = {e.event_id: e for e in events}
        reverse_chain_map = {v: event_map[k] for k, v in chain_map.items()}
        self.maxDiff = None
        self.assertCountEqual(
            expected_links,
            [
                (reverse_chain_map[(s1, s2)], reverse_chain_map[(t1, t2)])
                for s1, s2, t1, t2 in link_map.get_additions()
            ],
        )
        self.assertCountEqual(link_map.get_additions(), [])
        self.assertCountEqual(link_map.get_additions(), [(1, 3, 2, 3)])
    def test_exists_path_from(self) -> None:
        "Check that `exists_path_from` can handle non-direct links"
        link_map = _LinkMap()

        link_map.add_link((1, 1), (2, 1), new=False)
        link_map.add_link((2, 1), (3, 1), new=False)

        self.assertTrue(link_map.exists_path_from((1, 4), (3, 1)))
        self.assertFalse(link_map.exists_path_from((1, 4), (3, 2)))

        link_map.add_link((1, 5), (2, 3), new=False)
        link_map.add_link((2, 2), (3, 3), new=False)

        self.assertTrue(link_map.exists_path_from((1, 6), (3, 2)))
        self.assertFalse(link_map.exists_path_from((1, 4), (3, 2)))