CVE-2024-31208 (Python, published 2024-04-23T18:15Z)
Description: 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.
Severity: nan (CVSS v3 base score: )
Weakness: NVD-CWE-noinfo \u2014 Insufficient Information
There is insufficient information about the issue to classify it; details are unkown or unspecified.
Repository: https://github.com/element-hq/synapse
Files changed:
changelog.d/17044.misc
synapse/storage/databases/main/events.py
synapse/storage/schema/__init__.py
tests/storage/test_event_chain.py
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.


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)))