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.

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 device-to-device)
    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_message(
            welcome,
            &device_info.initial_delivery_address,
        )?;
    }

    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_message(welcome, &new_device.initial_delivery_address).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

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

struct KeyPackage {
    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,
).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>)> {
        self.devices.iter().map(|device| {
            let url = format!(
                "https://{}/api/v1/keypackage/fetch?device_id={}",
                device.keypackage_server,
                hex::encode(&device.device_id)
            );

            let result = http_client.get(&url)
                .and_then(|resp: KeyPackageResponse| Ok(resp.key_package));

            (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).await?;
            device.store_keypackage_private_keys(keypackage_bundles)?;
        }

        // Check every 24 hours
        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.