Subject: [MLS] High-level Questions and Clarifications

From: Michael Rosenberg <[email-masked]>
Date: Wed, 23 Jan 2019 01:22:17 -0500

Hey all, I'm just getting involved with MLS and everyone has been super helpful with onboarding and reviewing stuff, and I'm really grateful for it. I've been trying to do a close reading of protocol spec and these are the last of the questions that didn't fall under a previous PR or Github issue. Some of these questions, if nontrivial, might be better if split out into threads of their own. And of course, feel free to answer whichever subset of these questions you wish. Also, I hope to use what I do understand so far to begin building out a new Rust implementation of the protocol soon.

The following page numbers are from the PDF version of protocol draft #3.

Page 8
======
The sample exchange depicted here shows Add being sent before Welcome. But section 7.2 seems to indicate that Welcome messages have to come first. Does the order matter? I though it did, since Welcome messages are necessary to set the new participant up with the current GroupState so everyone's on the same page after the subsequent Add.

Pages 11,15
===========
The wording "A Diffie-Hellman finite-field group or elliptic curve" that appears twice feels awkward (specifically, I think it should say "finite-field multiplicative group") but more importantly, it's unclear if implementations MUST, SHOULD or, MAY use these mathematical objects for DHE. Further, [clicks in chinstrap on tinfoil hat] could this reasonably be loosened to allow for ciphersuites with quantum-resistant DH-like algorithms such as SIDH?

Page 12
=======
This may not be a well-founded concern, but it might be desirable that the Hash that's used iteratively to derive node secrets on the ratchet tree be keyed (or salted) with tree-specific information. One could imagine if participant D had poor enough entropy and an attacker had done a good amount of precomputation of Hash, the attacker could derive D from Hash(D). Then the attacker could go and do the same thing in another group with another participant with poor entropy without having to do any more precomputation.

Page 20
=======
Which AEAD and DH algorithms are supposed to be used for sending a node's secret to a leaf in the resolution of the copath? Suppose A and B are siblings and that they have different ciphersuite preferences. How does B compute the shared secret AB in order to encrypt new entropy for A?

Another related general question: There are cases when only a single party fails an operation, and it's not immediately clear what the procedure is to handle these. For example, a DirectPath in an Update operation could be filled with all correct ECIESCiphertexts except one, whose contents is random garbage. Then only a Participant with knowledge of the corresponding node secret would be able to tell that there was an invalid ciphertext in the bunch. The rest would be unable to see this, and furthermore, it's unclear how the affected Participant would even prove that it was invalid without having to reveal the node secret to the rest of the Group. How should the protocol handle this?

Page 21
=======
Derive-Secret is a function of HkdfLabel, which in turn contains a GroupState. But the serialization format of the GroupState is not specified anywhere. Am I missing something? This probably should not be implementation-defined, since it is fundamental to agreeing on internal state.

Page 26
=======
Why is cipher_suite in Welcome? Each init key corresponds to a unique cipher suite, so the sender and recipient already know the cipher suite they need to use.

Page 27
=======
What happens when you get two Welcomes? Could you arbitrarily send a Welcome to a person and DoS them from the group by forcing them to update their state to something wrong?

Page 35
=======
How exactly are the message signatures calculated? Does it mean the 16-byte tag at the end of the AES-GCM ciphertext? How does this generalize for AEADs with non-detachable signatures like AES-CCM (which is a mac-then-encrypt construction)?

---

From: Richard Barnes <[email-masked]>
Date: Wed, 23 Jan 2019 11:27:20 -0500

Hi Michael,

Thanks for the feedback.  Some responses inline.  FWIW, section numbers or
titles are easier points of reference than pages :)

On Wed, Jan 23, 2019 at 2:52 AM Michael Rosenberg <[email-masked]>
wrote:

> Hey all, I'm just getting involved with MLS and everyone has been super
> helpful with onboarding and reviewing stuff, and I'm really grateful for
> it. I've been trying to do a close reading of protocol spec and these are
> the last of the questions that didn't fall under a previous PR or Github
> issue. Some of these questions, if nontrivial, might be better if split out
> into threads of their own. And of course, feel free to answer whichever
> subset of these questions you wish. Also, I hope to use what I do
> understand so far to begin building out a new Rust implementation of the
> protocol soon.
>
> The sample exchange depicted here shows Add being sent before Welcome. But
> section 7.2 seems to indicate that Welcome messages have to come first.
> Does the order matter? I though it did, since Welcome messages are
> necessary to set the new participant up with the current GroupState so
> everyone's on the same page after the subsequent Add.
>

