Re: [MLS] Stupidest possible message protection

[Raphael Robert <[e-mail]>]

I agree with Richard that letting clients choose is a good idea. I think that for the sake of simplicity clients should choose whether to encrypt HS messages or not right at group creation (and prevent downgrade attacks by committing to extra state in the group state, just as mentioned). We can always explore later how we would handle “HS message protection agility”, if this turns out to be necessary.

The tree
————

The parts of the HS messages that would have to be in cleartext are mentioned on Richard’s slides [1] on the last slide ("Expose information for server assist”). The exposed bits are marked in orange.
This exposes the public DH keys of the tree to the server, as well as the structure of the tree. It allows the server to cache that data and make it available to new clients/members, so that existing clients/members don’t have to upload that data again. New clients/members can selectively download parts of the tree or all of it.

Right now I can think of 3 problems that should be further assessed:

1) How sensitive is a tree with only public keys? Does it leak more than the obvious statistical metadata (such as: group size, frequency of updates/add/removes, etc.)? If the leaf keys contain the same DH public key as UserInitKeys that are published on the server (because the clients did not yet perform an update), those leaves could be correlated with an identity of the members (see also further below in the roster section).

2) What if the server is not honest and modifies the tree? The remedy that has been proposed is to use an additional Merkle tree to verify the integrity of the ratcheting tree. The root of the Merkle tree would be transmitted as an encrypted commit hash in a Welcome HS (see penultimate slide of [1]).

3) What if the server is honest, but cannot distinguish between valid and invalid HS messages (and therefore caches the wrong values)? This problem could theoretically be solved with ZK proofs (mentioned in a different thread on the ML), but the preliminary conclusion is that ZK proofs would most likely be too expensive. Instead, the server could do versioning and discard version based on a sufficient number of NACKs received from different clients. Potentially clients could also request a specific version that is identified by the commit hash.
Note that this is also a problem for clients even when fully encrypted HS messages are used. Clients cannot always know if a HS message is valid or not (see relevant thread on the ML).

The roster
—————

The roster is unambiguously considered sensitive data, as it is essentially the members list of a group. The DS is the server part tasked with delivering messages, therefore the DS needs some notion of where to deliver messages to as they come in from clients. A few possibilities exist:

1) The roster is public anyway: In that case no special protection is needed on the HS level.

2) The recipient list is sent to the DS in real-time with every message that is sent out by a client. In that case the roster is only temporarily visible to the DS for the time of the fanout. This is probably similar to observable metadata in terms of scope, as long as the DS doesn’t not persist the recipient list anywhere.
2a) Similar to 2), but the participant list is stored on the DS encrypted with a key that is only held by clients and shared with the server every time a message is sent (and the server forgets the key immediately after the fan-out). This solutions does not have any FS as such, unless we can come up with more fancy schemes such as proxy re-encryption (see separate thread on the ML).

3) A fancy and privacy-preserving pubsub scheme? Suggestions are welcome, but keep in mind that most messengers use push notifications for smartphones (Apple push notifications and Google FCM) that require messages to be actively pushed to them, rather than listening for messages that fly by.

If the DS doe not have any knowledge of the roster whatsoever, we probably have to think about DoS attacks against a group. For example, an evicted member could still spam the group with (invalid) messages, because in a naive implementation the evicted member just needs to know the group ID to ask the server to fan out messages.
There might be privacy-preserving ways to prove group membership, such as re-using the root key pair of the ratcheting tree as a signing key pair. The server could verify those signatures and come to the conclusion the signing member must know the current private root key, as opposed to an evicted member. Further (and more formal) scrutiny would be good here.

In a nutshell, these are the ideas I’ve heard and discussed with folks so far. If I missed something or if you think there are alternative ways to better solve these problems, please chime in here or on the other relevant threads of the ML. 

Raphael


[1] https://datatracker.ietf.org/meeting/103/materials/slides-103-mls-sessa-stuff-00

> On 3 Dec 2018, at 09:28, Richard Barnes <[e-mail]> wrote:
> 
> 
> 
> On Mon, Dec 3, 2018 at 3:01 AM Karthikeyan Bhargavan <[e-mail] <mailto:[e-mail]>> wrote:
> > One way to try to split this baby would be to try to evaluate what information the server needs in order to provide its assistance, and leave that unencrypted.  This solution would of course require that we convince ourselves that the unencrypted bits are actually not sensitive, and would entail a fair bit of complexity in the encryption system.
> 
> Let me poke a bit more at this option. What minimal information do you think the server needs in order to provide its assistance?
> 
> If you take a look at Raphael's slides from the Bangkok meeting, there are a couple of different types of assistance the server might provide.  Most of these revolve around the linear-size pieces of group state: The (public keys in the) tree and the roster.  The server could cache a copy of the tree so that clients could download slices of it as needed.  Clients would have to either trust the server to do this or arrange the hash in the GroupState so that the slices could be verified.  That's where a lot of the complexity comes from.
> 
> Arguably, there's no harm in exposing the tree, since it should just be all random key material.  (Except in the case where you put a DH key from a UserInitKey at a leaf, in which case it can be used to correlate.)  Exposing the roster is obviously problematic.  Maybe Raphael has some ideas here.
> 
> --Richard
> 
> [1] https://datatracker.ietf.org/meeting/103/materials/slides-103-mls-sessa-efficiency-00 <https://datatracker.ietf.org/meeting/103/materials/slides-103-mls-sessa-efficiency-00>
> 
>  
> 
> -Karthik
> 
> > 
> > Another, simpler, approach we could take is to punt the decision to the application.  We would define in the document two options:
> > 
> > 1. Send Handshake messages in the clear
> > 2. Send Handshake messages encrypted as Application messages
> > 
> > (And specify details like how you do Welcome+Add, how you disambiguate Handshake from other Application messages.)  But we would not specify which of those paths a given application would do.
> > 
> > What do folks think about that idea?  Personally, I find it kind of appealing in its simplicity, though I acknowledge it adds another variable for interop testing / interop failure.  And if you want to make an MLS API, it's another switch to support.
> > 
> > Cheers,
> > --RIchard
> > 
> > 
> > _______________________________________________
> > MLS mailing list
> > [e-mail] <mailto:[e-mail]>
> > https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> 
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls