HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Relay

Algorithm: Who Gets to Put You in a Group

14 min read

Every article before this one has been about two people. This one is about the moment a third arrives — how a device decides that a group it has never seen, delivered by a server that deliberately does not know who belongs to it, is a group it should actually join.

Prerequisites: The End-to-End Layer for what the pairwise channel guarantees, and A Relay That Holds Nothing for why some traffic cannot ride the relay at all.

1. What the series has not said

Read back through the hierarchy and you will find it is 1:1 the whole way down. Sealed sender hides one sender from the relay. The deniable handshake establishes one pairwise key between two strangers. The ratchet advances one conversation. Nowhere does the series say how more than two people come to share a key — and that is a real gap, because the answer turns out to contain a mistake worth studying.

First, scope, because "group" is doing too much work in this system. Group threads and Feed posts do not use a group key at all. They are per-device sealed fan-out: the sender's device seals one ordinary 1:1 envelope per recipient device and ships them independently, with the groupID sealed inside the payload. The relay never sees a group, only a handful of unrelated 1:1 envelopes — better for metadata, and at the sizes these features actually run at, cheap enough that nothing cleverer was needed.

Two features do need genuine shared cryptographic state: a huddle (the agents of a mutually close-trusting clique conferring live, with turn-taking and a shared transcript) and a plan (a durable shared object people get added to over time, sometimes by someone other than its creator). Both are real MLS groups. Everything below is about those two, and only those two.

2. What RFC 9420 gives, and where it stops

The groups are MLS, via OpenMLS, on the hybrid ciphersuite MLS_256_XWING_CHACHA20POLY1305_SHA256_Ed25519 — X-Wing TreeKEM, so the group's key agreement is post-quantum in the same sense the rest of the system is. The suite's signature half is still Ed25519 — OpenMLS 0.8's SignatureScheme is a closed IANA enum with no ML-DSA in it — so the ML-DSA-65 co-signature that §4 turns on is layered above the library rather than folded into the wire format. MLS is an unusually complete protocol, and it hands you three things for free: confidentiality (application messages are encrypted to the current epoch key, and a non-member has no path to it), sender authentication (every message is attributable to a leaf in the tree), and forward secrecy with post-compromise security across epochs (each Commit rekeys, so a removed member's keys stop decrypting at the removal commit).

All three are conditional on the same clause: inside a group you are in. MLS answers "given this group, who may speak and what may they read." It does not answer "should this group exist for you at all." Admission — who is allowed to create your membership — is left to the application, and RFC 9420 says so. That deferral is the entire subject of this article.

3. The log that must not know its own members

Membership changes cannot ride the relay. The relay is pure publish/subscribe with no mailbox (article 05), so a Commit aimed at a member whose phone is asleep would simply evaporate, and that member would be permanently out of sync with the group's epoch chain. So there is a second, deliberately dull service: handshake-svc, a durable ordered per-group log with exactly two operations, POST /v1/handshake/:group_id to append and GET /v1/handshake/:group_id?since=&recipient= to catch up.

The interesting property is what it refuses to know. A row is opaque payload bytes under a group id and a sequence number; there is no account column, no roster, no key material. Its own source comments the trust model plainly: the group_id IS the capability, and that is deliberate. Consent was gated much earlier, at discovery — a huddle's members have each resolved and accepted one another through the CDH handshake and key transparency, and only then does anyone learn a group id — so membership is not a decision this service re-litigates. What the log carries for a Commit is MLS ciphertext, and a removed member reading it gains nothing, because the removal commit rekeyed the epoch. What possession of the id genuinely did allow was unbounded writes, which is what the per-group append throttle bounds.

Two things it does hold matter later. A Welcome row carries a recipient — the joining device's envelope pubkey — because the catch-up read has to hand you your Welcome and not everyone else's, so the log knows that this pubkey was welcomed into this group while knowing nothing about who put it there. And the per-plan routing addresses members announce ride the same log as cleartext rows any fetcher can read. The endpoints sit behind a session bearer token resolved against auth-svc, but that establishes only that the caller is some account; nothing connects it to the group.

Now notice the corner this paints us into. handshake-svc cannot perform authorization, because the one thing it would need is the one thing it must not learn. The server-side check would be "is this appender in this group?", and the appender is exactly who the log never sees: it authenticates a session, not a member, and it holds no roster to check the session against. Building one means assembling the group↔member linkage the design spent its effort destroying. The privacy win is the reason server-side authorization was never available. The check had nowhere to go but the endpoint.

For a while, nobody put it there.

4. A Welcome that verifies against itself

A Welcome is how a device installs a group it is not yet in: it carries the staged tree, the group context, and the secrets that let exactly one joiner derive the current epoch key. It is the one MLS message a non-member processes, which makes it the admission surface.

