Contact Exchange and Trust Establishment

Bootstrapping Trust

In any secure system, establishing initial trust without a pre-existing trusted third party is challenging. Cryptid uses out-of-band verification: a separate, authentic channel to exchange cryptographic keys.

This channel can be anything outside the Cryptid system:

• Pre-existing trusted chat (Signal, Matrix, etc)
• In-person meetup
• Phone call or video conference
• Shared physical medium (QR code printed on business card)

Contact Exchange via InfoPackages

When someone wants to share their Cryptid contact information, they generate an InfoPackage which is an ephemeral, on-demand token containing their identity and devices.

See InfoPackages for the detailed specification.

The Bootstrap Path

Everything needed to start a conversation with a stranger is reachable from a single QR code. The chain is short, but it crosses four documents, so it’s worth seeing end to end before the step-by-step below.

sequenceDiagram
    participant A as Alice
    participant IP as InfoPackage Host
    participant KS as Bob's keypackage_server
    participant BM as Bob's contact mailbox

    Note over A: Scan QR, obtain CompactInfoQR
    A->>IP: Fetch the InfoPackage by segment
    IP->>A: Ciphertext (the host cannot read it)
    Note over A: Decrypt with the key from the QR
    Note over A: Derive kp_handle and kp_key per device
    A->>KS: Fetch by handle (no token)
    KS->>A: Ciphertext, entry deleted on read
    Note over A: Verify credential matches the derived device_id
    A->>BM: Welcome
    Note over BM: Bob joins and broadcasts AddressRotation

What Each Step Yields

Step	Produces	Used for
Scan	CompactInfoQR	the URL, and the key the server never had
Fetch + decrypt	IdentityInfoPackage	user_id, personas, and devices
Read devices	DevicePublicInfo per device	device_id, keypackage_server, contact_addresses
Derive	kp_handle, kp_key	addressing and decrypting the KeyPackage
Fetch + decrypt	KeyPackage	add_members
Send	Welcome to contact_addresses	Bob’s contact mailbox, the one that accepts strangers

The Handle is Derived, Not Looked Up

There is no directory step, and no request that asks “where are these device’s KeyPackages”. Both the storage index and its encryption key are computed locally from a device_id you already hold:

let epoch = now() / KP_EPOCH_SECS;
let handle = kp_handle(&device_id, epoch);
let key = kp_key(&device_id, epoch);

This is what makes the store blind. The host serves an entry without knowing whose it is, because nobody every told it - and the parties who can derive a handle are exactly those who would legitimately add the device to a group.

The fetch spends no token and needs no authentication. Possession of the handle is the authorization, and since a handle can only be derived from a device_id, holding one is already evidence of being a contact or a fellow member.

The Other Direction

The path above is the pull: Alice has Bob’s InfoPackage and reaches out. The push is ContactRequest, which carries the sender’s own devices: Vec<DevicePublicInfo> to a recipient’s contact mailbox.

Same fields, same derivation, opposite direction - and it’s why InnerEnvelope.group_id is Option<group_id>. A None marks the one message that arrives before any group exists to name.

Two Things That Bite

1. The epoch boundary. Handles roll every 24 hours. A scan at 23:59:58 derives the incoming epoch’s handle while the target’s device uploaded under the outgoing one, and the fetch misses.

   • On the bootstrap path, clients MUST retry a miss against the adjacent epoch before reporting failure

   • This is stricter than the general rule in PrivacyPass Authentication, which makes the retry a SHOULD. Here a miss surfaces to the user as “this contact cannot be added”, not as a background retry, so it warrants the stronger requirement.

2. The device list is a snapshot. An IdentityInfoPackage is encrypted once and can live up to 30 days, so a device linked afterwards will not appear in it. The adder adds the devices it knows about; the contact’s other devices add the new one to those groups later, per Adding New Device to Existing Groups.

Contact Addition Flow

Step 1: Alice Generates Contact QR

