Re: [MLS] Revisiting Deniability

Konrad Kohbrok <> Fri, 14 April 2023 06:26 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 9FDE0C159A24 for <>; Thu, 13 Apr 2023 23:26:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.795
X-Spam-Status: No, score=-2.795 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, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_NONE=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 ZBB6ynAvUvrE for <>; Thu, 13 Apr 2023 23:26:02 -0700 (PDT)
Received: from ( []) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by (Postfix) with ESMTPS id C17E0C151B3A for <>; Thu, 13 Apr 2023 23:25:59 -0700 (PDT)
Received: from ( [IPv6:2001:67c:2050:b231:465::2]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-384) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by (Postfix) with ESMTPS id 4PyRKH1s7Cz9sT3 for <>; Fri, 14 Apr 2023 08:25:55 +0200 (CEST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=MBO0001; t=1681453555; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=+113ZnUf4ZNgZzpPyR20c2HH0T0I6G2LawUWzgz8COM=; b=Yy6y4mBGnrCfFIFm3RHt86bpDX1b6vGUcHXIDQcaFNQoed9zo4YFyG2X3DkfRwhLUW9qNC DNHp/7JW0fN8ACKeiptvQ051Pm+avZ3rtSEZ/jU9QUw3sqOYyjc+E4Tk1DdHKcKenI3WA9 3kuWE7kDEFvG3pbwRzPIUccIWGKFH4dBTZ4AqyJv+gO6m5sHHvmXcdVMzF13OdsVV81I+L 98YqfnnzheRyjfUILwfSaSCqcngGG/V8pvgaJqzVg4MexlamJrGMEZio9Rk2glZxxcGckH 8+SFJHXaYLX65Y1lU5Bm02Kak4Lz+3PiK2Z+q+l0+cwApNY8wWOBATRzA6lHcA==
Message-ID: <>
Date: Fri, 14 Apr 2023 08:25:54 +0200
MIME-Version: 1.0
Content-Language: en-US
References: <>
From: Konrad Kohbrok <>
In-Reply-To: <>
Content-Type: text/plain; charset="UTF-8"; format="flowed"
Content-Transfer-Encoding: 8bit
X-Rspamd-Queue-Id: 4PyRKH1s7Cz9sT3
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 06:26:06 -0000

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.

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).

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.


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