Beyond the ratchet: practical challenges in secure messaging
Simone Maria Stefano Colombo
Ph.D. thesis advised by Bryan Ford
January 10, 2025
Abstract:
Secure messaging systems are essential for ensuring privacy and confidentiality
in today’s digital communication. Thanks to the widespread adoption of
end-to-end encryption, messages are accessible only to
intended users, and advancements in protocol resilience against secret
compromise have enhanced messaging systems’ protection guarantees. However,
several open challenges remain. This thesis investigates three of these
challenges—active attack detection, metadata protection during key retrieval,
and real-world deniability—and presents cryptographic and system-level
solutions to strengthen the security and privacy of modern secure messaging
systems.
The first contribution of this thesis addresses active attack detection in
messaging. We address scenarios where the network can delay and drop messages,
and where adversaries can impersonate parties and inject forged messages. We
propose out-of-band detection mechanisms that always detect active attacks, and
in-band mechanisms that detect attacks as soon as an honest message goes
through. Optimizing these schemes, we also explore how active attack detection
can be practically achieved.
The second contribution addresses challenges in distributing cryptographic keys
that enable parties to establish secure messaging channels. Metadata protection
is crucial to safeguard users’ social graphs, and security issues arise from
potentially malicious service providers distributing adversarially-controlled
keys. To address these challenges, we introduce authenticated private
information retrieval, a cryptographic primitive that ensures clients 1)
do not reveal their social graph to the messaging service and 2) either
retrieve the correct key or abort. We implement and evaluate all our schemes,
assessing the practicality of multi-server authenticated private information
retrieval with Keyd, a PGP key-directory server we develop.
Finally, we analyze cryptographic deniability in secure messaging systems and
its practical relevance from technical and legal perspectives. Although often
presented as a key feature in protocols like Signal, our technical modeling,
which incorporates real-world factors, along with legal analysis of 140 court
cases in Switzerland, reveals that deniability typically fails in practice.
Based on these findings, we discuss whether deniability is desirable and
explore the challenges of designing systems that offer practical deniability.
Together, these contributions advance the resilience, privacy and practical
applicability of secure messaging systems in the face of real-world
adversaries.