I've been working on a new scheme for decentralised encrypted (group) messaging bus over at https://xn--nma.com/ unlike many other schemes, forward secrecy is not a goal: When I invite a friend to a group chat, I want them to be able to obtain historical conversation messages.
For your normal end user (at least what I think of as common: see how facebook messenger works, as well as slack, discord and even how many irc chat rooms have public logs), how is this MLS scheme useful?
Yes I'm aware of matrix. A couple of things that I don't like about the matrix protocol are: 1. identity is tied to a server and users are not free to move between servers. 2. servers are assumed to be always online and have low latency.
2. I'm not sure what gives this impression? I have a server that is very much on flaky network, and it federates just fine. The point is that servers can go online/offline without breaking anything on the whole network.
If you don't need PFS you could probably modify MLS to be a bit simpler.
Firstly, no need for sender keys. A single group key will do. When you remove someone from the group, you still do the group update and derive a new group key (unless you don't want post-compromise security either, in which case you can throw out the entire tree concept).
Now when you add someone to the group, you share with them the entire historical group transcript along with all the previous group keys.
In solution #2, when an encrypted message is received, does the receiver have to lookup the sender's specific key from a list that they maintain? In other words, does every member have a list of every other member's special group keys?
This is more or less equivalent to having a single shared group key, but there are some practical reasons why it's split out. I think one of them is that it makes symmetric key ratcheting (for the purposes of perfect forward secrecy) a little less disastrous in the case of out-of-order or failed message delivery. Not totally sure, though.
In terms of the open issue at the end, it seems like the 'obvious' solution is for (in the Zane #11 removal example) Zane #12 to then respond by promoting himself up one level in the tree and then generating new secrets for his own node and all ancestors. In this way you actively cull the blank nodes so you can't end up in the pathological situation.
Presumably this isn't done because the additional messages required to do this defeat the gains?
I don't think anyone has to update their keypairs if they get promoted. They would only get promoted if their sibling is blank. In that case, they can just take their parent's keypair and not worry about anyone else having it.
Can any of this be beaten into a way to verify group membership?
Say you want to prove you are a member of the AMA or IEEE, or Bar? Could you set up a large group for the association and their communications, and then when asked provide verifiable credentials that you are a member? Like a group membership signature?
Yes, much of the article is explaining why this is reasonable for a group of 2-5 and terrible for a group of 10,000, and ways to make this more manageable in non-obvious ways.
What are you imagining a "shared private/public key" is ? Because that's not a thing.
A private key is _private_, it doesn't mean anything to share one of those, if you're doing that it isn't a private key any more and you wasted your time.
They probably mean a single symmetric key shared between all. And private is not mean that only one person knows a thing. Quite the opposite. If the entire planet minus 1 person knows something, that's a form of private as well. Either way you're arguing semantics.
Even better, why not have a single symmetric group key that everyone uses to communicate? Assume the delivery service is perfect, so you never get dropped messages, and everyone ratchets the group key forward, thus providing perfect forward secrecy.
A question: if someone leaves the group, how do you determine the new group key?
If there is some one-way function f that determines the new group key, then the removed person can derive the new key K' = f(K), where K is the current key. That means that if they get ahold of the transcript of the group after they leave, they can decrypt everything.
So K' must be derived by some non-deterministic process. There's a group of people who need to arrive at the same value, and they need to use randomness. Whose randomness do they use? A simple answer is "the remover." That is, have the remover include a randomly generated K' in their Remove message to the rest of the group. This doesn't work though, because the removed person can still decrypt the Remove message and get K' just like everyone else.
A viable solution is to randomly generate K' and then encrypt it for everyone _except_ the removed party. But once you're here, you run into the problem of pairwise keys, and your runtime sucks.
This last step is basically where the article starts. Thank you for asking this question!
I think you missed a solution, which is a variant of #2.
To simplify things, consider a single global chat room, on an enormous server (probably in Salt Lake City), where every person on earth is connected and have a public/private key-pair, and every person on Earth can read everything anyone posts. You can post publicly ( anonymously or with a signature), or privately (pair key) to any individual on Earth. From this starting point, how do you make private group chats? (This starting point factors out a lot things we shouldn't worry about, and I think is simpler/nicer than a story about a Slack admin).
Your solution #1, pairwise encryption, clearly doesn't scale for the sender (as you point out). It is also aesthetically displeasing.
I feel like your solution #2, though, isn't what I would do, and I'm honestly surprised that's how WhatsApp, etc. works.
My first thought is that a person who wants a shared room creates a (symmetric) key K for the room, and then distributes K to all invited participants privately. To remove a user you generate a new K for the room, and send it to N-1 participants. They all agree to post using the new K (and a signature).
I don't see a performance issue with this solution. Consider that every message to the "room" causes O(N) fanout. If the rate of "normal" message addition is much less than the rate of participant addition/subtraction, well, that's performant enough. (Especially considering a new key for the room is some relatively small fixed size.)
(In a situation where you have a huge, passive audience and a single emitter, then yes my proposal will generate a lot of extra unnecessary traffic as people enter or leave. However, I'd argue that communication like this is probably better secured through more traditional centrally controlled means, e.g. a server process with ordinary user accounts that have a connection status.)
EDIT: There is a coordination problem with my solution, in that you can't guarantee members will use the new K; it might be useful to have a bot or something remind anyone who posts using the old K to use the new one instead.
Glad you asked. My solution allows for anonymous rooms, but "solution 2" does not. To be anonymous, just post ordinary text to the room using K. To be identified, post your text, your signature all encrypted with K.
Yes that's right. Normally for signatures you would do the final encryption with the receiver's public key creating the same issue as solution #1, but in this case you would use the symmetric key:
1. Hash message
2. Encrypt hash using your private key
3. Encrypt again using group's symmetric key
There's obviously good reason why symmetric keys don't work, especially in place of solution #2 - would be great to be enlightened on why by the author.
Ah, thanks. My mistake was assuming you could distribute new K as a normal message, encrypted with old K. Clearly (now) this wont work since new K will be distributed to everyone, including people who need to be omitted.
Balanced binary trees usually have some kind of rotations to maintain their properties like left-leaningness. In this application this is to be avoided in order to not not send so many messages.
I understood that all participating clients know about the structure of the tree, so could not all the clients do the rotations in this kind of mass removal without sending messages?
I mean that in the last example, the tree is not left leaning, but can be made so by promoting every Zayne to their ancestor nodes.
Good point. I don't think it'd be unreasonable to promote everyone to their parent in this example.
One thing that I left out of the post is that the MLS ratchet tree has something called a "tree hash". Every node carries a hash digest, which is the hash of its two children. The root node's hash is used to derive a bunch of group-specific values, so it's important to keep this hash up to date. If you promote every member to their parent, this would require about N log(N) total hash operations, since every path from a leaf to the root would have to have its hashes recalculated.
N log(N) hashes seems like a small price to pay for optimizing a structure that determines how many ECDH operations you end up doing. I'll ask other MLS people about this and see if I'm missing something.
45 comments
[ 3.1 ms ] story [ 115 ms ] threadFor your normal end user (at least what I think of as common: see how facebook messenger works, as well as slack, discord and even how many irc chat rooms have public logs), how is this MLS scheme useful?
2. I'm not sure what gives this impression? I have a server that is very much on flaky network, and it federates just fine. The point is that servers can go online/offline without breaking anything on the whole network.
Firstly, no need for sender keys. A single group key will do. When you remove someone from the group, you still do the group update and derive a new group key (unless you don't want post-compromise security either, in which case you can throw out the entire tree concept).
Now when you add someone to the group, you share with them the entire historical group transcript along with all the previous group keys.
Is this roughly what you're looking for?
In solution #2, when an encrypted message is received, does the receiver have to lookup the sender's specific key from a list that they maintain? In other words, does every member have a list of every other member's special group keys?
This is more or less equivalent to having a single shared group key, but there are some practical reasons why it's split out. I think one of them is that it makes symmetric key ratcheting (for the purposes of perfect forward secrecy) a little less disastrous in the case of out-of-order or failed message delivery. Not totally sure, though.
Presumably this isn't done because the additional messages required to do this defeat the gains?
I don't think anyone has to update their keypairs if they get promoted. They would only get promoted if their sibling is blank. In that case, they can just take their parent's keypair and not worry about anyone else having it.
Say you want to prove you are a member of the AMA or IEEE, or Bar? Could you set up a large group for the association and their communications, and then when asked provide verifiable credentials that you are a member? Like a group membership signature?
[0]: https://trailofbits.files.wordpress.com/2019/08/post_remove_...
[1]: https://trailofbits.files.wordpress.com/2019/08/image1-1.png
OR it is the typical knee jerk dismissal comment on HN.
The article is interesting for sure but that Rust part indeed threw me off. I've seen enough people/articles circle-jerking about Rust.
A private key is _private_, it doesn't mean anything to share one of those, if you're doing that it isn't a private key any more and you wasted your time.
A question: if someone leaves the group, how do you determine the new group key?
If there is some one-way function f that determines the new group key, then the removed person can derive the new key K' = f(K), where K is the current key. That means that if they get ahold of the transcript of the group after they leave, they can decrypt everything.
So K' must be derived by some non-deterministic process. There's a group of people who need to arrive at the same value, and they need to use randomness. Whose randomness do they use? A simple answer is "the remover." That is, have the remover include a randomly generated K' in their Remove message to the rest of the group. This doesn't work though, because the removed person can still decrypt the Remove message and get K' just like everyone else.
A viable solution is to randomly generate K' and then encrypt it for everyone _except_ the removed party. But once you're here, you run into the problem of pairwise keys, and your runtime sucks.
This last step is basically where the article starts. Thank you for asking this question!
To simplify things, consider a single global chat room, on an enormous server (probably in Salt Lake City), where every person on earth is connected and have a public/private key-pair, and every person on Earth can read everything anyone posts. You can post publicly ( anonymously or with a signature), or privately (pair key) to any individual on Earth. From this starting point, how do you make private group chats? (This starting point factors out a lot things we shouldn't worry about, and I think is simpler/nicer than a story about a Slack admin).
Your solution #1, pairwise encryption, clearly doesn't scale for the sender (as you point out). It is also aesthetically displeasing.
I feel like your solution #2, though, isn't what I would do, and I'm honestly surprised that's how WhatsApp, etc. works.
My first thought is that a person who wants a shared room creates a (symmetric) key K for the room, and then distributes K to all invited participants privately. To remove a user you generate a new K for the room, and send it to N-1 participants. They all agree to post using the new K (and a signature).
I don't see a performance issue with this solution. Consider that every message to the "room" causes O(N) fanout. If the rate of "normal" message addition is much less than the rate of participant addition/subtraction, well, that's performant enough. (Especially considering a new key for the room is some relatively small fixed size.)
(In a situation where you have a huge, passive audience and a single emitter, then yes my proposal will generate a lot of extra unnecessary traffic as people enter or leave. However, I'd argue that communication like this is probably better secured through more traditional centrally controlled means, e.g. a server process with ordinary user accounts that have a connection status.)
EDIT: There is a coordination problem with my solution, in that you can't guarantee members will use the new K; it might be useful to have a bot or something remind anyone who posts using the old K to use the new one instead.
1. Hash message
2. Encrypt hash using your private key
3. Encrypt again using group's symmetric key
There's obviously good reason why symmetric keys don't work, especially in place of solution #2 - would be great to be enlightened on why by the author.
I understood that all participating clients know about the structure of the tree, so could not all the clients do the rotations in this kind of mass removal without sending messages?
I mean that in the last example, the tree is not left leaning, but can be made so by promoting every Zayne to their ancestor nodes.
One thing that I left out of the post is that the MLS ratchet tree has something called a "tree hash". Every node carries a hash digest, which is the hash of its two children. The root node's hash is used to derive a bunch of group-specific values, so it's important to keep this hash up to date. If you promote every member to their parent, this would require about N log(N) total hash operations, since every path from a leaf to the root would have to have its hashes recalculated.
N log(N) hashes seems like a small price to pay for optimizing a structure that determines how many ECDH operations you end up doing. I'll ask other MLS people about this and see if I'm missing something.