Subject: [MLS] Message Protection

From: Richard Barnes <[email-masked]>
Date: Tue, 26 Jun 2018 17:38:42 -0700

Hey all,

One of the things we kind of waved our hands about in the charter and
current protocol draft is message protection.  That is, the idea of
specifying a concrete syntax for using the keys we negotiate using MLS to
actually protect content.

This is a simpler problem than key exchange (since you've already
established a group key), but it still has some nuances that matter to the
overall security story, so it seems worth writing some things down:

- Content encapsulation (e.g., what nonces / AAD you use with AEAD)
- Key schedule, i.e., how message keys are derived from the group key
- ACK / NACK / replay
- Transcript integrity (?)
- Expiration times (?)

What's missing here?

As far as getting something done: My MLS bandwidth is probably going to be
consumed with the key exchange protocol.  Is there someone who would like
to take a stab at writing a message protection specification?  Either as a
new draft or as a section in the protocol draft.

Cheers,
--Richard

---

From: Benjamin Beurdouche <[email-masked]>
Date: Tue, 26 Jun 2018 17:53:55 -0700

Hi Richard, Hi all,

> On Jun 26, 2018, at 5:38 PM, Richard Barnes <[email-masked]> wrote:
> 
> Hey all,
> 
> One of the things we kind of waved our hands about in the charter and current protocol draft is message protection.  That is, the idea of specifying a concrete syntax for using the keys we negotiate using MLS to actually protect content.
> 
> This is a simpler problem than key exchange (since you've already established a group key), but it still has some nuances that matter to the overall security story, so it seems worth writing some things down:
> 

Maximum payload length and rekeying have been left out, and these are very dependent on how often we roll the root keys.
I believe we currently leave it to the application to decide when to roll the keys, but obviously we must be very careful here…

> As far as getting something done: My MLS bandwidth is probably going to be consumed with the key exchange protocol.  Is there someone who would like to take a stab at writing a message protection specification?  Either as a new draft or as a section in the protocol draft.

Hand waving here ! ;)
My preference goes for most/all of that to be part of the protocol specification...

B.

---

From: Russ Housley <[email-masked]>
Date: Wed, 27 Jun 2018 17:36:08 -0400

> On Jun 26, 2018, at 8:38 PM, Richard Barnes <[email-masked]> wrote:
> 
> Hey all,
> 

If the tree produces a key and an identifier for that key, then the protocol is straightforward.

The key identifier could be derived from the key itself so that anyone that knows the key also knows the identifier.

	prk = HKDF-Extract('mls-key-id' | tree-identifier, key)

	keyid = HKDF-Expand(prk, '', sizeof(keyid))

Russ

---

From: Martin Thomson <[email-masked]>
Date: Thu, 28 Jun 2018 08:12:04 +1000

I was thinking that the nonce generation aspect would be worth looking
into as well.  If you crib from the TLS design, maybe you could have
per-participant keys so that each can be independently responsible for
ensuring nonce-uniqueness.  Then they can use counters to avoid nonce
reuse if they so choose.  Otherwise, I was tempted to suggest AES-SIV
or another nonce-reuse-resistant scheme, but there are fewer of those
available than straight up AEADs.
On Thu, Jun 28, 2018 at 7:36 AM Russ Housley <[email-masked]> wrote:
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Richard Barnes <[email-masked]>
Date: Thu, 28 Jun 2018 07:21:21 -0700

Yeah, when I wrote "key schedule", I was envisioning things like deriving
keys per-sender, or per-message-per-sender, hash-ratchet style.  Since you
can get some forward secrecy benefits that way if you delete older entries
in the hash ratchets.

On Wed, Jun 27, 2018 at 3:12 PM Martin Thomson <[email-masked]>
wrote:

> > The key identifier could be derived from the key itself so that anyone
> that knows the key also knows the identifier.
> >

---

From: Russ Housley <[email-masked]>
Date: Thu, 28 Jun 2018 10:38:28 -0400

Martin:

Each sender using a separate key seems pretty easy.  The key can be derived using the sender's position in the key or any other unique identifier that comes natural in the messaging protocol.

Russ

> On Jun 27, 2018, at 6:12 PM, Martin Thomson <[email-masked]> wrote:
>

---

From: "Katriel Cohn-Gordon" <[email-masked]>
Date: Thu, 28 Jun 2018 16:11:59 +0100

I've been chatting with Alexey at Virgil Security, who has started work on a PR [1] to add this form of key separation.

I think we all liked this design; shall we figure out exactly how it works? I like the idea of symmetric key chains so that each message has a separate encryption key, as in Signal; that requires N and PN counters in the header to figure out which key to use, which I guess should go into the authenticated data.

Note that this means that each message key is used once, which helps guard against nonce reuse.

best,
Katriel

  [1] https://github.com/ekr/mls-protocol/compare/master...Scratch-net:master

