A signature nobody asked for

Every message that leaves Gmail carries a cryptographic signature. DKIM was built to fight spam. It lets a receiving server confirm that a message really came from the domain it claims to come from, and that nobody altered it on the way. It works well, and almost nobody thinks about it.

Then a mailbox gets stolen and published. The messages arrive in the dump with their DKIM headers still attached, and anyone holding the provider's public key can check them. No journalist has to take the leaker's word that the emails are real. An anti-spam measure has quietly become permanent, machine-verifiable proof of authorship for every message in the archive. News organisations lean on this when a dump lands and the sourcing is murky, to the point where the Associated Press publishes a tool for checking the signatures.

Matthew Green's proposed fix sounds like a mistake the first time you read it. Providers should rotate their DKIM keys often, then publish the old private keys. Once a private key is public, anyone could have produced those old signatures, so the signatures prove nothing about who wrote the message. Mail still gets protected from spoofing while it is in flight. It just stops being evidence a few days later. There is already a tool, dkim-rotate, that does exactly this.

Now apply the same idea to a messaging app.

The obvious way to do it, and why Signal declined

Signal authenticates everything you send. When a message arrives from Alice, Bob's client can be certain it came from Alice and that nobody tampered with it in transit. That is the whole point of end-to-end encryption.

The obvious way to build that is a digital signature. Alice signs each message with her private key, Bob verifies it with her public key, done. It is the first tool most developers reach for when they need authenticity, and the ecosystem around it is mature.

Signal does not do this, and neither did OTR before it. Both sign key material and never messages. OTR's authors were explicit that the only data they ever sign is Alice's Diffie-Hellman value, which tells you she chose it and nothing more. Signal's X3DH specification says the protocol establishes a shared secret between two parties who authenticate each other from public keys, and that it provides forward secrecy and cryptographic deniability.

That last word is the answer. The rest of this post is about what it means and what it costs.

Convinced, but unable to prove it

Deniability is authentication that does not transfer. Bob must be convinced that Alice sent the message. Bob must not be able to convince anyone else.

Put more precisely, anything Bob could show a third party as proof of what Alice wrote, Bob could have produced himself without Alice's help. The evidence is worthless to an outsider because the person holding it had the means to fabricate it.

A digital signature is the exact opposite, and that is by design. A signature is meant to be verifiable by anyone, forever, which is why it works for software releases, certificates and contracts. Only Alice's private key could have produced it, so the signature is proof in a sense that holds up against a third party who trusts nobody involved.

The OTR paper made the argument in 2004. Systems like PGP give you long-lived encryption keys and signatures that amount to strong, in some places legally recognised, proof of authorship. The authors argued that casual private conversation wants the opposite two properties: forward secrecy and repudiability. A spoken conversation in an empty room has both. Your encrypted chat probably should too.

It is worth being precise about what is being denied. Deniability of message content means Alice can deny writing a particular message. Deniability of participation means she can deny talking to Bob at all. X3DH claims both, stating that it gives neither party a publishable cryptographic proof of the contents of their communication or of the fact that they communicated. That is a claim about the protocol rather than about the system around it, and who exchanged messages with whom stays visible to servers and networks whatever the handshake proves.

The whole trick is that the key is shared

A MAC and a signature look similar from the outside. Both take a message and a key, produce a tag, and let a receiver detect tampering. The difference is who holds the key.

With a signature, Alice signs with a key only she has, and Bob verifies with a key everyone has. Verification is public, which is exactly what makes the result transferable.

With a MAC, Alice and Bob hold the same key. Bob can verify a tag, and the moment he can verify it he can also create one, over any message he likes. So when Bob looks at a valid tag, he knows: either Alice produced this, or he did. He did not, so it was Alice. Nobody else gets to make that inference. A judge looking at the same tag sees a value that Bob could have generated over any text he wanted.

This is the entire mechanism. Authentication that convinces exactly one person, because verifying and forging take the same key.

The remaining question is how Alice and Bob get a shared key without a signature somewhere in the handshake, and that is what X3DH is for. It derives a shared secret from several Diffie-Hellman operations combining long-term identity keys with ephemeral keys. Authentication comes from which keys went into the computation, not from a signature over the transcript. There is a signature in the protocol, on Bob's signed prekey, but it only attests that Bob published a key. It says nothing about any conversation.

So the chain runs from a key agreement that authenticates implicitly, to a shared secret, to keys derived from it, to MACs on every message, and no step in it produces anything an outsider can check. The specification is explicit that this was a choice rather than an oversight. Swapping the Diffie-Hellman mutual authentication for signatures from the identity keys, it notes, would reduce deniability, increase the size of initial messages, and worsen the damage done if ephemeral or prekey private keys were compromised or the signature scheme broken.

