I wonder if you folks have noticed the IETF MLS WG? They are trying to distil a common protocol from all the signal/wire/matrix/whatsApp/hello mess that we currently have.

They already published two drafts, one about the messaging protocol another about the architecture of such a system.

For me the interesting bit is that group crypto is not downgraded security-wise (classic signal/double ratchet creates indivdual sender keys for groups, 1:1 communication doesn't and still has future secrecy - there recently was a paper about it which I can't find right now). Their stated goal is to have future secrecy also in groups and to make 1:1 communication a special case of groups.

The novelity here is what poeple are calling Asynchronous Ratcheting Tree (ART).

Stoked to see where this goes!

#cryptography #messaging

there recently was a paper about it which I can't find right now

I meant this one: More is Less: On the End-to-End Security of Group Chats in Signal, WhatsApp, and Threema

Here is the abstract:

Abstract—Secure instant messaging is utilized in two variants:
one-to-one communication and group communication. While
the first variant has received much attention lately (Frosch
et al., EuroS&P16; Cohn-Gordon et al., EuroS&P17; Kobeissi
et al., EuroS&P17), little is known about the cryptographic
mechanisms and security guarantees of secure group communication
in instant messaging.
To approach an investigation of group instant messaging
protocols, we first provide a comprehensive and realistic security
model. This model combines security and reliability goals
from various related literature to capture relevant properties
for communication in dynamic groups. Thereby the definitions
consider their satisfiability with respect to the instant delivery
of messages. To show its applicability, we analyze three widely
used real-world protocols: Signal, WhatsApp, and Threema.
Since these protocols and their implementations are mostly
undocumented for the public and two out of three applications
among them are closed source, we describe the group protocols
employed in Signal, WhatsApp, and Threema. By applying
our model, we reveal several shortcomings with respect to
the security definition. Therefore we propose generic countermeasures
to enhance the protocols regarding the required
security and reliability goals. Our systematic analysis reveals
that (1) the communications’ integrity – represented by the
integrity of all exchanged messages – and (2) the groups’
closeness – represented by the members’ ability of managing
the group – are not end-to-end protected.
We additionally show that strong security properties, such
as Future Secrecy which is a core part of the one-to-one
communication in the Signal protocol, do not hold for its group
communication.

a rather random (interesting to me) collection of quotes that interested me from a thread started by Matthew Hodgson (matrix.org) about mls in decent environments:

Since IETF101 I've been trying to work out how well MLS could be applied
in fully decentralised environments which lack any single controlling
server, as it seems that the current proposal effectively rules this out
due to the state sequencing requirements (thanks to Ben Schwartz for
spelling this out to me after the BOF!).

to:dos: link to the the state sequencing requirements from the draft.

So, how can we support something like this in MLS?

There seem to be two main obstacles: 1) the requirement for strict
sequencing of state changes, 2) the lack of keyshare semantics to
recover from the missing key data which is inevitable in an eventually
consistent view of a room. I'm going to ignore the second for now as it
can be fixed out of band ...

However, for state sequencing: Am I right in saying that a race between
B and C joining a group can cause one client to see a DH binary tree
with frontier (AB, C) versus (AC, B), and thus have inconsistent root
group keys - messages encrypted during the partition are going to
inevitably be undecryptable by the other side?

Is there a way where MLS could allow a group to recover from a partition
like this by (partially?) rebalancing the DH binary tree into a
canonical form once the partition heals? Thus if a partition was
detected at the application layer (in Matrix's case, we'd do this by
noting that the B-join and C-join events share the same A-join parent),
the servers participating in the room would rebalance (AB,C) and (AC,B)
to both be (AB,C) and then the conversation could proceed as normal.
One might be able to avoid rebalancing the whole tree to minimise CPU
impact (although in practice healing these races are fairly rare edge
cases). Obviously this assumes that one has a way to request keys to
recover the messages lost when the groups were out of sync.

i'm not sure yet how this balancing would work in a server-less setting (with matrix home servers still beeing where the trust is at, althought there was talk about one home server per user in the past i'm not sure where that went).

If this mechanism makes sense, it seems that it could provide a way to
eliminate the "Sequencing of State Changes" requirement entirely from
MLS - or at least provide an alternative for folks where either
server-side or client-side strict sequencing isn't an option, and so
solve the general 'how to handle races' problem mentioned at the BOF
(whilst also necessitating an interoperable solution to history/key
sharing, similar to the earlier “Use cases for avoiding forward secrecy”
thread)

this reply to the OP above does a nice job of explaining the problem matthew pointed out:

The problem is from the ratcheting tree construction: two updates which
both want to change a particular intermediate node cannot both be
applied at the same time.

and then some..!

Not the problem

One thing I should highlight up front is that this does not necessarily
prevent decrypting messages, only applying key updates. Specifically, if
A receives either C's or D's update they can apply it and compute the
resulting root key, then decrypt the message. Of course, if the update
is one that should have bounced, then they might have to "un-apply" it.
Moreover, if A wants to send their own update, they need to pick one of
y' and y'' to base it on. This is something I don't think we've reasoned
about in detail yet.
For other reasons due to malicious group members, I think we're likely
to come up with a system where each participant has various "proposed"
updates sitting around, and then only confirms them after receiving
some other message. This sort of algorithm should also help here,
because I think it will also need the ability to unwind or not apply a
potential update.
Another thing is having the server do some clever re-ordering. The
challenge is that in the end, by construction the correct value of the
intermediate node should only be computable by its children, so there's
only so much the server can do.
For the same reason, I'm not sure the server can unilaterally rebalance
the tree; I think it would need some help from one of the participants.
I'd have to think more carefully about the precise keys which it would
need to do so, though. In particular, if you are more worried about re-
ordering join events than re-ordering key updates, there might be some
specialised tricks that work.

Things we tried that don't yet work

...
Another thing is having the server do some clever re-ordering. The
challenge is that in the end, by construction the correct value of the
intermediate node should only be computable by its children, so there's
only so much the server can do.
For the same reason, I'm not sure the server can unilaterally rebalance
the tree; I think it would need some help from one of the participants.
I'd have to think more carefully about the precise keys which it would
need to do so, though. In particular, if you are more worried about re-
ordering join events than re-ordering key updates, there might be some
specialised tricks that work.

To which this question is raised:

Is it possible to have a common tie-breaker process and force the
loser to rebase?
That is, if the change c->c' wins, then d needs to apply their d->d'
change again on top of that change (or move to d'').

.. and responded to by katriel next:

Yes, I think so. Another one would be "the person who has least recently done an update wins ties", which would help with starvation issues. As you point out, the downside is that endpoints might have to keep quite a lot of potential state around in case an old message comes through and requires a large rebase.

I was wondering whether you could have a cap like "never rebase more than five updates ago" or something to prevent that case, but the challenge there is that without a centralised server you don't have a consistent view of how many updates have actually happened. The particularly problematic case is when e.g. A and B do a whole bunch of updates, and then C comes in and preempts them.

Having a centralised sequencing server makes this whole problem go away, sadly.

Still haven't looked into TreeKEM yet but was pleasantly surprised to see this #golang project on the mailing list:

JFYI, I tried to prototype the current draft:
https://github.com/r2ishiguro/mls.
It's just to understand the proposal better for myself.
If there're other implementations please let me know.
Ryuji

Love this whole thread. Pinning to come back to later.

#dan-notetoself