Subject: [MLS] *re*joining a group with the same identity key

From: "Katriel Cohn-Gordon" <[email-masked]>
Date: Wed, 25 Jul 2018 12:01:09 +0100

Hi all,

Here'a s case we might want to think about: what should happen if a
*current member* of a group asks to join, with the same long-term key
that they're already joined with?
The simple answer is to forbid such joins, but this might happen if a
device forgets its group state but remembers its identity key. (Perhaps
it writes the group state to a local database and the write got
corrupted.)
Alternatively I see a handful of different ways we could support these
joins, if we wanted to. Perhaps the simplest is to allow the device to
double-join but require it to immediately delete the old copy of itself.
best,
k

---

From: Jon Millican <[email-masked]>
Date: Wed, 25 Jul 2018 11:05:09 +0000

One potential option that comes to mind is for the server to help it reinsert itself in the correct place. This would essentially amount to a join, but serving its own copath instead of the group’s frontier. We could then reject somebody double-joining their own identity key; under the assumption that this could only happen with a malicious server anyway.

I don’t have strong feelings about this vs your proposed solution though. The main benefit would probably be just in terms of keeping the tree cleaner and minimising remove operations that need to be done.

Jon

On 25/07/2018, 12:01, "MLS on behalf of Katriel Cohn-Gordon" <[email-masked]<mailto:[email-masked]> on behalf of [email-masked]<mailto:[email-masked]>> wrote:

Hi all,

Here'a s case we might want to think about: what should happen if a current member of a group asks to join, with the same long-term key that they're already joined with?

The simple answer is to forbid such joins, but this might happen if a device forgets its group state but remembers its identity key. (Perhaps it writes the group state to a local database and the write got corrupted.)

Alternatively I see a handful of different ways we could support these joins, if we wanted to. Perhaps the simplest is to allow the device to double-join but require it to immediately delete the old copy of itself.

best,
k

---

From: Dennis Jackson <[email-masked]>
Date: Wed, 25 Jul 2018 12:58:30 +0100

[email-masked]<mailto:[email-masked]> wrote:

> device forgets its group state but remembers its identity key.

Depending on how MLS specifies update operations, this could also
happen if there was a network partition and some group members see a
different order of key updates. Even if we assume the existence of a
delivery service which can provide a linear order for key update
messages, the attacker will be allowed to compromise the server and
violate this property. Consequently, some participants will have
differing views of the group key and need to converge.

In both cases we have a long term key, already in the group, with bad
local state. I think we need a recovery mechanism for this other than
just starting a new group or allowing a rejoin since that would allow
an attacker with only knowledge of a long term key to join a previously
secure group. 

We could mitigate this by proving knowledge of some recent state: a
device which knew the group key five minutes ago is more trustworthy
than one which doesn’t know any group state. It’s an application-layer
decision to actually figure out what to do in this case, but we could
expose a way to prove state knowledge (e.g. by deriving a “recovery”
key after every update).

Best,
Dennis

On Wed, 25 Jul 2018 11:05:09 +0000
Jon Millican <[email-masked]> wrote:

> One potential option that comes to mind is for the server to help it
> reinsert itself in the correct place. This would essentially amount
> to a join, but serving its own copath instead of the group’s
> frontier. We could then reject somebody double-joining their own
> identity key; under the assumption that this could only happen with a
> malicious server anyway.
> 
> I don’t have strong feelings about this vs your proposed solution
> though. The main benefit would probably be just in terms of keeping
> the tree cleaner and minimising remove operations that need to be
> done.
> 
> Jon
> 
> On 25/07/2018, 12:01, "MLS on behalf of Katriel Cohn-Gordon"
> <[email-masked]<mailto:[email-masked]> on behalf of
> [email-masked]<mailto:[email-masked]>> wrote:
> 
> Hi all,
> 
> current member of a group asks to join, with the same long-term key
> device forgets its group state but remembers its identity key.
> (Perhaps it writes the group state to a local database and the write
> got corrupted.)
> 
> Alternatively I see a handful of different ways we could support
> these joins, if we wanted to. Perhaps the simplest is to allow the
> device to double-join but require it to immediately delete the old
> copy of itself.
> 
> best,
> k
> 

