Re: [MLS] Revisiting Deniability

Brendan McMillion <> Fri, 14 April 2023 15:21 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 0D21EC151B2C for <>; Fri, 14 Apr 2023 08:21:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.094
X-Spam-Status: No, score=-2.094 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id c06xO-rBNtgh for <>; Fri, 14 Apr 2023 08:21:06 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::32c]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by (Postfix) with ESMTPS id E7DDEC14F749 for <>; Fri, 14 Apr 2023 08:21:05 -0700 (PDT)
Received: by with SMTP id ca22-20020a056830611600b006a3c1e2b6d2so11320240otb.13 for <>; Fri, 14 Apr 2023 08:21:05 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20221208; t=1681485665; x=1684077665; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=7YVK4Zt57l83EmGJlQFBFAvd6P8wHwjk+Z7sA1ByGDI=; b=IC24HH4JElj8tvBGGX8qMr9mgqMlviIK8JHOQUUJxHLickFccT75d9M+KPg1712SJ3 z0Y/5n+swlRQ1LDIusS/NlCm0iQ4L1oWGAUFbY6Zi+kgSu1/lUeOC9q7YwI26Un8hL8Q bguTx6mupu8uZIxQ6h0A8rJo/1bpRf31d6VBXhWsa49PEQSQtGyR9ROHuODtlE/Cc9nS DJgns4ROuS8yiURz1yzzGpRtROI+FTmCCcAK50UmAd2l3muyewFar6xBd6dBKo7rZgqo WTnByHsUfQdKu1WuSG6JHHEjZHLGIuXJNXQfdmBPV/LRve6tSDeqaLaziqzxStyYdyju 5YMw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20221208; t=1681485665; x=1684077665; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=7YVK4Zt57l83EmGJlQFBFAvd6P8wHwjk+Z7sA1ByGDI=; b=VpBk1PeoluuEmBeRTp9oP3Mo1HmRyzpFMcPsnwH3MGCjxp6+8629SBc923NLDQ2Joi o/RAup9dLZy/l/9Io44U4ZsezawJza/2y1F5HH1ODIK83pmwBrtziUtEc+6dj+vz0LaV q/VLU+503e+58KMN46G82tsHYJTA0uEGC3K/G/IQJ/XYpw472Uu/sv0D3rqLgyQ14flt V+98RPvBd1MTRoQ3OzJXz6qu4S+nFRpCegliNmdWmV0zgLwCaUXtewgN8RFb2djPDKw6 yunkg/viTsWgpov0Lh8Ohc0TzY9pJSR9oFFmLg306ZNWFTwgVs37PomGYyvOvPMw6jx4 LK1w==
X-Gm-Message-State: AAQBX9f1iIUtrhFMaNnW7ir0YX8N+4oFbS2WeTI8guVcBk3mTvVGfhL0 f1F7RBN/Vv9IcTi8Gw9gqxeP97wSOkpp/Scf+hQeqGap
X-Google-Smtp-Source: AKy350ZUmnI0uZRSRYD/JIhJHkLQy3A3z3JXX6GpiGPKdw1MnA+pfly4jd9kwlUW7aJAJ/MPBwMr8fsw3I6N50aBZAs=
X-Received: by 2002:a9d:6a95:0:b0:6a4:2e21:12f6 with SMTP id l21-20020a9d6a95000000b006a42e2112f6mr1590771otq.4.1681485664897; Fri, 14 Apr 2023 08:21:04 -0700 (PDT)
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
From: Brendan McMillion <>
Date: Fri, 14 Apr 2023 08:20:53 -0700
Message-ID: <>
To: Konrad Kohbrok <>
Content-Type: multipart/alternative; boundary="000000000000c04efd05f94d633a"
Archived-At: <>
Subject: Re: [MLS] Revisiting Deniability
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 14 Apr 2023 15:21:10 -0000

Thanks Konrad

On Thu, Apr 13, 2023 at 11:26 PM Konrad Kohbrok <> wrote:

> Hi Brendan,
> I share your concern about key publishing in that I think it certainly
> has some sharp edges. However, as long as you have key expiration times
> that fit your needs for asynchronicity and your clients have reasonably
> synchronized local time, it should generally be doable.

The problem with approaches that require eventually disclosing your private
key, is that information is undeniable for some amount of time and then
suddenly it's forgeable. So you have this really ugly trade-off of either
disclosing your private key sooner than later to protect your deniability,
with the consequence that any users who haven't come online recently can't
trust the legitimacy of your messages when they do come online. Or waiting
longer to disclose your private key, to the point where the messages you
send are functionally undeniable.