As the draft is currently written, I think you're right.  The new joiner
should verify that the UIK in the corresponding Add actually belongs to the
new joiner, so it needs both the Welcome and the Add to initialize its
state.

As noted in the OPEN ISSUE in Section 7.2, there's a challenging
synchronization issue here.  In the event that the Add fails, you don't
want the new joiner to initialize its state based on the corresponding
Welcome, since that would result in a state the group never entered.  I
think that in practice this  can be managed (e.g., with locks), but if you
have ideas on what guidance would be useful in this document, that would be
helpful.

> Pages 11,15
> ===========
> The wording "A Diffie-Hellman finite-field group or elliptic curve" that
> appears twice feels awkward (specifically, I think it should say
> "finite-field multiplicative group") but more importantly, it's unclear if
> implementations MUST, SHOULD or, MAY use these mathematical objects for
> DHE. Further, [clicks in chinstrap on tinfoil hat] could this reasonably be
> loosened to allow for ciphersuites with quantum-resistant DH-like
> algorithms such as SIDH?
>

We could probably just replace these with "DH group" in general.
Post-quantum is no longer tinfoil hat territory.  I think a few WG
participants have been thinking about what it would look like to plug in PQ
primitives.  But I think "DH group" would still cover things like CSIDH
(but *not* SIDH IIUC).

The real question is whether we can get move from DH to a general KEM
construction, which would allow us even more choice in PQ primitives.

> Page 12
> =======
> This may not be a well-founded concern, but it might be desirable that the
> Hash that's used iteratively to derive node secrets on the ratchet tree be
> keyed (or salted) with tree-specific information. One could imagine if
> participant D had poor enough entropy and an attacker had done a good
> amount of precomputation of Hash, the attacker could derive D from Hash(D).
> Then the attacker could go and do the same thing in another group with
> another participant with poor entropy without having to do any more
> precomputation.
>

Poor entropy could be a concern, but TBH, I'm not sure how much we can do
about it.  We could, for example, require the leaf secret fold in some
value that likely has better entropy, e.g., new_leaf = KDF(salt=prior_leaf,
ikm=prior_epoch_secret).  But from the perspective of the rest of the
group, that's indistinguishable from the leaf holder just picking a random
value.

> Page 20
> =======
> Which AEAD and DH algorithms are supposed to be used for sending a node's
> secret to a leaf in the resolution of the copath? Suppose A and B are
> siblings and that they have different ciphersuite preferences. How does B
> compute the shared secret AB in order to encrypt new entropy for A?
>

There is one ciphersuite for the whole group, which is communicated to new
members in Welcome.cipher_suite.  I wouldn't be surprised if this were
unclear, though, so suggestions for how to clarify would be welcome.

> Another related general question: There are cases when only a single party
> fails an operation, and it's not immediately clear what the procedure is to
> handle these. For example, a DirectPath in an Update operation could be
> filled with all correct ECIESCiphertexts except one, whose contents is
> random garbage. Then only a Participant with knowledge of the corresponding
> node secret would be able to tell that there was an invalid ciphertext in
> the bunch. The rest would be unable to see this, and furthermore, it's
> unclear how the affected Participant would even prove that it was invalid
> without having to reveal the node secret to the rest of the Group. How
> should the protocol handle this?
>

This is still an OPEN ISSUE, noted in Section 7 (page 25).

> Page 21
> =======
> Derive-Secret is a function of HkdfLabel, which in turn contains a
> GroupState. But the serialization format of the GroupState is not specified
> anywhere. Am I missing something? This probably should not be
> implementation-defined, since it is fundamental to agreeing on internal
> state.
>

The GroupState struct is defined in Section 5.7 (page 18).  Since we're
using the TLS struct syntax, the definition of a struct defines its
serialization.

> Page 26
> =======
> Why is cipher_suite in Welcome? Each init key corresponds to a unique
> cipher suite, so the sender and recipient already know the cipher suite
> they need to use.
>

As above, the new joiner needs to know the ciphersuite for the group.  But
also, each UserInitKey can contain init keys for multiple ciphersuites, so
the recipient of the Welcome needs to know which one to use to decrypt.

Page 27
> =======
> What happens when you get two Welcomes? Could you arbitrarily send a
> Welcome to a person and DoS them from the group by forcing them to update
> their state to something wrong?
>

In general, this seems like it's a layer up from what this document is
specifying.  For example, it's perfectly plausible that you could receive
two welcomes with the same group_id and just initialize two different
sessions that work just fine.  That said, we should be clear that that's
the case -- if applications want group IDs to be unique, they need to
enforce that.