-- 
PGP Fingerprint: 5B93 F0B9 D6A8 9BC1 546B C98C 6105 A775 8CD2 46AC

---

From: Richard Barnes <[email-masked]>
Date: Thu, 26 Jul 2018 11:42:11 -0400

I actually expect this to be a not-uncommon case.  Two use cases
immediately come to mind:

1. New devices in an application where identity keys are sync'ed among
devices
2. Participants who have lost state and need to re-sync.

On account of (1), I had been thinking that the mapping between members /
leaves in the tree and identity keys would not be one-to-one, but
many-to-one.  Are folks thinking that there would be technical problems /
ambiguities in such a case?  None are coming to my mind.

It does seem worth thinking about the re-sync case (2), i.e., the case
where a participant has most of his state.  If he's forgotten everything
besides his identity private key (or including the identity private key), I
don't think there's much you can do but treat him like a new participant.
If he remembers his position in the tree, it seems like you could do a
"re-sync" transaction that's like an add, but for that position in the tree
-- it's the same logic as an add, except instead of the frontier, you send
the copath for that position; for other nodes, it just looks like an Update
at that position.

(Aside: This reinforces that we really only have 1.2 operations here:
Update + handle-update-at-edge + encrypt-leaf-secret)

It also seems like if we can solve the "re-sync a member with lost state"
problem, then we can probably also solve the "heal a network partition"
problem that Dennis raises.  Assuming we can choose a winning partition and
appoint someone to do the merge, the person doing the merge can just
re-initialize the losing members to their point in the tree, as if they had
lost their state.

--Richard

On Wed, Jul 25, 2018 at 7:59 AM Dennis Jackson <[email-masked]>
wrote:

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

---

From: Peter Saint-Andre <[email-masked]>
Date: Thu, 26 Jul 2018 10:32:47 -0600

On 7/26/18 9:42 AM, Richard Barnes wrote:
> On account of (1), I had been thinking that the mapping between members
> / leaves in the tree and identity keys would not be one-to-one, but
> many-to-one.  Are folks thinking that there would be technical problems
> / ambiguities in such a case?  None are coming to my mind.

This sounds similar to something we did in XMPP, allowing multiple
in-room sessions for the same JabberID (although, naturally, the MLS
context is more advanced cryptographically):

https://xmpp.org/extensions/xep-0045.html#enter-conflict

Peter

---

From: Ted Hardie <[email-masked]>
Date: Thu, 26 Jul 2018 09:43:15 -0700

> ambiguities in such a case?  None are coming to my mind.
I think there is an ambiguity, but it is fairly easy to resolve.  There are
cases where a participant attempting to add themselves with the same
identity to an existing group is implicitly replacing their previous
connection.  Katriel called that out as:  "Perhaps the simplest is to allow
the device to double-join but require it to immediately delete the old copy
of itself."  There are others where this is a true add-a new device that
should also receive communication.  I think the fix here is to replace
"require it to immediately delete" with "allow it to immediately delete";
that seems to support both use cases and make the decision about which is
in use explicit and in the user's control.

Ted

---

From: "Katriel Cohn-Gordon" <[email-masked]>
Date: Fri, 27 Jul 2018 11:35:04 +0100

