Session Handshake (X3DH + PQXDH)

This chapter specifies the cryptographic handshake that establishes a new Konstruct session between two identities. The classical part (X3DH) follows the Signal Protocol X3DH whitepaper with concrete parameters listed in §4.1. The post-quantum extension (PQXDH) layers an ML-KEM-768 KEM on top of X3DH such that the resulting session is secure if either the classical or the post-quantum component holds.

Keywords MUST, MUST NOT, SHOULD, MAY are per RFC 2119.

4.1 Notation and constants

The following protocol-level byte strings are fixed:

An interoperable implementation MUST use these exact byte values. Changing any of them produces incompatible sessions (the AEAD on the first message will fail).

4.2 Bundle publication (Bob)

Before any handshake can occur, Bob MUST have published a registration bundle to the directory. The bundle wire format is defined in §3.9.

Bob MUST:

1. Generate a fresh SPK and Kyber-SPK at registration; record the issue timestamp and spk_rotation_epoch = 0.
2. Sign the SPK as sig_SPK = Ed25519_Sign(SK_priv, SPK_pub || epoch_be).
3. Sign the Kyber-SPK as sig_KSPK = Ed25519_Sign(SK_priv, KEM_pub || epoch_be).
4. Upload (IK_pub, SK_pub, SPK_pub, sig_SPK, epoch, OPKs, Kyber-SPK, sig_KSPK, Kyber-OPKs) to the directory.
5. Re-upload (rotate) the SPK and Kyber-SPK at most every 10 days (SPK_MAX_AGE_SECS, §3.5), monotonically incrementing the epoch.

4.3 X3DH (Suite 1) — initiator path

Alice MUST perform the following steps to initiate a session with Bob.

Step 1: Fetch and validate the bundle

Alice fetches Bob's bundle from the directory. She MUST then:

1. Verify sig_SPK over SPK_pub || epoch_be using SK_pub. If verification fails, abort.
2. Verify that SPK_age = now − SPK_issued_at ≤ SPK_MAX_AGE_SECS (10 days). A stale SPK MUST cause abort (replay protection per SEC-001).
3. If the bundle contains one or more OPKs, select exactly one and record its opk_id (for Bob to consume).
4. (Suite 2 only) Verify sig_KSPK and Kyber-SPK freshness identically. If Suite 2 is requested and the Kyber-SPK is missing or stale, abort (SEC-002). The protocol MUST NOT silently downgrade from Suite 2 to Suite 1.

Step 2: Generate ephemerals

Alice generates a fresh X25519 ephemeral keypair EK_A.

Step 3: Compute DH outputs

The four (or three, if no OPK) DH outputs are:

DH1 = DH(IK_A_priv, SPK_B_pub)
DH2 = DH(EK_A_priv, IK_B_pub)
DH3 = DH(EK_A_priv, SPK_B_pub)
DH4 = DH(EK_A_priv, OPK_B_pub)        — omitted if no OPK

The order matters; an implementation that concatenates them in a different order produces a different root key and is non-interoperable.

DH_combined = DH1 || DH2 || DH3 || DH4

In Suite 1 the length of DH_combined is either 128 bytes (4-DH) or 96 bytes (3-DH fallback). The 3-DH fallback path is functional but has reduced forward secrecy and is tracked as the open issue BS-3; implementations SHOULD warn when it is taken.

Step 4: Derive the root key

SK_root = KDF(salt = F, IKM = DH_combined,
              info = b"Construct-X3DH-RootKey-v1", L = 32)

SK_root is the initial Double Ratchet root key (RK₀). Implementations MUST zeroise DH_combined and the individual DH_n slices after this step.

Step 5: Initialise the Double Ratchet sending state

The initiator immediately performs the first DH ratchet step (see §5.6) using SK_root and Bob's SPK_pub as the initial remote DH key. The result is RK₁ plus a new sending chain key CK_s₀.

Step 6: Encrypt and send the first message

Alice encrypts her first plaintext under MK_0 = KDF_CK(CK_s₀, "msg") (§5.4). The wire-format envelope MUST contain:

FirstMessageEnvelope (Suite 1) ::=
    suite_id          : u16 = 0x0001
    ek_pub            : [u8; 32]      -- Alice's X25519 ephemeral pub
    opk_id            : Option<u32>   -- which of Bob's OPKs was used
    message_number    : u32 = 0
    dh_pub            : [u8; 32]      -- Alice's first ratchet DH pub
    prev_chain_length : u32 = 0
    nonce             : [u8; 12]
    ciphertext        : Bytes
    aead_tag          : [u8; 16]

Field ordering and sizes are normative for interoperability. The nonce is generated by the AEAD implementation (chacha20poly1305 0.10).

4.4 X3DH (Suite 1) — responder path