let alice_identity = IdentityInfoPackage {
    user_id: alice_id,
    user_public_key: alice_pubkey,
    default_persona: Persona {
        display_name: Some("Alice".to_string()),
        pronouns: Some("she/her".to_string()),
        bio: Some("Engineer".to_string()),
        profile_picture: Some(ProfilePicture { ... }),
    },
    personas: None,
    devices: vec![alice_phone, alice_laptop],
    profile_picture: Some(ProfilePicture { ... }),
    created_at: now(),
};

// Upload to server (on-demand, encrypted)
let response = alice_client.upload_info_package(
    InfoPackageUploadRequest {
        package_type: InfoPackageType::Identity,
        content: InfoPackageContent::Identity(alice_identity),
        ttl_seconds: 24 * 3600, // Valid for 24 hours
        max_uses: Some(100),    // Up to 100 scans
    }
).await?;

// Get compact QR payload
let qr = response.qr_data;
// {
// "url": "https://chat.example.com/ip/abc123",
// "key": "...",
// "type": "identity",
// "name": "Alice"
// }

// Display QR code
alice_client.display_qr(&qr)?;

What the server stores: Encrypted blob only. Server cannot decrypt.

What Alice keeps: Decryption key (displayed in QR via info_package_key).

Step 2: Bob Scans Alice’s QR

// Bob's app scans and parses CompactInfoQR
let qr: CompactInfoQR = scan_qr()?;

println!("Add contact: {}", qr.display_name); // Shows "Alice"

// Bob's client fetches encrypted package from server
let response = bob_client.fetch_info_package(&qr.info_package_url).await?;

// Bob's client decrypts using key from QR
let alice_identity = decrypt_and_parse::<IdentityInfoPackage>(
    &response.ciphertext,
    &qr.info_package_key,
)?;

// Extract identity
let alice_contact = LocalContact {
    user_id: alice_identity.user_id,
    user_public_key: alice_identity.user_public_key,
    default_persona: alice_identity.default_persona,
    personas: alice_identity.personas,
    devices: alice_identity.devices,
    profile_picture: alice_identity.profile_picture,
    trust_level: DirectContactTrust::InPerson, // QR scan = high trust
    added_at: now(),
    last_verified: now(),
};

// Bob's app shows: "Add Alice as contact?"
// Bob confirms -> Alice is now in Bob's contact list
bob_client.add_contact(alice_contact).await?;

Privacy property: Server doesn’t know Bob fetched Alice’s package (fetch is anonymous).

LocalContact Structure

struct LocalContact {
    user_id: UserId,
    user_public_key: Ed25519PublicKey,

    // User's presentation identities
    default_persona: Persona,
    personas: HashMap<NonZeroU16, Persona>,

    // All devices for this user
    devices: Vec<DevicePublicInfo>,

    // Profile picture (thumbnail for quick display, full image via blob store)
    profile_picture: Option<ProfilePicture>,

    // Trust and metadata
    trust_level: DirectContactTrust,
    added_at: u64,
    last_verified: u64,
}

Trust Levels

enum DirectContactTrust {
    // QR code scanned or face-to-face meeting
    InPerson,

    // Exchanged over authenticated channel (Signal, encrypted email, etc.)
    SecureChannel,

    // Manual fingerprint verification completed
    Verified,

    // Received via unverified link or referral
    FirstContact,
}

Fingerprint Verification

Users verify the User Identity public key fingerprint (not individual device keys):

fn generate_user_fingerprint(user_public_key: &Ed25519PublicKey) -> String {
    let hash = Blake3(user_public_key.as_bytes());

    // Format as readable groups: "1234 5678 9ABC DEF0"
    hex::encode(&hash[..16])
        .chars()
        .collect::<Vec<char>>()
        .chunks(4)
        .map(|chunk| chunk.iter().collect::<String>())
        .collect::<Vec<String>>()
        .join(" ")
        .to_uppercase()
}

// Example output: "A1B2 C3D4 E5F6 1728 394A 7D8E 9F10"

Users can verify fingerprints later to upgrade trust level.

Why User Identity instead of Device Identity?

• More convenient (one fingerprint per person, not per device)
• Persistent (doesn’t change when adding new devices)
• User-centric (“I trust Alice” not “I trust Alice’s iPhone”)

Inviting Contacts to Groups

When adding a contact to a group, all their devices are invited simultaneously:

