HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

Algorithm: Rotating the Key Strangers Seal To

12 min read

Contact discovery ends by handing you a stranger's mailbox: an address to publish to and a key to seal a first hello with. The series stops there, as though the binding were a fixed property of a person. It is not. The key behind that address is replaced on a routine cadence, the address itself moves only when a device is removed, and for a day or two after either one the old and new both work. This article is that lifecycle — two rotations that look alike and do entirely different jobs.

Prerequisites: Bulk Membership PIR, which delivers the binding this article picks up, and The Transparency Log, whose append-only versioning is what makes a rotation expressible at all.

1. The object the series stopped at

A completed discovery gives you three fields, and it matters that they are three and not one:

discovery_xwing_pubkey   1216 bytes   what a first hello is sealed to
discovery_inbox            32 bytes   the relay subject that hello is published to
version                     4 bytes   monotone, one per rotation

The transparency log commits them as separate fields of one leaf, not as an opaque blob. That is the whole hinge of this article. Because the key and the address are committed independently, the account can replace one without disturbing the other — and the two operations that result have different costs, different reasons, and different guarantees.

The private halves live on the device as a small ring of epochs. An epoch is the pair that defines a reachable identity — the inbox, and the 32-byte seed the X-Wing keypair regenerates from — plus the moment it was minted, which is what expiry reads:

public struct DiscoveryEpoch: Equatable, Sendable {
    public let inbox: Data     // 32 — the relay subject
    public let seed: Data      // 32 — regenerates the X-Wing keypair
    public let createdAt: Date // drives grace-window expiry
}

They are stored as a single Keychain item rather than one item per epoch, for a reason worth stating because it is easy to get backwards: KeychainStore has no enumeration API, so epoch-suffixed items would be invisible to wipe() — and live private keys would quietly survive an uninstall.

2. Why a published key has to move at all

Every other key in the system gets forward secrecy from a ratchet: both sides are online, they exchange fresh material, and yesterday's traffic stops being decryptable by today's compromise. A cold-contact key cannot work that way. Its entire job is to be usable by a stranger who has never spoken to you, holds nothing of yours, and cannot do a round trip — they read the key out of the directory and seal. There is nothing to ratchet against.

So the window during which one compromised device key exposes inbound first-contact hellos is not bounded by any property of the key. It is bounded by how often the key is replaced, and by nothing else. That single observation is the reason the rest of this article exists.

The cadence is daily. The floor is not arbitrary: a rotation is not served until it has been folded into the transparency log, so replacing the key faster than the log cuts epochs would publish bindings that resolvers cannot yet prove — and every rotation costs an append to the authenticated dictionary, per account. Daily sits comfortably above the floor and well below the point where the append traffic becomes the problem.

3. Two rotations, and why they are not interchangeable

The sealing rotation keeps the inbox and mints a fresh key:

public func rotateDiscoverySealingKey() throws -> DiscoveryEpoch {
    let inbox = try (currentDiscoveryEpoch()?.inbox ?? randomInbox())
    let fresh = try XWingMLKEM768X25519.PrivateKey()
    ...
}

The identity rotation replaces both:

public func rotateDiscoveryIdentity() throws -> DiscoveryEpoch {
    let fresh = try XWingMLKEM768X25519.PrivateKey()
    let epoch = DiscoveryEpoch(inbox: try randomInbox(), seed: fresh.seedRepresentation)
    ...
}

The difference reads as one line of code and is the difference between a routine hygiene operation and a revocation.

Moving only the key is nearly free. Contacts pick it up on their next resolve, and nothing resubscribes — the relay subject is unchanged, so every live subscription, every cached binding, and every push registration keeps working. Moving the address as well churns all of that. The first cut of this rotated both every time, and paid the churn daily for a confidentiality gain of exactly zero: the address is not a secret, and hiding it from a contact who already resolved it protects nothing.

4. The grace window, and why it is a receiver-side decision

A rotation is not atomic across the people who care about it. Resolvers read the folded view of the directory, so for some interval after a rotation your contacts are still holding — and still sealing to — the previous key. If the device discarded that key the moment it minted a new one, every hello in that interval would arrive unopenable, and neither side would ever learn why.

