E2EE Design Plan

[Speykious]

Problem

This discussion thread is inspired by #703.

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).

Warning

This is not an official Fluxer discussion.

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 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?
• Where/How do we store messages and attachments, and what about chat history?
• What exactly should be encrypted in E2EE channels?
• 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:

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:

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)

Note

I've been informed that there is a whitepaper on encrypted collaboration spaces. Looking at their performance numbers, it would suggest that E2EE for large communities might actually be possible in the future! 👀

Some concrete runtimes from our GPU system are provided as well in Table 4.

Workload	Changes	Prove time (s)	Cycles	Per change (ms)
table	100	5.88	4.4M	59.39
table	1000	59.41	45.1M	59.47
list	100	10.30	7.7M	104.00
list	1000	103.61	80.1M	103.71

Table 4: Fast-forward proof time, total RISC-V cycles, and per-change time for batches of table and list operations over a pre-populated 100K-node tree, measured on a single NVIDIA RTX 5070 Ti 16GB. The table workload uses a simple 3-column schema; the list workload exercises the _lists double-linked-list machinery. Throughput is approximately 0.75 MHz across all four batches.

The size of the fast-forward proof is 272 KB, regardless of the number of changes, and the RISC Zero toolkit includes an optional Groth16 compression step; it can compress a proof to 256 bytes in 5.81s (on our GPU).

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.

   

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.

Caution

A very common misconception that comes up a lot in the #e2ee channel is that people think it means we want the server to be able to decrypt messages. That is not the case. Users participating in an E2EE channel have access to the decrypted message content, so they should send that decrypted message content. The instance owner as a third-party should not be able to decrypt any messages sent between the participating users. Imagine if you were sending a screenshot, but more automated, reliable, and compatible with Fluxer's current message report system.

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.

Checks

• I searched for existing discussions and didn't find a duplicate.

[toihr]

Super interesting writeup here, I learned quite a bit more about e2ee in it.

One question that I have been having through this disccussion and #335 is that this seems like it would add a massive amount of complexity the development. As e2ee and specifically federated e2ee is fundamentally hard as far as i understand.

What is the estimated impact on development speed and well development complexity?

[Speykious]

That is an extremely broad question, but I guess I could partially answer it.

I think E2EE channels, especially DM channels, largely won't affect the development speed of future feature implementations too much, as long as those features don't include the server being able to know the content of messages. Say for example Fluxer's markdown implementation adds new features, then E2EE isn't gonna slow anything down because it only applies once the messages have been decrypted.

It would definitely increase development complexity though, since the limitations of E2EE channels (unscalability of the algorithm after a few hundreds of members) have to be taken into account when developing features. For example, if you had secret channels in communities, how would permissions be affected? What if you give to a role the permission to see that channel, but that role has more members than what the secret channel can accept? In this specific case you have to inform the user that that's not possible because the role has too many members. Now what if you do the same thing with a role that has just enough members to receive that permission, but then you add a member to that role? That's also not possible. So it means that to implement secret channels in communities, you'd have to, at minimum, add a piece of code in the "add role" and "update permissions" functionalities of the application to have additional non-happy paths.

But, it's also important to highlight the fact that E2EE is not the focus of Fluxer in the first place. Most features pertain not to privacy of small groups, but to public communities: stuff like slash commands, forums, creator monetization etc. are pretty much completely separate concerns, and they likely won't have anything to do with E2EE channels inherently. (Though I may be wrong on that.)

As for an estimation, well... I've never been able to estimate something I've never developed before, so someone else might be able to answer that... But I can't x')

[toihr]

Thanks for the broad answer to a broad question. :D. What one of my understandings is, is that e2ee in a federated environment is fundamentally hard, as it then becomes a question of federated identity, which is equally hard.

[skidd-level-100]

Thanks for this awesome writeup, it is way better than what I would have written up!

[Speykious]

I've been informed that there is a whitepaper on encrypted collaboration spaces. Looking at their performance numbers, it would suggest that E2EE for large communities might actually be possible in the future! 👀