fn invite_user_to_group(
    group: &mut MlsGroup,
    contact: &LocalContact,
    self_device: &DeviceIdentity,
    provider: &impl OpenMlsProvider,
) -> Result<InvitationResult> {
    let mut successful_devices = Vec::new();
    let mut failed_devices = Vec::new();

    // Fetch KeyPackages for ALL devices
    for device_info in &contact.devices {
        match fetch_keypackage(&device_info.keypackage_server, &device_info.device_id) {
            Ok(keypackage) => {
                successful_devices.push((device_info.clone(), keypackage))
            }
            Err(e) => {
                failed_devices.push((device_info.device_id, e.to_string()))
            }
        }
    }

    // Proceed if at least ONE device has a KeyPackage
    if successful_devices.is_empty() {
        return Err("No KeyPackages available for any of contact's devices");
    }

    // Extract KeyPackages
    let keypackages: Vec<KeyPackage> = successful_devices.iter()
        .map(|(_, kp)| kp.clone())
        .collect();

    // Add all devices in single MLS commit
    let (commit, welcomes) = group.add_members(
        provider,
        &self_device.keypair,
        &keypackages,
    )?;

    group.merge_pending_commit(provider)?;

    // Send Welcome to each successfully added device
    for ((device_info, _), welcome) in successful_devices.iter().zip(welcomes) {
        send_to_contact_mailbox(
            welcome,
            &device_info.contact_addresses[0],
        )?;
    }

    Ok(InvitationResult {
        invited_user: contact.user_id,
        successful_devices: successful_devices.iter()
            .map(|(d, _)| d.device_id)
            .collect(),
        failed_devices,
    })
}

Why Invite All Devices?

• Users expect to access groups from all their devices
• One MLS commit keeps group state consistent
• Better UX than adding devices one-by-one
• Failed devices can be added later when KeyPackages available

Group Invites via InfoPackage

Moderators can invite people to groups using InfoPackages (similar to contact invites):

Creating a Group Invite

let group_invite = GroupInviteInfoPackage {
    group_id: team_chat_group.id,
    group_name: "Team Chat".to_string(),
    group_description: Some("Engineering team".to_string()),
    group_avatar: Some(ProfilePicture { /* ... */ }),

    // MLS welcome message (group admission credential)
    welcome_message: team_chat_group.create_welcome_message()?,

    invited_by: alice_id,
    invited_by_name: "Alice".to_string(),
    created_at: now(),
}

// Upload invite to server (ephemeral)
let response = alice_client.upload_info_package(
    InfoPackageUploadRequest {
        package_type: InfoPackageType::GroupInvite {
            group_id: team_chat_group.id,
        },
        content: InfoPackageContent::GroupInvite(group_invite),
        ttl_seconds: 7 * 24 * 3600, // Valid 1 week
        max_uses: Some(10),         // Max 10 people
    }
).await?;

// Display QR code
alice_client.display_qr(&response.qr_data)?;

Joining via Group Invite

// Bob scans group invite QR
let qr = scan_qr()?;

// Bob's client fetches and decrypts invite
let invite = bob_client.fetch_and_decrypt_info_package::<GroupInviteInfoPackage>(
    &qr.info_package_url,
    &qr.info_package_key,
).await?;

// Bob sees: "Join 'Team Chat' invited by Alice?"
println!("Join '{}' invited by {}?",
invite.group_name,
invite.invited_by_name
);

// Bob confirms -> joins group using welcome message
bob_client.join_group_from_invite(&invite).await?;

Privacy benefit: Server doesn’t know how many people joined via a group invite.

Managing Multi-Device Contacts

Updating Device Lists

When a contact adds a new device, they can share an updated InfoPackages:

fn update_contact_devices(
    contact: &mut LocalContact,
    updated_package: &IdentityInfoPackage,
) -> Result<Vec<DevicePublicInfo>> {
    // Verify same user
    if contact.user_id != updated_package.user_id {
        return Err("User ID mismatch");
    }

    // Find new devices
    let new_devices: Vec<DevicePublicInfo> = updated_package.devices.iter()
        .filter(|new_device| {
            !contact.devices.iter()
                .any(|existing| existing.device_id == new_device.device_id)
        })
        .cloned()
        .collect();

    // Update device list
    contact.devices = updated_package.devices.clone();

    // Update metadata
    contact.default_persona = updated_package.default_persona.clone();
    contact.personas = updated_package.personas.clone();
    contact.profile_picture = updated_package.profile_picture.clone();

    Ok(new_devices)
}

