Subject: [MLS] Stupidest possible message protection

From: Richard Barnes <[email-masked]>
Date: Sun, 2 Dec 2018 17:24:42 -0500

Hey all,

As we discussed in Bangkok, there are trade-offs between encrypting
handshake messages and enabling the delivery service to assist with
scaling.

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.

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

---

From: Watson Ladd <[email-masked]>
Date: Sun, 2 Dec 2018 14:30:50 -0800

On Sun, Dec 2, 2018 at 2:25 PM Richard Barnes <[email-masked]> wrote:
>
> Hey all,
>
> As we discussed in Bangkok, there are trade-offs between encrypting handshake messages and enabling the delivery service to assist with scaling.
>
> 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.
>
> Another, simpler, approach we could take is to punt the decision to the application.  We would define in the document two options:
>
> (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.

Doesn't the server need to agree with the client how to do this? And
what about downgrade attacks?
>
> Cheers,
> --RIchard
>
>
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Richard Barnes <[email-masked]>
Date: Sun, 2 Dec 2018 17:51:33 -0500

On Sun, Dec 2, 2018 at 17:31 Watson Ladd <[email-masked]> wrote:

> handshake messages and enabling the delivery service to assist with scaling.
> >
> Doesn't the server need to agree with the client how to do this?

The server needs to be aware of it’s going to provide any assistance, yes.
  But in principle, clients could choose to encrypt and the server would
never know.  I think the more important question is whether clients all
need to agree.

And
> what about downgrade attacks?

Seems like there are basically two choices: (1) don’t worry about it, let
the application figure it out, or (2) include the “encryptHandshake” bit in
the GroupState so that everyone agrees on it.

I think (1) is probably sufficient, since I think most apps will pick one.
But (2) seems prudent.

—Richard

---

From: "Katriel Cohn-Gordon" <[email-masked]>
Date: Sun, 02 Dec 2018 23:15:13 +0000

This seems like a neat approach; I agree that putting the bit into the
GroupState is a good idea.
As Watson says, this could be an opening for downgrade attacks, so we
should make sure that there's as little negotiation as possible about
the "encrypt handshake messages" bit. Having it just go in the group
state and requiring clients to know it seems fine, although there is the
case of an app which previously didn't encrypt handshake messages and
now wants to.
At a high level I support the idea.

k

On Sun, 2 Dec 2018, at 10:51 PM, Richard Barnes wrote:
> 
> 
> On Sun, Dec 2, 2018 at 17:31 Watson Ladd
> <[email-masked]> wrote:>> On Sun, Dec 2, 2018 at 2:25 PM Richard Barnes <[email-masked]> wrote:
>>  >
>>  > Hey all,
>>  >
>>  > As we discussed in Bangkok, there are trade-offs between
>>  > encrypting handshake messages and enabling the delivery service to
>>  > assist with scaling.>>  >
>>  > 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.>>  >
>>  > Another, simpler, approach we could take is to punt the decision
>>  > to the application.  We would define in the document two options:>>  >
>>  > (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.>> 
> The server needs to be aware of it’s going to provide any assistance,
> yes.   But in principle, clients could choose to encrypt and the
> server would never know.  I think the more important question is
> whether clients all need to agree.> 
>> And
> Seems like there are basically two choices: (1) don’t worry
> about it, let the application figure it out, or (2) include the
> “encryptHandshake” bit in the GroupState so that everyone
> agrees on it.> 
> I think (1) is probably sufficient, since I think most apps will pick
> one.  But (2) seems prudent.> 
> —Richard
> 
> 
>> 
>> >
>>  > Cheers,
>>  > --RIchard
>>  >
>>  >
> _________________________________________________
> MLS mailing list
> [email-masked]

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Mon, 3 Dec 2018 09:01:27 +0100

> 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 requir…

Let me poke a bit more at this option. What minimal information do you think the server needs in order to provide its assistance?

-Karthik

---

From: Richard Barnes <[email-masked]>
Date: Mon, 3 Dec 2018 03:28:18 -0500

On Mon, Dec 3, 2018 at 3:01 AM Karthikeyan Bhargavan <
[email-masked]> wrote:

> 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

---

From: Raphael Robert <[email-masked]>
Date: Mon, 3 Dec 2018 16:46:25 +0100

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 <[email-masked]> wrote:
> 
> 
> 
> On Mon, Dec 3, 2018 at 3:01 AM Karthikeyan Bhargavan <[email-masked] <mailto:[email-masked]>> wrote:
> 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
> 
> > 
> > [email-masked] <mailto:[email-masked]>
> > https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
>

---

From: Russ Housley <[email-masked]>
Date: Mon, 3 Dec 2018 16:10:18 -0500

> On Dec 3, 2018, at 10:46 AM, Raphael Robert <raphael=[email-masked]> wrote:
> 
> 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

It is not clear to me how a user would make that choice.  They do not really have much visibility into the consequences of the choice.  So, it would be good for this group to make to choice or provide a concise description of those consequences in language a user might find helpful.

Russ

---

From: "Katriel Cohn-Gordon" <[email-masked]>
Date: Mon, 03 Dec 2018 21:27:00 +0000

I think "clients choose" != "users choose" --- rather, whoever builds
this into their application makes the choice for their users in the
client code.

On Mon, 3 Dec 2018, at 9:10 PM, Russ Housley wrote:
> 
> 
>> On Dec 3, 2018, at 10:46 AM, Raphael Robert
>> <raphael=[email-masked]> wrote:>> 
>> 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> 
> It is not clear to me how a user would make that choice.  They do not
> really have much visibility into the consequences of the choice.  So,
> it would be good for this group to make to choice or provide a concise
> description of those consequences in language a user might find
> helpful.> 
> Russ
>

---

From: Raphael Robert <[email-masked]>
Date: Mon, 3 Dec 2018 22:36:43 +0100

> On 3 Dec 2018, at 22:27, Katriel Cohn-Gordon <[email-masked]> wrote:
> 
> I think "clients choose" != "users choose" --- rather, whoever builds this into their application makes the choice for their users in the client code.

That’s what I meant. It will be up to the application vendor to decide on the UX.

>>> On Dec 3, 2018, at 10:46 AM, Raphael Robert <raphael=[email-masked] <mailto:raphael=[email-masked]>> wrote:
>>>

---

From: Richard Barnes <[email-masked]>
Date: Mon, 3 Dec 2018 16:38:44 -0500

Do you also mean that all the clients in a group decide independently?
(Even with a single vendor, you could have version migrations). Or does the
group need to agree?

On Mon, Dec 3, 2018, 16:37 Raphael Robert <raphael=[email-masked]
wrote:

> I think "clients choose" != "users choose" --- rather, whoever builds this
> into their application makes the choice for their users in the client code.
>
>
> On Dec 3, 2018, at 10:46 AM, Raphael Robert <
> raphael=[email-masked]> wrote:
>
> 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
>
>
> really have much visibility into the consequences of the choice.  So, it
> would be good for this group to make to choice or provide a concise
> description of those consequences in language a user might find helpful.
>
> Russ
>
> *_______________________________________________*
> MLS mailing list
> [email-masked]

---

From: Raphael Robert <[email-masked]>
Date: Mon, 3 Dec 2018 22:42:04 +0100

As I said earlier:

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

In other words, HS encryption should be fixed for now. Possibly even forever, unless we come to the conclusion it’s a bad idea.

> On 3 Dec 2018, at 22:38, Richard Barnes <[email-masked]> wrote:
> 
> Do you also mean that all the clients in a group decide independently?  (Even with a single vendor, you could have version migrations). Or does the group need to agree?
> 
> On Mon, Dec 3, 2018, 16:37 Raphael Robert <raphael=[email-masked] <mailto:[email-masked]> wrote:
> 
> 
>> On 3 Dec 2018, at 22:27, Katriel Cohn-Gordon <[email-masked] <mailto:[email-masked]>> wrote:
>>