Key Transparency and the Right to be Forgotten

This post is the first in a new series covering some of the reasoning behind decisions made in my project to build end-to-end encryption for direct messages on the Fediverse.

(Collectively, Fedi-E2EE.)

Although the reasons for specific design decisions should be immediately obvious from reading the relevant specification (and if not, I consider that a bug in the specification), I believe writing about it less formally will improve the clarity behind the specific design decisions taken.

In the inaugural post for this series, I’d like to focus on how the Fedi-E2EE Public Key Directory specification aims to provide Key Transparency and an Authority-free PKI for the Fediverse without making GDPR compliance logically impossible.

CMYKat‘s art, edited by me.

Background

Key Transparency

For a clearer background, I recommend reading my blog post announcing the focused effort on a Public Key Directory, and then my update from August 2024.

If you’re in a hurry, I’ll be brief:

The goal of Key Transparency is to ensure everyone in a network sees the same view of who has which public key.

How it accomplishes this is a little complicated: It involves Merkle trees, digital signatures, and a higher-level protocol of distinct actions that affect the state machine.

If you’re thinking “blockchain”, you’re in the right ballpark, but we aren’t propping up a cryptocurrency. Instead, we’re using a centralized publisher model (per Public Key Directory instance) with decentralized verification.

Add a bit of cross-signing and replication, and you can stitch together a robust network of Public Key Directories that can be queried to obtain the currently-trusted list of public keys (or other auxiliary data) for a given Fediverse user. This can then be used to build application-layer protocols (i.e., end-to-end encryption with an identity key more robust than “trust on first use” due to the built-in audit trail to Merkle trees).

I’m handwaving a lot of details here. The Architecture and Specification documents are both worth a read if you’re curious to learn more.

Harubaki

Right To Be Forgotten

I am not a lawyer, nor do I play one on TV. This is not legal advice. Other standard disclaimers go here.

Okay, now that we’ve got that out of the way, Article 17 of the GDPR establishes a “Right to erasure” for Personal Data.

What this actually means in practice has not been consistently decided by the courts yet. However, a publicly readable, immutable ledger that maps public keys (which may be considered Personal Data) with Actor IDs (which includes usernames, which are definitely Personal Data) goes against the grain when it comes to GDPR.

It remains an open question of there is public interest in this data persisting in a read-only ledger ad infinitum, which could override the right to be forgotten. If there is, that’s for the courts to decide, not furry tech bloggers.

I know it can be tempting, especially as an American with no presence in the European Union, to shrug and say, “That seems like a them problem.” However, if other folks want to be able to use my designs within the EU, I would be remiss to at least consider this potential pitfall and try to mitigate it in my designs.

So that’s exactly what I did.

AJ

Almost Contradictory

At first glance, the privacy goals of both Key Transparency and the GDPR’s Right To Erasure are at odds.

• One creates an immutable, append-only history.
• The other establishes a right for EU citizens’ history to be selectively censored, which means history has to be mutable.

However, they’re not totally impossible to reconcile.

An untested legal theory circulating around large American tech companies is that “crypto shredding” is legally equivalent to erasure.

Crypto shredding is the act of storing encrypted data, and then when given a legal takedown request from an EU citizen, deleting the key instead of the data.

AJ

This works from a purely technical perspective: If the data is encrypted, and you don’t know the key, to you it’s indistinguishable from someone who encrypted the same number of NUL bytes.

In fact, many security proofs for encryption schemes are satisfied by reaching this conclusion, so this isn’t a crazy notion.

Is Crypto Shredding Plausible?

In 2019, the European Parliamentary Research Service published a lengthy report titled Blockchain and the General Data Protection Regulation which states the following:

Before any examination of whether blockchain technology is capable of complying with Article 17 GDPR; it must be underscored that the precise meaning of the term ‘erasure’ remains unclear.

Article 17 GDPR does not define erasure, and the Regulation’s recitals are equally mum on how this term should be understood. It might be assumed that a common-sense understanding of this terminology ought to be embraced. According to the Oxford English Dictionary, erasure means ‘the removal or writing, recorded material, or data’ or ‘the removal of all traces of something: obliteration’.494

From this perspective, erasure could be taken to equal destruction. It has, however, already been stressed that the destruction of data on blockchains, particularly these of a public and permissionless nature, is far from straightforward.

There are, however, indications that the obligation inherent to Article 17 GDPR does not have to be interpreted as requiring the outright destruction of data. In Google Spain, the delisting of information from research results was considered to amount to erasure. It is important to note, however, that in this case, this is all that was requested of Google by the claimant, who did not have control over the original data source (an online newspaper publication). Had the claimant wished to obtain the outright destruction of the relevant data it would have had to address the newspaper, not Google. This may be taken as an indication that what the GDPR requires is that the obligation resting on data controllers is to do all they can to secure a result as close as possible to the destruction of their data within the limits of [their] own factual possibilities.

