A Brief Introduction to Deniability

Earlier this week, security researcher Ryan Castellucci published a blog post with a somewhat provocative title: DKIM: Show Your Privates.

After reading the ensuing discussions on Hacker News and Reddit about their DKIM post, it seems clear that the importance of deniability in online communications seems to have been broadly overlooked.

Security Goals, Summarized

When you design or implement any communications protocol, you typically have most or all of the following security goals:

• Confidentiality: Only the intended recipients can understand the contents of a message (almost always achieved through encryption).
• Integrity: The message will be delivered without alterations; and if it is, the recipient will know to reject it.
• Availability: Authorized users will have access to the resources they need (i.e. a medium they can communicate through).

However, you may also have one or more of the following security goals:

• Authenticity: In a group communication protocol, you want to ensure you can validate which participant sent each message. This is loosely related to, yet independent from, integrity.
• Non-Repudiation: An extension of authenticity, wherein you cannot deny that you sent a message after you sent it; it’s provable that you sent it.
• Deniability: The complement to non-repudiation, wherein you can prove that you sent a message to your recipient, and then at a future time make it possible for other participants to have forged the message.

It’s tempting to think of deniability as the opposite of non-repudiation, but in practice, you want messages to have authenticity for at least a brief period of time for both.

However, you cannot simultaneously have deniability and non-repudiation in a communication. They’re mutually exclusive concepts, even if they both build off authenticity. Hence, I call it a complement.

Off-The-Record messaging achieved deniability through publishing the signing key of the previous message with each additional message.

Security Properties of DKIM

Ryan Castellucci’s blog post correctly observed that the anti-spam protocol DKIM, as used by most mail providers in 2020, incidentally also offers non-repudiation…even if that’s not supposed to be a primary goal of DKIM.

Non-repudiation can be bolted onto any protocol with long-term asymmetric cryptographic keys used to generate digital signatures of messages–which is exactly what DKIM does.

Real World Case Study

A while ago, the New York Post published a DKIM-signed email from someone claiming to be named Vadym Pozharskyi to Hunter Biden–son of the presidential candidate and former Vice President Joe Biden.

Because the DKIM public keys used by Gmail during that time period are known–but not the private keys–it’s possible to authenticate that the emails came from Gmail and is a valid email. And someone did exactly this.

In a similar vein, if someone wanted to embarrass an executive at a large company, accessing their colleagues’ email and leaking messages would be sufficient, since DKIM could be used to verify that the emails are authentic.

Deniability in DKIM

Ryan’s proposal for introducing deniability in DKIM was to routinely rotate signing keys and publish fragments of their old DKIM private keys (which are RSA keys) so that anyone can reconstruct the private key after-the-fact.

This kind of deniability is mostly to mitigate against the harm of data leaks–such as your friend’s laptop getting stolen and someone trying to lambaste you on social media for an email you sent 10+ years ago–rather than provide a legal form of deniability. (We’re cryptography nerds, not lawyers.)

If the laptop theft scenario took place, with DKIM, someone can cryptographically prove you sent the email at a specific time to your friend with a specific body, because it’s signed by (presumably Gmail’s) DKIM keys.

Conversely, if you had used an email provider that practiced what Ryan proposed (rotating/publishing the private key at a regular interval), they couldn’t cryptographically prove anything. If the past private keys are public, anyone could have come along and forged the DKIM signature.

On Post-Compromise Security

The concept of Post-Compromise Security is somewhat related to deniability (but affects confidentiality rather than integrity or authenticity):

If someone successfully compromises one participant in a private discussion group, and their access is discovered, can the rest of the participants recover from this breach and continue to have privacy for future conversations?

It’s easy to see how the concepts are related.

• Deniability offers short-term authenticity followed by a long-term break in authenticity.
• Post-Compromise Security offers long-term confidentiality even if there’s a short-term break in confidentiality.

Robust private messaging protocols–such as what the IETF is trying to provide with Message Layer Security–would ideally offer both properties to their users.

Past attempts to build non-repudiation (through “message franking”) on top of cipher constructions like AES-GCM led to a class of attacks known affectionately as Invisible Salamanders, based on the title of the relevant research paper.

In Conclusion

Apropos of nothing, I really wish Gmail would start publishing its expired DKIM secret keys.

— Matthew Green (@matthew_d_green) November 1, 2020

It might seem really weird for cryptographers to want large-scale email providers to publish their expired DKIM secret keys, but when you understand the importance of deniability in past private communications, it’s a straightforward thing to want.

It’s worth noting: Some security experts will push back on this, because they work in computer forensics, and making DKIM deniable would theoretically make their job slightly more difficult.

Keep their self-interest in mind when they’re complaining about this notion, since the proposal is not to publish non-expired DKIM secret keys, and therefore it would not make spam more challenging to combat.