Synapse federates `Ed25519` public keys with invalid Edwards points

[gamesguru]

Description

Rust errors

|  WARN |   command    | Signature verification failed for event unknown. Error: Parse(PublicKey(signature::Error { source: Some(Cannot decompress Edwards point) })). Available keys: {"msgs.cloud": {"ed25519:0": "SSYCjCuSLiIpCjQakVN/1XeDLRetYAvXQqOmDzcHBOc"}}. Event signatures: {"msgs.cloud":{"ed25519:0":"SkGo8VIsHVoJ2Fh60QynXjElOTsAhZ5ZdmSFEU7ZpKMjjzLQa+Hks5Q9IzFabJhMSq4pA3ixz7x3fEg2U3dVBg"}} |
|  WARN |   command    | get_remote_dag: PDU $84ED0Bgv6emCtjE_7U_nzEgVTUqrMA7ovMZlh4ssZos failed sig verify, storing as rejected outlier: Event $84ED0Bgv6emCtjE_7U_nzEgVTUqrMA7ovMZlh4ssZos failed verification: Parse error: Could not parse public key: signature error: Cannot decompress Edwards point |

Origin server runs Synapse, room is V12

Keys are cached incorrectly as expected by Rust server (pending MSC4499 draft-finalization and compliance). But why this invalid key was ever federated in the first place?

If fetched from a notary, that notary was nearly certainly Synapse.

uwu> debug ping msgs.cloud
Got response which took 153.874675ms time:
{
  "name": "Synapse",
  "version": "1.155.0"
}

uwu> debug get-signing-keys msgs.cloud
ServerSigningKeys {
    server_name: "msgs.cloud",
    verify_keys: {
        "ed25519:0": VerifyKey {
            key: "l/O9hxMVKB6Lg+3Hqf0FQQZhVESQcMzbPN1Cz2nM3og",
        },
        "ed25519:1": VerifyKey {
            key: "3rzsNQSJj/2dRJEsznqqDl0SIFcgVL0WIkWXhCLh4m0",
        },
    },
    old_verify_keys: {
        "ed25519:0": OldVerifyKey {
            expired_ts: 2026-02-12T10:29:16.994,
            key: "SSYCjCuSLiIpCjQakVN/1XeDLRetYAvXQqOmDzcHBOc",
        },
    },
    signatures: Signatures(
        {},
    ),
    valid_until_ts: 2026-02-06T22:45:30.209,
}

Python script to verify

#!/usr/bin/env python3
"""Demo to show invalid keys are being shared in the wild."""

import base64

P = 2**255 - 19
D = -121665 * pow(121666, P - 2, P) % P


