Bidirectional Asynchronous Ratcheted Key Agreement without Key-Update Primitives.

F. Betül Durak, Serge Vaudenay B

Bertram Poettering, Paul Rösler

Olivier Blazy, Angèle Bossuat, Xavier Bultel +3 more

As messaging applications are becoming increasingly popular, it is of utmost importance to analyze their security and mitigate existing weaknesses. This paper focuses on one of the most acclaimed messaging applications: Signal. Signal is a protocol that provides end-to-end channel security, forward secrecy, and post-compromise security. These features are achieved thanks to a key-ratcheting mechanism that updates the key material at every message. Due to its high security impact, Signal's key-ratcheting has recently been formalized, along with an analysis of its security. In this paper, we revisit Signal, describing some attacks against the original design and proposing SAID: Signal Authenticated and IDentity-based. As the name indicates, our protocol relies on an identity-based setup, which allows us to dispense with Signal's centralized server. We use the identity-based long-term secrets to obtain persistent and explicit authentication, such that SAID achieves higher security guarantees than Signal. We prove the security of SAID not only in the Authenticated Key Exchange (AKE) model (as done by previous work), but also in the Authenticated and Confidential Channel Establishment (ACCE) model, which we adapted and redefined for SAID and asynchronous messaging protocols in general into a model we call identity-based Multistage Asynchronous Messaging (iMAM). We believe our model to be more faithful in particular to the true security of Signal, whose use of the message keys prevents them from achieving the composable guarantee claimed by previous analysis.

Hyoung-Mok Lee, Eun‐Kyung Ryu, Kee-Won Kim +2 more

Katriel Cohn-Gordon, Cas J. F. Cremers, Benjamin Dowling +2 more

Signal is a new security protocol and accompanying app that provides end-to-end encryption for instant messaging. The core protocol has recently been adopted by WhatsApp, Facebook Messenger, and Google Allo among many others, the first two of these have at least 1 billion active users. Signal includes several uncommon security properties (such as "future secrecy" or "post-compromise security"), enabled by a novel technique called ratcheting in which session keys are updated with every message sent. Despite its importance and novelty, there has been little to no academic analysis of the Signal protocol. We conduct the first security analysis of Signal's key agreement and double ratchet as a multi-stage key exchange protocol. We extract from the implementation a formal description of the abstract protocol, and define a security model which can capture the "ratcheting" key update structure. We then prove the security of Signal's core in our model, demonstrating several standard security properties. We have found no major flaws in the design, and hope that our presentation and results can serve as a starting point for other analyses of this widely adopted protocol.

Joohee Lee, Jihoon Kwon, Ji Sun Shin

Continuous Key Agreement (CKA) is a two-party protocol used in double-ratchet protocols such as signal. It enables continuous and synchronous key distribution that generates a fresh key to encrypt each transaction in messenger apps. It guarantees forward secrecy and post-compromise security. In recent years, the post-quantum versions of the double-ratchet protocol and CKA have been intensively studied. In Eurocrypt 2019, Alwenet al. suggest a generic construction of CKA based on the Key Encapsulation Mechanism (KEM), achieving the post-quantum CKA from post-quantum KEMs. They also mention that the bandwidth can be reduced by half using ElGamal KEM. In this paper, we generalize this idea by defining a new primitive called Decomposable Key Encapsulation Mechanism (DKEM) and instantiate it with the promising lattice-based schemes such as CRYSTALS-KYBER and SABER. Using DKEM instantiated with CRYSTALS-KYBER (resp. SABER) and security category 1 parameters, our CKA achieves 51% (resp. 48%) reduced bandwidths compared to the generic construction from KEM. We also implement our CKA on both Intel Xeon E5-1650 v3 and ARMv8 Cortex-A72 processors, respectively, and show that the performance of sender algorithm is improved from 79.29 to 96.94% (resp. from 74.64 to 91.04%) when instantiated with CRYSTALS-KYBER (resp. SABER).