The Welcome is not unprotected. This system co-signs every handshake message with ML-DSA-65 at the application layer, so the wire is ml_dsa_sig(3309) ‖ welcome, and the joiner verifies that signature fail-closed before the group is persisted — in backend/pixie-mobile-ffi/src/mls.rs, join() refuses before into_group(). Forging one therefore requires breaking Ed25519 and ML-DSA. That looks like a closed door.

Read the next line of that function and the door swings open. The signature is verified against the committer's leaf, and the committer's leaf is resolved by staged.welcome_sender() — from the staged tree inside that same Welcome. The Welcome supplies both the claim and the key that checks it. An attacker who creates their own group is its committer, sits in its tree, and holds its signing key, so their Welcome verifies perfectly. It always will. The check proves the message was not tampered with in flight; it says nothing whatsoever about whether the author had any business adding you.

Combine that with §3 and the attack writes itself. Any account with a session can append a Welcome addressed to (groupID, recipient), and the server cannot refuse, by construction: refusing would mean knowing who belongs. For a huddle, the cohort_id is a hash of the sorted member set, so any former member can derive it offline and the attacker does not even need to steal one. The victim's next sync pulls the entry, the ML-DSA co-signature verifies, and the victim installs the attacker's group.

5. Losing the group is worse than losing the secret

The obvious harm is confidentiality: the victim holds a key shared with someone who chose the membership, and anything they send into that "plan" goes to the attacker. Bad, and easy to narrate.

The quieter harm is worse. Look at the catch-up loop in ios/Pixie/Pixie/Cognitive/Huddle/PlanMLSService.swift: sync installs a Welcome only when !isMember, because an already-joined device must not re-install its own group and reset its epoch cursor. Perfectly reasonable. It also means whichever Welcome lands first wins, permanently. A rogue Welcome at a lower seq than the real one flips isMember to true, and the genuine Welcome from the genuine convener is skipped — not retried, not queued, skipped, on this sync and every sync after it.

So the victim is not merely eavesdropped, they are silently partitioned out of the real group: a plan that exists and appears to work, populated by nobody, while the real one carries on without them and no error is raised anywhere, because from the protocol's point of view everything verified. A confidentiality break is loud once discovered. This one has no symptom.

6. Why the in-clique trust model does not reach this

This system takes a deliberate stance — the one handshake-svc's own trust-model comment states in §3 — that in-group forgery is out of scope: in-clique membership is authorization. It is defensible. Consent is gated at discovery, a huddle is a maximal clique of the mutual-consent graph — everyone in it has accepted everyone else — and a member who abuses group state was already trusted with the group's content, so sender-level authorization for commits inside a group is effort spent against an adversary the design does not model.

Being exact about why that fails to cover this case matters, because "we already decided that class is out of scope" is precisely how a real hole survives review. The in-clique model covers commits inside a group you are already in, and leans on the removal rekey to bound what a departed member retains. Here isMember == false: the victim is being moved into a group they were never part of, by an attacker who was never part of it either. No prior clique, no epoch to rekey, no removal to lean on. The model has nothing to say, and mistaking it for coverage is the failure — not the code.

7. The fix has to fit through the same keyhole

The check has to happen on the joiner's device, using only material the joiner already holds, and it must not put a single new fact on handshake-svc. Those constraints are tight enough that they almost write the mechanism.

The sponsor — whoever performed the add — signs a preimage under the domain tag pixie:mls-welcome-sponsor:v1:

sponsorPreimage = "pixie:mls-welcome-sponsor:v1" ‖ planID ‖ recipient ‖ welcome

so the wire becomes sponsor_sig(64) ‖ ml_dsa_sig(3309) ‖ welcome — two signatures over the same message, answering different questions. The joiner splits off the outer one, rebuilds the preimage from the group id it asked about and its own pubkey, and installs the group only if one of an expected set of sponsors signed (PlanMLSService.openSponsored). Each field earns its place: binding planID stops a valid Welcome being replayed into a different plan or cohort; binding recipient stops one legitimately addressed to someone else being replayed at you; binding the exact welcome bytes stops the signature being lifted onto a different tree.

Two details make it fit the constraints rather than fight them.

Only the detached signature goes on the wire — never the sponsor's public key. This is the whole reason the mechanism is admissible. The log already knows a Welcome's recipient, because it has to route the catch-up read; what it does not know is the author. A Welcome carrying "signed by X" would hand it exactly that edge — the group's authority, named, beside the member being added — trading an admission bug for a metadata leak. Instead the joiner supplies the candidate keys locally and tries each in turn; the server still sees an opaque blob whose length grew by 64 bytes.

The signing key is one the joiner already has. The sponsor's public half is its device envelope pubkey — the same value that appears in memberPubkeys and in recipient. No new key type, no new directory, no new distribution path. If you can be added to a group, you already know the keys of the people who could legitimately add you.