On Thu, 28 Jun 2018, at 3:38 PM, Russ Housley wrote:
> Martin:
> 
> Each sender using a separate key seems pretty easy.  The key can be 
> derived using the sender's position in the key or any other unique 
> identifier that comes natural in the messaging protocol.
> 
> Russ
> 
>

---

From: Martin Thomson <[email-masked]>
Date: Fri, 29 Jun 2018 16:36:33 +1000

A few comments here (I'd comment on a PR if one existed :)

Is "Contant" supposed to be the content of the message, a constant, or
something else?  Is "Msg" a label in the sense of the label passed to
HKDF in TLS 1.3, or the the content of the message?  Assuming the
former, a 255 octet limit is probably plenty.  You probably don't want
to use the plaintext of the message for key derivation; then you won't
be able to read messages out of order.

Your PR-in-progress seems to imply that one use of HKDF is used.  It
might be best to have three derivations: one for the next key, one for
the key, and another for the nonce.

You don't seem to include the number of messages from the previous
epoch in the counter.  Is this just under the AAD?  What happens if an
endpoint doesn't send any messages in a given epoch?  How is the count
of messages from the previous epoch protected?

(Sorry, too many questions.  I'm sure that you'll sort most of these out.)

---

From: "Alexey Ermishkin" <[email-masked]>
Date: Fri, 29 Jun 2018 12:39:04 +0500

Hello, Alex here.

Thanks for the comments, my reply below:

Sorry for the typo, Contant == Constant. It's purely for domain separation.

I'm not sure if nonce should be also derived as keys will be unique and used
only once. It does not seem to affect security in either way. Signal is also
using zero nonces for one time keys.

As stated in the PR, each message includes 2 counters:
1) PN. Number of messages in previous epoch (can be zero)
2) N. Message number in the current epoch.

Both of them are under AAD

I think I'll add couple of amends and make a proper PR so that we could
start a proper dialogue there

-----Original Message-----
From: MLS <[email-masked]> On Behalf Of Martin Thomson
Sent: Friday, June 29, 2018 11:37 AM
To: Katriel Cohn-Gordon <[email-masked]>
Cc: [email-masked]; [email-masked]
Subject: Re: [MLS] Message Protection

Is "Contant" supposed to be the content of the message, a constant, or
something else?  Is "Msg" a label in the sense of the label passed to HKDF
in TLS 1.3, or the the content of the message?  Assuming the former, a 255
octet limit is probably plenty.  You probably don't want to use the
plaintext of the message for key derivation; then you won't be able to read
messages out of order.

Your PR-in-progress seems to imply that one use of HKDF is used.  It might
be best to have three derivations: one for the next key, one for the key,
and another for the nonce.

You don't seem to include the number of messages from the previous epoch in
the counter.  Is this just under the AAD?  What happens if an endpoint
doesn't send any messages in a given epoch?  How is the count of messages
from the previous epoch protected?

(Sorry, too many questions.  I'm sure that you'll sort most of these out.)
On Fri, Jun 29, 2018 at 1:12 AM Katriel Cohn-Gordon <[email-masked]>
wrote:
>
> I've been chatting with Alexey at Virgil Security, who has started work on
a PR [1] to add this form of key separation.
>
> I think we all liked this design; shall we figure out exactly how it
works? I like the idea of symmetric key chains so that each message has a
separate encryption key, as in Signal; that requires N and PN counters in
the header to figure out which key to use, which I guess should go into the
authenticated data.
>   [1] 
> https://github.com/ekr/mls-protocol/compare/master...Scratch-net:maste
> r
>
> > > I was thinking that the nonce generation aspect would be worth 
> > > looking into as well.  If you crib from the TLS design, maybe you 
> > > could have per-participant keys so that each can be independently 
> > > responsible for ensuring nonce-uniqueness.  Then they can use 
> > > counters to avoid nonce reuse if they so choose.  Otherwise, I was 
> > > tempted to suggest AES-SIV or another nonce-reuse-resistant 
> > > scheme, but there are fewer of those available than straight up AEADs.
> > >>> One of the things we kind of waved our hands about in the charter
and current protocol draft is message protection.  That is, the idea of
specifying a concrete syntax for using the keys we negotiate using MLS to
actually protect content.
established a group key), but it still has some nuances that matter to the
overall security story, so it seems worth writing some things down:
> > >> The key identifier could be derived from the key itself so that
anyone that knows the key also knows the identifier.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 29 Jun 2018 17:57:29 +1000

> using zero nonces for one time keys.

In TLS we chose to derive nonces so that it would become less feasible
to do precomputation attacks.  Messages are often predictable, and if
you can calculate a table for common responses, it might be possible
to have enough values stored to compromise confidentiality.

(That was the argument; not sure how much weight it carries relative
to just using a stronger primitive, but there you have it.)