Session Handshake (X3DH + PQXDH v2)

This chapter specifies how a Konstruct session between two devices is established. The classical part (X3DH) follows the Signal Protocol X3DH specification with the parameters in §4.1. The post-quantum part (PQXDH v2) adds an ML-KEM-1024 shared secret to the initial root-key derivation, so the session is secure from its first message if either the classical or the post-quantum component holds.

PQXDH v2 is mandatory: a new session is not created without a validly signed ML-KEM-1024 prekey (§4.5). There is no classical-only fallback.

Changed 2026-09-25 / 2026-09-27. Earlier revisions of this chapter specified PQXDH v1 (ML-KEM-768 mixed in after the first DH ratchet step, so the first chain was classical only), a responder that fetched the initiator's bundle from the server, and a tie-break rule for simultaneous initiation. All three are gone. See the changelog.

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

4.1 Notation and constants

Fixed byte strings:

An interoperable implementation MUST use these exact byte values; any difference produces a different root key and the first message fails its AEAD check.

4.2 Bundle publication (Bob)

Before any handshake, Bob MUST have published a bundle (wire format in §3.9). Bob MUST:

1. Generate an SPK and an ML-KEM-1024 KEM-SPK, and a batch of OPKs and KEM-OPKs.

2. Sign the SPK: sig_SPK = Ed25519_Sign(SK_priv, b"KonstruktX3DH-v1" || [0x00, 0x01] || SPK_pub).

3. Sign every Kyber prekey, signed and one-time alike, over its creation time:

   m        = b"KonstruktX3DH-v1" || [0x00, 0x11] || created_at (u64 BE) || KEM_pub
   sig_K    = Ed25519_Sign(SK_priv, m)
   hsig_K   = Hybrid_Sign(HIK_priv, m)            -- Ed25519 + ML-DSA-65
   

   created_at sits under the signature because the bundle's upload time is the server's own, unsigned claim; without it a server could serve a long-rotated key as current (kyber_prekey_auth.rs:44-:57).

4. Publish the hybrid identity key HIK_pub with its cross-signature (§2.3.3). It is required: PQXDH v2 refuses a bundle without it.

5. Upload the bundle to the directory and rotate SPK and KEM-SPK periodically. Old SPK secrets (classical and Kyber) are kept for 14 days after rotation, so that handshakes already in the relay's 7-day queue still open (SPK_RETENTION_AFTER_ROTATION_SECS, crypto/keys.rs:18).

The Kyber secret keys, the choice of prekey and decapsulation live in the core only; platforms store and publish what the core produces and never handle ML-KEM secrets.

4.3 Initiator path

Alice opens a session with one of Bob's devices when she has a message for it and holds no session with it.

Step 1: Fetch and validate the bundle

Alice fetches the bundle of Bob's device. She MUST:

1. Verify sig_SPK under SK_pub. On failure, abort.

2. Check SPK freshness (SPK_MAX_AGE_SECS, 30 days). Implementations MAY expose an explicit degraded path that skips only this check for the classical SPK; it never applies to Kyber prekeys (step 4).

3. If the bundle offers an OPK, select exactly one.

4. Plan the post-quantum part (construct-core/src/orchestration/pq_prekey_plan.rs:108, plan_pqxdh). Alice MUST refuse the bundle — and create no session — if any of these holds:

   Refusal	Condition
   NoKyberPrekey	no Kyber prekey offered
   KyberPrekeyMalformed	the key is not a 1568-byte ML-KEM-1024 key
   KyberSignatureMissing / KyberSignatureInvalid	sig_K absent or not verifying
   HybridIdentityMissing / HybridIdentityBindingInvalid	no HIK_pub, or its cross-signature fails
   HybridSignatureMissing / HybridSignatureInvalid	hsig_K absent or not verifying
   KyberPrekeyStale	the KEM-SPK's signed created_at is older than 30 days
   HybridIdentityChanged	HIK_pub differs from the one pinned for this device

   A KEM-OPK is preferred; if it fails its checks, the KEM-SPK is used, and the KEM-SPK MUST pass them. The fingerprint of HIK_pub is pinned once X3DH has verified the bundle.

There is no PQ-ratchet downgrade check here: the PQ ratchet (Suite 4, §2.4) is mandatory wherever post-quantum is built, so there is nothing a bundle can withhold to downgrade it.

Removed with PQXDH v2 (2026-09-25, construct-core 0.18). Before then, step 5 of this list refused a bundle (PQ_DOWNGRADE_REFUSED) if this device had previously advertised or used the PQ ratchet and the fetched bundle no longer advertised the unsigned supports_pq_ratchet capability. The same commit that made PQXDH v2 mandatory removed the capability flag and its downgrade ledger together: once every build negotiates the PQ ratchet unconditionally, a capability nobody can withhold cannot be downgraded.

Step 2: Classical DH

Alice generates EK_A and computes, in this order:

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

Without an OPK the handshake is 3-DH, with reduced forward secrecy for the first flight; this is the open issue BS-3.

Step 3: ML-KEM-1024 encapsulation