So a superseded epoch stays openable:

public static let discoverySealingKeyLifetime: TimeInterval = 24 * 60 * 60
public static let discoveryGraceWindow: TimeInterval = 48 * 60 * 60
public static let discoveryEpochRetention = 2

Two days over a one-day cadence keeps exactly one full superseded epoch alive, which is the retention constant saying the same thing a second way: the current epoch, plus the one still inside its window. Retaining more would multiply precisely the exposure the rotation exists to bound.

The part worth pausing on is that none of this needs server support. Opening a box is a local act with a local key; the directory is not consulted, and no proof is fetched. Retention is a decision the receiver makes alone about which of its own keys it is still willing to try. That is why the window can be generous without weakening anything the log asserts — the log has already moved on, and the device is simply declining to forget quite yet.

The inverse error is the dangerous one, and it is silent: drop an epoch that some contact is still sealing to, and every hello addressed under it is black-holed. Nothing fails loudly, because from the receiver's side an unopenable box is indistinguishable from noise.

5. The address no longer names the key

There is a consequence of keeping the inbox still that is easy to miss and expensive to get wrong. Once a sealing rotation leaves several epochs sharing one address, the subject a hello arrived on no longer identifies which key opens it. Before rotation existed, "which key?" and "which inbox?" were the same question. They are not any more.

Anything that needs to name an epoch therefore keys off its public half instead:

/// Stable 32-byte identifier for an epoch: SHA-256 of its X-Wing public half.
public func epochKeyID(for epoch: DiscoveryEpoch) throws -> Data

The receive path tries every retained epoch, so opening an inbound hello was never at risk — one of them works. The risk is on the reply. The handshake transcript binds both sides' discovery public keys, so a device that opens a hello under the superseded epoch and then answers under the current one produces a transcript the sender cannot reproduce. The authenticator fails, the handshake dies, and there is no diagnostic anywhere, because every individual step succeeded. Recording the opening epoch's key id at the moment the hello is opened, and answering under that same epoch, is what closes it.

6. One key for the whole fleet

Everything so far has described the discovery secret as though it belonged to a device. It does not. It belongs to the account, and every device on the account holds the same one.

This is a deliberate reversal of the more obvious design, and it is worth being direct about what it costs. Per-device discovery keys would mean a compromise of one phone exposes only the hellos addressed to that phone. Sharing means a compromise of any one device exposes the account's inbound first-contact traffic, full stop. That trade was made knowingly, and it follows the same line the rest of the multi-device design takes: the devices on an account are one another's equals, not a hierarchy with a weak tier.

What it buys is the thing users actually notice. A first-contact hello arrives for you, not for a particular handset, and a sign-in approval has to be answerable from whichever device you happen to be holding. Both require that any sibling can open a box sealed to the account's discovery key. With per-device keys, the device that published most recently would be the only one that could — and approving a new phone would depend on which of your old ones you had left at home.

The secret travels on the ordinary sealed sibling channel, and it has to be that channel rather than the sign-in approval frame: the sibling channel key is derived from the account seed, so a device only has this channel once it already holds the account root — by which point the approval has done its job. Epochs travel newest-first, exactly as stored, so a joining sibling inherits the grace window rather than just the current key, and can open a hello still addressed to the previous epoch.

One consequence lands in a place you would not look for it. The relay pins a discovery subject to the first key that claims it, and push registration is pinned the same way. If that claim were signed with a per-device key, whichever sibling connected first would own the account's inbox and lock out every other one. So the claim key is derived from the epoch seed:

let derived = HKDF<SHA256>.deriveKey(
    inputKeyMaterial: SymmetricKey(data: epoch.seed),
    info: Data("pixie:discovery-subject-claim:v1".utf8),
    outputByteCount: 32)

Every device holding the epoch derives the same keypair, so they all present the same claim and the pin admits all of them. It is also the more honest statement of the right being claimed: the entitlement to receive on a discovery inbox belongs to whoever holds the discovery secret, which is precisely the account. An outsider who merely learned the subject — and it is derivable from the directory — still cannot produce the signature, so the squatting attack the pin exists to stop is unaffected.

