Paper 2021/642

On the Cryptographic Deniability of the Signal Protocol

Nihal Vatandas, Rosario Gennaro, Bertrand Ithurburn, and Hugo Krawczyk

Abstract

Offline deniability is the ability to a-posteriori deny having participated in a particular communication session. This property has been widely assumed for the Signal messaging application, yet no formal proof has appeared in the literature. In this paper, we present what we believe is the first formal study of the offline deniability of the Signal protocol. Our analysis shows that building a deniability proof for Signal is non-trivial and requires strong assumptions on the underlying mathematical groups where the protocol is run. To do so, we study various *implicitly authenticated* key exchange protocols including MQV, HMQV and 3DH/X3DH, the latter being the core key agreement protocol in Signal. We first present examples of mathematical groups where running MQV results in a provably non-deniable interaction. While the concrete attack applies only to MQV, it also exemplifies the problems in attempting to prove the deniability of other implicitly authenticated protocols, such as 3DH. In particular, it shows that the intuition that the minimal transcript produced by these protocols suffices for ensuring deniability does not hold. We then provide a characterization of the groups where deniability holds, defined in terms of a knowledge assumption that extends the Knowledge of Exponent Assumption (KEA). We conclude the paper by showing two additional positive results. The first is a general theorem that links the deniability of a communication session to the deniability of the key agreement protocol starting the session. This allows us to extend our results on the deniability of 3DH/X3DH to the entire Signal communication session.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision.ACNS'20
Keywords
signalprivacydeniability
Contact author(s)
nihal vatandas @ gmail com
rosario @ ccny cuny edu
bithurburn @ gmail com
hugokraw @ gmail com
History
2021-05-17: received
Short URL
https://ia.cr/2021/642
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/642,
      author = {Nihal Vatandas and Rosario Gennaro and Bertrand Ithurburn and Hugo Krawczyk},
      title = {On the Cryptographic Deniability of the Signal Protocol},
      howpublished = {Cryptology ePrint Archive, Paper 2021/642},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/642}},
      url = {https://eprint.iacr.org/2021/642}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.