(kem_ct, kem_ss) = ML-KEM-1024.Encaps(KEM_pub_B)    -- kem_ct: 1568 bytes, kem_ss: 32 bytes

Step 4: Root key

IKM     = DH1 || DH2 || DH3 [|| DH4] || kem_ss
info    = b"Construct-PQXDH-RootKey-v3" || SHA-256(KEM_pub_B) || SHA-256(kem_ct) || SHA-256(KIK_A)
SK_root = KDF(salt = F, IKM, info, L = 32)

(x3dh.rs, derive_root_key.) KIK_A is Alice's ML-KEM-1024 identity key (§4.4.4). The Kyber key, the ciphertext and KIK_A are bound through info; a KIK_A substituted in transit gives Bob a different root key, so the first message fails rather than a foreign key being pinned. v2 of this label had no KIK_A; a v2 first message is refused. ML-KEM already hashes the encapsulation key into its secret; binding both explicitly removes any reliance on a particular KEM's properties. Implementations MUST zeroise IKM and kem_ss after this step.

Because kem_ss enters the initial root key, every message of the session — including the first — is protected by both components.

Step 5: First message and the handshake header

Alice initialises the Double Ratchet from SK_root, taking SPK_B_pub as the initial remote ratchet key, and encrypts. Every message she sends on this state carries the handshake header until Bob's first reply arrives (construct-core/src/crypto/messaging/double_ratchet/mod.rs:306-:317):

• EK_A_pub and opk_id (in the header fields of §5.3);
• kem_ct (1568 bytes) and kyber_otpk_id (0 when the KEM-SPK was used);
• KIK_A, Alice's ML-KEM-1024 identity key (1568 bytes), with bit 0x0200;
• the PQXDH v2 flag, bit 0x0100 of the wire suite_id. The receiver strips it before the suite is used; its purpose is that a core without PQXDH v2 rejects the frame as an unknown suite instead of deriving a classical key and reading the AEAD failure as corruption.

Repeating the header means Bob can build the session from whichever message of the first flight reaches him first. Once Bob replies, Alice stops sending it.

4.4 Responder path

4.4.1 What opens a session

A message opens a new state if and only if it carries a KEM ciphertext (construct-core/src/orchestration/receiving_init_plan.rs:37). Its message number does not matter: a header on message 5 opens exactly as one on message 0. Until 2026-09-27 only message 0 could open, and a lost first message cost the session until a reset.

• If Bob holds no state with Alice's device, the message is queued and opened (§4.4.2).
• If Bob holds a state and the message decrypts on it or on a previous state (§5.9), it is simply delivered.
• If Bob holds a state and nothing held decrypts it but it carries the header, a new state is opened from it. The state it replaces is not dropped: it becomes a previous state (§5.9).

4.4.2 Opening without the server

Bob does not fetch Alice's bundle to open. A sealed message carries a sender certificate (§8), and the certificate names Alice's identity key and device id, signed by the server. Bob's core opens with the key the certificate names once the certificate passes identity_for_opening (construct-core/src/crypto/sealed_sender/mod.rs:299):

1. The certificate signature verifies under a server key the client accepts (check_signature, :323; Chapter 3 §3.11): a delegated hybrid key once a root is pinned, otherwise one of the Ed25519 certificate-signing keys the platform handed to the core. With no such key held yet, nothing is dropped and the open is retried later.
2. The identity key is 32 bytes and derives to the device id the certificate names. A certificate naming someone else's device is refused.
3. The certificate has not been expired for longer than a message may wait at the relay (MAX_DELIVERY_AGE_SECS, 7 days, sealed_sender/mod.rs:213).

The signature is mandatory here and only here. Anyone who knows Bob's public identity key can seal an envelope to him, so an unsigned certificate is a stranger's claim to be any account. Before 2026-09-27 that did not matter because the key came from a bundle the server served; now the key comes from the certificate, and the server's signature is what binds the key to an account. Delivery into an existing session does not consult the certificate: the ratchet authenticates it.

What this removes: the server no longer learns, from a bundle fetch, whom a sealed first message was from, and the receiver no longer guesses which of the sender's devices wrote it.

Every message names its writer. A first message names its device through the certificate; a later sealed message through the session envelope's tag (Chapter 8). A receiver therefore decrypts a message on the one session of the device it names, and never tries it against each of a peer's devices in turn. construct-core 0.34.0 (2026-10-04) removed the export that planned such a walk (plan_receiving_decrypt); it had been used only for unsealed messages from a peer.

4.4.3 Key agreement

Bob computes

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
kem_ss = ML-KEM-1024.Decaps(KEM_priv_B[kyber_otpk_id or SPK], kem_ct)

derives SK_root exactly as in §4.3 Step 4, initialises the receiving ratchet with EK_A_pub, and decrypts. If the AEAD fails, the attempt leaves nothing behind: a state already held with Alice's device is put back unchanged. Only after a successful decrypt does Bob delete the consumed OPK_priv and KEM-OPK secret.

