Four months after encrypted messenger Signal merged some intriguing code, the company has confirmed upgrades to its key exchange protocol specification that are designed to ensure quantum-resistant encryption.
Signal said it has upgraded its Extended Triple Diffie-Hellman "X3DH" key agreement protocol to Post-Quantum Extended Diffie-Hellman "PQXDH".
The approach uses X3DH's elliptic curve key agreement protocol and augments it with a post-quantum key encapsulation mechanism.
The latter, called CRYSTALS-Kyber, was one of four quantum-resistant cryptographic algorithms approved by NIST in 2022 – which at the time said “among its advantages are comparatively small encryption keys that two parties can exchange easily, as well as its speed of operation.”
Harvest Now, Decrypt Later fears
The move by Signal, which boasts over 40 million active users, comes as speculation mounts about when quantum computers will be able to break public-key cryptography – and various organisations look to move pre-emptively to avoid the risk of "harvest now, decrypt later" attacks.
Signal itself noted this week that "the middle ground seems to be around the 5 to 10 year time horizon. We are not in a position to judge which timeline is most likely, but we do see a real and growing risk..."
(It also comes as some organisations look to use the power of quantum mechanics to power secure data transfers; testing quantum key distribution (QKD) networks for example that rely on encoding each bit of a cryptographic key on a single photon. HSBC is running tests on BT and Toshiba’s commercial QKD network in the UK. Other QKD network tests are ongoing globally including across an expansive Chinese network.)
Signal's post-quantum shift uses CRYSTALS-Kyber
Signal said on September 19: “We believe that the key encapsulation mechanism we have selected, CRYSTALS-Kyber, is built on solid foundations, but to be safe we do not want to simply replace our existing elliptic curve cryptography foundations with a post-quantum public key cryptosystem. Instead, we are augmenting our existing cryptosystems such that an attacker must break both systems in order to compute the keys protecting people’s communications.
“The essence of our protocol upgrade from X3DH to PQXDH is to compute a shared secret, data known only to the parties involved in a private communication session, using both the elliptic curve key agreement protocol X25519 and the post-quantum key encapsulation mechanism CRYSTALS-Kyber. We then combine these two shared secrets together so that any attacker must break both X25519 and CRYSTALS-Kyber to compute the same shared secret…”
PQXDH Deniability...
A big part of E2EE messaging is cryptographic deniability. Offline deniability, specifically, is the ability to a posteriori deny having participated in a particular communication session. Deniability proof for a protocol is "non-trivial". Does PQXDH offer it?
In a whitepaper available here, Signal says that "PQXDH, like X3DH, aims to provide both Alice and Bob deniabililty 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 [11].
"PQXDH has some forms of cryptographic deniability. Motivated by the goals of X3DH, Brendel et al. [12] 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. [13] 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 [14] 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 [15] we expect that for future revisions of this protocol (that provide post-quantum mutual authentication) assertions about deniability against semi-honest quantum advsersaries will hold. Deniability in the face of malicious quantum adversaries requires further research.
Signal added: "Our new protocol is already supported in the latest versions of Signal’s client applications and is in use for chats initiated after both sides of the chat are using the latest Signal software. In the coming months (after sufficient time has passed for everyone using Signal to update), we will disable X3DH for new chats and require PQXDH for all new chats. In parallel, we will roll out software updates to upgrade existing chats to this new protocol."