OTR went further and made the crypto worse on purpose

Shared-key MACs get you deniability against a third party who was never in the room. OTR was not satisfied with that, because of a weaker but real objection. Bob can verify the tag, so a transcript plus Bob's testimony is still more convincing than a transcript alone. Only two people in the world could have made that tag.

OTR's answer was to expand that set to everyone. When a Diffie-Hellman key is about to be discarded, OTR gathers up the MAC keys derived from it that were actually used, and attaches them to the next data message in a field the protocol specification calls, plainly, old MAC keys to be revealed. The keys go out in the clear, to anyone watching. From that moment any observer can alter one of those old messages and still have it verify. Timing matters here, as keys are revealed only once the D-H keys behind them are being thrown away, so a revealed key can never be used to slip a forgery into a live conversation. The authentication was real while the conversation was happening, and the transcript becomes forgeable afterwards. The paper frames this as the analogue of perfect forward secrecy for authentication.

The second idea is stranger. The paper lists malleable encryption as one of the four primitives it builds on, and says what it is for, which is forgeability of transcripts, repudiation of contents and plausible deniability. So OTR encrypts with a stream cipher, AES in counter mode, where flipping a bit of ciphertext flips the matching bit of plaintext. Anyone who can guess what a message said can rewrite it into any other message of the same length without holding the key. Everywhere else this is a flaw you work hard to eliminate, which is why we reach for authenticated encryption. Here it is the goal, and combined with a revealed MAC key it leaves behind a transcript that anyone could have written.

This is the same move as publishing old DKIM keys. Authenticate strongly now, destroy the evidentiary value later, and treat those as two separate requirements.

Signal inherited the first half of this. The Double Ratchet, designed by Trevor Perrin and Moxie Marlinspike, credits its Diffie-Hellman ratchet directly to OTR, and pairs it with a symmetric-key ratchet, an older idea that protocols like SCIMP and MinimaLT had also used. What it did not inherit is the revealed MAC keys or the deliberate malleability. Revealing a MAC key is only safe once every message it authenticated has arrived, which is the condition the OTR paper waits for before publishing one. Publish earlier and an attacker can forge under that key, while a recipient still waiting on a delayed message would accept the forgery as genuine. OTR could rely on that condition because both parties were online in a live conversation. Signal cannot, since a phone may be off for days with messages still sitting on a server.

What this does not protect you from

It is worth being honest about how little of this reaches a courtroom.

Nobody needs to verify a MAC when they have your unlocked phone. Screenshots, forensic extraction from a seized device, the other party's testimony, and the service provider's own records about who talked to whom all get used, and none of them care what your protocol proves. A judge weighs evidence on the balance of probabilities and is not obliged to discard a transcript because it is theoretically forgeable.

There is also a gap between the property as advertised and the property as proven. Offline deniability was widely assumed for Signal for years before anyone wrote down a proof, and when Vatandas, Gennaro, Ithurburn and Krawczyk went looking, they found the proof is not straightforward and depends on strong assumptions about the mathematical groups the protocol runs in. Their result is positive for Signal, but the intuition that a minimal transcript is obviously deniable turns out not to hold on its own.

And deniability has a version harder than the one Signal provides. Offline deniability protects you against someone who turns up afterwards with a transcript. Online deniability protects you against a judge who is colluding with Bob while the conversation is still happening. The X3DH specification concedes this one, noting that a party who collaborates with a third party during the protocol run can prove the communication to them, and that the limitation appears intrinsic to the asynchronous setting. Unger and Goldberg's work on strongly deniable key exchanges is an attempt at the harder problem.

So the honest claim is narrow. Deniability removes one specific thing, the cryptographic artefact that makes a leaked transcript self-authenticating to the world. The DKIM case is exactly where that matters, because there the artefact was the whole reason the leak was credible.

Authenticated is not one property

The lesson here is not about messaging. It is that "authenticated" names a family of properties, not a single one, and the member you want depends on who you are protecting the user from.

If the adversary is someone impersonating your software release, you want a signature that is public, transferable and permanent. If the adversary is whoever ends up holding a copy of the conversation later, those same three properties are the attack. Same word, opposite requirement.

That is why the primitive choice is the design work. A MAC is not a cheaper signature. It is a different claim about who gets to be convinced, and OTR's published keys and malleable encryption are what that claim looks like taken to its conclusion.

It also cuts the other way. Platforms want users to be able to report abuse, and a report is only useful if the provider can verify it. Facebook's message franking exists precisely to make certain messages provable to the service. You cannot maximise deniability and reportability at once, and choosing between them is a product decision wearing a cryptography costume. That one deserves its own post.

Sources