Dr Michèle Finck, Blockchain and the General Data Protection Regulation, pp. 75-76

From this, we can kind of intuit that the courts aren’t pedantic: The cited Google Spain case was satisfied by merely delisting the content, not the erasure of the newspaper’s archives.

The report goes on to say:

As awareness regarding the tricky reconciliation between Article 17 GDPR and distributed ledgers grows, a number of technical alternatives to the outright destruction of data have been considered by various actors. An often-mentioned solution is that of the destruction of the private key, which would have the effect of making data encrypted with a public key inaccessible. This is indeed the solution that has been put forward by the French data protection authority CNIL in its guidance on blockchains and the GDPR. The CNIL has suggested that erasure could be obtained where the keyed hash function’s secret key is deleted together with information from other systems where it was stored for processing.

Dr Michèle Finck, Blockchain and the General Data Protection Regulation, pp. 76-77

That said, I cannot locate a specific court decision that affirms that crypto erasure is legally sufficient for complying with data erasure requests (nor any that affirm that it’s necessary).

I don’t have a crystal ball that can read the future on what government compliance will decide, nor am I an expert in legal matters.

Given the absence of a clear legal framework, I do think it’s totally reasonable to consider crypto-shredding equivalent to data erasure. Most experts would probably agree with this. But it’s also possible that the courts could rule totally stupidly on this one day.

Therefore, I must caution anyone that follows a similar path: Do not claim GDPR compliance just because you implement crypto-shredding in a distributed ledger. All you can realistically promise is that you’re not going out of your way to make compliance logically impossible. All we have to go by are untested legal hypotheses, and very little clarity (even if the technologists are near-unanimous on the topic!).

Towards A Solution

With all that in mind, let’s start with “crypto shredding” as the answer to the GDPR + transparency log conundrum.

This is only the start of our complications.

CMYKat

Protocol Risks Introduced by Crypto Shredding

Before the introduction of crypto shredding, the job of the Public Key Directory was simple:

1. Receive a protocol message.
2. Validate the protocol message.
3. Commit the protocol message to a transparency log (in this case, Sigsum).
4. Retrieve the protocol message whenever someone requests it to independently verify its inclusion.
5. Miscellaneous other protocol things (cross-directory checkpoint commitment, replication, etc.).

Point being: there was very little that the directory could do to be dishonest. If they lied about the contents of a record, it would invalidate the inclusion proofs of every successive record in the ledger.

In order to make a given record crypto-shreddable without breaking the inclusion proofs for every record that follows, we need to commit to the ciphertext, not the plaintext. (And then, when a takedown request comes in, wipe the key.)

Now, things are quite more interesting.

Do you…

• …Distribute the encryption key alongside the ciphertext and let independent third parties decrypt it on demand?
  …OR…
• Decrypt the ciphertext and serve plaintext through the public API, keeping the encryption key private so that it may be shredded later?

The first option seems simple, but runs into governance issues: How do you claim the data was crypto-shredded if countless individuals have a copy of the encryption key, and can therefore recover the plaintext from the ciphertext?

I don’t think that would stand up in court.

CMYKat

Clearly, your best option is the second one.

Okay, so how does an end user know that the ciphertext that was committed to the transparency ledger decrypts to the specific plaintext value served by the Public Key Directory? How do users know it’s not lying?

Quick aside: This question is also relevant if you went with the first option and used a non-committing AEAD mode for the actual encryption scheme.

In that scenario, a hostile nation state adversary could pressure a Public Key Directory to selectively give one decryption key to targeted users, and another to the rest of the Internet, in order to perform a targeted attack against citizens they’d rather didn’t have civil rights.

My entire goal with introducing key transparency to my end-to-end encryption proposal is to prevent these sorts of attacks, not enable them.

There are a lot of avenues we could explore here, but it’s always worth outlining the specific assumptions and security goals of any design before you start perusing the literature.

AJ

Assumptions

This is just a list of things we assume are true, and do not need to prove for the sake of our discussion here today. The first two are legal assumptions; the remainder are cryptographic.

Ask your lawyer if you want advice about the first two assumptions. Ask your cryptographer if you suspect any of the remaining assumptions are false.

1. Crypto-shredding is a legally valid way to provide data erasure (as discussed above).
2. EU courts will consider public keys to be Personal Data.
3. The SHA-2 family of hash functions is secure (ignoring length-extension attacks, which won’t matter for how we’re using them).
4. HMAC is a secure way to build a MAC algorithm out of a secure hash function.
5. HKDF is a secure KDF if used correctly.
6. AES is a secure 128-bit block cipher.
7. Counter Mode (CTR) is a secure way to turn a block cipher into a stream cipher.
8. AES-CTR + HMAC-SHA2 can be turned into a secure AEAD mode, if done carefully.
9. Ed25519 is a digital signature algorithm that provides strong security against existent forgery under a chosen-message attack (SUF-CMA).
10. Argon2id is a secure, memory-hard password KDF, when used with reasonable parameters. (You’ll see why in a moment.)
11. Sigsum is a secure mechanism for building a transparency log.

