Mailbox Keypairs

Delivery addresses in Cryptid are not random identifiers assigned by a server. Each address is derived from its own keypair, held by the device that owns the mailbox. This gives a device a way to prove mailbox ownership cryptographically, without revealing its Device Identity and with each group’s address independent of every other’s.

Master Mailbox Seed

A device holds exactly one long-term mailbox secret: a 32-byte seed. Every mailbox keypair it will ever use is derived from that seed on demand.

MasterMailboxSeed Structure

/// Identifies what a mailbox is for. Bound into the derivation context so
/// each group gets an address that no other group ever sees.
enum MailboxScope {
    Group(GroupId),

    // Well-known scope for inbound ContactRequests. These arrive from
    // strangers, so the mailbox is kept separate for independent rate-limiting
    // and discard policy
    Contact,
}

impl MailboxScope {
    fn context_label(&self) -> String {
        match self {
            MailboxScope::Group(gid) => format!("group {}", hex(gid.as_bytes())),
            MailboxScope::Contact => "contact".to_string(),
        }
    }
}

/// The only long-term mailbox secret. Never used as a keypair, so no master
/// public key exists that would let anyone enumerate a device's mailboxes.
struct MasterMailboxSeed([u8; 32]);

impl MasterMailboxSeed {
    // Hardened derivation: children cannot be derived without the seed.
    //
    // The server domain MUST be bound in. The same keypair appearing on two
    // federated servers would let them link a multi-homed device.
    // The rotation counter is what makes an address replaceable.
    fn derive_mailbox(&self, server: &str, scope: &MailboxScope, rotation: u32)
        -> MailboxKeypair
    {
        let context = format!(
            "cryptid mailbox v1 {} {} {}",
            server, scope.context_label(), rotation
        );
        let child_seed = blake3::derive_key(&context, &self.0);

        let secret = X25519StaticSecret::from(child_seed);
        let public = X25519PublicKey::from(&secret);

        MailboxKeypair {
            secret,
            public,
            server: server.to_string(),
            scope: scope.clone(),
            rotation,
        }
    }
}

The seed is never used as a keypair. There is no master public key, which means there is no key that could be used to enumerate a device’s mailboxes even if it leaked.

Requirements

• Devices MUST generate that seed with cryptographically secure randomness
• Derivation MUST be hardened: child keypairs MUST NOT be derivable from any public value
• The server domain MUST be bound into the derivation context
• The seed SHOULD be stored in platform-provided secure storage; derived mailbox secrets MAY be cached in ordinary application storage
• Implementations MUST NOT transmit the seed, the scope label, or the rotation counter

Caution

Compromise of the master seed exposes every mailbox a device has ever had or will hold, past and future. Individual mailbox secrets have a far smaller blast radius, which is why the seed warrants stronges storage than the keys derived from it.

Domain Separation

The server domain is bound into every derivation context. If the same mailbox keypair were registered on two federated servers, those servers would hold an identical public key for the same device. Comparing registries would link a multi-homed device across both, defeating the purpose of separate addresses entirely.

• A mailbox keypair MUST NOT be used on more than one server
• Implementations MUST derive a distinct keypair per server, even for the same group

Mailbox Keypairs

MailboxKeypair Structure

struct MailboxKeypair {
    // Proves mailbox ownership to the server via challenge-response and
    // decrypts the outer envelope layer
    secret: X25519StaticSecret,

    // Distributed to contacts inside MLS. Never sent to servers.
    public: X25519PublicKey,

    // Server this mailbox is registered on. A keypair MUST NOT be
    // reused across servers.
    server: String,

    // What this mailbox is for. Client-side state only, never transmitted.
    scope: MailboxScope,

    // Incremented on each rotation of this scope
    rotation: u32,

}

impl MailboxKeypair {
    // First 15 bytes of the Blake3 hash of the public key, base32-encoded to
    // exactly 24 characters. Base32 is case-insensitive, which is what an
    // email-shaped identifier needs
    fn address_prefix(&self) -> String {
        let hash = blake3::hash(self.public.as_bytes());
        base32::encode(&hash.as_bytes()[..15])
    }