For the same reason, a device never mints an epoch lazily. A joining sibling that minted its own would be reachable at an address no contact resolves, and would fork the account's discovery identity exactly as a locally-minted account key forks its trust root. Epochs appear by rotation or by adoption from a sibling, and by no other route.

7. Removal has to move the address

Now the two rotations stop being a matter of taste.

When a device is removed from an account, the server can strike it from the roster, refuse its sessions, and stop answering its queries. What no amount of server work can do is retrieve the copy of the discovery secret already sitting in that device's Keychain. It has the seed. It knows the inbox. And because the subject claim derives from the seed rather than from the device, it can still present a valid claim for the account's discovery subject.

That last point is what makes a sealing-only rotation inadequate here. Move just the key, and the removed device can no longer read new hellos — but it can still subscribe to the address they arrive at, which means it can still receive them, and a subscriber that receives and discards is a subscriber that denies. The account would look reachable and silently not be.

So removal takes the identity rotation, unconditionally:

// Identity rotation, not just the sealing key: the removed device
// knows the inbox and can still claim its relay subject, so moving
// only the key would leave it able to receive and deny hellos.
_ = try await contactDiscoveryService.rotateDiscoveryIdentity()

The ordering is chosen so that a failure degrades safely. Mint and publish first — a failed publish leaves the previous epoch current, which keeps the account reachable rather than orphaning it. Then push the new epoch set to the siblings that remain. Then re-subscribe locally. And if the rotation itself fails, it says so loudly, because the alternative is a user who believes a revocation happened that did not.

Siblings that were offline for the push are not lost. The push is fire-and-forget with no delivery duty; the guarantee is the pull, which re-requests the account's epochs on every bootstrap. The push is only the fast path.

8. What a rotation hides, and what it does not

The honest accounting, because this is the section most likely to be overstated elsewhere.

A rotation is not retroactive. It bounds the window in which a compromised key is useful going forward. Hellos sealed to the old key before the rotation were decryptable by whoever held it, and remain so — the ciphertext does not become safer because a successor exists. The claim is about tomorrow, never about yesterday.

Removal is not instant. The removed device stops receiving when contacts stop publishing to the old address, which happens as they re-resolve — not at the moment the button is pressed. Until then the old inbox is still live and the old seed still opens what arrives there. The gap is the same fold-and-resolve interval that motivates the grace window, and it is short, but it is not zero.

The old key is gone from you, not from them. Retention expiry deletes the superseded epoch from your Keychain. It cannot delete the copy on a device you removed. Everything in §7 is arranged around that asymmetry: you cannot revoke a secret someone already has, so you revoke the address, which is the one half of the binding you still control.

Rotation is not unlinkability. The version is monotone and the log is public, so an observer who can already identify an account's leaf sees that it rotated, and when. What the log does not give them is which phone number the leaf belongs to — the label is a keyed PRF of the identifier, not a hash of it, which is the property What a Lookup Proof Binds establishes. Rotation neither strengthens nor weakens that; it is simply a different question.

One compromised device compromises the account's inbound discovery. Stated once more, plainly, because it is the cost of §6 and it should not be discovered by reading source. Sharing the discovery secret across the fleet is what makes any-device approval and account-addressed hellos work, and it means the blast radius of a single compromised handset is the account, not the handset.

References

  • RFC 5869, "HMAC-based Extract-and-Expand Key Derivation Function (HKDF)" — the derivation that turns one epoch seed into the subject-claim keypair every sibling reproduces.
  • RFC 9420, "The Messaging Layer Security (MLS) Protocol," §2 — the post-compromise security framing this borrows: recovery is a property of replacing key material on a schedule, not of any single key being strong.
  • Wikipedia: Forward secrecy, Key rotation.

Back to Bulk Membership PIR, which hands you the binding this article puts a clock on, or across to Absorbing a New Device, which is the approval flow the fleet-shared key exists to serve.