One thing to be clear about: all of these "rejoin"-style operations
break post-compromise security in some way, because they allow an actor
who knows long-term keys but not the current state to become a full-
fledged group member.
That's not to say we shouldn't support them, of course (it's no good
building a secure protocol that doesn't work), just that we should be
careful about when they can happen. I think it's also important to make
sure they're clearly differentiated from normal operations, so that
applications can disallow them or show warnings.
k

On Thu, 26 Jul 2018, at 5:43 PM, Ted Hardie wrote:
>> immediately come to mind:>> 
>> 1. New devices in an application where identity keys are sync'ed
>>    among devices>> 2. Participants who have lost state and need to re-sync.
>> 
>> On account of (1), I had been thinking that the mapping between
>> members / leaves in the tree and identity keys would not be one-to-
>> one, but many-to-one.  Are folks thinking that there would be
>> technical problems / ambiguities in such a case?  None are coming to
>> my mind.>> 
> 
> I think there is an ambiguity, but it is fairly easy to resolve.
> There are cases where a participant attempting to add themselves with
> the same identity to an existing group is implicitly replacing their
> previous connection.  Katriel called that out as:  "Perhaps the
> simplest is to allow the device to double-join but require it to
> immediately delete the old copy of itself."  There are others where
> this is a true add-a new device that should also receive
> communication.  I think the fix here is to replace "require it to
> immediately delete" with "allow it to immediately delete"; that seems
> to support both use cases and make the decision about which is in use
> explicit and in the user's control.> 
> Ted
> 
>  
>> 
>> It does seem worth thinking about the re-sync case (2), i.e., the
>> case where a participant has most of his state.  If he's forgotten
>> everything besides his identity private key (or including the
>> identity private key), I don't think there's much you can do but
>> treat him like a new participant.  If he remembers his position in
>> the tree, it seems like you could do a "re-sync" transaction that's
>> like an add, but for that position in the tree -- it's the same logic
>> as an add, except instead of the frontier, you send the copath for
>> that position; for other nodes, it just looks like an Update at that
>> position.>> 
>> Update + handle-update-at-edge + encrypt-leaf-secret)>> 
>> It also seems like if we can solve the "re-sync a member with lost
>> state" problem, then we can probably also solve the "heal a network
>> partition" problem that Dennis raises.  Assuming we can choose a
>> winning partition and appoint someone to do the merge, the person
>> doing the merge can just re-initialize the losing members to their
>> point in the tree, as if they had lost their state.>> 
>> --Richard
>> 
>> 
>> On Wed, Jul 25, 2018 at 7:59 AM Dennis Jackson
>> <[email-masked]> wrote:>>> [email-masked]<mailto:[email-masked]> wrote:
>>> 
>>>  > The simple answer is to forbid such joins, but this might happen
>>>  > if a>>>  > device forgets its group state but remembers its identity key.
>>> 
>>>  happen if there was a network partition and some group members
>>>  see a>>>  different order of key updates. Even if we assume the
>>>  existence of a>>>  delivery service which can provide a linear order for key update
>>>  messages, the attacker will be allowed to compromise the server and>>>  violate this property. Consequently, some participants will have
>>>  In both cases we have a long term key, already in the group,
>>>  with bad>>>  local state. I think we need a recovery mechanism for this
>>>  other than>>>  just starting a new group or allowing a rejoin since that would
>>>  allow>>>  an attacker with only knowledge of a long term key to join a
>>>  previously>>>  secure group. 
>>> 
>>>  We could mitigate this by proving knowledge of some recent state: a>>>  device which knew the group key five minutes ago is more
>>>  trustworthy>>>  than one which doesn’t know any group state. It’s an application-
>>>  layer>>>  decision to actually figure out what to do in this case, but we
>>>  could>>>  expose a way to prove state knowledge (e.g. by deriving a
>>>  “recovery”>>>  key after every update).
>>> 
>>>  Best,
>>>  Dennis
>>> 
>>>  > One potential option that comes to mind is for the server to
>>>  > help it>>>  > reinsert itself in the correct place. This would essentially
>>>  > amount>>>  > to a join, but serving its own copath instead of the group’s
>>>  > frontier. We could then reject somebody double-joining their own>>>  > identity key; under the assumption that this could only happen
>>>  > with a>>>  > malicious server anyway.
>>>  > 
>>>  > I don’t have strong feelings about this vs your proposed solution>>>  > though. The main benefit would probably be just in terms of
>>>  > keeping>>>  > the tree cleaner and minimising remove operations that need to be>>>  > done.
>>>  > 
>>>  > Jon
>>>  > 
>>>  > Here'a s case we might want to think about: what should happen
>>>  > if a>>>  > current member of a group asks to join, with the same long-term
>>>  > key>>>  > that they're already joined with?
>>>  > 
>>>  > The simple answer is to forbid such joins, but this might happen
>>>  > if a>>>  > device forgets its group state but remembers its identity key.
>>>  > (Perhaps it writes the group state to a local database and the
>>>  > write>>>  > got corrupted.)
>>>  > 
>>>  > Alternatively I see a handful of different ways we could support>>>  > these joins, if we wanted to. Perhaps the simplest is to allow
>>>  > the>>>  > device to double-join but require it to immediately delete the
>>>  > old>>>  > copy of itself.
>>>  > 
>>>  > best,
>>>  > k
>>>  > 
>>> 
>>> 
>>> 
>>>  -- 
>>>  PGP Fingerprint: 5B93 F0B9 D6A8 9BC1 546B C98C 6105 A775 8CD2 46AC>>> _______________________________________________
>>>  MLS mailing list
>>> [email-masked]
> _________________________________________________
> MLS mailing list
> [email-masked]

