E2EE Design Plan

Problem

This discussion thread is inspired by #1093. As the official Fluxer team has stated that they will accept external contributions for E2EE channels provided it doesn't overcomplicate the existing stack, there have been discussions in the #e2ee (now #e2e-encryption) channel of the Fluxer Developers community to elaborate on how we think it should be implemented, and what technical and UX trade-offs we should make. A successful implementation of E2EE channels, whatever their nature turns out to be, should be mostly transparent to the user, and be very easy to grasp if there happens to be limitations. We should not repeat Matrix's mistakes, where [ Unable to decrypt message ]. This is my attempt at consolidating all of this discussion into a single place, so that we can refer back to it to remember where we arrived at the last time we discussed something, especially because we discussed a lot of issues multiple times by now (such is the nature of instant messaging).

Proposed solution

E2EE stands for end-to-end encryption. It is a type of secure communication where only the sender and intended recipient can read the messages, and no one else, especially not the instance owner. There are multiple ways to implement it with different tradeoffs, but some specific implementations we can take as reference are:

• The PQXDH protocol for key agreement, providing post-quantum forward secrecy (if one message is compromised, the previous messages are still safe)
• Signal's Double Ratchet algorithm for message exchange, providing both forward secrecy and post-compromise security- Potentially, [Simplex's patched version of the Double Ratchet algorithm](https://simplex.chat/blog/20240314-simplex-chat-v5-6-quantum-resistance-signal-double-ratchet-algorithm.html) is worth taking a look at, as they claim to fix some important security flaw(s) involving compromised RNG attacks
• The MLS protocol for efficiently handling more than two people in the same channel using a tree of ratchets

Ultimately, our goal is to outline an implementation that has the right compromise between security and user experience. The best case scenario is that we get E2EE channels that behave just like normal channels on the client side, completely transparently to the user, and that no regular functionality is lost in the process. For example, on Matrix, you cannot search messages in E2EE channels, which I think is unacceptable; but Signal seems to be able to do it just fine, so not all hope is lost. Importantly, it should be transparent to both the regular user and instance admins, and moderation capabilities need to be taken into account. Additionally, federation brings its own set of issues, so we should be very careful to think about the typical use case in a federated network. There are a few very important key aspects of E2EE that we must consider.

• [How does it affect performance?](#how-does-it-affect-performance)
• [Where/How do we store messages and attachments, and what about chat history?](#where-how-do-we-store-messages-and-attachments-and-what-about-chat-history)
• [What exactly should be encrypted in E2EE channels?](#what-exactly-should-be-encrypted-in-e2ee-channels)
• [What are the implications for instance-level moderation?](#what-are-the-implications-for-instance-level-moderation)

How does it affect performance?

The most crucial restriction of E2EE channels is that they do not scale as well as regular channels. In a naive implementation, a user has to send a message to every other user, which means O(n²) growth and a serious toll on the server's bandwidth. Luckily, the MLS protocol seems to reduce that to O(log n) for most operations (at least from my understanding), which is much better. Some Matrix developers have made a rough comparison between MLS and olm/megolm protocols, which is very useful to get a grasp of what is acceptable with MLS, with the following logarithmic chart: image

https://gitlab.matrix.org/uhoreg/mls-comparison Shared by @ChrisGPT#5729 in #e2ee

There are some details about these tests worth reading in the Readme. That being said, according to the chart, MLS operations other than the creation of a new group from scratch seem to fit squarely below 300ms for up to a group size of 2000: image The creation of a group with a size that large is bound to be extremely rare, so I think it is fine for it to take almost 10 seconds. Now one important question is, is the group size in terms of users or devices? Given how E2EE works (a bunch of public/private key pairs, one associated with the user's identity, the other with the user's device, etc.), I suspect it is in terms of devices, which begs the question of how multiple devices are handled in E2EE channels. The way I picture this, users already have a limit for how many simultaneous device connections they can have. Let's say it's 5. In that case, then we can have 5 keys per active user-device session, which would bring down the acceptable group size limit to 400 users, which is still a very high limit. If some technical aspect makes this kind of active session rolling of keys infeasible, or if it's not necessary for some other reason, please let me know. At that size, you could potentially have entire small private communities use exclusively E2EE channels, but that is without taking into account the multitudes of UX considerations that are specific to Fluxer. So, arranged from easiest to most difficult, the scope of E2EE can be laid out as follows:

1. DMs (conversation between two people; pretty straightforward)
2. Group chats (conversation between more than two people, with a size limit; feasible)
3. "Secret channels" in communities (group chats with extra steps, but inside a community; more complicated due to roles and other community-specific features)
4. Entire private communities (very unlikely)

>

The future looks bright... :D

Where/How do we store messages and attachments, and what about chat history?

Messages

In Signal, if I am not mistaken, messages are not stored indefinitely on the cloud, they are gone forever from their servers as soon as it reaches its destination. That is unless you use its opt-in encrypted cloud message backup feature, which is free for all message content and 45 days of media, but paid for more media storage up to 100 GB. In the case of Fluxer, due to the difference in expectations and E2EE not being the main point of the platform, I think it makes sense to have completely free encrypted message backups (that is, just the message content, not the attachments which are a separate problem) for E2EE channels, either as an opt-out feature or a choice to make during onboarding on first login. I was originally not considering message backups, because the most secure data is data that doesn't exist, but I think I underestimated the security encrypted backups (standard encryption algorithms like AES are extremely solid), and I mean, if Signal does it then we might as well. This brings the following question: how do we structure those backups for DMs and group chats? In this case we have to account for federation as well. There are several possibilities:

1. Backups are stored per user. This would mean duplicating messages twice for every DM channel, as Alice would store a backup of her DM channel with Bob on her own instance, and Bob would do the same on his instance. For group chats of N users, it would mean duplicating messages N times. While text content generally doesn't take up a lot of storage, this multiplication factor of strictly more than 2 is not ideal (though a fast compression algorithm like LZ4 could be used to reduce the issue).
2. Backups are stored per channel. This would mean no message duplication, but backups would be shared between multiple users. This potentially risks exposing metadata and is therefore less secure.
3. Backups are stored per user and only store the user's own messages. This would mean no message duplication, and a greater respect of the ownership model under federation. From Lilith:

I think our current plan is for each person's E2EE content to be backed up to their home instance as well as having a local copy. If Alice and Bob are dming, Alice's home instance saves an encrypted copy of Alice's messages and Bob's message signing keys, then each can request the contents from each other and verify that it's still the original message. Alice's phone would also have a local copy of all messages from Bob and Alice, and the keys.

To that, I raise the following point: my idea of "message backup" is that if Alice wants her messages backed up on her own instance, then she should also be able to get Bob's previous messages from the cloud too. But in this situation, it seems like if Bob has opted out of that, then in the event that Alice gets her device broken, she will lose all of Bob's previous messages even though she opted for cloud message backups. Therefore, I think it would be reasonable that if Alice has cloud message backups enabled, Bob's instance stores a message backup of Bob's messages to Alice, regardless of whether Bob uses cloud message backups. image For users who would disable encrypted cloud message backups, all of the user's messages have to be stored indefinitely mainly on their device. So in the event that they get a new device, a local transfer of messages from an old device to the new one will need to happen to get the old content back. This can happen in a P2P communication as long as the two devices are verified. Previously acquired chat history would remain unavailable on a device as long as it stays unverified, in which case the client can simply display a warning to inform the user that chat history is unavailable due to the device being unverified. This fixes the biggest UX problem with Matrix, which instead shows a bunch of [ Unable to decrypt message ]. This also brings arguably the most important restriction of E2EE: a new user joining an E2EE channel does not have immediate access to the previous history of the chat, something which users typically expect on a platform like Fluxer. However, I've heard that Simplex has a feature where one of the other users in the chat can automatically give the last 100 messages in the channel to a joining user. So in a utopic scenario, I think we could have a feature where a new user gathers up the entire chat history from the other users' locally available decrypted messages; but that raises questions about whether the network bandwidth required is feasible for Fluxer's servers. At the very least, getting the last 100 messages is a good compromise. Ultimately, it is important for the UX to make it clear that retrieving the entire chat history prior to joining is impossible in an E2EE channel.

• For DMs, this is straightforward, because no new users join the chat, there's always only two people.
• For group chats and secret channels, previous chat history will noticeably be unavailable, so the UI will need to have a warning, a short disclaimer, or some kind of easily interpretable sign/icon somewhere, showing that the channel is E2EE and therefore past chat history is unavailable.

Attachments

I'd like to think of attachments as a separate problem. The huge difference between typical message content and attachments is that attachments are big. They take up a lot of storage. This is actually one of the main complaints I hear about WhatsApp: compared to other chat apps like Instagram or Discord, WhatsApp stores received attachments indefinitely on the user's device, which takes up space, and users end up wondering why WhatsApp takes so much space on their phone, when in reality it's all the images they've received. This is made worse by the AI bubble which has significantly increased the price of RAM and storage for the average consumer. Therefore, I think it is in Fluxer's best interest to keep attachments stored on their cloud servers for the most part. It relaxes the user's devices as they don't need to permanently store all the attachments they've ever received and can fetch them back only when needed, so long as the file has not expired (since attachments have an expiration date on Fluxer). It also continues to contribute to Fluxer's financial incentive — one could imagine a premium feature to expand or completely remove attachment expiration dates. But I also think that whether Fluxer indefinitely stores the attachments it has received on the user's device should be left as a choice to the user. It could even be a per-community toggle. For example, I would personally let Fluxer keep all my attachments on my devices for all my DMs and the communities where I'm the most active, because I believe I have enough storage for that in particular. The question that I am now left with is, what should the default behavior be? Indefinitely store attachments for DMs but not for communities is where I'm at right now, but I'd love to hear anyone's thoughts on this. Finally, attachments sent in private channels should be encrypted at rest with something like AES. The encryption key should exist solely within the message(s) containing that attachment, and that key can become a CDN URL parameter when looking at that attachment from anywhere, whether it's inside the official app or from the browser. This way, it helps preserve all of the features related to attachments: seeing them inside the app, opening them in the browser, and forwarding messages from a channel to any other.

What exactly should be encrypted in E2EE channels?

The most obvious part of the channel to encrypt is of course the message content. But what do we do about the message metadata (who sent it, which instance does it come from, when was it sent, does it have attachments...)? And what about the channel's member list? @Lilith#1252 (from Fluxer's Trust & Safety Staff), invested in discussions about the practical implementation of federation and E2EE channels in Fluxer, said:

Whatever protocol is used, at the very least the following information will be shared with your home instance: a. the users in the dms / gdms and their home instances and the relationships between users (necessary for privacy settings) b. the fact that messages have been sent by specific home instances (however it would be semi trivial to transform that into knowing who is sending messages when)

As well as:

Re: Metadata encryption, I don't think we plan to do too much of it. We actually do want instances to have some knowledge of who you are messaging for safety purposes. Any metadata encryption would be around message content metadata rather than go for zero knowledge entirely If for example, we have knowledge that certain accounts are spambots or people who sending CSAM to users for shock content, we want to be able to preemptively block them from reaching our users > Why not use client-side blocklists [...] ? Two reasons:

1. We would require clients to update that list constantly - which really doesn't work at scale. Users would most likely be left unprotected against the newest accounts.
2. As we think about scale (especially in federation) - that client side list can balloon to 10s of millions of accounts. While storage of that is one thing to consider, that does also mean that on every new dm, a client would have to perform a lookup against that large list.

When we look at federation, we can assume new instances and accounts on said instances will be popping up constantly. The first wave to hit the blocklist will be individual accounts, and then potentially entire instances. Generally on centralized platforms, we expect a the real to fake user ratio to be massively weighted on the fake side of things. Centralized platforms have the privilege of removing those accounts entirely. Federated networks do not. As such, if the network consists of say 10m real good users, the number of fake users over the course of a few years can easily scale to the hundreds of millions as accounts get blocked. I am not in favor of building a e2ee solution that works for when the network is 250k users but is very private, only to rip that out when we reach 2 million and say it has to be less private. I would rather have privacy expectations set properly at the start and maintained consistently as we grow (or become more private if we think possible)

The important takeaway I get from this, is that we need to make sure that whatever we wish to encrypt in terms of channel or message metadata doesn't make it more difficult or impossible for instances to do moderation at scale. The instance needs to be able to refuse any traffic coming from a user they blocked, therefore – for example – the metadata of which account (+instance) the message comes from needs to be exposed to the receiving instance. This means Signal's Sealed Sender technology (or anything similar) cannot be used, and instance admins have to know at the very least that you specifically interact with their instance. (Unless someone finds a way to create an anonymous blocklist. Maybe use naively hashed account IDs? Hmmm...) With that said, here is the metadata I can think of:

• sender (has to be unencrypted)
• receiver
• timestamp
• edited timestamp
• message reference (replying to another message)
• reactions

Receiver

Intuitively, you'd think that the receiver would have to remain unencrypted so that the server knows where they should send the sender's message. However, I have found a presentation from NDSS talking about "Improving Signal's Sealed Sender", proposing a mailbox system that would provide two-way privacy. We could potentially explore using this to have a Sealed Receiver kind of system instead. As far as I can tell, knowing the receiver is not necessary for instance-level moderation purposes, so that is not off the table.

Timestamp

Intuitively, the timestamp of a message corresponds to the moment it reaches the server. If we imagine that it arrives in some temporary mailbox, the question of whether we encrypt the timestamp seems valid to ask. If the timestamp is necessary to establish message order, then it would have to stay unencrypted. If not, the question is whether it is useful to encrypt it at all. If the server keeps a copy of encrypted messages from DM channels, then it might become a vector of statistical attack, but if it doesn't, it seems to me that the impact might be small enough to not care about it. (This is really outside my area of expertise though, and I have no data to favor either side of this consideration.)

Edited timestamp, message reference, reactions...

The rest of the message metadata can be considered part of the message content, as it is not relevant to the receiving instance in any way.

What are the implications for instance-level moderation?

Even in E2EE channels, we want users to be able to report messages to instance admins. When a user reports a message, the client has to send the message it has decrypted to the instance admins. The problem with this is that it opens the door for a malicious client or user to report fake messages to the instance admin. To prevent that, we can enforce that the official client needs to cryptographically sign every message they send before encrypting it, and reject any message they receive that doesn't have a valid signature, and consider clients that do not do that to be insecure. (Indeed, the client has to be the one to make this verification; the server cannot because the signed message would be encrypted.) The receiving client could then notify the server of that rejection so that the sending client can display that the message failed to send. As long as the process of signing messages, encrypting them, and sending them securely is all transparent to the lambda user, this should result in unsigned messages being treated as failures in the ecosystem, and therefore stop being a problem. The worst case scenario that isn't straight up device and account stolen, would be that one of the accounts gets hacked somehow but the device's private keys are still intact. In that case, the hacker can send unsigned or invalidly signed messages in the channel, and those would be ignored or would fail to send. But to make this stronger, we could also require the encrypted message packets to be cryptographically signed as well, so that the server itself can check that the message was really sent by the user. One thing to note though, is that if the client is responsible for ignoring the unsigned message due to the message content being encrypted, then a message could get refused a very long time after it has actually been sent while the receiver was inactive, remaining in a mailbox until the receiver's client becomes active. Intuitively speaking, this contrived scenario where people might send unsigned messages on purpose to game the report system shouldn't happen often (if at all) supposing everything I talked about is already in place, so that edge-case should be acceptable in context.

Notes (optional)

Let me know if I missed something or if you have things that could make this document better.