Subject: [MLS] Deniability as external to the MLS protocol

From: Richard Barnes <[email-masked]>
Date: Thu, 22 Oct 2020 13:49:49 -0400

Hey all,

Some recent and soon-to-be-proposed changes involving signatures over the
group's ratchet tree have raised concerns about the deniability of the
protocol.  I'd like to propose that we can safely punt deniability to a
different layer, and not worry about it in the core protocol.

The basic idea here is that signing keys only need to be denied to the
degree they are associated with an identity, so if the Authentication
Service is deniable, all artifacts generated by MLS are as well.

For example, supposed an application were set up in the following way:

* Signature keys are only used with a single group (thus so are KeyPackages)
* MLS credentials have no meaningful identity data (e.g., BasicCredential
with identity=H(public_key))
* Group members authenticate one another by exchanging signature public
keys over a 1:1 deniable channel (e.g., X3DH)

(Here we have instantiated a distributed, deniable Authentication Service
as a full mesh of 1:1 deniable channels.)  In this setup, as far as an
external observer knows, the whole group could have been generated by a
single participant, which seems like a not-bad definition of deniablity.
The MLS messages could be generated by anyone holding the relevant
signature private keys, and the deniable signature key distribution means
that anyone in the group could be the holder of those private keys.

This model is still compatible with things like pre-publishing KeyPackages
for asynchronous add.  You could obviously do an "add first, authenticate
when the joiner comes online" scheme.  You might also be able to do
something more proactive by pre-publishing some deniable data along with
the KeyPackage.

My goal here is to argue that there is at least one way of operating MLS in
a deniable mode, pretty much regardless of what the protocol itself does.
If this argument seems plausible to folks, it should then be safe to make
some changes that had been gated on deniability concerns:

* Updating #406 so that the GroupPublicState is signed by the member that
issues it
* Updating the path hash / parent hash scheme as recommended in Joël's
forthcoming proposal (and which I expect will look like what Benjamin and
Karthik suggested back in January)

I would also be open to adding something like the above discussion to the
architecture document, if people thought it would be useful for posterity.

Best,
--Richard

---

From: Chelsea Komlo <[email-masked]>
Date: Thu, 22 Oct 2020 12:38:19 -0600

Hi Richard,

This approach of per-conversation non-attributable signing keys ensures
"conversation/participation unlinkability", which implies deniability.

This is certainly a viable option for implementations at a level above MLS,
with the caveat that it has sharp edges as nothing in MLS forces signing
keys to be used for exactly one group. Further, ensuring both async
conversations and single-use-keys may be tricky.

It would be great for future versions of MLS to think about how to move
deniability within the protocol itself, but most importantly I think it is
best to keep the core protocol simple to understand and implement. Allowing
deniability protections to be implemented at a layer above MLS seems like a
good compromise towards finalizing the first version of the protocol.

Best,
Chelsea

On Thu, Oct 22, 2020 at 11:50 AM Richard Barnes <[email-masked]> wrote:

> My goal here is to argue that there is at least one way of operating MLS
> in a deniable mode, pretty much regardless of what the protocol itself
> does.  If this argument seems plausible to folks, it should then be safe to
> make some changes that had been gated on deniability concerns:
>
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Raphael Robert <[email-masked]>
Date: Fri, 23 Oct 2020 17:05:49 +0200

Hi Richard,

I’m fully aligned on the idea that we have to revisit past choices and define more clearly what we want to achieve in terms of deniability. As you say, having one way of achieving that is what we should aim for.
The lead that the core protocol should be agnostic to the question of deniability/unlinkability also really resonates. I do however have some concerns with the approach you propose. Concretely, it looks like you are proposing to choose between one the following:

a) Have a bootstrap protocol to distribute deniable signature keys to all potential future members, or
b) Add members to groups without being able to authenticate them right away