Adding New Device to Existing Groups

When a contact adds a new device, add it to groups where user is already member:

async fn add_new_device_to_group(
    group: &mut MlsGroup,
    new_device: &DevicePublicInfo,
    self_device: &DeviceIdentity,
    provider: &impl OpenMlsProvider,
) -> Result<()> {
    // Fetch KeyPackage for new device
    let keypackage = fetch_keypackage(
        &new_device.keypackage_server,
        &new_device.device_id,
    ).await?;

    // Add device to group
    let (commit, welcome) = group.add_members(
        provider,
        &self_device.keypair,
        &[keypackage],
    )?;

    group.merge_pending_commit(provider)?;

    // Send Welcome to new device
    send_to_contact_mailbox(welcome, &new_device.contact_addresses[0]).await?;

    Ok(())
}

Tracking Devices in Groups

Maintain mapping of which devices are in each group:

struct GroupMember {
    // User identity
    user_id: UserId,

    // User's personas
    default_persona: Persona,
    personas: HashMap<NonZeroU16, Persona>,

    // Device membership tracking
    devices_in_group: HashSet<DeviceId>,     // Device IDs currently in
    devices_pending: Vec<DevicePublicInfo>,  // Failed during initial invite

    // Metadata
    added_by: DeviceId,
    added_at: u64,
}

MLS KeyPackage Management

Overview

To add contacts to MLS groups, KeyPackages must be available on their designated server.

KeyPackage properties:

• One-time use (adds device to exactly one group)
• Pre-generated and uploaded to servers
• Fetched on-demand when inviting
• Contains ephemeral HPKE keys + device credential

KeyPackage Structure

KeyPackage Structure

struct KeyPackageBundle {
    key_package: KeyPackage,     // Public (uploaded to server)
    private_key: HpkePrivateKey, // Private (stored locally)
}

struct KeyPackage {
    // MLS protocol version (RFC 9420), currently mls10. This is MLS's field,
    // not a Cryptid specification version
    protocol_version: ProtocolVersion,
    cipher_suite: CipherSuite,
    init_key: HPKEPublicKey,     // For Welcome encryption
    leaf_node: LeafNode {
        encryption_key: HPKEPublicKey,
        signature_key: Ed25519PublicKey,
        credential: BasicCredential {
            identity: device_id,
        },
    },
    signature: Ed25519Signature, // Signed by device
}

Key points:

• Public KeyPackage uploaded to server
• Private HPKEPrivateKey stored locally (decrypt Welcome)
• Each KeyPackage has unique ephemeral keys
• All share same device credential

KeyPackage Upload

Devices upload KeyPackages to their primary server:

// Generate 100 KeyPackages
let keypackage_bundles = alice.device.generate_key_packages(100);

// Extract public parts for upload
let public_keypackages: Vec<KeyPackage> = keypackage_bundles.iter()
    .map(|bundle| bundle.key_package.clone())
    .collect();

// Upload to server
alice_client.upload_keypackages(
    &keypackage_server,
    public_keypackages,
    token
).await?;

// Store private keys locally
alice.store_keypackage_private_keys(keypackage_bundles)?;

KeyPackage Fetching

When adding contact to group, fetch their KeyPackages:

impl LocalContact {
    fn fetch_all_keypackages(
        &self,
        http_client: &HttpClient,
    ) -> Vec<(DevicePublicInfo, Result<KeyPackage>)> {
        let epoch = now() / KP_EPOCH_SECS;

        self.devices.iter().map(|device| {
            // Both values derived locally. Nothing identifies the device
            // to the server holding its KeyPackages
            let handle = kp_handle(&device.device_id, epoch);
            let key = kp_key(&device.device_id, epoch);

            let url = format!(
                "https://{}/api/v1/keypackages/{}",
                device.keypackage_server,
                hex::encode(&handle)
            );

            // No token: the handle is the capability
            let result = http_client.get(&url)
                .and_then(|ct: Vec<u8>| decrypt_keypackage(&key, &ct))
                .and_then(|kp| verify_credential(&kp, &device.device_id));

            (device.clone(), result)
        }).collect()
    }
}

