Leverage "sealed sender" to encrypt message sender

[nrktkt]

After inquiring on #matrix, @uhoreg suggested I create an issue here so that there's a record of this topic.

I'm interested in the potential to reduce the amount of metadata a server is exposed to for messages in encrypted rooms. The folks over at signal had a clever (as usual) idea they're calling sealed sender. It seems like this could be pretty easily applied to matrix.

The idea has two parts

1. a sender cert issued by the sending user's home server
2. a recipient token known only to participants of the room (this is a symmetric secret shared with the room host server)

The flow might go basically like

1. sender signs each message with the sender cert and encrypts it for the recipient
2. sender sends the message with the recipient token and no sender metadata (my matrix knowledge is weak here, would the sender send to their home server, or the room home server?)
3. recipient's server verifies the recipient token
4. recipient requests the sender cert from the sender home server and validates the message

IMO decreasing the amount of metadata being passed around to different servers would be a huge step forward in getting support for federation.

EDIT:
I've thought more about this and some initial issues became very obvious.
For starters a per-room secret is not going to work. That would be literally giving the server a way to see who is in a room. Two solutions came to mind, the former is what I think is better, but I'm including the other for comparison.

Recipient key approach: similar to signal's delivery token, but with asymmetric tokens.
Each user generates an a key pair.
The user shares the verification key with their home server.
The user shares the signing key with each group they're a member of. New users to those groups can be given all the members keys by the member who invites them.
Abusive users can be blocked by rotating the key pair and not sharing the new key with the abusing user. This prevents the abusing user from using sealed sender so the host server can rate limit or block them.

Group-recipient key approach: similar to above, but instead of one recipient key per user there's one key per user per group. Each user would rotate their key for a group when a user leaves the group.
The upside of this approach is that no user can contact another using sealed sender outside of an existing group, so a sender could be blocked from using sealed sender one-on-one, but still allowed in a larger group.
The downside is that even though a server can't identify the members of a group from just the recipient id and key, a less-than-privacy-respecting server might be able to de-anonymize users using fingerprinting, etc and would then be able to identify group members based on sender fingerprint and recipient key (eg. A is talking to B#group1 and C is talking to B#group1, therefore A and C, are talking to each other with B in #group1).

[dkasak]

Unless I'm missing something, I don't think your recipient key approach would work on Matrix since a homeserver needs to know which room you are sending to be able to maintain server-side room history, for federation (because a server is not always delivering messages directly to clients, but also to other servers) and probably other things.

IIRC, Signal has no server-side concept of rooms/groups so the server has the opportunity to act as a giant mixer, with any given incoming message being potentially intended for any recipient.

In any case, it doesn't look easy. It probably requires trying to chip at the problem bit by bit, in the hope that something like this could eventually be achieved. A large obstacle is that state events in Matrix are currently not encrypted at all.

[nrktkt]

I was just thinking that server-side room history would be disabled for sealed sender messages and the server would relay messages to the client to resolve.

Maybe there could be a technique where the client maintains server state and then uploads it (encrypted) to the server for other clients to download.

Can you talk more (or link me) about state events being unencrypted vs the parts of messages that are encrypted? I don't have a deep knowledge on the protocol, especially this part.

[uhoreg]

Some thoughts:

• when a message is sent to other homeservers, they need some sort of proof that it was sent by someone who is allowed to send the message. This is currently done by the sender's server signing the event, proving that it came from that server, and the other servers checking that the sender belongs to that server, and is allowed to send the event. We could loosen it slightly, by having other servers just check that the event is signed by a server that has some user in the room who is allowed to send the event, and then have clients check that the sender is actually allowed to send the event, and drop it if not. However, having the event signed by the server still leaks information about who sent the event, especially in the cases of single-user homeservers. For example, if you see an event signed by uhoreg.ca, then you will know that I sent it, even if you can't see the sender field.
• currently, the sender information is used to help determine which megolm session to decrypt with -- megolm sessions are indexed by sender key and megolm session ID. We could drop the sender info and lookup the megolm session by only the megolm session ID, though you would need to allow for having multiple megolm sessions with the same ID, and then loop over the sessions to see which one actually decrypts the message and gives us the sender. This would hide the sender. But the server would still be able to correlate the senders of messages to some degree by looking at the megolm session ID: messages with the same megolm session ID are likely from the same sender. We could drop the megolm session and just try to decrypt it with every megolm session that we have, but that would not be pleasant.
• It will probably be easier to do sealed sender when we integrate MLS, as it already defines how the sender can be encrypted, and defines how to get group secrets. So, for example, the event signing could possibly be solved by having a shared signing keypair, with the public half known by all the servers in the room. Events can be signed with the private half, so that servers know that it was sent by someone in the room, but do not know who.

[JanZerebecki]

I think Anonymous Credentials https://eprint.iacr.org/2019/1416 as used in Signal Groups can be used to authenticate messages as belonging to a room, to get to the full privacy effect you'd also need to have a mixer or something to prevent tracking of clients even on the connected to server.