This list isn’t exhaustive or formal, but should be sufficient for our purposes.

Security Goals

1. The protocol messages stored in the Public Key Directory are accompanied by a Merkle tree proof of inclusion. This makes it append-only with an immutable history.
2. The Public Key Directory cannot behave dishonestly about the decrypted plaintext for a given ciphertext without clients detecting the deception.
3. Whatever strategy we use to solve this should be resistant to economic precomputation and brute-force attacks.

Can We Use Zero-Knowledge Proofs?

At first, this seems like an ideal situation for a succinct, non-interactive zero-knowledge proof.

After all, you’ve got some secret data that you hold, and you want to prove that a calculation is correct without revealing the data to the end user. This seems like the ideal setup for Schnorr’s identification protocol.

CMYKat

Unfortunately, the second assumption (public keys being considered Personal Data by courts, even though they’re derived from random secret keys) makes implementing a Zero-Knowledge Proof here very challenging.

First, if you look at Ed25519 carefully, you’ll realize that it’s just a digital signature algorithm built atop a Schnorr proof, which requires some sort of public key (even an ephemeral one) to be managed.

Worse, if you try to derive this value solely from public inputs (rather than creating a key management catch-22), the secret scalar your system derives at will have been calculated from the user’s Personal Data–which only strengthens a court’s argument that the public key is therefore personally identifiable.

CMKat

There may be a more exotic zero-knowledge proof scheme that might be appropriate for our needs, but I’m generally wary of fancy new cryptography.

Here are two rules I live by in this context:

1. If I can’t get the algorithms out of the crypto module for whatever programming language I find myself working with, it may as well not even exist.
   
   • Corollary: If libsodium bindings are available, that counts as “the crypto module” too.

   
   

2. If a developer needs to reach for a generic Big Integer library (e.g., GMP) for any reason in the course of implementing a protocol, I do not trust their implementation.

Unfortunately, a lot of zero-knowledge proof designs fail one or both of these rules in practice.

(Sorry not sorry, homomorphic encryption enthusiasts! The real world hasn’t caught up to your ideas yet.)

What About Verifiable Random Functions (VRFs)?

It may be tempting to use VRFs (i.e., RFC 9381), but this runs into the same problem as zero-knowledge proofs: we’re assuming that an EU court would deem public keys Personal Data.

But even if that assumption turns out false, the lifecycle of a protocol message looks like this:

1. User wants to perform an action (e.g., AddKey).
2. Their client software creates a plaintext protocol message.
3. Their client software generates a random 256-bit key for each potentially-sensitive attribute, so it can be shredded later.
4. Their client software encrypts each attribute of the protocol message.
5. The ciphertext and keys are sent to the Public Key Directory.
6. For each attribute, the Public Key Directory decrypts the ciphertext with the key, verifies the contents, and then stores both. The ciphertext is used to generate a commitment on Sigsum (signed by the Public Key Directory’s keypair).
7. The Public Key Directory serves plaintext to requestors, but does not disclose the key.
8. In the future, the end user can demand a legal takedown, which just wipes the key.

Let’s assume I wanted to build a VRF out of Ed25519 (similar to what Signal does with VXEdDSA). Now I have a key management problem, which is pretty much what this project was meant to address in the first place.

VRFs are really cool, and more projects should use them, but I don’t think they will help me.

CMYKat

Soatok’s Proposed Solution

If you want to fully understand the nitty-gritty implementation details, I encourage you to read the current draft specification, plus the section describing the encryption algorithm, and finally the plaintext commitment algorithm.

Now that we’ve established all that, I can begin to describe my approach to solving this problem.

First, we will encrypt each attribute of a protocol message, as follows:

• For subkey derivation, we use HKDF-HMAC-SHA512.
• For encrypting the actual plaintext, we use AES-256-CTR.
• For message authentication, we use HMAC-SHA512.
• Additional associated data (AAD) is accepted and handled securely; i.e., we don’t use YOLO as a hash construction.

This prevents an Invisible Salamander attack from being possible.

This encryption is performed client-side, by each user, and the symmetric key for each attribute is shared with the Public Key Directory when publishing protocol messages.

If they later issue a legal request for erasure, they can be sure that the key used to encrypt the data they previously published isn’t secretly the same key used by every other user’s records.

They always know this because they selected the key, not the server. Furthermore, everyone can verify that the hash published to the Merkle tree matches a locally generated hash of the ciphertext they just emitted.

This provides a mechanism to keep everyone honest. If anything goes wrong, it will be detected.