Joining via Welcome

When receiving Welcome from group addition:

// Receive Welcome message from Bob's server
let welcome = alice.receive_message_from_mls_server()?;

// Decrypt using stored private key from KeyPackageBundle
let staged_join = StagedWelcome::new_from_welcome(
    provider,
    &MlsGroupJoinConfig::default(),
    welcome,
    None, // Ratchet tree is already in Welcome
)?;

// Finalize join
let mut alice_group = staged_join.into_group(provider)?;

KeyPackage Rotation

Clients monitor count and upload more when running low:

async fn maintain_keypackages(device: &mut DeviceIdentity, server: &str) {
    loop {
        // Check remaining
        let remaining = query_remaining_keypackages(server, &device.device_id).await?;

        if remaining < 20 {
            // Generate and upload more
            let keypackage_bundles = device.generate_key_packages(100);
            let public_keypackages: Vec<KeyPackage> = keypackage_bundles.iter()
                .map(|b| b.key_package.clone())
                .collect();

            upload_keypackages(server, public_keypackages, token).await?;
            device.store_keypackage_private_keys(keypackage_bundles)?;
        }

        // Check every 24 hours. This also re-uploads under the new handle,
        // since entries cannot cross an epoch boundary
        sleep(Duration::hours(24)).await;
    }
}

Ratchet Tree Requirement

Joiners need the ratchet tree (group’s current key state) to join via Welcome.

You can do this by enabling RatchetTreeExtension in the MlsGroupCreateConfig:

let config = MlsGroupCreateConfig::builder()
    .use_ratchet_tree_extension(true)
    .build();

let mut group = MlsGroup::new(
    provider,
    &creator.device.keypair,
    &config,
    creator.device.create_mls_credential(),
)?;

// Welcome automatically includes ratchet tree
let (commit, welcome, _) = group.add_members(...)?;

// Joiner doesn't need separate tree fetch
let staged_join = StagedWelcome::new_from_welcome(
    provider,
    &config,
    welcome,
    None, // No separate tree needed
)?;

All Cryptid groups MUST enable RatchetTreeExtension.

Supported Cipher Suites

Currently supported:

• MLS_128_DHKEMX25519_CHACHA20POLY1305_SHA256_Ed25519

See MLS Integration for details.

Privacy Considerations

KeyPackage Storage Privacy

Danger

Servers storing KeyPackages can observe when you get invited to groups (KeyPackage consumption spike), but not:

• Who is inviting you
• Which group you’re joining
• Message content

However, if multiple devices from the same server get invited simultaneously, the server can guess they might be in the same group.

Blind KeyPackage storage (eliminating per-device tracking) is planned for Cryptid v2.

Observable Metadata

Per-device tracking:

• Total KeyPackages uploaded
• Total KeyPackages consumed (aggregate)
• Approximate group addition frequency

Example: Server knows “Device X consumed 50 KeyPackages over 30 days” (implies ~1-2 groups per day).

What Servers CANNOT Observe

• Which specific groups
• Who else is in those groups
• Message content (E2EE)
• Message recipients (sender addresses hidden)
• Group membership lists

Multi-Device Privacy

When inviting a user with multiple devices:

Server-side visibility:

• Multiple KeyPackages consumed simultaneously
• Reveals approximate device count for invited user

Group member visibility:

• All members see user operates multiple devices
• Device count and IDs visible in MLS state
• This is acceptable (expected in groups)

Remains private:

• Device names
• User-to-device mapping
• Message content

Future Improvements (v2.0)

Blind KeyPackage Storage:

• Index by cryptographic hash (not device_id)
• Eliminates per-device activity tracking
• Requires larger ShareableIdentityBundles (include hashes)
• Client manages hash lookup

For v1.0, standard storage (device_id indexed) prioritizes simplicity with documented privacy tradeoffs.