Dissertations, Theses, and Capstone Projects

Date of Degree

9-2022

Document Type

Dissertation

Degree Name

Ph.D.

Program

Computer Science

Advisor

Rosario Gennaro

Committee Members

Nelly Fazio

William E. Skeith

Hugo Krawczyk

Subject Categories

Information Security | Theory and Algorithms

Keywords

Cryptography, Privacy, Key Exchange Protocols, Deniability, Authenticated Key Exchange, Secure Messaging Protocols

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 work, we present 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 our research by presenting additional results. First, we prove 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.

We show how our Knowledge of Diffie-Hellman Assumptions (KDH) knowledge assumption family can be used to establish a deniability proof for other implicitly authenticated Diffie-Hellman protocols, specifically the OAKE family \cite{Yao13}.

By examining the deniability of the implicitly authenticated AKE protocols augmented with a confirmation step, we also demonstrate a counterintuitive result. Although such a modification requires protocol users to exchange additional information during the session, deniability may be established for these protocols under weaker assumptions (compared to the implicitly authenticated version).

Lastly, we discussed our observations on various attack scenarios that undermine offline deniability with the assistance of third-party services and why these attacks should be put in a different category than offline deniability.

Download

Share

COinS