For me a) is not very practical, I don’t see how you can do that without losing the asynchronicity of the MLS bootstrapping mechanism. And b) is simply very dangerous, because you send encrypted messages to members that are not authenticated.

Again, I’m all for addressing the authentication concerns, but if we want to claim that MLS has a deniable mode we should describe one that is actually practical. I don’t have a good comprehensive proposal to make at this point, the only thing I can think of right now is that we reduce the scope of deniability to just cover application messages. In that case we could say that the MLSPlaintext framing application messages can be signed with deniable signature keys (small spec adaptation necessary). The signing member who just have to make sure all recipients have the deniable signature key, but that doesn’t break asynchronicity, the member can just fan out those keys when needed. With that proposal we would however punt on membership deniability. 

For completeness, there were quite a few talks about deniability in different forums over the past years. Folks have very varying views on the question, often with good arguments. We discussed concepts like publishing signature keys after a while or using time-lock puzzles. In certain scenarios this can work, but it is equally simple to find scenarios where this doesn’t work so well. So the minimum attempt was to limit what signatures cover, and it turns out that this comes at a certain price.

Raphael

> On 22 Oct 2020, at 20:38, Chelsea Komlo <[email-masked]> wrote:
> 
> Hi Richard,
> 
> This approach of per-conversation non-attributable signing keys ensures "conversation/participation unlinkability", which implies deniability.
> 
> This is certainly a viable option for implementations at a level above MLS, with the caveat that it has sharp edges as nothing in MLS forces signing keys to be used for exactly one group. Further, ensuring both async conversations and single-use-keys may be tricky.
> 
> It would be great for future versions of MLS to think about how to move deniability within the protocol itself, but most importantly I think it is best to keep the core protocol simple to understand and implement. Allowing deniability protections to be implemented at a layer above MLS seems like a good compromise towards finalizing the first version of the protocol. 
> 
> Best,
> Chelsea
> 
> On Thu, Oct 22, 2020 at 11:50 AM Richard Barnes <[email-masked] <mailto:[email-masked]>> wrote:
> Hey all,
> 
> Some recent and soon-to-be-proposed changes involving signatures over the group's ratchet tree have raised concerns about the deniability of the protocol.  I'd like to propose that we can safely punt deniability to a different layer, and not worry about it in the core protocol.
> 
> The basic idea here is that signing keys only need to be denied to the degree they are associated with an identity, so if the Authentication Service is deniable, all artifacts generated by MLS are as well.
> 
> * MLS credentials have no meaningful identity data (e.g., BasicCredential with identity=H(public_key))
> * Group members authenticate one another by exchanging signature public keys over a 1:1 deniable channel (e.g., X3DH)
> 
> (Here we have instantiated a distributed, deniable Authentication Service as a full mesh of 1:1 deniable channels.)  In this setup, as far as an external observer knows, the whole group could have been generated by a single participant, which seems like a not-bad definition of deniablity.  The MLS messages could be generated by anyone holding the relevant signature private keys, and the deniable signature key distribution means that anyone in the group could be the holder of those private keys.
> 
> This model is still compatible with things like pre-publishing KeyPackages for asynchronous add.  You could obviously do an "add first, authenticate when the joiner comes online" scheme.  You might also be able to do something more proactive by pre-publishing some deniable data along with the KeyPackage.
> 
> My goal here is to argue that there is at least one way of operating MLS in a deniable mode, pretty much regardless of what the protocol itself does.  If this argument seems plausible to folks, it should then be safe to make some changes that had been gated on deniability concerns:
> 
> * Updating #406 so that the GroupPublicState is signed by the member that issues it
> * Updating the path hash / parent hash scheme as recommended in Joël's forthcoming proposal (and which I expect will look like what Benjamin and Karthik suggested back in January)
> 
> I would also be open to adding something like the above discussion to the architecture document, if people thought it would be useful for posterity.
> 
> Best,
> --Richard
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> 
> 
>