Paper 2022/355

A More Complete Analysis of the Signal Double Ratchet Algorithm

Alexander Bienstock, New York University
Jaiden Fairoze, University of California, Berkeley
Sanjam Garg, University of California, Berkeley, NTT Research
Pratyay Mukherjee, Swirlds Labs
Srinivasan Raghuraman, Visa Research
Abstract

Seminal works by Cohn-Gordon, Cremers, Dowling, Garratt, and Stebila [EuroS&P 2017] and Alwen, Coretti and Dodis [EUROCRYPT 2019] provided the first formal frameworks for studying the widely-used Signal Double Ratchet (DR for short) algorithm. In this work, we develop a new Universally Composable (UC) definition F_DR that we show is provably achieved by the DR protocol. Our definition captures not only the security and correctness guarantees of the DR already identified in the prior state-of-the-art analyses of Cohn-Gordon et al. and Alwen et al., but also more guarantees that are absent from one or both of these works. In particular, we construct six different modified versions of the DR protocol, all of which are insecure according to our definition F_DR, but remain secure according to one (or both) of their definitions. For example, our definition is the first to capture CCA-style attacks possible immediately after a compromise — attacks that, as we show, the DR protocol provably resists, but were not captured by prior definitions. We additionally show that multiple compromises of a party in a short time interval, which the DR should be able to withstand, as we understand from its whitepaper, nonetheless introduce a new non-trivial (albeit minor) weakness of the DR. Since the definitions in the literature (including our F_DR above) do not capture security against this more nuanced scenario, we define a new stronger definition F_TR that does. Finally, we provide a minimalistic modification to the DR (that we call the Triple Ratchet, or TR for short) and show that the resulting protocol securely realizes the stronger functionality F_TR. Remarkably, the modification incurs no additional communication cost and virtually no additional computational cost. We also show that these techniques can be used to improve communication costs in other scenarios, e.g. practical Updatable Public Key Encryption schemes and the re-randomized TreeKEM protocol of Alwen et al. [CRYPTO 2020] for Secure Group Messaging.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2022
Keywords
Secure Messaging Continuous Key Agreement Ratcheting Applied Cryptography Real-world systems
Contact author(s)
abienstock @ cs nyu edu
fairoze @ berkeley edu
sanjamg @ berkeley edu
pratyay85 @ gmail com
srini131293 @ gmail com
History
2022-06-24: last of 4 revisions
2022-03-18: received
See all versions
Short URL
https://ia.cr/2022/355
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2022/355,
      author = {Alexander Bienstock and Jaiden Fairoze and Sanjam Garg and Pratyay Mukherjee and Srinivasan Raghuraman},
      title = {A More Complete Analysis of the Signal Double Ratchet Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2022/355},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/355}},
      url = {https://eprint.iacr.org/2022/355}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.