    fn delivery_address(&self) -> DeliveryAddress {
        DeliveryAddress {
            prefix: self.address_prefix(),
            server: self.server.clone(),
            mailbox_public: self.public,
            created_at: now(),
            active: true,
        }
    }

    // Server sends a fresh nonce; a static signature would be replayable
    fn prove_ownership(&self, challenge: &[u8]) -> MailboxProof {
        MailboxProof {
            mailbox_public: self.public,
            signature: sign_challenge(&self.secret, challenge),
        }
    }
}

Each mailbox is scoped to a single group. An address is a capability to deliver to a device, and every group member holds it. This scopes what a leaked or abused address can reach. An attacker who obtains one group’s address can flood or target that mailbox alone, and the device can burn/rotate it without disrupting any other group. ContactRequest traffic gets its own well-known scope, since it arrives from strangers and warrants separate rate-limiting and discard policy.

Note

Scoping is about containing delivery capability, not about hiding identity from group members. Device Identities are visible in MLS credentials, so anyone you share two groups with can link you across those groups. This is the intended trust boundary, group members are trusted with your identity, servers are not.

Address Derivation

DeliveryAddress Structure

struct DeliveryAddress {
    // Base32 identifier, 24 chars, derived from mailbox_public
    prefix: String,

    // Server domain (e.g., "chat.example.com")
    server: String,

    // Senders encrypt the outer envelope layer to this key. Reaches contacts
    // inside MLS via AddressRotation, never via server.
    mailbox_public: X25519PublicKey,

    // Timestamp of when the address was generated
    created_at: u64,

    // Kept live through the rotation overlap window, so a contact who missed an
    // AddressRotation still reaches a real mailbox
    active: bool,
}

impl DeliveryAddress {
    fn full_address(&self) -> String {
        format!("{}@{}", self.prefix, self.server)
    }

    // Anyone holding the address can check if the prefix binds to the key
    fn verify_binding(&self) -> bool {
        let hash = blake3::hash(self.mailbox_public.as_bytes());
        self.prefix == base32::encode(&hash.as_bytes()[..15])
    }
}

Field Descriptions

• prefix: String

  • First 15 bytes of the Blake3 hash of mailbox_public, base32-encoded
  • Exactly 24 characters
  • base32 is case-insensitive, which an address of the form prefix@server will require
  • MUST be recomputable from mailbox_public by any party holding the address

• server: String

  • Domain of the server hosting this mailbox
  • Devices MAY hold mailboxes on multiple servers, subject to domain separation

• mailbox_public: X25519PublicKey

  • Senders encrypt the outer envelope layer to this key
  • Distributed to group members inside MLS, never to servers

• created_at: u64

  • Unix timestamp of generation
  • MUST NOT be modified after creation

• active: bool

  • Whether the mailbox currently accepts delivery or not
  • Kept true through the rotation overlap window

Note

The prefix is a routing label, not a security boundary. Ownership is proven against mailbox_public. An attacker who finds a colliding prefix would still hold a different keypair, fail challenge-response, and be unable to decrypt anything. Prefix collisions are detectable and rejectable at registration since the server holds the mailbox registry.

Registration

Before a mailbox can receive messages, it must be registered with its server. The server issues a challenge and the device signs it with the mailbox secret.

sequenceDiagram
    participant D as Device
    participant S as Server
    D->>S: Register request (mailbox_public)
    S->>D: Challenge (fresh nonce)
    D->>S: Signature over nonce
    S->>S: Verify signature, verify prefix binds to mailbox_public
    S->>D: Mailbox active

• Servers MUST issue a fresh, unpredictable nonce per registration attempt
• Servers MUST verify that the submitted prefix derives from mailbox_public
• Servers MUST reject a prefix that is already registered
• Servers MUST NOT accept a static signature in place of challenge-response as these are replayable.
• Renewal is re-registration: a device MUST repeat challenge-response with the same prefix before expires_at, and each renewal MUST spend a token like any other registration

Caution

Registration is where unlinkability is won or lost. A device that registers many mailboxes over one authenticated session hands the server a trivial correlation, regardless of how the keys were derived. Registrations SHOULD each spend a separate unlinkable authentication token.

Retrieval

