Breaking RHQC’s Post-Compromise Security
摘要
Instant messaging applications, such as Signal or iMessage, are highly-popular, enabling users to communicate asynchronously in a secure manner. Asynchronous messaging protocols are particularly interesting since they allow the evolution of session keys through ratcheting. This evolution guarantees both Forward Secrecy ( \(\textsf{FS}\) ) —past session keys are protected even upon leakage— and Post-Compromise Secrecy ( \(\textsf{PCS}\) ) —following the compromise of a party’s state, future session keys eventually become secure again. Classical ratcheting algorithms, such as the Double Ratchet (proposed by Marlinspike and Perrin) rely on successive Diffie-Hellman key-exchange steps run asynchronously, which essentially amount to Non-Interactive Key-Exchange (NIKE). Yet, such algorithms are not quantum-secure. A recent proposal details RHQC: a double ratchet relying on the HQC Key-Encapsulation Mechanism —KEM— (with modified parameters). The RHQC scheme is optimized compared to a naïve quantum-secure ratchet, such as the one recently proposed in the context of Signal, and uses only two polynomials instead of three. This is possible since the first part of an HQC ciphertext is a syndrome and the public key is also a syndrome, with the same morphology. Unfortunately, we prove in this paper that RHQC is not \(\textsf{PCS}\) -secure, contradicting the claims made by the proposing work. Our attack exploits the fact that compromising one of the two endpoints essentially allows the attacker to extract the private ratchet keys of following ratchets, which ensures that healing is never achieved. As, essentially, the ratchet public key is an Ouroboros-like ciphertext, we propose an extraction algorithm called \(\texttt{noisyBFmax}\) based on \(\texttt{BFmax}\) , as introduced by Baldelli et al.. This decoder allows us to break the \(\textsf{PCS}\) -security of RHQC with overwhelming probability. Additionally, we prove that it is impossible to fix RHQC with a lower complexity than the naïve approach.