def decompress_ed25519_public_key(pub_bytes: bytes) -> tuple[int, int]:
    """Decompresses a 32-byte public key into (X, Y) coordinates.

    Returns (x, y) if valid, or raises ValueError if corrupt.
    """

    y = int.from_bytes(pub_bytes, "little")

    # Extract the sign bit from the highest bit, then mask it out of "y"
    sign = y >> 255
    y &= (1 << 255) - 1

    # Coordinate "y" must be less than the prime P
    if y >= P:
        raise ValueError("Invalid key: y >= P")

    # Solve the curve equation for x^2
    num = (y * y - 1) % P
    den = (D * y * y + 1) % P
    x2 = (num * pow(den, P - 2, P)) % P

    # Check: does a square root for x2 even exist?
    euler_residue = pow(x2, (P - 1) // 2, P)
    print(f"euler_residue={euler_residue}")
    if euler_residue not in (1, 0):
        raise ValueError("Invalid key: Not a quadratic residue (no X exists)")

    # Calculate the square root candidate for "x"
    x = pow(x2, (P + 3) // 8, P)

    # If x^2 doesn't match x2, attempt other square root candidate
    if (x * x - x2) % P != 0:
        x = (x * pow(2, (P - 1) // 4, P)) % P

    #  Flip "x" if the parity doesn't match key's sign bit
    if (x & 1) != sign:
        x = P - x

    return x, y


# --- Testing the keys ---
def try_print_key(key_body: str) -> None:
    """Attempt printing (x, y) coordinates for a given public key's base 64."""
    try:
        x, y = decompress_ed25519_public_key(base64.b64decode(key_body))
        print(f"Key ({key_body[:16]}) SUCCESS -> Point (X: {x}, Y: {y})")
    except ValueError as e:
        print(f"Key ({key_body[:16]}): FAILED ->", e)


# Evaluate the two examples from the Synapse server in question
try_print_key("SSYCjCuSLiIpCjQakVN/1XeDLRetYAvXQqOmDzcHBOc=")
try_print_key("l/O9hxMVKB6Lg+3Hqf0FQQZhVESQcMzbPN1Cz2nM3og=")

# ~~~~~~~~~~~~~~~~~~~~~~
# Output:
#
# euler_residue=57896044618658097711785492504343953926634992332820282019728792003956564819948
# Key (SSYCjCuSLiIpCjQa): FAILED -> Invalid key: Not a quadratic residue (no X exists)
# euler_residue=1
# Key (l/O9hxMVKB6Lg+3H) SUCCESS -> Point (X: 19016999126562708050698722554798891544934591409079259419010545528047437376527, Y: 4012153645923228469894369171496632063946423800262448132709498704531052950423)

Root cause

Synapse relies on Python cryptographic backends that treat Ed25519 public keys as opaque byte sequences during parsing, failing gracefully with a standard verification failure rather than a parsing exception when encountering invalid curve points. As a result, if a server's database contains a corrupted key blob, Synapse will blindly distribute it over federation and via notary endpoints.

Modern Rust-based homeservers enforce strict type-level decompression checks upon deserialization, causing them to throw a hard Cannot decompress Edwards point error when verifying signatures. Because blindly dropping the associated PDUs risks permanently partitioning the room DAG due to out-of-band network failures, some Rust implementations choose to quarantine these events as rejected outliers instead of dropping them entirely.

Now here's where things get even weirder. Under a strict interpretation of the spec, because the second requirement for "passes signature checks" is not met, this PDU should technically be unpersistable and immediately dropped. In the case of historical events solidified in the DAG, leaving holes like this may not be desirable, and it is not the behavior Synapse follows today. Synapse is generally more permissive in terms of what it will persist locally (and serve over federation).

This tolerance makes sense; some underlying cryptographic libraries choose to defer curve-validation errors or report them silently. While the PDU signature cannot be successfully verified, it also cannot be conclusively ruled out at the transport layer. Especially considering Matrix's out-of-band notary key fetching, it's entirely possible the event was historically valid but had its key ID accidentally or adversarially clobbered, duplicated, or overwritten on the wire.

All of this makes it incredibly unclear what the actual desired or expected behavior is, and it gives renewed interest in solving this problem and setting things straight.

Proposed solution

• Synapse should identify any possible sources of library exception swallowing, PDU check spec non-compliance, or storage corruption. Synapse should stop generating invalid keys today, marking their use as deprecated in relevant areas of code and documentation.
• Also starting today, Synapse should cease serving or circulating these keys. Unless demonstrated otherwise, these invalid keys are not even internally usable by Synapse's own crypto libraries. Ceasing the distribution of these specific keys to legacy peers is therefore minimally invasive or risky.
• Synapse should implement the upcoming key ID uniqueness requirements laid out in the pending MSC4499 draft to prevent possible sub-types of these cross-signing/old-key collisions.
• The spec should clarify expectations and behaviors in these edge cases or grey areas, and all major homeserver implementations should coalesce around agreed standards of "persistable" and any newly introduced taxonomical distinctions in the PDU intake check flow.

Steps to reproduce

Federate in room !NOGZYBedfuPsideoi2PSA_ouduzbb2mKrhu3fbUIeWk

Synapse Version

unsure. between 1.150 and 1.155.0?