Next, to prevent the server from being dishonest, we include a plaintext commitment hash, which is included as part of the AAD (alongside the attribute name).

(Implementing crypto-shredding is straightforward: simply wipe the encryption keys for the attributes of the records in scope for the request.)

If you’ve read this far, you’re probably wondering, “What exactly do you mean by plaintext commitment?”

Art by Scruff.

Plaintext Commitments

The security of a plaintext commitment is attained by the Argon2id password hashing function.

By using the Argon2id KDF, you can make an effective trapdoor that is easy to calculate if you know the plaintext, but economically infeasible to brute-force attack if you do not.

However, you need to do a little more work to make it safe.

Harubaki

The details here matter a lot, so this section is unavoidably going to be a little dense.

Pass the Salt?

Argon2id expects both a password and a salt.

If you eschew the salt (i.e., zero it out), you open the door to precomputation attacks (see also: rainbow tables) that would greatly weaken the security of this plaintext commitment scheme.

You need a salt.

If you generate the salt randomly, this commitment property isn’t guaranteed by the algorithm. It would be difficult, but probably not impossible, to find two salts (, ) such that .

Deriving the salt from public inputs eliminates this flexibility.

By itself, this reintroduces the risk of making salts totally deterministic, which reintroduces the risk of precomputation attacks (which motivated the salt in the first place).

If you include the plaintext in this calculation, it could also create a crib that gives attackers a shortcut for bypassing the cost of password hashing.

Furthermore, any two encryptions operations that act over the same plaintext would, without any additional design considerations, produce an identical value for the plaintext commitment.

CMYKat

Public Inputs for Salt Derivation

The initial proposal included the plaintext value for Argon2 salt derivation, and published the salt and Argon2 output next to each other.

Hacker News comex pointed out a flaw with this technique, so I’ve since revised how salts are selected to make them independent of the plaintext.

The public inputs for the Argon2 salt are now:

1. The version identifier prefix for the ciphertext blob.
2. The 256-bit random value used as a KDF salt (also stored in the ciphertext blob).
3. A recent Merkle tree root.
4. The attribute name (prefixed by its length).

These values are all hashed together with SHA-512, and then truncated to 128 bits (the length required by libsodium for Argon2 salts).

This salt is not stored, but can deterministically be calculated from public information.

Crisis Averted?

This sure sounds like we’ve arrived at a solution, but let’s also consider another situation before we declare our job done.

High-traffic Public Key Directories may have multiple users push a protocol message with the same recent Merkle root.

This may happen if two or more users query the directory to obtain the latest Merkle root before either of them publish their updates.

Later, if both of these users issue a legal takedown, someone might observe that the recent-merkle-root is the same for two messages, but their commitments differ.

Is this enough leakage to distinguish plaintext records?

In my earlier design, we needed to truncate the salt and rely on understanding the birthday bound to reason about its security. This is no longer the case, since each salt is randomized by the same random value used in key derivation.

Choosing Other Parameters

As mentioned a second ago, we set the output length of the Argon2id KDF to 32 bytes (256 bits). We expect the security of this KDF to exceed , which to most users might as well be infinity.

With apologies to Filippo.

The other Argon2id parameters are a bit hand-wavey. Although the general recommendation for Argon2id is to use as much memory as possible, this code will inevitably run in some low-memory environments, so asking for several gigabytes isn’t reasonable.

For the first draft, I settled on 16 MiB of memory, 3 iterations, and a parallelism degree of 1 (for widespread platform support).

Plaintext Commitment Algorithm

With all that figured out, our plaintext commitment algorithm looks something like this:

1. Calculate the SHA512 hash of:
   
   • A domain separation constant
   • The header prefix (stored in the ciphertext)
   • The randomness used for key-splitting in encryption (stored in the ciphertext)
   • Recent Merkle Root
   • Attribute Name Length (64-bit unsigned integer)
   • Attribute Name

   
   

2. Truncate this hash to the rightmost 16 bytes (128 bits). This is the salt.
3. Calculate Argon2id over the following inputs concatenated in this order, with an output length of 32 bytes (256 bits), using the salt from step 2:
   
   • Recent Merle Root Length (64-bit unsigned integer)
   • Recent Merkle Root
   • Attribute Name Length (64-bit unsigned integer)
   • Attribute Name
   • Plaintext Length (64-bit unsigned integer)
   • Plaintext

   
   

The output (step 3) is included as the AAD in the attribute encryption step, so the authentication tag is calculated over both the randomness and the commitment.

To verify a commitment (which is extractable from the ciphertext), simply recalculate the commitment you expect (using the recent Merkle root specified by the record), and compare the two in constant-time.

If they match, then you know the plaintext you’re seeing is the correct value for the ciphertext value that was committed to the Merkle tree.

