Contact Exchange and Trust Establishment

Bootstrapping Trust

In any secure system, you run into a problem where establishing initial trust is difficult without already having a trusted third party. This is why Cryptid uses out-of-band verification, i.e., we use a separate, authentic channel to exchange cryptographic keys.

This channel could be anything outside the system. A pre-existing trusted chat somewhere, or even in-person meetups.

Shareable Identity Bundles

When someone wants to share their Cryptid contact information, they can generate a ShareableIdentityBundle which looks like this:

struct ShareableIdentityBundle {
    // Device identifier (permanent)
    device_id: [u8; 32],
    // For signature verification
    public_key: Ed25519PublicKey,
    // When the device was created
    created_at: u64,

    // Initial delivery address for first contact
    initial_delivery_address: String,

    // Server where MLS keypackages are uploaded
    keypackage_server: String,

    // User-chosen name
    display_name: Option<String>,
    // User-chosen profile picture
    profile_picture: Option<ProfilePicture>,

    // Self-signed proof that we own the private key for this device_id
    proof_of_ownership: Ed25519Signature,
}

Field Descriptions

device_id and public_key:

• Permanent cryptographic identity
• Used for blocking, trust decisions, and MLS group membership
• Never changes unless device identity is recreated

initial_delivery_address:

• Where to send messages initially
• May become stale if contact rotates addresses
• Contacts update automatically via MLS group address rotation messages
• Format: <16_byte_prefix>@<server_domain> (e.g., a1b2c3d4e5...@chat.example.com)

keypackage_server:

• Where to fetch this device’s MLS KeyPackages from for group additions
• Typically the contact’s primary server
• Required to add this contact to groups (See the MLS KeyPackage Management section below)

display_name and profile_picture:

• Optional user-facing information
• Can be updated independently

proof_of_ownership:

• Signature of device_id using the device’s private key
• Proves that the bundle creator owns the private key for device_id
• Prevents impersonation attacks

Contact Exchange Methods

Method 1: QR Code

Format: qr://chat-device?data=<base64_encoded_identity_bundle>

Method 2: Invite Links

Format: https://example.com/invite/<base64_encoded_identity_bundle>?expires=<timestamp>

Contact Addition Process

Step 1: Alice scans Bob’s QR code

fn add_contact_from_qr(qr_data: &str) -> Result<LocalContact> {
    // Parse the QR data
    let bundle = parse_identity_bundle_from_qr(qr_data)?;

    // Verify proof of ownership - very important
    if !bundle.public_key.verify(&bundle.proof_of_ownership, &bundle.device_id) {
        return Err("Invalid identity proof!");
    }

    // Create local contact entry
    Ok(LocalContact {
        device_id: bundle.device_id,
        public_key: bundle.public_key,
        display_name: bundle.display_name.unwrap_or("Unknown Contact".to_string()),

        // Store delivery address and KeyPackage server
        delivery_addresses: vec![bundle.initial_delivery_address],
        keypackage_server: bundle.keypackage_server,

        trust_level: DirectContactTrust::InPerson,
        added_at: current_unix_timestamp(),
        last_verified: current_unix_timestamp(),
        last_address_update: current_unix_timestamp(),
    })
}

Step 2: Alice sends encrypted first message to Bob

fn send_initial_contact_message(bob_contact: &LocalContact, message: &str) -> Result<()> {
    // Create MLS group for direct messaging
    let dm_group = create_dm_group(&alice_identity, bob_contact)?;

    // Send encrypted first message
    let secure_message = create_secure_message(message, &dm_group)?;
    send_message_via_federation(secure_message, &bob_contact.delivery_address)?;

    Ok(())
}

Trust Levels and Upgrading

enum DirectContactTrust {
    // QR Scanned or face-to-face meeting (highest)
    InPerson,
    // Exchanged over authenticated channel
    SecureChannel,
    // Manual fingerprint verification completed
    Verified,
    // Received via link, needs verification
    FirstContact,
}

Fingerprint Verification

