Version 1, 2024-06-22
- Overview
- Comparison with the other approaches
- Augmented double ratchet algorithm
- Double ratchet with encrypted headers augmented with double PQ KEM
- Implementation considerations
- Chosen KEM algorithm
- Summary
It is a reasonable assumption that "record-now-decrypt-later" attacks are ongoing, so the users want to use cryptographic schemes for end-to-end encryption that are augmented with some post-quantum algorithm that is believed to be resistant to quantum computers.
SimpleX Chat uses double-ratchet with header encryption to provide end-to-end encryption to messages and files. This document describes augmented algorithm with post-quantum key encapsulation mechanism (KEM) making it resistant to quantum computers.
Double-ratchet algorithm is a state of the art solution for end to end encryption offering a set of qualities that is not present in any other algorithm:
- perfect forward secrecy, i.e. compromise of session or long term keys does not lead to the ability to decrypt any of the past messages.
- deniability (also known as repudiation), i.e. the fact that the recipient of the message while having the proof of message authenticity, cannot prove to a third party that the sender actually sent this message.
- break-in recovery (also know as post-compromise security or future secrecy), i.e. the ability of the end-to-end encryption security to recover from the compromise of the long term keys. This is achieved by generating a new random key pair whenever a new DH key is received (DH ratchet step).
It is desirable to preserve all these qualities when augmenting the algorithm with a post-quantum algorithm, and having these qualities resistant to both conventional and quantum computers.
The solution recently introduced by Signal augments the initial key agreement (X3DH) that is made prior to double ratchet algorithm. This is believed to provide protection from "record-now-decrypt-later" attack, but if the attacker at any point obtains long term keys from any of the devices, the break-in recovery will not be post-quantum resistant, and the attacker with quantum computer will be able to decrypt all the subsequent messages.
The solution proposed by Tutanota aims to preserve the break-in recovery property of double ratchet, but in doing so it:
- replaces rather than augments DH key agreement with post-quantum KEM mechanism, making it potentially vulnerable to conventional computers.
- adds signature to the DH ratchet step, to compensate for not keeping DH key agreement, but losing the deniability property for some of the messages.
The double ratchet algorithm is augmented with post-quantum KEM mechanism, preserving all properties of the double ratchet algorithm.
It is possible, because although double ratchet uses DH (which is a non-interactive key exchanges), it uses it "interactively", when the new DH keys are generated by both parties in turns. Parties of double-ratchet encrypted communication can run two post-quantum key encapsulation mechanisms in parallel with both DH and KEM key agreements in each DH ratchet step, making break-in recovery of double ratchet algorithm post-quantum resistant, without losing deniability or resistance to conventional computers.
Specifically, double ratchet with encrypted headers is augmented with some post-quantum key encapsulation mechanism (KEM) as described below. A possible algorithm for PQ KEM is NTRU-prime, that is currently adopted in SSH and has available implementations. It is important though that the proposed scheme can be used with any PQ KEM algorithm.
The downside of the scheme is its substantial size overhead, as the encapsulation key and encapsulated shared secret are added to the header of each message. For the algorithm described below NTRU-prime adds ~2-4kb to each message (depending on the key size and the chosen variant). See this table for key and ciphertext sizes and the assessment of the security level for various key sizes.
It is possible to reduce size overhead by using only one KEM agreement and making only one of two ratchet steps providing post-quantum resistant break-in recovery.
Algorithm below assumes that in addition to shared secret from the initial key agreement, there will be an encapsulation key available from the party that published its keys (Bob).
The double ratchet initialization is defined in pseudo-code. This pseudo-code is identical to Signal algorithm specification except for that parts that add post-quantum key agreement.
// Alice obtained Bob's keys and initializes ratchet first
def RatchetInitAlicePQ2HE(state, SK, bob_dh_public_key, shared_hka, shared_nhkb, bob_pq_kem_encapsulation_key):
state.DHRs = GENERATE_DH()
state.DHRr = bob_dh_public_key
// below added for post-quantum KEM
state.PQRs = GENERATE_PQKEM()
state.PQRr = bob_pq_kem_encapsulation_key
state.PQRss = random // shared secret for KEM
state.PQRct = PQKEM-ENC(state.PQRr, state.PQRss) // encapsulated additional shared secret
// above added for KEM
// the next line augments DH key agreement with PQ shared secret
state.RK, state.CKs, state.NHKs = KDF_RK_HE(SK, DH(state.DHRs, state.DHRr) || state.PQRss)
state.CKr = None
state.Ns = 0
state.Nr = 0
state.PN = 0
state.MKSKIPPED = {}
state.HKs = shared_hka
state.HKr = None
state.NHKr = shared_nhkb
// Bob initializes ratchet second, having received Alice's connection request
def RatchetInitBobPQ2HE(state, SK, bob_dh_key_pair, shared_hka, shared_nhkb, bob_pq_kem_key_pair):
state.DHRs = bob_dh_key_pair
state.DHRr = None
// below added for KEM
state.PQRs = bob_pq_kem_key_pair
state.PQRr = None
state.PQRss = None
state.PQRct = None
// above added for KEM
state.RK = SK
state.CKs = None
state.CKr = None
state.Ns = 0
state.Nr = 0
state.PN = 0
state.MKSKIPPED = {}
state.HKs = None
state.NHKs = shared_nhkb
state.HKr = None
state.NHKr = shared_hka
GENERATE_PQKEM generates decapsulation/encapsulation key pair.
PQKEM-ENC is key encapsulation algorithm.
Other than commented lines, the above adds parameters bob_pq_kem_encapsulation_key and bob_pq_kem_key_pair to the ratchet initialization. Otherwise it is identical to the original double ratchet initialization.
def RatchetEncryptPQ2HE(state, plaintext, AD):
state.CKs, mk = KDF_CK(state.CKs)
// encapsulation key from PQRs and encapsulated shared secret is added to header
header = HEADER_PQ2(
dh = state.DHRs.public,
kem = state.PQRs.public, // added for KEM #2
ct = state.PQRct // added for KEM #1
pn = state.PN,
n = state.Ns,
)
enc_header = HENCRYPT(state.HKs, header)
state.Ns += 1
return enc_header, ENCRYPT(mk, plaintext, CONCAT(AD, enc_header))
Other than adding encapsulation key and encapsulated shared secret into the header, the above is identical to the original double ratchet message encryption step.
def RatchetDecryptPQ2HE(state, enc_header, ciphertext, AD):
plaintext = TrySkippedMessageKeysHE(state, enc_header, ciphertext, AD)
if plaintext != None:
return plaintext
header, dh_ratchet = DecryptHeader(state, enc_header) // DecryptHeader is the same as in double ratchet specification
if dh_ratchet:
SkipMessageKeysHE(state, header.pn) // SkipMessageKeysHE is the same as in double ratchet specification
DHRatchetPQ2HE(state, header)
SkipMessageKeysHE(state, header.n)
state.CKr, mk = KDF_CK(state.CKr)
state.Nr += 1
return DECRYPT(mk, ciphertext, CONCAT(AD, enc_header))
// DecryptHeader is the same as in double ratchet specification
def DecryptHeader(state, enc_header):
header = HDECRYPT(state.HKr, enc_header)
if header != None:
return header, False
header = HDECRYPT(state.NHKr, enc_header)
if header != None:
return header, True
raise Error()
def DHRatchetPQ2HE(state, header):
state.PN = state.Ns
state.Ns = 0
state.Nr = 0
state.HKs = state.NHKs
state.HKr = state.NHKr
state.DHRr = header.dh
// save new encapsulation key from header
state.PQRr = header.kem
// decapsulate shared secret from header - KEM #2
ss = PQKEM-DEC(state.PQRs.private, header.ct)
// use decapsulated shared secret with receiving ratchet
state.RK, state.CKr, state.NHKr = KDF_RK_HE(state.RK, DH(state.DHRs, state.DHRr) || ss)
state.DHRs = GENERATE_DH()
// below is added for KEM
state.PQRs = GENERATE_PQKEM() // generate new PQ key pair
state.PQRss = random // shared secret for KEM
state.PQRct = PQKEM-ENC(state.PQRr, state.PQRss) // encapsulated additional shared secret KEM #1
// above is added for KEM
// use new shared secret with sending ratchet
state.RK, state.CKs, state.NHKs = KDF_RK_HE(state.RK, DH(state.DHRs, state.DHRr) || state.PQRss)
PQKEM-DEC is key decapsulation algorithm.
DHRatchetPQ2HE augments both DH agreements with decapsulated shared secret from the received header and with the new shared secret, respectively. The new shared secret together with the new encapsulation key are saved in the state and will be added to the header in the next sent message.
Other than augmenting DH key agreements with the shared secrets from KEM, the above is identical to the original double ratchet DH ratchet step.
It is worth noting that while DH agreements work as ping-pong, when the new received DH key is used for both DH agreements (and only the sent DH key is updated for the second DH key agreement), PQ KEM agreements in the proposed scheme work as a "parallel ping-pong", with two balls in play all the time (two KEM agreements run in parallel).
As SimpleX Messaging Protocol pads messages to a fixed size, using 16kb transport blocks, the size increase introduced by this scheme can be compensated for by using ZSTD encryption of JSON bodies and image previews encoded as base64. While there may be some rare cases of random texts that would fail to compress, in all real scenarios it would not cause the message size reduction.
Sharing the initial keys in case of SimpleX Chat it is equivalent to sharing the invitation link. As encapsulation key is large, it may be inconvenient to share it in the link in some contexts, e.g. when QR codes are used.
It is possible to postpone sharing the encapsulation key until the first message from Alice (confirmation message in SMP protocol), the party sending connection request. The upside here is that the invitation link size would not increase. The downside is that the user profile shared in this confirmation will not be encrypted with PQ-resistant algorithm.
Another consideration is pairwise ratchets in groups. Key generation in sntrup761 is quite slow - on slow devices it can be as slow as 10-20 keys per second, so using this primitive in groups larger than 10-20 members would result in slow performance.
For backward compatibility the implementation must support adding PQ-resistant key agreement to the existing connections.
It is also beneficial to support removing PQ-resistant key agreement from the connections that have them, e.g. as the group size grows.
The implementation uses Streamlined NTRU-Prime 761 (sntrup761) that was also used for OpenSSH for a long time.
It was chosen over ML-KEM (Kyber) standardized by NIST for several reasons:
- sntrup761 was used in OpenSSH for a long period of time.
- ML-KEM standardization process raised concerns amongst the experts.
- ML-KEM (if modified) is likely to have conflicts with the existing patents, unlike sntrup761.
It was chosen over non-interactive CTIDH due to its slower implementation, and lack of optimized code for aarch64 CPUs used in mobile devices.
If chosen PQ KEM proves secure against quantum computer attacks, then the proposed augmented double ratchet will also be secure against quantum computer attack, including break-in recovery property, while keeping deniability and forward secrecy, because the same proof as for double ratchet algorithm would hold here, provided chosen KEM is secure.