---

From: Richard Barnes <[email-masked]>
Date: Fri, 27 Jul 2018 11:23:59 -0400

Just to confirm, the PCS risk you're thinking of is something like:
- Attacker finds an identity key lying on a street corner
- Attacker shows up at the group and say "hey guys, i lost all my other
state, can you let me back in"?

IIRC, we touched on this in the IETF meeting discussions, this idea that we
might adopt a different PCS posture w.r.t. long-term identity keys than
confidentiality keys.

There's an underlying tension here between the desire for persistent
identities and the ephemerality / rotation that PCS requires.  Even
assuming maximal rotation of all the key material, if you have a policy
that says "$IDENTITY is a member of this group" and someone shows up with a
valid credential for $IDENTITY, are you going to let them in?

Given that, I'm kind of tempted to argue that PCS isn't even a meaningful
concept with regard to identity keys.  At least not in the same way as for
confidentiality keys.  Or at least that it needs to be framed in quite a
different way.

--Richard

On Fri, Jul 27, 2018 at 6:35 AM Katriel Cohn-Gordon <[email-masked]>
wrote:

> One thing to be clear about: all of these "rejoin"-style operations break
> post-compromise security in some way, because they allow an actor who knows
> long-term keys but not the current state to become a full-fledged group
> member.
>
> I think there is an ambiguity, but it is fairly easy to resolve.  There
> are cases where a participant attempting to add themselves with the same
> in use explicit and in the user's control..
>
> Ted
>
>
>
>
> *_______________________________________________*
> MLS mailing list
> [email-masked]
> https://www.ietf..org/mailman/listinfo/mls
> <https://www.ietf.org/mailman/listinfo/mls>
>
>

---

From: Dennis Jackson <[email-masked]>
Date: Fri, 27 Jul 2018 16:47:38 +0100

Richard Barnes <[email-masked]> wrote:
> if you have a policy that says "$IDENTITY is a member of this
> group" and someone shows up with a valid credential for $IDENTITY,
> are you going to let them in?

But the point here is that they have lost a valid credential for the
group (the group key). Maybe we are going to readmit them, but we
should certainly warn the user in same way Signal and WhatsApp
currently do ("Participants safety code has changed"). 

I think we can do better than this though, as I alluded to in my earlier
message. Losing all of your local state except your identity key is
actually a pretty rare case. If a user gets a new device then they
should/must generate a new key. If a user has a bad key update, they
will still know information about previous group states. 