Edited the post with this information

[toihr]

damn thats realy cutting edge

[ImDaBigBoss]

Perhaps I am missing something, but I have a question about how encryption key management would work in practice. To keep things simple, let's ignore group chats and focus on two users exchanging messages.

Fluxer is at least partly intended to work as a web application, so users don't necessarily have to install anything locally. But browsers can't really be relied on as a secure or permanent place to store data. Ignoring forward secrecy for the moment, this seems to create a problem: regardless of whether messages are encrypted asymmetrically or symmetrically, the necessary keys must exist somewhere so that messages can be decrypted later.

With asymmetric encryption, users need access to their private keys. With symmetric encryption, they need access to the shared key. If browser storage is cleared or a device is lost, those keys would disappear unless they have been backed up somewhere. This is where I start to get confused.

I know it has been suggested that when a new device is added, it can obtain the required encryption material from an existing trusted device. However, what happens if a user loses all of their devices or clears all local data? Is the expectation simply that they lose access to their messages, or do server instances retain enough information to allow recovery of the decryption keys?

If server instances do retain recovery information, that information would obviously need to be encrypted before being uploaded. However, at that point it feels as though the federation is collectively storing all of the information required to recover access to the user's messages, just in a more complicated form. How is that fundamentally different from storing an encrypted zip file of the user's messages in cloud storage?

Related to that, how would the master key be generated in the first place? If a user authenticates using a WebAuthn passkey or another identity provider, those mechanisms prove identity, but I don't see how they could be used to make some sort of "master key".

[Speykious]

I know it has been suggested that when a new device is added, it can obtain the required encryption material from an existing trusted device. However, what happens if a user loses all of their devices or clears all local data? Is the expectation simply that they lose access to their messages, or do server instances retain enough information to allow recovery of the decryption keys?

If server instances do retain recovery information, that information would obviously need to be encrypted before being uploaded. However, at that point it feels as though the federation is collectively storing all of the information required to recover access to the user's messages, just in a more complicated form. How is that fundamentally different from storing an encrypted zip file of the user's messages in cloud storage?

Not sure if I was clear about that, but the section on where messages should be stored mentions encrypted cloud message backups. That is, the user gets to choose whether to backup their messages to their instance or not. If they choose to not backup their messages, then they have more security, but they risk losing access to all their DMs if they lose all of their devices. You can indeed think of these cloud backups as essentially encrypted zip files, yes. It would be encrypted with the user's password, or with a key stored encrypted in the user's profile that can be retrieved on login after the device has been verified.

As a reminder, the goal of E2EE is to encrypt communications in transit and this it doesn't dictate anything about storage, hence why we decided to be flexible on where messages are stored in our discussions and why I specified cloud message backups as a default opt-out in this design plan to maximize positive UX.

[Sir-Walrus]

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

That sounds quite complicated, and also likely vulnerable to context switching attacks (for example moving "so beautiful 💥💥" from a convo about new years fireworks to a convo about 9/11). (Such attacks can be prevented, but only by adding even more complexity.)

Instead, I propose a slightly different solution: When a user reports a message, the client sends the message key to the instance admin.

(But I do agree with client signing the ciphertext, and server verifying that signature.)

[Speykious]

the client sends the message key to the instance admin.

From my understanding, that runs the risk of exposing other messages in the channel, due to next keys being generated based on the previous ones. Though it's been a while since I looked at this stuff, so I don't exactly remember how good the post-compromise security is, so I'll have to check.

That being said, message signing itself might be a complicated piece of math, but choosing what we cryptographically sign isn't. Choosing which metadata gets signed along the message is just a matter of changing the content that gets signed, nothing more. Additionally, message signing is already a crucial part of Polyproto, which is going to be used for Fluxer's federation.

[Sir-Walrus]

If the Polyproto folks haven't already taken that into consideration, I'd expect adding a quick sha256 between the generated key and the message key would fix it.

But I don't have a complete understanding of the proposed protocol either, I'm just going by this thread.

Cryptography is hard. Key management is hard.