← PQXDH
Bölüm 3 / 7

3. The PQXDH Protocol

3.1. Overview

PQXDH has three phases:

  1. Bob publishes his elliptic curve identity key, elliptic curve prekeys, and pqkem prekeys to a server.
  2. Alice fetches a "prekey bundle" from the server, and uses it to send an initial message to Bob.
  3. Bob receives and processes Alice's initial message.

The following sections explain these phases.

3.2. Publishing keys

Bob generates a sequence of 64-byte random values Z_SPK, Z_PQSPK, Z1, Z2, ... and publishes a set of keys to the server containing:

  • Bob's curve identity key IK_B
  • Bob's signed curve prekey and its identifier (SPK_B, IdEC(SPK_B))
  • Bob's signature on the curve prekey Sig(IK_B, EncodeEC(SPK_B), Z_SPK)
  • Bob's signed last-resort pqkem prekey and its identifier (PQSPK_B, IdKEM(PQSPK_B))
  • Bob's signature on the pqkem prekey Sig(IK_B, EncodeKEM(PQSPK_B), Z_PQSPK)
  • A set of Bob's one-time curve prekeys (OPK_B1, OPK_B2, OPK_B3, ...) along with their identifiers (IdEC(OPK_B1), IdEC(OPK_B2), IdEC(OPK_B3), ...)
  • A set of Bob's signed one-time pqkem prekeys (PQOPK_B1, PQOPK_B2, PQOPK_B3, ...) along with their identifiers (IdKEM(PQOPK_B1), IdKEM(PQOPK_B2), IdKEM(PQOPK_B3), ...)
  • The set of Bob's signatures on the signed one-time pqkem prekeys (Sig(IK_B, EncodeKEM(PQOPK_B1), Z1), Sig(IK_B, EncodeKEM(PQOPK_B2), Z2), Sig(IK_B, EncodeKEM(PQOPK_B3), Z3), ...)

Bob only needs to upload his identity key to the server once. However, Bob may upload new one-time prekeys at other times (e.g. when the server informs Bob that the server's store of one-time prekeys is getting low).

For both the signed curve prekey and the signed last-resort pqkem prekey, Bob will upload a new prekey along with its signature using IK_B at some interval (e.g. once a week or once a month). The new signed prekey and its signatures will replace the previous values.

After uploading a new pair of signed curve and signed last-resort pqkem prekeys, Bob may keep the private key corresponding to the previous pair around for some period of time to handle messages using it that may have been delayed in transit. Eventually, Bob should delete this private key for forward secrecy (one-time prekey private keys will be deleted as Bob receives messages using them; see Section 3.4).

3.3. Sending the initial message

To perform a PQXDH key agreement with Bob, Alice contacts the server and fetches a "prekey bundle" containing the following values:

  • Bob's curve identity key IK_B
  • Bob's signed curve prekey with its identifier (SPK_B, IdEC(SPK_B))
  • Bob's signature on the curve prekey Sig(IK_B, EncodeEC(SPK_B), Z_SPK)
  • One of either Bob's signed one-time pqkem prekey PQOPK_Bn or Bob's last-resort signed pqkem prekey PQSPK_B if no signed one-time pqkem prekey remains. Call this key PQPK_B. The bundle also contains IdKEM(PQPK_B)
  • Bob's signature on the pqkem prekey Sig(IK_B, EncodeKEM(PQPK_B), Z_PQPK)
  • (Optionally) Bob's one-time curve prekey OPK_Bn and its identifier IdEC(OPK_Bn)

The server should provide one of Bob's curve one-time prekeys if one exists and then delete it. If all of Bob's curve one-time prekeys on the server have been deleted, the bundle will not contain a one-time curve prekey element.

The server should prefer to provide one of Bob's pqkem one-time signed prekeys PQOPK_Bn if one exists and then delete it. If all of Bob's pqkem one-time signed prekeys on the server have been deleted, the bundle will instead contain Bob's pqkem last-resort signed prekey PQSPK_B.

Alice verifies the signatures on the prekeys. If any signature check fails, Alice aborts the protocol. Otherwise, if all signature checks pass, Alice then generates an ephemeral curve key pair with public key EK_A. Alice additionally generates a pqkem encapsulated shared secret:

(CT, SS) = PQKEM-ENC(PQPK_B)
    shared secret SS
    ciphertext CT

If the bundle does not contain a curve one-time prekey, she calculates:

DH1 = DH(IK_A, SPK_B)
DH2 = DH(EK_A, IK_B)
DH3 = DH(EK_A, SPK_B)
SK  = KDF(DH1 || DH2 || DH3 || SS)

If the bundle does contain a curve one-time prekey, the calculation is modified to include an additional DH:

DH4 = DH(EK_A, OPK_B)
SK  = KDF(DH1 || DH2 || DH3 || DH4 || SS)

After calculating SK, Alice deletes her ephemeral private key, the DH outputs and the shared secret SS.

Alice then calculates an "associated data" byte sequence AD that contains identity information for both parties:

AD = EncodeEC(IK_A) || EncodeEC(IK_B)

If pqkem does not incorporate PQPK_B into the ciphertext, Alice must also append EncodeKEM(PQPK_B) to AD (see the discussion in Section 4.12). Alice may optionally append additional information to AD, such as Alice and Bob's usernames, certificates, or other identifying information.

Alice then sends Bob an initial message containing:

  • Alice's identity key IK_A
  • Alice's ephemeral key EK_A
  • The pqkem ciphertext CT encapsulating SS for PQPK_B
  • Identifiers stating which of Bob's prekeys Alice used
  • An initial ciphertext encrypted with some AEAD encryption scheme [5] using AD as associated data and using an encryption key which is either SK or the output from some cryptographic PRF keyed by SK.

The initial ciphertext is typically the first message in some post-PQXDH communication protocol. In other words, this ciphertext typically has two roles, serving as the first message within some post-PQXDH protocol, and as part of Alice's PQXDH initial message.

The initial message must be encoded in an unambiguous format to avoid confusion of the message items by the recipient.

After sending this, Alice deletes the ciphertext CT and may continue using SK or keys derived from SK within the post-PQXDH protocol for communication with Bob, subject to the security considerations discussed in Section 4.

3.4. Receiving the initial message

Upon receiving Alice's initial message, Bob retrieves Alice's identity key and ephemeral key from the message. Bob also loads his identity private key and uses the key identifiers to load the private key(s) corresponding to the signed prekeys, one-time prekeys, and KEM key Alice used.

Using these keys, Bob calculates PQKEM-DEC(PQPK_B, CT) as the shared secret SS and repeats the DH and KDF calculations from the previous section to derive SK, and then deletes the DH values and SS values.

Bob then constructs the AD byte sequence using IK_A and IK_B as described in the previous section. Finally, Bob attempts to decrypt the initial ciphertext using SK and AD. If the initial ciphertext fails to decrypt, then Bob aborts the protocol and deletes SK.

If the initial ciphertext decrypts successfully, the protocol is complete for Bob. For forward secrecy, Bob deletes the ciphertext and any one-time prekey private key that was used. Bob may then continue using SK or keys derived from SK within the post-PQXDH protocol for communication with Alice subject to the security considerations discussed in Section 4.