If the encryption key is shredded in the future, an attacker without knowledge of the plaintext will have an enormous uphill battle recovering it from the KDF output (and the salt will prove to be somewhat useless as a crib).

AJ

Caveats and Limitations

Although this design does satisfy the specific criteria we’ve established, an attacker that already knows the correct plaintext can confirm that a specific record matches it via the plaintext commitment.

This cannot be avoided: If we are to publish a commitment of the plaintext, someone with the plaintext can always confirm the commitment after the fact.

CMYKat

Whether this matters at all to the courts is a question for which I cannot offer any insight.

Remember, we don’t even know if any of this is actually necessary, or if “moderation and platform safety” is a sufficient reason to sidestep the right to erasure.

If the courts ever clarify this adequately, we can simply publish the mapping of Actor IDs to public keys and auxiliary data without any crypto-shredding at all.

Trying to attack it from the other direction (download a crypto-shredded record and try to recover the plaintext without knowing it ahead of time) is attack angle we’re interested in.

Herd Immunity for the Forgotten

Another interesting implication that might not be obvious: The more Fediverse servers and users publish to a single Public Key Directory, the greater the anonymity pool available to each of them.

Consider the case where a user has erased their previous Fediverse account and used the GDPR to also crypto-shred the Public Key Directory entries containing their old Actor ID.

To guess the correct plaintext, you must not only brute-force guessing possible usernames, but also permute your guesses across all of the instances in scope.

The more instances there are, the higher the cost of the attack.

CMYKat

Recap

I tasked myself with designing a Key Transparency solution that doesn’t make complying with Article 17 of the GDPR nigh-impossible. To that end, crypto-shredding seemed like the only viable way forward.

A serialized record containing ciphertext for each sensitive attribute would be committed to the Merkle tree. The directory would store the key locally and serve plaintext until a legal takedown was requested by the user who owns the data. Afterwards, the stored ciphertext committed to the Merkle tree is indistinguishable from random for any party that doesn’t already know the plaintext value.

I didn’t want to allow Public Key Directories to lie about the plaintext for a given ciphertext, given that they know the key and the requestor doesn’t.

After considering zero-knowledge proofs and finding them to not be a perfect fit, I settled on designing a plaintext commitment scheme based on the Argon2id password KDF. The KDF salts can be calculated from public inputs.

Altogether, this meets the requirements of enabling crypto-shredding while keeping the Public Key Directory honest. All known attacks for this design are prohibitively expensive for any terrestrial threat actors.

As an added bonus, I didn’t introduce anything fancy. You can build all of this with the cryptography available to your favorite programming language today.

CMYKat

Closing Thoughts

If you’ve made it this far without being horribly confused, you’ve successfully followed my thought process for developing message attribute shreddability in my Public Key Directory specification.

This is just one component of the overall design proposal, but one that I thought my readers would enjoy exploring in greater detail than the specification needed to capture.

Header art: Harubaki, CMYKat.

(This post was updated on 2024-11-22 to replace the incorrect term “PII” with “personal data”. Apologies for the confusion!)

#Argon2 #crypto #cryptography #E2EE #encryption #FederatedPKI #fediverse #passwordHashing #symmetricCryptography

Dhole Moments

2022-11-22 10:57:46

Update (2024-06-06): There is an update on this project.

---

As Twitter’s new management continues to nosedive the platform directly into the ground, many people are migrating to what seem like drop-in alternatives; i.e. Cohost and Mastodon. Some are even considering new platforms that none of us have heard of before (one is called “Hive”).

Needless to say, these are somewhat chaotic times.

One topic that has come up several times in the past few days, to the astonishment of many new Mastodon users, is that Direct Messages between users aren’t end-to-end encrypted.

And while that fact makes Mastodon DMs no less safe than Twitter DMs have been this whole time, there is clearly a lot of value and demand in deploying end-to-end encryption for ActivityPub (the protocol that Mastodon and other Fediverse software uses to communicate).

However, given that Melon Husk apparently wants to hurriedly ship end-to-end encryption (E2EE) in Twitter, in some vain attempt to compete with Signal, I took it upon myself to kickstart the E2EE effort for the Fediverse.

https://twitter.com/elonmusk/status/1519469891455234048

So I’d like to share my thoughts about E2EE, how to design such a system from the ground up, and why the direction Twitter is heading looks to be security theater rather than serious cryptographic engineering.

If you’re not interested in those things, but are interested in what I’m proposing for the Fediverse, head on over to the GitHub repository hosting my work-in-progress proposal draft as I continue to develop it.

How to Quickly Build E2EE

If one were feeling particularly cavalier about your E2EE designs, they could just generate then dump public keys through a server they control, pass between users, and have them encrypt client-side. Over and done. Check that box.

Every public key would be ephemeral and implicitly trusted, and the threat model would mostly be, “I don’t want to deal with law enforcement data requests.”