Bob first learns about the session by receiving Alice's first message. He MUST:

1. Look up his own IK_priv, SPK_priv (at the epoch indicated by the bundle Alice consumed), and OPK_priv[opk_id] from his key store.

2. Compute the same four DH outputs:

   DH1 = DH(SPK_B_priv, IK_A_pub)
   DH2 = DH(IK_B_priv,  EK_A_pub)
   DH3 = DH(SPK_B_priv, EK_A_pub)
   DH4 = DH(OPK_B_priv, EK_A_pub)        — when opk_id is present
   

   Note: subscripts swap to maintain DH(IK_A_priv, SPK_B_pub) = DH(SPK_B_priv, IK_A_pub) (X25519 is symmetric).

3. Derive SK_root with the same KDF call as the initiator.

4. Initialise the Double Ratchet receiving state, then run the first ratchet step using EK_A_pub from the envelope as the initial remote DH key.

5. AEAD-decrypt the ciphertext (with AD as defined in §5.4). If decrypt fails, abort and surface a clear error (the reference returns Crypto::AeadVerifyFailed rather than silently dropping).

6. MUST delete the consumed OPK_priv[opk_id] so it cannot be reused (this is the source of forward secrecy contributed by the OPK).

If both Alice and Bob initiate concurrently (each fetched the other's bundle simultaneously), the tie-break rule is:

The party whose device_id is lexicographically greater wins the INITIATOR role and proceeds; the other party MUST discard its half-built state and accept the winner's first message as RESPONDER.

The reference implements this in orchestration/session_lifecycle.rs.

4.5 PQXDH (Suite 2) — post-quantum extension

Suite 2 augments Suite 1 with an ML-KEM-768 shared secret. The addition is deferred: the ML-KEM shared secret is mixed in after the first DH ratchet step, not into the initial root-key derivation. This design lets the same KEM_priv be safely paired with multiple incoming sessions and matches the construct-core implementation in src/crypto/pq_x3dh.rs.

Step P1: Initiator KEM encapsulation

After §4.3 Step 1 (bundle validation), Alice additionally selects Bob's Kyber-SPK (or, if available, a Kyber-OPK) and calls:

(KEM_pub_ct, kem_ss) = MlKem768::Encapsulate(KEM_pub_B)

KEM_pub_ct is the 1088-byte ciphertext. kem_ss is the 32-byte post-quantum shared secret. The classical X3DH proceeds in parallel and produces SK_root exactly as in §4.3.

Step P2: First message includes the KEM ciphertext

The Suite 2 envelope additionally carries:

+ kem_ct          : [u8; 1088]    -- ML-KEM-768 ciphertext
+ kyber_opk_id    : Option<u32>   -- which Kyber-OPK was consumed
+ kem_len         : u16 = 1088    -- defensive length tag

The classical part of the envelope is unchanged.

Step P3: Initiator caches kem_ss until the first ratchet completes

Alice MUST persist kem_ss to durable storage before sending the first message. The reference uses RustPQContributions, an in-memory + Keychain-backed store, to survive an app crash between "first message sent" and "PQ contribution applied" (open issue BS-6: the persistence layer is currently in-memory only, which means a crash in this window degrades the session to classical-only silently).

Step P4: Responder KEM decapsulation

Bob, after performing classical X3DH (§4.4) and the first DH ratchet step, calls:

kem_ss = MlKem768::Decapsulate(KEM_priv_B, kem_ct)

He MUST then immediately persist kem_ss (same BS-6 caveat).

Step P5: Apply the PQ contribution at RK₁

After the first Double Ratchet DH step has produced RK₁ (the post- first-ratchet root key), both sides MUST update:

RK₁' = KDF(salt = RK₁, IKM = kem_ss,
           info = b"Construct-X3DH-RootKey-v1", L = 32)

and re-derive any sending chain key that was already computed from RK₁. From this point onward the session is secured under both the classical X25519 contribution and the PQ ML-KEM-768 contribution.

The deferred-mix design ensures the responder applies the PQ strengthening at the same logical state as the initiator (after the first DH step), which is required for the chains to stay in sync.

Step P6: Zeroise kem_ss

Once RK₁' is computed and persisted, kem_ss MUST be zeroised. The PQ contribution store removes the entry from the Keychain at this point.

4.6 Failure modes and recovery

4.7 Reference

• Classical X3DH: construct-core/src/crypto/handshake/x3dh.rs
• PQXDH KEM: construct-core/src/crypto/pq_x3dh.rs
• Session initiation orchestration: construct-core/src/orchestration/session_lifecycle.rs
• PQ contribution store: construct-core/src/orchestration/pq_contribution.rs

The cryptographic test vectors that an interoperable implementation should reproduce are in construct-core/tests/handshake_vectors.rs (to be expanded in v0.2 of this specification with a published vector set).