PQXDH DM Handshake Protocol

Abstract

This LP defines the Post-Quantum Extended Diffie-Hellman (PQXDH) protocol for establishing secure direct message sessions in LuxDA Bus chat.

Motivation

Signal's X3DH protocol provides excellent security properties but relies on classical Diffie-Hellman. PQXDH extends X3DH with:

1. Post-quantum KEM for long-term security
2. Hybrid approach preserving classical security guarantees
3. Compatibility with existing Double Ratchet algorithm

Specification

1. Key Types

// Identity key (long-term)
type IdentityKey struct {
    Classical *Ed25519KeyPair
    PQ        *MLDSAKeyPair
}

// Signed prekey (medium-term, rotated weekly)
type SignedPreKey struct {
    Classical *X25519KeyPair
    PQ        *MLKEMKeyPair
    Signature []byte  // ML-DSA over both public keys
    Timestamp uint64
}

// One-time prekey (single use)
type OneTimePreKey struct {
    Classical *X25519KeyPair
    PQ        *MLKEMKeyPair
    ID        uint32
}

2. Key Bundle

type PQXDHKeyBundle struct {
    IdentityKey     *IdentityKey
    SignedPreKey    *SignedPreKey
    OneTimePreKeys  []*OneTimePreKey
}

// Published to key directory
type PublicKeyBundle struct {
    IdentityPubKey     IdentityPublicKey
    SignedPrePubKey    SignedPrePublicKey
    SignedPreKeyID     uint32
    SignedPreKeySig    []byte
    OneTimePrePubKeys  []OneTimePrePublicKey
}

3. PQXDH Protocol

Alice (initiator) → Bob (responder)

Alice has: IK_A (identity), EK_A (ephemeral)
Bob has: IK_B (identity), SPK_B (signed prekey), OPK_B (one-time prekey)

Step 1: Alice fetches Bob's key bundle from directory

Step 2: Alice computes shared secrets:
  DH1 = X25519(IK_A, SPK_B)           // Identity to signed prekey
  DH2 = X25519(EK_A, IK_B)            // Ephemeral to identity
  DH3 = X25519(EK_A, SPK_B)           // Ephemeral to signed prekey
  DH4 = X25519(EK_A, OPK_B)           // Ephemeral to one-time (if available)

  KEM1 = MLKEM.Encap(SPK_B.PQ)        // KEM to signed prekey
  KEM2 = MLKEM.Encap(OPK_B.PQ)        // KEM to one-time (if available)

Step 3: Alice derives shared secret:
  SK = KDF(DH1 || DH2 || DH3 || DH4 || KEM1.ss || KEM2.ss)

Step 4: Alice sends initial message:
  - IK_A public key
  - EK_A public key
  - SPK_B key ID
  - OPK_B key ID (if used)
  - KEM1 ciphertext
  - KEM2 ciphertext (if used)
  - Encrypted initial message

4. Implementation

type PQXDHSession struct {
    LocalIdentity    *IdentityKey
    RemoteIdentity   *IdentityPublicKey
    SharedSecret     [32]byte
    AssociatedData   []byte
}

func InitiateSession(
    localIdentity *IdentityKey,
    remoteBundle *PublicKeyBundle,
) (*PQXDHSession, *InitialMessage, error)

func RespondToSession(
    localBundle *PQXDHKeyBundle,
    initialMsg *InitialMessage,
) (*PQXDHSession, error)

type InitialMessage struct {
    IdentityKey       []byte     // Sender's identity public key
    EphemeralKey      []byte     // Sender's ephemeral public key
    SignedPreKeyID    uint32
    OneTimePreKeyID   uint32     // 0 if not used
    KEMCiphertext1    []byte     // To signed prekey
    KEMCiphertext2    []byte     // To one-time prekey (optional)
    Ciphertext        []byte     // AEAD encrypted payload
}

5. Associated Data

// AD binds session to both parties' identities
func ComputeAD(
    initiatorIdentity, responderIdentity []byte,
) []byte {
    return append(
        append([]byte("PQXDH"), initiatorIdentity...),
        responderIdentity...,
    )
}

6. Key Derivation

func DeriveSharedSecret(
    dh1, dh2, dh3, dh4 []byte,   // X25519 secrets
    kem1, kem2 []byte,           // ML-KEM secrets
) [32]byte {
    // Concatenate all secrets
    input := make([]byte, 0, 32*6)
    input = append(input, dh1...)
    input = append(input, dh2...)
    input = append(input, dh3...)
    if len(dh4) > 0 {
        input = append(input, dh4...)
    }
    input = append(input, kem1...)
    if len(kem2) > 0 {
        input = append(input, kem2...)
    }

    // KDF with domain separation
    return hkdf.Extract(sha256.New, input, []byte("PQXDH_SK"))
}

7. Transition to Double Ratchet

// Initialize Double Ratchet from PQXDH session
func InitializeRatchet(session *PQXDHSession) *DoubleRatchet {
    return &DoubleRatchet{
        RootKey:        session.SharedSecret,
        LocalIdentity:  session.LocalIdentity,
        RemoteIdentity: session.RemoteIdentity,
    }
}

8. Key Rotation

type KeyRotationPolicy struct {
    SignedPreKeyRotation  time.Duration  // Default: 7 days
    OneTimePreKeyRefill   int            // Refill when below threshold
    IdentityKeyRotation   time.Duration  // Default: never (manual)
}

// Check if rotation needed
func (p *KeyRotationPolicy) NeedsRotation(bundle *PQXDHKeyBundle) bool

Security Considerations

1. Forward secrecy: Ephemeral keys and one-time prekeys ensure forward secrecy
2. Post-compromise security: Double Ratchet provides healing after compromise
3. Hybrid security: Both classical and PQ must be broken to compromise session
4. Deniability: PQXDH provides offline deniability like X3DH
5. One-time prekey exhaustion: Falls back to signed prekey if OPKs exhausted

Test Plan

1. Interoperability with reference PQXDH implementations
2. Session establishment under various key availability scenarios
3. Key rotation and bundle refresh testing
4. Performance benchmarks (latency, key bundle size)

References

• Signal Protocol X3DH Specification
• PQXDH IETF Draft
• LP-6461: DM Sessions

---

LP-2211 v1.0.0 - 2026-01-02