Hell, I’ve previously written an incremental blog post to teach developers about E2EE that begins with this sort of design. Encrypt first, ratchet second, manage trust relationships on public keys last.

If you’re catering to a slightly tech-savvy audience, you might throw in SHA256(pk1 + pk2) -> hex2dec() and call it a fingerprint / safety number / “conversation key” and not think further about this problem.

Look, technical users can verify out-of-band that they’re not being machine-in-the-middle attacked by our service.

An absolute fool who thinks most people will ever do this

From what I’ve gathered, this appears to be the direction that Twitter is going.

https://twitter.com/wongmjane/status/1592831263182028800

Now, if you’re building E2EE into a small hobby app that you developed for fun (say: a World of Warcraft addon for erotic roleplay chat), this is probably good enough.

If you’re building a private messaging feature that is intended to “superset Signal” for hundreds of millions of people, this is woefully inadequate.

https://twitter.com/elonmusk/status/1590426255018848256

Art: LvJ

If this is, indeed, the direction Musk is pushing what’s left of Twitter’s engineering staff, here is a brief list of problems with what they’re doing.

1. Twitter Web. How do you access your E2EE DMs after opening Twitter in your web browser on a desktop computer?
   
   • If you can, how do you know twitter.com isn’t including malicious JavaScript to snarf up your secret keys on behalf of law enforcement or a nation state with a poor human rights record?
   • If you can, how are secret keys managed across devices?
   • If you use a password to derive a secret key, how do you prevent weak, guessable, or reused passwords from weakening the security of the users’ keys?
   • If you cannot, how do users decide which is their primary device? What if that device gets lost, stolen, or damaged?

   
   

2. Authenticity. How do you reason about the person you’re talking with?
3. Forward Secrecy. If your secret key is compromised today, can you recover from this situation? How will your conversation participants reason about your new Conversation Key?
4. Multi-Party E2EE. If a user wants to have a three-way E2EE DM with the other members of their long-distance polycule, does Twitter enable that?
   
   • How are media files encrypted in a group setting? If you fuck this up, you end up like Threema.
   • Is your group key agreement protocol vulnerable to insider attacks?

   
   

5. Cryptography Implementations.
   
   • What does the KEM look like? If you’re using ECC, which curve? Is a common library being used in all devices?
   • How are you deriving keys? Are you just using the result of an elliptic curve (scalar x point) multiplication directly without hashing first?

   
   

6. Independent Third-Party Review.
   
   • Who is reviewing your protocol designs?
   • Who is reviewing your cryptographic primitives?
   • Who is reviewing the code that interacts with E2EE?
   • Is there even a penetration test before the feature launches?

   
   

As more details about Twitter’s approach to E2EE DMs come out, I’m sure the above list will be expanded with even more questions and concerns.

My hunch is that they’ll reuse liblithium (which uses Curve25519 and Gimli) for Twitter DMs, since the only expert I’m aware of in Musk’s employ is the engineer that developed that library for Tesla Motors. Whether they’ll port it to JavaScript or just compile to WebAssembly is hard to say.

How To Safely Build E2EE

You first need to decompose the E2EE problem into five separate but interconnected problems.

1. Client-Side Secret Key Management.
   
   • Multi-device support
   • Protect the secret key from being pilfered (i.e. by in-browser JavaScript delivered from the server)

   
   

2. Public Key Infrastructure and Trust Models.
   
   • TOFU (the SSH model)
   • X.509 Certificate Authorities
   • Certificate/Key/etc. Transparency
   • SigStore
   • PGP’s Web Of Trust

   
   

3. Key Agreement.
   
   • While this is important for 1:1 conversations, it gets combinatorially complex when you start supporting group conversations.

   
   

4. On-the-Wire Encryption.
   
   • Direct Messages
   • Media Attachments
   • Abuse-resistance (i.e. message franking for abuse reporting)

   
   

5. The Construction of the Previous Four.
   
   • The vulnerability of most cryptographic protocols exists in the joinery between the pieces, not the pieces themselves. For example, Matrix.

   
   

This might not be obvious to someone who isn’t a cryptography engineer, but each of those five problems is still really hard.

To wit: The latest IETF RFC draft for Message Layer Security, which tackles the Key Agreement problem above, clocks in at 137 pages.

Additionally, the order I specified these problems matters; it represents my opinion of which problem is relatively harder than the others.

When Twitter’s CISO, Lea Kissner, resigned, they lost a cryptography expert who was keenly aware of the relative difficulty of the first problem.

https://twitter.com/LeaKissner/status/1592937764684980224

You may also notice the order largely mirrors my previous guide on the subject, in reverse. This is because teaching a subject, you start with the simplest and most familiar component. When you’re solving problems, you generally want the opposite: Solve the hardest problems first, then work towards the easier ones.