fn generate_fingerprint(public_key: &Ed25519PublicKey) -> String {
    let hash = sha256(public_key.as_bytes());
    // We want to format this 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 these fingerprints over a voice call or in person to upgrade trust level.

MLS KeyPackage Management

Overview

To add contacts to MLS groups, KeyPackages (one-time-use cryptographic material) must be available on their designated server.

KeyPackage properties:

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

Why KeyPackages are Separate from Bundles

ShareableIdentityBundle does NOT include KeyPackages because:

• Bundles are long-lived (stored in contacts, shared via QR codes)
• KeyPackages are ephemeral (used once and discarded)
• KeyPackages must be fresh (pre-generating 100 to include in bundle would require constant regeneration)

Instead, bundles specify a keypackage_server where KeyPackages can be fetched on-demand.

KeyPackage Structure

Each KeyPackage contains:

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

struct KeyPackage {
    protocol_version: ProtocolVersion,
    cipher_suite: CipherSuite, // e.g., MLS_128_DHKEMX25519_AES128GCM_SHA256_Ed25519
    init_key: HPKEPublicKey, // Ephemeral public key for Welcome encryption
    leaf_node: LeafNode {
        encryption_key: HPKEPublicKey, // Ephemeral encryption key
        signature_key: Ed25519PublicKey, // Device identity key
        credential: BasicCredential {
            identity: device_id, // Device identity
        },
    },
    signature: Ed25519Signature, // Signed by device's private key
}

Key points:

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

KeyPackage Upload

Devices upload KeyPackages to their primary server:

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

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

// Upload to server
// POST /api/v1/keypackage/upload
// {
//     "device_id": "aabbccdd...",
//     "key_packages": public_keypackages, // Public part only
//     "signature": "...",
//     "timestamp": 1758315663
// }

// Store private keys locally (needed for Welcome decryption)
alice.store_keypackage_private_keys(keypackage_bundles)?;

Server storage:

struct KeyPackageStore {
    device_id: [u8; 32],
    key_packages: Vec<KeyPackage>, // Public KeyPackages only
    uploaded_at: u64,
    total_consumed: u32,
}

// Indexed by device_id
keypackage_storage: HashMap<DeviceId, KeyPackageStore>

Danger

Unfortunately, this does mean that the server can see when you get invited to a chat because a KeyPackage will get consumed for the invitation.

However, the server doesn’t know who is inviting you or which group you’re being invited to.

If multiple devices from the same server get invited to a group at the same time, the server can guess that all of you might be in the same group though.

I’m figuring out ways to shield from this, but they require quite a bit of work, so I’m planning on getting them ready for Cryptid V2.

KeyPackage Fetching and Group Addition

When adding a contact to a group:

impl LocalContact {
    /// Fetch KeyPackage for adding this contact to a group
    fn fetch_keypackage(&self, http_client: &HttpClient) -> Result<KeyPackage> {
        // Fetch from contact's designated server
        let url = format!(
            "https://{}/api/v1/keypackage/fetch?device_id={}",
            self.keypackage_server,
            hex::encode(&self.device_id)
        );

        let response: KeyPackageResponse = http_client.get(&url)?;

        // KeyPackage is deleted from server (one-time use)
        Ok(response.key_package)
    }
}

// Usage: Bob adds Alice to "Work Team" group
let alice = bob.contacts.get(&alice_device_id)?;

// Fetch Alice's KeyPackage
let alice_keypackage = alice.fetch_keypackage(&http_client)?;

// Add Alice to group (OpenMLS API)
let (commit, welcome, _) = work_team_group.add_members(
    provider,
    &bob.device.keypair,
    &[alice_keypackage]
)?;

// Merge pending commit
work_team_group.merge_pending_commit(provider)?;

// Send Welcome to Alice's delivery address
bob.send_welcome(&alice.delivery_address, welcome)?;

Joining via Welcome

When receiving a Welcome message:

// Alice receives Welcome from Bob
let welcome = alice.receive_welcome_message()?;

// Alice uses her stored private key (from KeyPackageBundle) to decrypt
let staged_join = StagedWelcome::new_from_welcome(
    provider,
    &MlsGroupJoinConfig::default(),
    welcome,
    None, // Ratchet tree included in Welcome (RatchetTreeExtension)
)?;

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

Important: The Welcome is encrypted with the ephemeral HPKE public key from Alice’s KeyPackage. Alice needs the corresponding private key (stored when she generated the KeyPackage) to decrypt it.

KeyPackage Rotation

Clients monitor KeyPackage count and upload more when running low:

async fn maintain_keypackages(device: &mut DeviceIdentity, server: &str) {
    loop {
        // Check remaining count
        let remaining = query_remaining_keypackages(server, &device.device_id).await?;
        if remaining < 20 {
            // Generate and upload more KeyPackages
            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?;

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

        // Check every 24 hours
        sleep(Duration::hours(24)).await;
    }
}

Ratchet Tree Requirement

When joining a group via Welcome, the joiner needs:

1. The Welcome message (encrypted with their KeyPackage)
2. The ratchet tree (group’s current key state)

Solution: Enable RatchetTreeExtension when creating groups:

// Alice creates group with RatchetTreeExtension
let config = MlsGroupCreateConfig::builder()
    .use_ratchet_tree_extension(true) // Include tree in Welcome
    .build();

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

// When adding Bob, Welcome automatically includes ratchet tree
let (commit, welcome, _) = alice_group.add_members(...)?;

// Bob can join without separate tree (it's in the Welcome)
let staged_join = StagedWelcome::new_from_welcome(
    provider,
    &config,
    welcome,
    None, // No separate tree needed
)?;

All Cryptid groups MUST enable RatchetTreeExtension for simpler Welcome handling.

Multi-Server Considerations

When multi-homing (addresses on multiple servers):

• KeyPackages are uploaded to the primary server only (specified in keypackage_server)
• Other servers handle message delivery only
• This avoids KeyPackage synchronization complexity

Supported Cipher Suites

At the moment, Cryptid only supports one MLS cipher suite:

1. MLS_128_DHKEMX25519_AES128GCM_SHA256_Ed25519

   • Uses AES-128-GCM for encryption
   • Best for devices with hardware AES acceleration (modern CPUs)
   • Faster when hardware support is available

Privacy Considerations

KeyPackage Storage Privacy Limitation

Servers storing KeyPackages can observe:

Observable metadata (per device)

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

Example: Server knows “Device X consumed 50 KeyPackages over 30 days”.

What servers CANNOT observe

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

Privacy impact

This reveals aggregate social activity level (how socially active a user is) but not:

• Message content or relationships
• Specific group memberships
• Individual conversation patterns

Planned improvement (v2.0):

Future versions will support blind KeyPackage storage where servers store KeyPackages indexed by cryptographic hash (not device_id), eliminating per-device activity tracking.

This requires:

• Larger ShareableIdentityBundles (include KeyPackage hashes)
• Client-side hash management
• KeyPackage refresh protocol

For v1.0, standard storage (indexed by device_id) prioritizes simplicity and UX with documented privacy trade-offs.