We don't have any mechanism right now for authenticating the information in
a Welcome.  You would basically need a way to authenticate a GroupState
object as a valid state of the group.  Suggestions welcome.

Of course, if we can't authenticate the information in a Welcome, we should
describe the risks in the Security Considerations.  Suggestions also
welcome here :)

> Page 35
> =======
> How exactly are the message signatures calculated? Does it mean the
> 16-byte tag at the end of the AES-GCM ciphertext? How does this generalize
> for AEADs with non-detachable signatures like AES-CCM (which is a
> mac-then-encrypt construction)?
>

No, it's a signature, not a MAC. As I understand it, the sender:

- Constructs a MLSSignatureContent struct with the (plaintext) content and
the various indicators of the key being used
- Serializes that struct
- Signs the serialized struct with its identity key (corresponding to its
entry in the group's roster)

That text is due to Benjamin Beurdouche; he might have further corrections.

--Richard

_______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Michael Rosenberg <[email-masked]>
Date: Wed, 23 Jan 2019 15:32:39 -0500

Many thanks for the quick response. This clears up a few things. I have some inline responses and follow-ups.

> On Jan 23, 2019, at 11:27 AM, Richard Barnes <[email-masked]> wrote:
> 
>> Pages 11,15
>> ===========
> We could probably just replace these with "DH group" in general.  Post-quantum is no longer tinfoil hat territory.  I think a few WG participants have been thinking about what it would look like to plug in PQ primitives.  But I think "DH group" would still cover things like CSIDH (but *not* SIDH IIUC).
> 
> The real question is whether we can get move from DH to a general KEM construction, which would allow us even more choice in PQ primitives.

I think the primitive we're looking for might be a "2 part key agreement protocol with perfect forward secrecy" but I can't find much literature on this after a cursory check. Besides DH, ECDH, CSIDH, and SIDH there are some pairing-based constructions (https://eprint.iacr.org/2006/199.pdf has a review of a few such schemes).
 
> Poor entropy could be a concern, but TBH, I'm not sure how much we can do about it.  We could, for example, require the leaf secret fold in some value that likely has better entropy, e.g., new_leaf = KDF(salt=prior_leaf, ikm=prior_epoch_secret).  But from the perspective of the rest of the group, that's indistinguishable from the leaf holder just picking a random value.

Right, but even picking a static salt for each Group could at least cover the case of precomputation attacks against node public keys, no?
 
> There is one ciphersuite for the whole group, which is communicated to new members in Welcome.cipher_suite.  I wouldn't be surprised if this were unclear, though, so suggestions for how to clarify would be welcome.

Oh, this changes a lot. I didn't realize that. I'll try to understand how this actually works and make a PR at some point.

> The GroupState struct is defined in Section 5.7 (page 18).  Since we're using the TLS struct syntax, the definition of a struct defines its serialization.

Gotcha. This was confusing for me. The architecture spec explicitly states that MLS does not have a canonical wire encoding, but I now see that that is different from having an internal serialization format. I might submit a PR that makes this clearer, because the spec currently only says that the TLS syntax is used, and nothing more.
 
> As above, the new joiner needs to know the ciphersuite for the group.  But also, each UserInitKey can contain init keys for multiple ciphersuites, so the recipient of the Welcome needs to know which one to use to decrypt.

I'm still confused. What happens if I specify some Welcome.cipher_suite and then pick the user_init_key_id such that the UserInitKey.cipher_suites_[user_init_key_id] does not agree with the Welcome.cipher_suite? Isn't this a conflict?

> In general, this seems like it's a layer up from what this document is specifying.  For example, it's perfectly plausible that you could receive two welcomes with the same group_id and just initialize two different sessions that work just fine.  That said, we should be clear that that's the case -- if applications want group IDs to be unique, they need to enforce that.
> 
> We don't have any mechanism right now for authenticating the information in a Welcome.  You would basically need a way to authenticate a GroupState object as a valid state of the group.  Suggestions welcome.
> 
> Of course, if we can't authenticate the information in a Welcome, we should describe the risks in the Security Considerations.  Suggestions also welcome here :)

Fair enough. It seems state synchronization is going to be one of the biggest hurdles to overcome. Unfortunately I don't have much experience in designing distributed systems.
 
> - Constructs a MLSSignatureContent struct with the (plaintext) content and the various indicators of the key being used
> - Serializes that struct
> - Signs the serialized struct with its identity key (corresponding to its entry in the group's roster)
>  

Ah, I forgot that the identity key exists. It doesn't appear that any signature algorithm is specified anywhere. I suppose that's for some time in the future, though. The OPEN ISSUE in 10.2 makes a good case for waiting to see which guarantees we want to support.

-Michael