Failure is a continue, not a throw: an unrecognised Welcome is logged and skipped, because one stray append must not brick the real group.

8. Who counts as a sponsor

An authorization check is only as good as its expected set, and sync takes it as a parameter (expectedSponsors) rather than guessing. An empty set authorizes nothing and installs no Welcome — fail-closed by default.

For a plan, the set is whoever invited you — persisted on your invitation as invitedBy — plus the plan's existing participants (and anyone who has issued an invitation to it). The widening is not laxity, it is the feature: plans support bring-a-friend, so the device that adds you is often not the one that invited you, and a set containing only your inviter would refuse a legitimate add. It is also the loosest part of the mechanism, and worth seeing as such: it authorizes anyone already inside the plan.

For a huddle, the set is the convener plus the current members, and the reason is failover. When the device driving one member's side drops out, a sibling device takes the vacated seat, and because that sibling is a new leaf it has to be MLS-added mid-session — by whichever existing member is servicing the takeover, which is not in general the convener. A convener-only set would refuse every such add, which is to say it would make failover fail. The trust story is unchanged, because "current member" is already the boundary the clique model draws.

Both sets are computed locally and exclude the joiner's own key (planSponsors in ComposeService, cohortSponsors in LiveHuddleSession).

9. Two adjacent holes of the same shape

Fixing the signature exposed two more places where a value was trusted without being pinned to anything outside itself.

The joined group id was being discarded. A Welcome is fetched under groupID: planID, but nothing made the group inside it be that group — so an attacker's Welcome installed a different MLS group under this plan's cursor, and every later operation silently addressed the wrong one. PlanGroup.join returns the joined id; sync now requires joined == planID. It is worth being clear that this does not stop §4 — an attacker is free to name their own group with the victim's plan id, after which the equality holds. The sponsor signature does the authorizing; this closes the separate case of a Welcome that installs some group under a cursor belonging to a different one.

The "already added?" check counted the wrong Welcomes. establish is deliberately idempotent — a retry after a partial failure must add the still-missing members without double-adding the rest — and it decided by looking for a Welcome already on the log for that recipient. Any Welcome. So an attacker could pre-post one and the real convener would conclude that member was handled and skip them: an exclusion denial-of-service that survives the joiner-side sponsor check entirely, because no Welcome the joiner would accept is ever authored. The count now includes only Welcomes this device signed.

10. Verified against itself

Two of the defects above, and one in the sibling series, reduce to the same sentence: a signature that proves integrity is not a signature that proves authorization. The Welcome's ML-DSA co-signature was checked against a key resolved from the Welcome. The group id was checked against the group that arrived. In what a lookup proof binds, a transparency-log entry carried its committed value twice — once folded into the signed root, once as a plain wire field — and the code read the field nobody compared to the root, so a genuine proof with one rewritten field opened to anything.

All of these pass on honest input, which is why they survive testing and review. The question that catches all three is the same: what independent thing is this value pinned to? If the answer is "the message it arrived in," you have verified nothing but the message's internal consistency.

11. The residual

Three things this does not protect. The first two are refusals rather than breaches, which is the correct direction and still a cost. The third is not a refusal.

Groups established before the sponsor signature existed have unsigned Welcomes on their handshake logs, and those are now skipped. A joiner has no way to distinguish "legacy, honest, unsigned" from "appended by an attacker," and the whole point of §4 is that guessing is what got us here. So the fail-closed rule applies uniformly: a member who had not yet installed an old group's Welcome will not install it now, and that group has to be re-established rather than joined.

A sponsor set that is wrong or stale refuses a legitimate add. The check is only as good as the joiner's local belief about who could plausibly have added them. If invitedBy was never recorded, if a plan's participant list has not caught up, or if a huddle's member set on the joining device lags the failover that handed the add to a new driver, the Welcome is genuine and the joiner still walks away. The symptom is a member who quietly never joins — which, uncomfortably, looks from the outside exactly like the partition attack in §5. Fail-closed does not mean fail-obvious.

The authorization signature is classical. The sponsor signs with its device envelope key, and that key is Ed25519 — alone among the things it sits beside, since the Welcome's own co-signature is ML-DSA-65 and the group's key agreement is X-Wing. That is the direct price of §7's cheapness: the verifying key had to be one the joiner already held, and what it holds is 32 bytes of Ed25519. The device does have an ML-DSA half derived from the same seed, but its 1952-byte public half is a separate value no participant list carries, and the per-plan ML-DSA key MLS itself binds lives inside the group's tree — obtainable only from the Welcome, which is the thing §4 taught us not to verify against itself. Hybridising therefore means building the distribution path the mechanism was admissible for not needing, and until that exists, an adversary who can forge Ed25519 reopens §4 unchanged. Authorization is at least a real-time property: a break in 2035 forges 2035 admissions and leaves a harvest-now adversary nothing to bank.

References & further reading