The same challenge-response that proves ownership at registration authorizes retrieval. A device proves it holds the mailbox secret and receives a short-lived session scoped to that one mailbox.

Retrieval is not token-metered. Tokens price creating work for a server - an envelope to queue, a mailbox to track, a blob to store. Fetching what is already queued creates none, and metering it would spend a second token per received message purely to read the first one’s result.

• Servers MUST issue a fresh, unpredictable nonce per retrieval attempt
• A retrieval session MUST be scoped to exactly one mailbox
• Servers MUST NOT accept one session as authorization for another mailbox
• Servers MUST NOT retain any record relating two sessions to each other
• Clients SHOULD hold sessions no longer than needed, and MUST establish them independently per mailbox

Caution

A session covering several mailboxes at once would hand the server the exact join key the whole derivation scheme exists to withhold. One session per mailbox is the requirement; see Security Considerations for the timing correlation that remains regardless.

Rotation

Rotation increments the rotation counter for a scope and derives a fresh keypair. It is two-phase:

1. Derive and register the new mailbox; broadcast an AddressRotation to the group.
2. Keep the old mailbox active through an overlap window, then deregister it.

The overlap matters because AddressRotation is an application message. A member who misses it would otherwise be unable to reach the rotating device at all.

• Devices SHOULD rotate mailboxes periodically
• The previous mailbox MUST remain active for the overlap window

// Matches the PrivacyPass issuance key overlap, so a client that has been
// offline for a week recovers its addressing and its token supply together
const MAILBOX_ROTATION_OVERLAP: Duration = Duration::days(7);

Because registrations expire after 24 hours, holding the overlap open means renewing the old mailbox for its duration, not merely leaving it alone. A full rotation therefore costs one registration for the new mailbox plus up to six renewals of the old one.

• The previous mailbox MUST remain registered for MAILBOX_ROTATION_OVERLAP after the AddressRotation is broadcast
• Devices MUST NOT renew the previous mailbox once the overlap closes
• A member who missed the AddressRotation entirely recovers via AddressBookSnapshot, which is the fallback when the overlap is not enough

Address Distribution

MLS carries credentials, not addresses. A newly added member therefore knows every device_id in the group and no addresses at all - it cannot even address its own announcement. The adding member closes this gap.

sequenceDiagram
    participant A as Adder
    participant J as Joiner
    participant G as Group
    A->>J: MLS Welcome
    A->>J: AddressBookSnapshot
    J->>G: AddressRotation (old_addresses = None)
    G->>G: Address book updated

Clients maintain an address book keyed by (DeviceId, GroupId). The same device presents a different address in every group.

SystemOperation AddressBookSnapshot and AddressRotation message definitions

Transport Independence

Mailboxes are transport-agnostic. Whatever channel wakes a client - a persistent socket, a UnifiedPush distributor, or just plain polling - the wakeup MUST be contentless and MUST NOT identify which mailbox received a message. Naming the mailbox would disclose group structure to the push provider for a negligible saving.

Security Considerations

What this protects against

• Delivery capability containment. A leaked or abused address reaches one group’s mailbox. It can be burned and rotated independently, without disrupting other groups.
• Cross-server linkage. Domain separation means two federated servers share no identifier for a multi-homed device.
• Device identity exposure to servers. The device identity key never appears on the wire. A fully compromised mailbox yields a routing label and nothing that links to device_id.
• Mailbox impersonation. Challenge-response binds registration to the keypair.

What this does not protect against

• Group members linking a device across shared groups. Device Identities are visible in MLS credentials. This is by design: participation in a group means trusting its members with your identity.
• A server linking one device’s mailboxes to each other. Retrieval from a shared source address within correlated time windows links them regardless of how keys are derived. Connection discipline doesn’t really do anything here either; it needs network-level anonymity which is out of scope at this time.
• Group membership inference from delivery timing. A message fan-out delivers to every recipient mailbox at once and as this repeats across conversations, co-delivery sets can reconstruct group membership from the server’s own delivery logs.
• A stored push endpoint. When a client configures push, the endpoint is a long lived identifier that survives mailbox rotation. Distinct endpoints per mailbox avoid handing the server a single join key, however the residual correlation remains.
• Master seed compromise. Total and permanent, across every mailbox.