Re: [Cfrg] Multi-recipient public key authenticated encryption

Phillip Hallam-Baker <> Tue, 12 May 2020 18:06 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 6866F3A0898 for <>; Tue, 12 May 2020 11:06:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.396
X-Spam-Status: No, score=-1.396 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.25, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 3EJRj0iOxSuS for <>; Tue, 12 May 2020 11:06:57 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id BD25D3A088C for <>; Tue, 12 May 2020 11:06:57 -0700 (PDT)
Received: by with SMTP id a68so2761560otb.10 for <>; Tue, 12 May 2020 11:06:57 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=tW/NjitAq8QctKZ6/oEYoaeUhZPenJI/fcab+OMv59c=; b=jOoOjjG6rD/N4sWelFpNp2mcWvd1VsqnRL0D4x5HwQHVzpTnJ9NbbG8Nt7S6gx8Js0 JpP0TP9O/OMfmmYEiq+jAFQLLIzGPbiREqfm1yb2uiVGtRk7HqKOl87yYYHh+FzhK89U BXJWZba1N6xOWS0GI+W74uDp3Q1DSxhQg37fRwbx94Dbyu4wdJk/e26psaHsLv5Y2HkN FWA1TgZOWEYD2X4y5/ddtMn09SccwV9qiw4O5aDqqAW1ustd9pj5GNOAGRD+Qqq3Hlaz HZWaNax/P9uVXQEzlyQjVkpIzO772bDhx36z0rCsAOfSy7yNi3cBrANc2i0k5UHM1CeD MCIw==
X-Gm-Message-State: AGi0PuZtTzet8Ltikd/mPqMfSQGOneoP+F4VEu1HHPNF6cBijWfDRgU7 lCC3E1k4T1NHxOn9LYbk2eZ7baazWP1skBy2nK8=
X-Google-Smtp-Source: APiQypJ3w4LgWR/jZLIq4h4bOsG8qgIrxYLjEUDH2tOWGdp53n00C+UdyFYW6xrv2WrF9j8pGaVasQ/bvEaj2TVbyl8=
X-Received: by 2002:a9d:75ce:: with SMTP id c14mr17027406otl.64.1589306816697; Tue, 12 May 2020 11:06:56 -0700 (PDT)
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
From: Phillip Hallam-Baker <>
Date: Tue, 12 May 2020 14:06:45 -0400
Message-ID: <>
To: Mihir Bellare <>
Cc: Neil Madden <>, CFRG <>
Content-Type: multipart/alternative; boundary="0000000000003faa3e05a57754e3"
Archived-At: <>
Subject: Re: [Cfrg] Multi-recipient public key authenticated encryption
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 12 May 2020 18:06:59 -0000

It is an interesting question. One approach is to look at it from a systems

Alice is going to send a message to Bob, Carol and herself. She wants each
to be able to authenticate the message but without being able to prove
Alice sent it (so can't just sign).

Let us begin by assuming we are using ECDH. This means that we are going to
need a keywrap for each recipient under the agreed key. We can generate a
unique input to a MAC at the same time.

So to put the pieces together:

Alice generates an ephemeral key {g^e, e} and an encryption session key k.
She encrypts and authenticates the message resulting in a ciphertext we can
ignore at this point and an authentication tag t.

For each recipient, Alice calculates

IKM_p = (P)^e where P is the recipient public key.
kw_p = WRAP (k, HKDF (IKM, "keywrap"))
Auth_p = HMAC(t, HKDF (IKM, "tagmac"))

So each recipient has an independent verification tag that is derived from
the same key exchange used to encrypt the data for their use.

I am sure this can't be a novel construction simply because it is so
heavily constrained. If we are going to use a MAC to authenticate data, we
must encrypt to data that is only shared bilaterally. Which means we have
to look at the output of the El-Gamal key agreement. Since we have a KDF in
there already, the approach falls out naturally.

The other detail that is commonly missed out is what to do about signing.
Do we sign then encrypt or encrypt then sign?

I use a similar approach to get around the limitations of either approach.
At the protocol level it is almost invariably essential to be able to
verify the signature before decrypting. So if we only calculate one message
digest, it has to be over the ciphertext.

We can however prove that the party who had the ability to access the
plaintext approved signature by creating a witness value as a
one-way function of (k, S, MD(C)) where S is the public signature key and
MD(C) is the message digest of the content.

That is not identical as a signature over the plaintext value but it is
close enough to defeat the application protocol level attacks that come
from assumptions made about ciphertext being signed.

This does not really affect the constructs I use in DARE very much because
I generate the encryption key for each envelope from k by means of unique
per-envelope salt value and a second KDF.