and metadata privacy. DenIM distinguishes two kinds of
messages: (i) regular messages that do not require metadata
privacy, and (ii) deniable messages that do require it.
Regular and deniable communication is combined in one
system, and users decide which messages to send privately.
To withstand traffic analysis, deniable messages are not
communicated immediately, instead they are piggybacked
on top of the regular messages, which in turn requires
that all messages are extended by a small known amount
of bytes. The store-and-forward server breaks the link
between the sender and receiver of a private message
by buffering the message until there is an opportunity to
piggyback it on some other regular message to the receiver.
It is vital that the messages are extended even if the
communicating parties have nothing to say, in which case
a dummy payload is sent instead. To minimize overhead,
the size of the payload must be small in proportion to the
overall communication.
The importance of incorporating metadata privacy into an
existing IM protocol aligns with earlier observations in
the literature. As EFF put it, “An app with great security
features is worthless if none of your friends and contacts
use it” [
31
]. In their paper “Practical Traffic Analysis
Attacks on Secure Messaging Applications’’, Bahramali et
al. [
32
] recommend that metadata privacy for IM should
be adopted by IM services to be effective. An encouraging
development in this direction already is WhatsApp’s use
of the Noise Protocol Framework (NPF) [
33
] to protect
certain metadata [
1
]. Finally, Zuckerman’s [
34
]cute cat
theory of censorship posits that platforms that combine
entertainment with political activism are more resilient to
censorship than dedicated political platforms.
In our case, we pair DenIM with the (unmodified) Signal
protocol. We call the resulting system DenIM on Signal.
We chose Signal because it provides the state-of-the art se-
curity guarantees in instant messaging, including: forward
secrecy, backward secrecy (post-compromise security), data
confidentiality and integrity (see [4] for detail).
DenIM’s piggybacking of deniable messages is a form of
tunneling (e.g., [
35
], [
36
], [
37
]). Yet tunneling alone is
insufficient. The reason is that in settings where adversaries
are legitimate users in the system, information may be
leaked inadvertently through parts of the protocol state
that are shared between all users. For example, in Signal,
adversaries can gain information about other users through
the state of the key distribution center because the protocol
allow users to run out of keys – this allows adversaries
to count the number of keys a user has and in extension
allows the adversary to deduce how many conversations a
user is part of.
To ensure that DenIM guarantees metadata privacy for
deniable messages, including unknown attacks, we use
techniques from secure information flow. Our insight is to
model user deniable behavior as user strategies [
38
] – a
technical device that is traditionally used for specifying
semantic security of interactive and nondeterministic pro-
grams. In DenIM, a user strategy is a function that given a
history of the user’s communication determines their next
deniable action, e.g., send a deniable message, request key
material from the server to initiate new deniable communi-
cation, or block a user from receiving deniable messages.
We recast the notion of metadata privacy as strategy-based
noninterference: user strategies must not leak through the
protocol. The significance of this insight is that because
noninterference is an end-to-end characterization, proving
noninterference requires that there is no way in which the
sensitive information may leak anywhere in the protocol,
not just on the transport layer. In essence, this guides the
features and non-features of DenIM. For example, DenIM
restricts the notification of user blocking, because notifying
a user that they have been blocked leaks information about
the blocking user’s deniable behavior.
The contributions of this paper are as follows:
•
It presents a deniable variant of the Signal protocol
(Section 2.2) called DenIM (Section 4.1), that supports
both the original strong cryptographic guarantees of
Signal, and metadata privacy.
•
It presents a system design that layers deniable Signal
messages on top of the unmodified Signal protocol,
which we call DenIM on Signal (Section 4).
•
It presents a formal privacy analysis (Section 5) that
constitutes a principled approach of using information
flow techniques to guarantee privacy by proving
noninterference.
•
It presents a proof-of-concept implementation (Sec-
tion 6.1) of an instant messaging system with DenIM.
•
It presents an empirical evaluation (Sections 6.2
and 6.3) of the performance of DenIM.
2. Background
This section provides an overview of instant messaging
(IM), and the main machinery in the Signal protocol which
we design a deniable version of in Section 4.1.
2.1. Instant messaging
In 2019, instant messaging (IM) services had seven billion
registered accounts worldwide [
39
]. The most popular IM
services include WhatsApp (2B users), Facebook messen-
ger (1.3B users), iMessage (estimated to 1B users), Tele-
gram (550M users), and Snapchat (538M users) [
40
], [
41
].
While IM appears deceptively simple, the sheer amount
of users and traffic (69M messages/min in 2021 [
42
])
present several engineering challenges. Keeping up with
the demands, requires deploying and maintaining robust
systems. As an example, WhatsApp’s architecture handles
over one million connections per server [43].
All major IM services, including WhatsApp, Facebook
messenger, Telegram and Snapchat, use centralized servers
to forward messages [
32
]. Many IM apps also come
with end-to-end encryption, in addition to server-client
encryption (through TLS). Telegram uses their own pro-
tocol, MTProto [
44
], iMessage uses RSAES-OAEP [
45
],
and Snapchat uses an unnamed encryption scheme for
some of its content [
46
]. The most popular protocol is
Signal [
47
], [
48
], which also has the strongest security
guarantees of the mentioned protocols, and is used by
WhatsApp [
1
], Facebook Messenger [
3
], Wire [
2
], Chat-
Secure, Conversations, Pond, the Signal app, and Silent
Circle [
4
]. The Signal protocol is formally secure [
4
], and is
based on Off-the-Record Messaging (OTR) [
49
] and Silent
2