This is precisely what I’m doing with my E2EE proposal for the Fediverse.

The Journey of a Thousand Miles Begins With A First Step

Before you write any code, you need specifications.

Before you write any specifications, you need a threat model.

Before you write any threat models, you need both a clear mental model of the system you’re working with and how the pieces interact, and a list of security goals you want to achieve.

Less obviously, you need a specific list of non-goals for your design: Properties that you will not prioritize. A lot of security engineering involves trade-offs. For example: elliptic curve choice for digital signatures is largely a trade-off between speed, theoretical security, and real-world implementation security.

If you do not clearly specify your non-goals, they still exist implicitly. However, you may find yourself contradicting them as you change your mind over the course of development.

Being wishy-washy about your security goals is a good way to compromise the security of your overall design.

In my Mastodon E2EE proposal document, I have a section called Design Tenets, which states the priorities used to make trade-off decisions. I chose Usability as the highest priority, because of AviD’s Rule of Usability.

Security at the expense of usability comes at the expense of security.

Avi Douglen, Security StackExchange

Underneath Tenets, I wrote Anti-Tenets. These are things I explicitly and emphatically do not want to prioritize. Interoperability with any incumbent designs (OpenPGP, Matrix, etc.) is the most important anti-tenet when it comes to making decisions. If our end-state happens to interop with someone else’s design, cool. I’m not striving for it though!

Finally, this section concludes with a more formal list of Security Goals for the whole project.

Art: LvJ

Every component (from the above list of five) in my design will have an additional dedicated Security Goals section and Threat Model. For example: Client-Side Secret Key Management.

You will then need to tackle each component independently. The threat model for secret-key management is probably the trickiest. The actual encryption of plaintext messages and media attachments is comparatively simple.

Finally, once all of the pieces are laid out, you have the monumental (dare I say, mammoth) task of stitching them together into a coherent, meaningful design.

If you did your job well at the outset, and correctly understand the architecture of the distributed system you’re working with, this will mostly be straightforward.

Making Progress

At every step of the way, you do need to stop and ask yourself, “If I was an absolute chaos gremlin, how could I fuck with this piece of my design?” The more pieces your design has, the longer the list of ways to attack it will grow.

It’s also helpful to occasionally consider formal methods and security proofs. This can have surprising implications for how you use some algorithms.

You should also be familiar enough with the cryptographic primitives you’re working with before you begin such a journey; because even once you’ve solved the key management story (problems 1, 2 and 3 from the above list of 5), cryptographic expertise is still necessary.

• If you’re feeding data into a hash function, you should also be thinking about domain separation. More information.
• If you’re feeding data into a MAC or signature algorithm, you should also be thinking about canonicalization attacks. More information.
• If you’re encrypting data, you should be thinking about multi-key attacks and confused deputy attacks. Also, the cryptographic doom principle if you’re not using IND-CCA3 algorithms.
• At a higher-level, you should proactively defend against algorithm confusion attacks.

How Do You Measure Success?

It’s tempting to call the project “done” once you’ve completed your specifications and built a prototype, and maybe even published a formal proof of your design, but you should first collect data on every important metric:

1. How easy is it to use your solution?
2. How hard is it to misuse your solution?
3. How easy is it to attack your solution? Which attackers have the highest advantage?
4. How stable is your solution?
5. How performant is your solution? Are the slow pieces the deliberate result of a trade-off? How do you know the balance was struck corectly?

Where We Stand Today

I’ve only begun writing my proposal, and I don’t expect it to be truly ready for cryptographers or security experts to review until early 2023.

However, my clearly specified tenets and anti-tenets were already useful in discussing my proposal on the Fediverse.

@soatok @fasterthanlime Should probably embed the algo used for encryption in the data used for storing the encrypted blob, to support multiples and future changes.

@fabienpenso@hachyderm.io proposes in-band protocol negotiation instead of versioned protocols

The main things I wanted to share today are:

1. The direction Twitter appears to be heading with their E2EE work, and why I think it’s a flawed approach
2. Designing E2EE requires a great deal of time, care, and expertise; getting to market quicker at the expense of a clear and careful design is almost never the right call

Mastodon? ActivityPub? Fediverse? OMGWTFBBQ!

In case anyone is confused about Mastodon vs ActivityPub vs Fediverse lingo:

The end goal of my proposal is that I want to be able to send DMs to queer furries that use Mastodon such that only my recipient can read them.

Achieving this end goal almost exclusively requires building for ActivityPub broadly, not Mastodon specifically.

However, I only want to be responsible for delivering this design into the software I use, not for every single possible platform that uses ActivityPub, nor all the programming languages they’re written in.

I am going to be aggressive about preventing scope creep, since I’m doing all this work for free. (I do have a Ko-Fi, but I won’t link to it from here. Send your donations to the people managing the Mastodon instance that hosts your account instead.)