If the named OPK or Kyber prekey is no longer held, Bob cannot reproduce the key. He answers with a DECRYPTION_ERROR carrying the hint PrekeyUnavailable (§5.10), and Alice's next open skips one-time prekeys.

4.4.4 The initiator proves its KEM identity key

Everything above authenticates Alice to Bob classically: DH1 uses her X25519 identity key and the certificate carries the server's Ed25519 signature. A quantum adversary able to break both at the time of the attack could open a state "from Alice", and since any handshake header opens a state (§5.9), at any time. Alice's side does not have this gap — she encapsulates to a Kyber key signed by Bob's pinned hybrid key. The proof below closes Bob's side without a signature, so the first contact stays deniable (decisions/responder-authenticates-initiator-by-kem.md).

1. The key. Every device has an ML-KEM-1024 identity key KIK, whose 64-byte seed is derived from the ML-DSA-65 seed of its hybrid key (§4.1). It is not stored separately and is restored with the private keys. The X25519 identity is not a usable source: its private half follows from the public one for a quantum adversary.

2. The pin. Bob pins SHA-256(KIK_A) for Alice's device on the first open that decrypts. An open naming another KIK for a pinned device is refused (KEM_IDENTITY_CHANGED); one naming none is refused (KEM_IDENTITY_REQUIRED). The first contact is trust-on-first-use, as the initiator's hybrid pin is.

3. The answer. Having opened, Bob computes (kik_ct, kik_ss) = ML-KEM-1024.Encaps(KIK_A) and, before sending anything, replaces the root key and his first sending chain key:

   RK'  = HKDF(salt = kik_ss, IKM = RK,  info = "Construct-KEM-identity-root-v1",  L = 32)
   CKs' = HKDF(salt = kik_ss, IKM = CKs, info = "Construct-KEM-identity-chain-v1", L = 32)
   

   kik_ct (1568 bytes, bit 0x0400) rides on every message Bob sends until Alice has proved herself.

4. Alice decapsulates kik_ct with KIK_A and applies the same two derivations on her first receiving DH ratchet step — to the root and the receiving chain that step produced. Without the answer that step fails (the core reports it); with a wrong key the AEAD fails.

5. The proof. A message from Alice that Bob decrypts on a chain after that step could only be derived by the holder of KIK_A. Bob stops attaching kik_ct and labels the state ReceivedProven; until then it is Received.

What this does not give: messages of Alice's first flight are authenticated classically, and an unproven state is not treated differently from a proven one when it becomes current. Both are open questions in the decision.

4.5 Simultaneous opening

There is no tie-break. If Alice and Bob open at the same time, each holds the state it opened and receives the other's header; each opens the peer's state beside its own. Both states are kept (§5.9) and the first message either side reads settles which one is current. Nothing is announced, confirmed, ranked or waited for.

A device keeps at most one open in flight per peer device: two concurrent opens would spend two of the peer's one-time prekeys for one state that will be used (construct-core/src/orchestration/session_machine.rs, Opening, 30 s time-out).

4.6 Suite 4 is not negotiated

Suite 4 (the sparse continuous ML-KEM-768 ratchet, per-message chains — §2.4, §5) is not negotiated from the bundle's crypto_suite, or from anything else: it is mandatory wherever the core's post-quantum build feature is present, which is every shipping platform build. The handshake itself is the same PQXDH v2 for every suite; Suite 4 is the ratchet layer that continues after it. The split mirrors Signal (PQXDH and SPQR) and Apple PQ3: ML-KEM-1024 for prekeys and the first message, ML-KEM-768 in the ratchet.

Changed with PQXDH v2 (2026-09-25, construct-core 0.18). Before then this suite (numbered 3) was negotiated per session from an unsigned supports_pq_ratchet bundle capability, with a downgrade refused (PQ_DOWNGRADE_REFUSED, §4.3 Step 1) if a device that had used it saw the capability withdrawn. The same commit that made PQXDH v2 mandatory removed the capability and the downgrade check together, heading this section "Suite 3/4 negotiation boundary" until this revision — there has been no negotiation boundary to describe since 2026-09-25.

Suite 3 — the same mandatory ratchet, but an epoch secret mixed once per epoch instead of a chain per message — is retired as of construct-core 0.24.0 without a compatibility path: a suite-3 message is refused at unpack, and a suite-3 stored session is refused at restore, so the next send opens a suite-4 session instead (§2.4).

4.7 Failure modes

4.8 Reference

• Root key and X3DH: construct-core/src/crypto/handshake/x3dh.rs
• ML-KEM: construct-core/src/crypto/pq_x3dh.rs (mlkem1024_*)
• Kyber prekey signatures: construct-core/src/crypto/kyber_prekey_auth.rs
• PQ plan and refusals: construct-core/src/orchestration/pq_prekey_plan.rs
• Receiving open: construct-core/src/orchestration/orchestrator.rs (open_receiving)
• Sender certificate check: construct-core/src/crypto/sealed_sender/mod.rs
• Design record: construct-docs decisions/pqxdh-v2-mandatory-pq-cutover.md, decisions/first-message-opens-without-the-server.md