The security of the composition of X3DH [6] with the Double Ratchet [7] was formally studied in [8] and proven secure under the Gap Diffie-Hellman assumption (GapDH) [9] while making simplifying assumptions that avoid modeling the reuse of IK_B for both key agreement and signing. PQXDH composed with the Double Ratchet retains this security against an adversary without access to a quantum computer, but strengthens the security of the initial handshake to require the solution of both GapDH and Module-LWE [10].
In [11] PQXDH has been formally analyzed in the symbolic model with ProVerif [12] and in the computational model with CryptoVerif [13]. With ProVerif, the authors prove both authentication and secrecy in the symbolic model and enumerate the precise conditions under which the attacker can break these properties. These security properties notably imply forward secrecy, resistance to harvest now decrypt later attacks, resistance to key compromise impersonation, and session independence.
Using the CryptoVerif prover, the authors prove the computational secrecy and authentication of any completed key exchange under the GapDH assumption for the X25519 curve, the UF-CMA assumption on XEdDSA (assuming no key reuse between XEdDSA and X25519), the hash function modeled as a random oracle, and the IND-CPA+INT-CTXT assumptions for the AEAD. Moreover, they also show forward secrecy when the signature was UF-CMA secure at the time the key exchange took place, assuming post-quantum IND-CCA security for the KEM, modelling the hash function as a PRF, and IND-CPA+INT-CTXT security for the AEAD.
For both PQXDH and X3DH, however, a full proof of security under a joint assumption of GapDH and UF-CMA security for X25519 and XEdDSA is still needed.
The remainder of this section discusses an incomplete list of further security considerations.
4.1. Authentication
Before or after a PQXDH key agreement, the parties may compare their identity public keys IK_A and IK_B through some authenticated channel. For example, they may compare public key fingerprints manually, or by scanning a QR code. Methods for doing this are outside the scope of this document.
Authentication in PQXDH is not quantum-secure. In the presence of an active quantum adversary, the parties receive no cryptographic guarantees as to who they are communicating with. Post-quantum secure deniable mutual authentication is an open research problem which we hope to address with a future revision of this protocol.
If authentication is not performed, the parties receive no cryptographic guarantee as to who they are communicating with.
4.2. Protocol replay
If Alice's initial message doesn't use a one-time prekey, it may be replayed to Bob and he will accept it. This could cause Bob to think Alice had sent him the same message (or messages) repeatedly.
To mitigate this, a post-PQXDH protocol may wish to quickly negotiate a new encryption key for Alice based on fresh random input from Bob. This is the typical behavior of Diffie-Hellman-based ratcheting protocols [7].
Bob could attempt other mitigations, such as maintaining a blacklist of observed messages, or replacing old signed prekeys more rapidly. Analyzing these mitigations is beyond the scope of this document.
4.3. Replay and key reuse
Another consequence of the replays discussed in the previous section is that a successfully replayed initial message would cause Bob to derive the same SK in different protocol runs.
For this reason, any post-PQXDH protocol that uses SK to derive encryption keys MUST take measures to prevent catastrophic key reuse. For example, Bob could use a DH-based ratcheting protocol to combine SK with a freshly generated DH output to get a randomized encryption key [7].
4.4. Deniability
Informally, cryptographic deniability means that a protocol neither gives its participants a publishable cryptographic proof of the contents of their communication nor proof of the fact that they communicated. PQXDH, like X3DH, aims to provide both Alice and Bob deniability that they communicated with each other in a context where a "judge" who may have access to one or more party's secret keys is presented with a transcript allegedly created by communication between Alice and Bob.
We focus on offline deniability because if either party is collaborating with a third party during protocol execution, they will be able to provide proof of their communication to such a third party. This limitation on "online" deniability appears to be intrinsic to the asynchronous setting [14].
PQXDH has some forms of cryptographic deniability. Motivated by the goals of X3DH, Brendel et al. [15] introduce a notion of 1-out-of-2 deniability for semi-honest parties and a "big brother" judge with access to all parties' secret keys. Since either Alice or Bob can create a fake transcript using only their own secret keys, PQXDH has this deniability property. Vatandas, et al. [16] prove that X3DH is deniable in a different sense subject to certain "Knowledge of Diffie-Hellman Assumptions". PQXDH is deniable in this sense for Alice, subject to the same assumptions, and we conjecture that it is deniable for Bob subject to an additional Plaintext Awareness (PA) assumption for pqkem. We note that Kyber uses a variant of the Fujisaki-Okamoto transform with implicit rejection [17] and is therefore not PA as is. However, in PQXDH, an AEAD ciphertext encrypted with the session key is always sent along with the Kyber ciphertext. This should offer the same guarantees as PA. We encourage the community to investigate the precise deniability properties of PQXDH.
These assertions all pertain to deniability in the classical setting. As discussed in [18] we expect that for future revisions of this protocol (that provide post-quantum mutual authentication) assertions about deniability against semi-honest quantum adversaries will hold. Deniability in the face of malicious quantum adversaries requires further research.
4.5. Signatures
It might be tempting to omit the prekey signature after observing that mutual authentication and forward secrecy are achieved by the DH calculations. However, this would allow a "weak forward secrecy" attack: A malicious server could provide Alice a prekey bundle with forged prekeys, and later compromise Bob's IK_B to calculate SK.
Alternatively, it might be tempting to replace the DH-based mutual authentication (i.e. DH1 and DH2) with signatures from the identity keys. However, this reduces deniability, increases the size of initial messages, and increases the damage done if ephemeral or prekey private keys are compromised, or if the signature scheme is broken.
4.6. Key compromise
Compromise of a party's private keys has a disastrous effect on security, though the use of ephemeral keys and prekeys provides some mitigation.
Compromise of a party's identity private key allows impersonation of that party to others. Compromise of a party's prekey private keys may affect the security of older or newer SK values, depending on many considerations.
A full analysis of all possible compromise scenarios is outside the scope of this document, however a partial analysis of some plausible scenarios is below:
If either an elliptic curve one-time prekey (OPK_B) or a post-quantum key encapsulation one-time prekey (PQOPK_B) are used for a protocol run and deleted as specified, then a compromise of Bob's identity key and prekey private keys at some future time will not compromise the older SK.
If one-time prekeys were not used for a protocol run, then a compromise of the private keys for IK_B, SPK_B, and PQSPK_B from that protocol run would compromise the SK that was calculated earlier. Frequent replacement of signed prekeys mitigates this, as does using a post-PQXDH ratcheting protocol which rapidly replaces SK with new keys to provide fresh forward secrecy [7].
Compromise of prekey private keys may enable attacks that extend into the future, such as passive calculation of SK values, and impersonation of arbitrary other parties to the compromised party ("key-compromise impersonation"). These attacks are possible until the compromised party replaces his compromised prekeys on the server (in the case of passive attack); or deletes his compromised signed prekey's private key (in the case of key-compromise impersonation).
4.7. Passive quantum adversaries
PQXDH is designed to prevent "harvest now, decrypt later" attacks by adversaries with access to a quantum computer capable of computing discrete logarithms in curve. While this security is primarily derived from pqkem, it also requires that aead provides post-quantum IND-CPA and INT-CTXT security. There is great uncertainty in estimating post-quantum security strength of cryptosystems, making it challenging to define this requirement precisely. Taking the NIST evaluation criteria for post-quantum cryptography submissions [19] as a guide, it places a key-search attack on AES256 at its highest security level. While this does not correspond exactly to our security requirements, it suggests that using an appropriate AEAD mode of AES256 will suffice. We note some particular security properties of PQXDH in this setting.
If an attacker has recorded the public information and the message from Alice to Bob, even access to a quantum computer will not compromise SK.
If a post-quantum key encapsulation one-time prekey (PQOPK_B) is used for a protocol run and deleted as specified then compromise after deletion and access to a quantum computer at some future time will not compromise the older SK.
If post-quantum one-time prekeys were not used for a protocol run, then access to a quantum computer and a compromise of the private key for PQSPK_B from that protocol run would compromise the SK that was calculated earlier. Frequent replacement of signed prekeys mitigates this, as does using a post-PQXDH ratcheting protocol which rapidly replaces SK with new keys to provide fresh forward secrecy [7].
4.8. Active quantum adversaries
PQXDH is not designed to provide protection against active quantum attackers. An active attacker with access to a quantum computer capable of computing discrete logarithms in curve can compute DH(PK1, PK2) and Sig(PK, M, Z) for all elliptic curve keys PK1, PK2, and PK. This allows an attacker to impersonate Alice by using the quantum computer to compute the secret key corresponding to PK_A then continuing with the protocol. A malicious server with access to such a quantum computer could impersonate Bob by generating new key pairs PQSPK'_B and PQOPK'_B, computing the secret key corresponding to PK_B, then using PK_B to sign the newly generated post-quantum KEM keys and delivering these attacker-generated keys in place of Bob's post-quantum KEM key when Alice requests a prekey bundle.
It is tempting to consider adding a post-quantum identity key that Bob could use to sign the post-quantum prekeys. This would prevent the malicious server attack described above and provide Alice a cryptographic guarantee that she is communicating with Bob, but it does not provide mutual authentication. Bob does not have any cryptographic guarantee about who he is communicating with. The post-quantum KEM and signature schemes being standardized by NIST [20] do not provide a mechanism for post-quantum deniable mutual authentication, although this can be achieved through the use of a post-quantum ring signature or designated verifier signature [15], [18]. We urge the community to work toward standardization of these or other mechanisms that will allow deniable mutual authentication.
4.9. Server trust
A malicious server could cause communication between Alice and Bob to fail (e.g. by refusing to deliver messages).
If Alice and Bob authenticate each other as in Section 4.1, then the only additional attack available to the server is to refuse to hand out one-time prekeys, causing forward secrecy for SK to depend on the signed prekey's lifetime (as analyzed in Section 4.6).
This reduction in initial forward secrecy could also happen if one party maliciously drains another party's one-time prekeys, so the server should attempt to prevent this (e.g. with rate limits on fetching prekey bundles).
4.10. Identity binding
Authentication as in Section 4.1 does not necessarily prevent an "identity misbinding" or "unknown key share" attack.
This results when an attacker ("Charlie") falsely presents Bob's identity key fingerprint to Alice as his (Charlie's) own, and then either forwards Alice's initial message to Bob, or falsely presents Bob's contact information as his own. The effect of this is that Alice thinks she is sending an initial message to Charlie when she is actually sending it to Bob.
To make this more difficult the parties can include more identifying information into AD, or hash more identifying information into the fingerprint, such as usernames, phone numbers, real names, or other identifying information. Charlie would be forced to lie about these additional values, which might be difficult.
However, there is no way to reliably prevent Charlie from lying about additional values, and including more identity information into the protocol often brings trade-offs in terms of privacy, flexibility, and user interface. A detailed analysis of these trade-offs is beyond the scope of this document.
4.11. Risks of weak randomness sources
In addition to concerns about the generation of the keys themselves, the security of the PQKEM shared secret relies on the random source available to Alice's machine at the time of running the PQKEM-ENC operation. This leads to a situation similar to what we face with a Diffie-Hellman exchange. For both Diffie-Hellman and Kyber, if Alice has weak entropy then the resulting shared secret will have low entropy when conditioned on Bob's public key. Thus both the classical and post-quantum security of SK depend on the strength of Alice's random source.
Kyber hashes Bob's public key with Alice's random bits to generate the shared secret, making Bob's key contributory, as it is with a Diffie-Hellman key exchange. This does not reduce the dependence on Alice's entropy source, as described above, but it does limit Alice's ability to control the post-quantum shared secret. Not all KEMs make Bob's key contributory and this is a property to consider when selecting pqkem.
4.12. Preventing KEM Re-encapsulation Attacks
Typically, when using a KEM that relies on a public key encryption to encrypt a fresh shared secret, the fresh shared secret is not tied to the public key. A shared secret corresponding to the encapsulation of a given compromised public key can easily be re-encapsulated against another uncompromised public key. IND-CCA security of the KEM does not prevent this behavior.
For a KEM for which this attack is possible, as soon as one PQPK is compromised, an attacker can force all initiators to use this compromised PQPK, and by always reencapsulating the shared secret against another fresh uncompromised PQPK, make the responder believe that nothing is going awry. This notably breaks the usual notion of session independence: compromising one PQPK of a responder can in fact impact the security of other sessions of the responder that should be using distinct and independent PQPKs.
The Kyber KEM incorporates the KEM public key into the generation of the shared secret, preventing this attack. For a generic IND-CCA KEM, this attack can be prevented by adding PQPK_B to AD for the initial message. See [11] for more details about this attack and mitigations.
4.13. Key Identifiers
The public key identifiers are not security critical, notably as the actual values of the keys are signed or used within the AD. Note however that identifiers that would collide too often would cause decryption failures on the responder side, as the responder would try to complete the key exchange with the wrong public key, which would fail.
An application can choose to use public keys as key identifiers, but may choose an identifier with a smaller representation to reduce message sizes, provided that collisions are unlikely. Possible implementations include a hash of the public key, a random value, or sequentially generated values starting from a random offset.