KeyPackages

KeyPackages are what let a device be added to a group while offline. Distributing them naively would reintroduce device_id on every axis the rest of the design removes it from - the upload authenticates as a device, the store indexes by one, and the fetch names the device being added, which states a social-graph edge outright.

Cryptid stores them under a derived handle, encrypted under a derived key. The server holds ciphertext at an opaque index and can read neither.

Handle Derivation

const KP_EPOCH_SECS: u64 = 86_400;

fn kp_handle(device_id: &[u8; 32], epoch: u64) -> [u8; 32] {
    blake3::derive_key(&format!("cryptid kp handle v1 {}", epoch), device_id)
}

fn kp_key(device_id: &[u8; 32], epoch: u64) -> [u8; 32] {
    blake3::derive_key(&format!("cryptid kp key v1 {}", epoch), device_id)
}

Anyone holding a device_id derives both independently, with no registry and no distribution step. That set is exactly the parties who would legitimately add the device to a group. Nobody else can, because device_id is a 256-bit Blake3 hash and is not enumerable.

BlindKeyPackageEntry Structure

/// What the server stores. It holds no device_id in any field, and cannot
/// read the credential inside the ciphertext.
struct BlindKeyPackageEntry {
    // blake3::derive_key("cryptid kp handle v1 {epoch}", device_id)
    handle: [u8; 32],

    // KeyPackage encrypted under a key derived the same way. Without this
    // the stored MLS credential would still expose the device_id
    ciphertext: Vec<u8>,

    // Plaintext so the server can garbage-collect. Leaks nothing.
    expires_at: u64,
}

UploadKeyPackages

Stores a batch of encrypted KeyPackages under a handle.

• Input: Vec<BlindKeyPackageEntry>
• Output: UploadReceipt { handle, accepted }
• Auth: PrivacyPass
• Idempotent: No - entries accumulate
• Errors: TOKEN_INVALID, TOKEN_REPLAYED, BUDGET_EXHAUSTED, ENTRY_CAP_EXCEEDED

Requirements

• Upload MUST spend one token per batch
• The request MUST NOT carry device_id in any field
• Entries MUST be encrypted under kp_key before upload
• Servers MUST NOT attempt to validate stored KeyPackages, which they cannot read
• Server MAY enforce a per-handle entry cap to bound storage

Devices upload 50-100 per epoch. One token buys the batch, not the entry.

HTTP Binding

POST /api/v1/keypackages
Authorization: PrivateToken token="<base64url>"
Content-Type: application/cryptid+tls

FetchKeyPackage

Consumes one KeyPackage from a handle.

• Input: None - the handle is in the path
• Output: ciphertext
• Auth: Capability handle
• Idempotent: No - delete-on-read
• Errors: HANDLE_NOT_FOUND, HANDLE_EXHAUSTED

Requirements

• Fetch MUST NOT require a token
• Clients fetch directly from the target’s keypackage_server, taken from DevicePublicInfo
• Servers MUST address entries by handle only
• Servers MUST delete an entry on read; KeyPackages are one-time use
• Servers SHOULD rate limit fetches per source address and per handle
• Clients MUST verify the decrypted credential matches the device_id they derived the handle from

That last requirement is what makes a hostile server harmless here. It cannot forge an entry, because it holds no kp_key and cannot produce valid ciphertext under one. The worst it can do is withhold.

Why Fetch is Unmetered

The same wall that makes blob fetch unmetered. A device’s KeyPackages live on its own keypackage_server, which is usually not your own, and tokens redeem only at the server that issued them - so you hold nothing that server would accept.

Relaying through your home server would restore metering, but at a worse price. The handle is opaque, so your server would need the destination to route, which hands it a social-graph edge at server granularity. We explicitly do not want this according to our threat model.

Note

Depletion is bounded by rate limiting rather than by tokens. Deriving a handle requires the target’s device_id, so a drainer is already a contact or a fellow group member - not an arbitrary stranger - and every request arrives at one server from one source. A compromised server can observe KeyPackage consumption either way; metering only charged for the fetch, it never hid it.

HTTP Binding

GET /api/v1/keypackages/{handle}

Epoch Rotation

Handles roll every 24 hours and both parties re-derive independently. Nothing is redistributed.

Entries do not survive the boundary. KeyPackages uploaded under epoch N sit at a handle nobody looks for during N+1. Devices MUST re-upload each epoch and let the old entries expire.

This is deliberate. Any server-side “migrate this handle to that one” would tell the server the two handles belong to one device, collapsing the epoch reset entirely. Re-upload is the price of the property.

• Devices SHOULD upload under the new epoch shortly before the boundary, keeping both live briefly
• Clients SHOULD retry a miss against the adjacent epoch before treating it as exhaustion
• Servers MUST NOT link handles across an overlap; they cannot distinguish two epochs of one device from two different devices

What the Server Sees

Observes	Cannot Determine
A handle exists and holds N entries	Which device the handle belongs to
Entries were uploaded and consumed	What is inside any entry
Consumption rate per handle, within one epoch	That two handles are the same device across epochs

Within a 24 hour epoch, fetches for one device share a handle, so consumption per pseudonym is visible. That is the residual, and the epoch length is what bounds it.