By providing a way to prove knowledge of recent group state, without
revealing or storing old group keys, we can differentiate between the
attacker attempting to join with just the identity key, or a user
rejoining after a brief hiccup. 

All the best,
Dennis 

On Fri, 27 Jul 2018 11:23:59 -0400
Richard Barnes <[email-masked]> wrote:

> - Attacker shows up at the group and say "hey guys, i lost all my
> other state, can you let me back in"?
> 
> IIRC, we touched on this in the IETF meeting discussions, this idea
> that we might adopt a different PCS posture w.r.t. long-term identity
> keys than confidentiality keys.
> 
> assuming maximal rotation of all the key material, if you have a
> policy that says "$IDENTITY is a member of this group" and someone
> shows up with a valid credential for $IDENTITY, are you going to let
> them in?
> 
> Given that, I'm kind of tempted to argue that PCS isn't even a
> meaningful concept with regard to identity keys.  At least not in the
> same way as for confidentiality keys.  Or at least that it needs to
> be framed in quite a different way.
> 
> --Richard
> 
> 
> > break post-compromise security in some way, because they allow an
> > actor who knows long-term keys but not the current state to become
> > a full-fledged group member.
> >
> > building a secure protocol that doesn't work), just that we should
> > be careful about when they can happen. I think it's also important
> > to make sure they're clearly differentiated from normal operations,
> > so that applications can disallow them or show warnings.
> >
> > k
> >
> > among devices
> > members / leaves in the tree and identity keys would not be
> > one-to-one, but many-to-one.  Are folks thinking that there would
> > be technical problems / ambiguities in such a case?  None are
> > coming to my mind.
> >
> >
> > There are cases where a participant attempting to add themselves
> > with the same identity to an existing group is implicitly replacing
> > their previous connection.  Katriel called that out as:  "Perhaps
> > the simplest is to allow the device to double-join but require it
> > to immediately delete the old copy of itself."  There are others
> > where this is a true add-a new device that should also receive
> > immediately delete" with "allow it to immediately delete"; that
> > seems to support both use cases and make the decision about which
> > is in use explicit and in the user's control..
> >
> > Ted
> >
> >
> >
> >
> > like an add, but for that position in the tree -- it's the same
> > logic as an add, except instead of the frontier, you send the
> > copath for that position; for other nodes, it just looks like an
> > Update at that position.
> >
> > (Aside: This reinforces that we really only have 1.2 operations
> > here: Update + handle-update-at-edge + encrypt-leaf-secret)
> >
> > point in the tree, as if they had lost their state.
> >
> > --Richard
> >
> >
> > <[email-masked]> wrote:
> >
> > > if a device forgets its group state but remembers its identity
> > > key.
> >
> > In both cases we have a long term key, already in the group, with
> > bad local state. I think we need a recovery mechanism for this
> > other than just starting a new group or allowing a rejoin since
> > that would allow an attacker with only knowledge of a long term key
> > to join a previously secure group.
> >
> > than one which doesn’t know any group state. It’s an
> > application-layer decision to actually figure out what to do in
> > this case, but we could expose a way to prove state knowledge (e.g.
> > by deriving a “recovery” key after every update).
> >
> > Best,
> > Dennis
> >
> > > One potential option that comes to mind is for the server to help
> > > it reinsert itself in the correct place. This would essentially
> > > amount to a join, but serving its own copath instead of the
> > > group’s frontier. We could then reject somebody double-joining
> > > their own identity key; under the assumption that this could only
> > > happen with a malicious server anyway.
> > >
> > > though. The main benefit would probably be just in terms of
> > > keeping the tree cleaner and minimising remove operations that
> > > need to be done.
> > >
> > > Jon
> > >
> > > Here'a s case we might want to think about: what should happen if
> > > a current member of a group asks to join, with the same long-term
> > > key that they're already joined with?
> > >
> > > if a device forgets its group state but remembers its identity
> > > key. (Perhaps it writes the group state to a local database and
> > > the write got corrupted.)
> > >