[MLS] Revisiting Deniability

Brendan McMillion <brendanmcmillion@gmail.com> Wed, 12 April 2023 21:41 UTC

Return-Path: <brendanmcmillion@gmail.com>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 883B5C1522D9 for <mls@ietfa.amsl.com>; Wed, 12 Apr 2023 14:41:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -7.094
X-Spam-Status: No, score=-7.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_DNSWL_HI=-5, 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: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id ECy8UKwfLqeH for <mls@ietfa.amsl.com>; Wed, 12 Apr 2023 14:41:13 -0700 (PDT)
Received: from mail-ot1-x332.google.com (mail-ot1-x332.google.com [IPv6:2607:f8b0:4864:20::332]) (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 ietfa.amsl.com (Postfix) with ESMTPS id 4AAA8C152574 for <mls@ietf.org>; Wed, 12 Apr 2023 14:41:13 -0700 (PDT)
Received: by mail-ot1-x332.google.com with SMTP id 39-20020a9d04aa000000b006a1370e214aso4496124otm.11 for <mls@ietf.org>; Wed, 12 Apr 2023 14:41:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1681335672; x=1683927672; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=MQInq2ujEvDsZauGw6SQHRjXvjXs6P1OQocP3G10Y/4=; b=TytXYwwg34URSkIYqHk+s83roPkPuNsXFdnxGksks5dA1eEq+fm9OjN6ZT9tO6Pmcj vQkLPEsGaijIGXxrGH3Wt5tKsLNzJ9cHeZJ8pFKXPQ1iKf17ruQ/k/JVYEPKGkhxhieo 4rCTSEYooJqrPVkvqC4M0b9jJ4LcwjmnFw0oukJMegK3/OIa7aRyZ1AfUGAFzylIQNew NWcDI2ifRt5ruEEp6iw9Jy3A+5BaC+WpQyyP+byNR85oGfCwvzuZ8o7q4hGKMbj7o79d SXvqre7UTTrj+ZglgP9MKkCoYuZk7/9yMs8oy/Qs5W4qWYZliXJomGonigFAhCx4v2Jw ITDg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1681335672; x=1683927672; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=MQInq2ujEvDsZauGw6SQHRjXvjXs6P1OQocP3G10Y/4=; b=CwSGmso9jCw1kV8tCbCeXt8eupQjSVQBX8btDAJVpMO56xGuHPr5E/QvAozwGI2Vdz UBdKIdAQpEWTWvf6XKSF4lKAZEO0FPLjlZIjExQhDl3wdVHKyxSReNEKmnX3RiUwy+8u jwqmgigBhmafG/9aF32nmIz2hlfgFmiV0G92uxPdOnC0MqXJQk0sPpeRM06s0u8ASlBj 3HIb2V25W3xAnG+f8o0tjQA2QioMBD1Iu93FlOFXF36BzqkRlEAMkYPI+YGGPGL5Xhoh 3uSfyuUUAdHaxxkWxvYoEnIXgY25g8s4TaIJ2kVsi5uym0wLDJ3KVti153r+cEzKRcj8 USmw==
X-Gm-Message-State: AAQBX9fOIVJYCcb14S2d3rqwSV1MJZMihIsXVUS+d+w09y+PAsoo5AKd vYveIxxnps+xnW1abxLt9DprUxtlDZ2nr9O/ARheIMDJz/w=
X-Google-Smtp-Source: AKy350bmAjVlnVZRIl7XI5+92RrPkgdWi0dSc0kFCXNWESZq1EcLWnkSJ8a3DN2zsWzMm0A9Cxkp6Ki4Yj7MnSx1w+k=
X-Received: by 2002:a05:6830:83:b0:6a3:934f:b741 with SMTP id a3-20020a056830008300b006a3934fb741mr5099792oto.4.1681335671963; Wed, 12 Apr 2023 14:41:11 -0700 (PDT)
MIME-Version: 1.0
From: Brendan McMillion <brendanmcmillion@gmail.com>
Date: Wed, 12 Apr 2023 14:41:01 -0700
Message-ID: <CAJTd26Kvo9uaNgZ5rMD2rOimYL0naAtv5RjtbsM_nsTs=r43Rw@mail.gmail.com>
To: MLS List <mls@ietf.org>
Content-Type: multipart/alternative; boundary="00000000000079c2d205f92a77a1"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/geIgIDNnR5hIKUIZtJ2RYgMAmVE>
Subject: [MLS] Revisiting Deniability
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 12 Apr 2023 21:41:17 -0000

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

Is there group interest in publishing such a document? Is there anyone else
that wants to help write it?

1. https://github.com/ZenGo-X/dlog-verifiable-enc
2. https://www.shoup.net/papers/verenc.pdf
3. https://eprint.iacr.org/2018/529.pdf