My hope is that the design documents and technical specifications become clear enough that anyone can securely implement end-to-end encryption for the Fediverse–even if special attention needs to be given to the language-specific cryptographic libraries that you end up using.

Art: LvJ

Why Should We Trust You to Design E2EE?

This sort of question comes up inevitably, so I’d like to tackle it preemptively.

My answer to every question that begins with, “Why should I trust you” is the same: You shouldn’t.

There are certainly cryptography and cybersecurity experts that you will trust more than me. Ask them for their expert opinions of what I’m designing instead of blanketly trusting someone you don’t know.

I’m not interested in revealing my legal name, or my background with cryptography and computer security. Credentials shouldn’t matter here.

If my design is good, you should be able to trust it because it’s good, not because of who wrote it.

If my design is bad, then you should trust whoever proposes a better design instead. Part of why I’m developing it in the open is so that it may be forked by smarter engineers.

Knowing who I am, or what I’ve worked on before, shouldn’t enter your trust calculus at all. I’m a gay furry that works in the technology industry and this is what I’m proposing. Take it or leave it.

Why Not Simply Rubber-Stamp Matrix Instead?

(This section was added on 2022-11-29.)

There’s a temptation, most often found in the sort of person that comments on the /r/privacy subreddit, to ask why even do all of this work in the first place when Matrix already exists?

The answer is simple: I do not trust Megolm, the protocol designed for Matrix.

Megolm has benefited from amateur review for four years. Non-cryptographers will confuse this observation with the proposition that Matrix has benefited from peer review for four years. Those are two different propositions.

In fact, the first time someone with cryptography expertise bothered to look at Matrix for more than a glance, they found critical vulnerabilities in its design. These are the kinds of vulnerabilities that are not easily mitigated, and should be kept in mind when designing a new protocol.

You don’t have to take my word for it. Listen to the Security, Cryptography, Whatever podcast episode if you want cryptographic security experts’ takes on Matrix and these attacks.

From one of the authors of the attack paper:

So they kind of, after we disclosed to them, they shared with us their timeline. It’s not fixed yet. It’s a, it’s a bigger change because they need to change the protocol. But they always said like, Okay, fair enough, they’re gonna change it. And they also kind of announced a few days after kind of the public disclosure based on the public reaction that they should prioritize fixing that. So it seems kind of in the near future, I don’t have the timeline in front of me right now. They’re going to fix that in the sense of like the— because there’s, notions of admins and so on. So like, um, so authenticating such group membership requests is not something that is kind of completely outside of, kind of like the spec. They just kind of need to implement the appropriate authentication and cryptography.

Martin Albrecht, SCW podcast

From one of the podcast hosts:

I guess we can at the very least tell anyone who’s going forward going to try that, that like, yes indeed. You should have formal models and you should have proofs. And so there’s this, one of the reactions to kind of the kind of attacks that we presented and also to prior previous work where we kind of like broken some cryptographic protocols is then to say like, “Well crypto’s hard”, and “don’t roll your own crypto.” But in a way the thing is like, you know, we need some people to roll their own crypto because that’s how we have crypto. Someone needs to roll it. But we have developed techniques, we have developed formalisms, we have developed methods for making sure it doesn’t have to be hard, it’s not, it’s not a dark art kind of that only kind of a few, a select few can master, but it’s, you know, it’s a science and you can learn it. So, but you need to then indeed employ a cryptographer in kind of like forming, modeling your protocol and whenever you make changes, then, you know, they need to look over this and say like, Yes, my proof still goes through. Um, so like that is how you do this. And then, then true engineering is still hard and it will remain hard and you know, any science is hard, but then at least you have some confidence in what you’re doing. You might still then kind of on the space and say like, you know, the attack surface is too large and I’m not gonna to have an encrypted backup. Right. That’s then the problem of a different hard science, social science. Right. But then just use the techniques that we have, the methods that we have to establish what we need.

Thomas Ptacek, SCW podcast

It’s tempting to listen to these experts and say, “OK, you should use libsignal instead.”

But libsignal isn’t designed for federation and didn’t prioritize group messaging. The UX for Signal is like an IM application between two parties. It’s a replacement for SMS.

It’s tempting to say, “Okay, but you should use MLS then; never roll your own,” but MLS doesn’t answer the group membership issue that plagued Matrix. It punts on these implementation details.

Even if I use an incumbent protocol that privacy nerds think is good, I’ll still have to stitch it together in a novel manner. There is no getting around this.

Maybe wait until I’ve finished writing the specifications for my proposal before telling me I shouldn’t propose anything.

---

Credit for art used in header: LvJ, Harubaki

https://soatok.blog/2022/11/22/towards-end-to-end-encryption-for-direct-messages-in-the-fediverse/

#endToEndEncryption #Twitter