To Sign, or Not to Sign

[PranayAnchuri]

Let's first look at the message structure in V2

Message structure in V2 conversations

payload = encoded content,
header = {topic, timestamp}
digest = Hash(header || payload)
packet = {payload, sender address, sender's signature using prekey (digest)}
encrypted = encrypt(packet, shared_key, header)
packet = {encrypted, header}

Question

The primary question we want to address in this issue is Does the message sender need to sign the digest of the header and payload?

By including a signature on header+payload, the sender is attesting to the message contents and context (because it's used as AAD in the encryption). In addition, the attestation is verifiable by both the intended recipients and parties external to the communication.

Properties

Each function in the message structure defined above results in different properties

1. Encryption gets confidentiality that only intended recipients can read the plaintext message
2. MAC gets the integrity of the message
3. Signature with the private key enables public verifiability

We focus on the last property here

Definitions

Deniable authentication

Say Alice and Bob are communicating via a secure pairwise channel

The shared key they establish for communication is called a DAKE (Deniable Authenticated Key Exchange) iff

1. Alice and Bob are each convinced that they established this secret with the counterparty
2. Alice (resp Bob) can convince Judge Judy that Bob(resp Alice) participated in a key exchange session with them.

There are two types of deniability depending on the role of the Judge in 2 above

Offline deniability

In this version, Judy is not observing actively observing the key establishment session.

Online deniability

In this version, Alice colludes with Judy to frame Bob. This is similar to Alice wearing a wire.

Establishing deniability

A protocol is said to have deniability properties if a simulator can produce a communication transcript similar to the transcript for true interaction between the parties. The defendant could deny it in this case by arguing that the transcript is fabricated.

Implications of non-deniability

Without deniability every message is on-the-record. This is potentially harmful to the senders as the messages can be used against them (now or in the future). For example, a whistleblower using a non-deniable communication system will have their identity leaked. Deniability is a complex issue requiring legal, social sciences, and cryptography inputs.

• Legal: In a legal setting, a Judge relies on a wide range of evidence. A deniable communication by itself doesn't provide enough evidence. At the same time, there is no precedent where courts admitted cryptographic deniability as the key evidence. However, the non-deniability property makes digital communication less private compared to real-world conversation. Without deniability, the Judge will consider A) Who is making the statements and B) the Digital trace of the communication.
• Social sciences: There is an argument that the deniability property favors the powerful more than it favors the less powerful participant in a conversation.
• Technical: Deniability is easy to achieve in a pairwise setting. But, it's more challenging in a group setting. Although, there is some recent work showing deniability can be achieved without sacrificing scalability.

Deniability in existing secure communication systems

Most of the existing secure message services have deniable communications by default. In Signal protocol, it can be shown that X3DH is an instance of DAKE. It follows that the communications are deniable too. The same holds for OTR and HMQV protocols.

Deniability in pairwise vs group communications

Pairwise communications

As mentioned earlier, deniability is easy and default in most of the pairwise communication protocols including Signal, OTR, etc. Things get more complicated in a group messaging scenario.

Group communications

Most of the existing deployments of group messaging sacrifice scalability to support deniability. Signal App uses pairwise channels that have linear message complexity to achieve authentication+deniability. Multiparty OTR (mpOTR) has similar complexity to achieve deniability. Tree-based methods (ART + TreeKEM) sacrifice the deniability property to achieve sublinear (log n) message complexity. More recently, Epochal Signatures have been proposed that can be integrated with tree-based methods to achieve deniability.

My current thoughts

1. Similar to widely deployed messaging Apps, pairwise communication should be deniable. In this setting, the receiver doesn't need a digital signature from the sender. A secret key is already shared between the sender and receiver. Without deniability, communication is less private compared to physical communication in the real world.
2. Even in a group setting, deniability should be the default behavior with support for adding non-deniability in individual groups. For example, a signature might be required after the fact to prove the authenticity of a message.
3. It's possible to have different deniability properties depending on the size of the group.

References

Epochal signatures: https://eprint.iacr.org/2020/1138 OTR: https://otr.cypherpunks.ca/otr-wpes.pdf Deniability of Signal protocol: https://eprint.iacr.org/2021/642.pdf Deniable Email: https://eprint.iacr.org/2019/390.pdf Time deniable signatures : https://eprint.iacr.org/2022/1018

[mkobetic]

We've had a lot of discussions on this internally earlier this year, I tried to find them, but failed. @jazzz, @neekolas do you remember where we had these discussions?