Thinking about it further, I'm not even sure that this approach achieves
deniability if a malicious user can, say, use a blockchain to memorialize
that a given signed message existed before the private key would've been

Regarding the incompatibility of key publishing and key transparency in
> general, I'm not sure I understand the problem. With the AS being an
> abstract component, you could have intermediate keys that are
> client-signed (and later published) with a (non-deniable) top-level
> client key that is then potentially signed by some more central, trusted
> entity and that can be uploaded to a key transparency service.
> All that being said, we are working on a extension document that takes a
> bit of a different approach (that I believe has also been discussed in
> the past, if not on the list, then during interims). Instead of going
> for deniability for all messages, the document will introduce a new
> message type akin to application messages that allows signatures by
> deniable keys. Not including signatures on handshake messages and leaf
> nodes makes things quite a bit easier.
> A member joining a group will have to distribute their "deniable
> signature key" to each other group member individually via direct
> messages (for which we also have a document drafted up). Direct messages
> in turn rely on the DH-based AuthEncap and AuthDecap functions of HPKE,
> which makes them deniable (in the pairwise sense).

If I'm understanding your description correctly, then group membership
would not be deniable since handshake messages are signed normally. Which I
think likely falls short of what most of the people who need deniability
would accept.

> Since both documents (deniable application messages and direct messages)
> define extensions, we're waiting for the extensions document s.t. they
> are compatible with the language and the API defined in that document.
> Cheers,
> Konrad
> Am 12.04.23 um 23:41 schrieb Brendan McMillion:
> > Hi @mls
> >
> > In the past, the working group came to consensus that the best way to
> > support deniability in MLS was to make the authentication layer
> > deniable. That is to say, the protocol would continue using
> > non-repudiable signatures as normal, and however users come to associate
> > a signature public key with a user identity would just need to be
> deniable.
> >
> > I don’t really like this model because deniable authentication is
> > incompatible with a transparent authentication mechanism like Key
> > Transparency. I think we definitely want the Authentication Service to
> > *not* be able to deniably distribute malicious public keys for users. We
> > want a strong guarantee that we’re actually talking to the user we think
> > that we are, while still not being able to prove to a third party that
> > our conversation actually happened. This is akin to TLS where the
> > authentication layer (a certificate from a CA) is transparent and
> > non-repudiable, while the encryption layer (TLS itself) is deniable.
> >
> > There have also been several proposals for deniability in MLS that rely
> > crucially on users disclosing their private key after some amount of
> > time has passed. I don’t think this approach is great either given that
> > MLS is an asynchronous protocol and users are supposed to be allowed to
> > be offline for significant amounts of time.
> >
> > In short, to resolve this, I think we should probably publish an
> > extension document on using the protocol with “deniable signatures”.
> > “Deniable signature” is in quotes because that’s not a real primitive.
> > But roughly, we want to authenticate messages with a value that is: 1.)
> > a function of the message the user is sending, 2.) publicly verifiably
> > correct, and 3.) computable by either the user sending the message or
> > all other users of the group in collusion.
> >
> > There are a few options for how to construct this that come to mind:
> >
> > - Pairwise Signatures/MACs. Users authenticate each message with a
> > series of signatures/MACs, where each signature/MAC key is known only by
> > that user and one other user in the group, for each recipient user.
> >
> > - Verifiable Key Escrow like [1] or [2]. Users sign their messages with
> > a private key that is verifiably escrowed to all other users of the
> group.
> >
> > - NIZKPOK of a Signature. Users sign their messages with a private key
> > but instead of revealing the signature directly, they publish a
> > non-interactive zero-knowledge proof of knowledge of the signature. The
> > challenges in the non-interactive proof are generated with a trapdoor
> > function, where the trapdoor can be recovered by all other users of the
> > group in collusion. This makes the zero-knowledge proof simulatable (and
> > hence deniable) with knowledge of the trapdoor. A good trapdoor function
> > might be something like [3].
> >
> > Is there group interest in publishing such a document? Is there anyone
> > else that wants to help write it?
> >
> > 1.
> > <>
> > 2.
> > <>
> > 3.
> > <>
> >
> >
> > _______________________________________________
> > MLS mailing list
> >
> >
> _______________________________________________
> MLS mailing list