19 KiB
Version 1, 2024-06-22
Post-quantum resistant augmented double ratchet algorithm (PQDR)
Table of contents
- Overview
- Comparison with the other approaches
- Augmented double ratchet algorithm
- Double ratchet with encrypted headers augmented with double PQ KEM
- Ratchet message wire format
- Implementation considerations
- Chosen KEM algorithm
- Summary
Overview
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.
Comparison with the other approaches
PQXDH for post-quantum key agreement
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.
Hybrid Signal protocol for post-quantum encryption
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.
Augmented double ratchet algorithm
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.
Double ratchet with encrypted headers augmented with double PQ KEM
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).
Initialization
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.PQRct, state.PQRss = PQKEM-ENC(state.PQRr) // encapsulate: generates shared secret and ciphertext
// 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.
Encrypting messages
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.
Decrypting messages
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.PQRct, state.PQRss = PQKEM-ENC(state.PQRr) // encapsulate: generates shared secret and ciphertext 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).
Ratchet message wire format
The pseudocode above describes the algorithm. This section specifies the actual binary encoding used in SimpleX implementation with Curve448 DH keys, sntrup761 KEM and AES-256-GCM AEAD.
The ratchet-encrypted message has three encoding layers, from outermost to innermost:
- Encrypted ratchet message — the complete ratchet message envelope, referenced as an opaque encrypted body in agent protocol.
- Encrypted message header — the encrypted header within the ratchet message, used as associated data for message body encryption.
- Plaintext message header — the DH and KEM ratchet keys and counters.
Encrypted ratchet message
The outer envelope contains the encrypted header (used as associated data for body authentication), the body authentication tag, and the encrypted message body.
The message body is encrypted with AES-256-GCM using the message key derived from the sending chain key (KDF_CK). The associated data for body encryption is the concatenation of the ratchet associated data and the encoded encrypted header.
encRatchetMessage = versionedLength encMessageHeader msgAuthTag encMsgBody
; encMessageHeader is used as associated data for body decryption: AD = rcAD || encMessageHeader
msgAuthTag = 16*16 OCTET ; AES-256-GCM authentication tag for the message body
encMsgBody = *OCTET ; AES-256-GCM encrypted padded message body (remaining bytes)
Encrypted message header
The encrypted header wraps the current ratchet e2e encryption version, an initialization vector, an authentication tag, and the encrypted padded header body.
The header body is encrypted with AES-256-GCM using the header key (HKs). The associated data for header encryption is the ratchet associated data. The header is padded before encryption to a fixed size to prevent leaking information about the KEM state.
encMessageHeader = currentVersion headerIV headerAuthTag versionedLength encHeaderBody
currentVersion = 2*2 OCTET ; Word16, current ratchet e2e encryption version
headerIV = 16*16 OCTET ; AES-256 initialization vector for header encryption
headerAuthTag = 16*16 OCTET ; AES-256-GCM authentication tag for the header
encHeaderBody = *OCTET ; AES-256-GCM encrypted padded header (see plaintext format below)
versionedLength uses a 2-byte length prefix (Word16) when the current e2e version supports PQ encryption, or a 1-byte length prefix otherwise. The parser distinguishes the two encodings by peeking at the first byte: values below 32 indicate a 2-byte prefix (as the header is always at least 69 bytes).
versionedLength = largeLength / length ; 2-byte for PQ versions, 1-byte for pre-PQ versions
The padded header sizes before encryption are: 2310 bytes when PQ is supported, 88 bytes when PQ is not supported. Padding uses a 2-byte big-endian length prefix followed by the plaintext header and # fill bytes.
Plaintext message header
msgHeader = maxVersion dhPublicKey [kemParams] prevMsgCount msgCount
maxVersion = 2*2 OCTET ; Word16, max supported e2e encryption version
dhPublicKey = length x509encoded ; Curve448 public DH ratchet key
kemParams = noKEM / proposedKEM / acceptedKEM
; present only when current ratchet version >= pqRatchetE2EEncryptVersion
noKEM = %x30 ; "0" - no KEM parameters
proposedKEM = %x31 %s"P" kemEncapsulationKey ; KEM proposed, not yet accepted
acceptedKEM = %x31 %s"A" kemCiphertext kemEncapsulationKey ; KEM accepted
kemEncapsulationKey = largeLength 1158*1158 OCTET ; sntrup761 encapsulation key
kemCiphertext = largeLength 1039*1039 OCTET ; sntrup761 ciphertext
prevMsgCount = 4*4 OCTET ; Word32, number of messages in previous sending chain
msgCount = 4*4 OCTET ; Word32, message number in current sending chain
length = 1*1 OCTET
largeLength = 2*2 OCTET ; Word16
KEM state machine
PQ encryption can be enabled or disabled during a connection's lifetime. The KEM parameters in the header reflect three states:
- No KEM (
noKEM): PQ encryption is not active. The header contains only the DH key, as in the original double ratchet. - Proposed (
proposedKEM): One party generated a KEM key pair and includes the encapsulation key in the header, proposing PQ encryption. No ciphertext is included because the other party has not yet sent its encapsulation key. - Accepted (
acceptedKEM): The party received the other's encapsulation key, performed encapsulation (KEM #1), and includes both the ciphertext and its own new encapsulation key (for KEM #2). This is the steady state for active PQ encryption.
The transition from Proposed to Accepted happens when a party receives a message containing KEM parameters (either Proposed or Accepted) and responds with its own Accepted parameters. Once both parties are in Accepted state, the double PQ KEM augmentation described in the algorithm above operates in each DH ratchet step.
Implementation considerations for SimpleX Messaging Protocol
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.
Chosen KEM algorithm
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.
Summary
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.