In my previous blog post covering WhatsApp end-to-end encryption, I spoke about Signal Protocol and how certain design decisions allowed Signal Protocol to be efficient on mobile devices. For this blog post, I’ll cover deniable authentication, how it has worked in the Off-The-Record (OTR) Messaging protocol, and how Signal Protocol has approached this problem.

What is deniable authentication?

Deniable authentication tries to digitally recreate “off-the-record” conversations in the physical realm. If you tell Bob an embarrassing story in-person and Bob proceeds to tell Mallory about that story, it is possible for you to claim that Bob made the story up. Conversely, if you were to “sign” every statement you have ever made to Bob it would be practically impossible to deny that you told that story to Bob.

How do I know I am talking to Bob?

Of course, this system would fail completely if you were not guaranteed to be speaking to Bob. I’ll get to this, but for now, assume we know that we are speaking to Bob (or whatever individual or group you want to speak to).

Deniability? That sounds bad.

Deniability isn’t a panacea. For example, deniable bank transactions could be a disaster. However, deniability could be a (literal) life-saver for political dissidents, or whistleblowers.

Okay, you got me. How does it work?

Signal Protocol’s method of achieving deniable authentication is a modification of OTR. However, OTR’s authentication process is a bit more complicated and satisfies a weaker notion of deniability so I’ll just cover Signal Protocol’s deniable authentication scheme (If you are interested, Matthew Green has a great write-up on OTR).

In Signal Protocol, Alice and Bob must first exchange keys using three Diffie-Hellman key exchanges. The three key exchanges derive shared secrets from Alice’s long term and ephemeral keys (A and a respectively) and Bob’s long term and ephemeral keys (B and b respectively). Once the three key exchanges are complete, Alice and Bob share secrets: S_Ab, S_Ba, and S_ab. S_Ab is a shared secret that Bob creates using Alice’s long term identity A (Alice’s long-term “identity” public key) and b (Bob’s ephemeral secret). S_Ba is a shared secret that does that same for Alice. S_ab is a shared secret derived from Alice’s and Bob’s ephemeral keys. If Alice and Bob trusts that A and B are the expected identity keys for one another, they can trust that the three shared keys are legitimate. These three shared keys can be then passed into a key derivation function (KDF) to generate a shared symmetric key. In order to authenticate messages between parties, one of the derived shared symmetric keys is used to sign messages with a message authentication code (e.g. HMAC-SHA256).

That was confusing. How is this deniable?

Valid point! After they complete an untampered key exchange Alice and Bob have this Frankenstein shared key which also authenticates one another. Alice and Bob use this shared key to derive symmetric encryption and authentication keys. When Alice sends Bob a message, the message is encrypted and signed using these derived keys. When Bob receives that message, he can decrypt it and verify the signature. If the signature is valid, Bob knows that Alice sent the message because Bob knows he did not send the message himself. However, because authentication is done using a key shared between Alice and Bob, Bob could also show Mallory a message that was “signed” with this key.

Welp. That sounds bad.

We talked about this earlier, remember? It’s not necessarily bad! If this property is understood by both parties, when Bob blabs to Mallory, Alice can deny that she sent the message even if she did actually send it. If the construction of the protocol is sound, then all Mallory can do is take Bob’s word on it.

Is that it?

Not quite. Remember the confusing key exchange from earlier? Signal Protocol’s triple Diffie-Hellman key exchange also allows any individual with an identity key to construct a completely fake transcript between themselves and another individual. This allows individuals who have never communicated to forge message from one another. Neat!

Are you done?

Yes. Thanks for listening.