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

Mihir Bellare <> Fri, 08 May 2020 20:49 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 404AC3A0ED9 for <>; Fri, 8 May 2020 13:49:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Afv09X7Bo3dk for <>; Fri, 8 May 2020 13:49:30 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::533]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id A74FB3A0ED7 for <>; Fri, 8 May 2020 13:49:29 -0700 (PDT)
Received: by with SMTP id s10so2384760edy.9 for <>; Fri, 08 May 2020 13:49:29 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=vFj4NEV3nFjHtY2noin/Zm2TBcWxun97VmwzU8s3TbU=; b=cK41VUrL5+i1yJzI3ZXQXtplQQCXjHza6wO9pSEYT8ngn/YwLifcF3T72jfxxA0/P4 9GyH1bm0Lhj3e55PtdtKTKpreib7HRYFQzY6SAtxRIutnIt1hpwiGAxDX1vtxBoRVtxX t8aNLiGK92j9DgX1bpuvrfecW5DNUytvELYbo=
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=vFj4NEV3nFjHtY2noin/Zm2TBcWxun97VmwzU8s3TbU=; b=JWslUsxfG5qPLqTQhhmIt9YAk3/jCEjQwD+T7u6NW1nYIMZ36UukX6ACLMIdmGxf4S 1AfkjoOBwY2W5mGLjRzF5kXGfnHiYIEITWUMbYOtQZF4rCSMajLmwAYzgZ7OBp/jHhYc bG/4HLL30syb38+PrC99PekQJSfsKfUdqs0g9AXzbVyxp7jej+4O9NEdYFtTdXU91GFR trgP1j4zjumrBDi11ZV0fnbtIyjHbLqUeAEWMROpSrhyGGGCEOpbiXeKuunDGmgixLRc s0gbQTd38GcARZI2J4A5nhImnhuM6YJr8TJoMLu0U8mNHeGKd7+7op3YnUGVnG59YdVX u2Fw==
X-Gm-Message-State: AGi0PuaUb+sSrcPFJtpQPGv1OmAckj34xmR0DIv9mXALafJmLvNfbmsx vXZPr9II8GYFzyK8aTD34Nro/phL71UQsocmN1A37Q==
X-Google-Smtp-Source: APiQypJXl1Up/XN09iUl/tB3xfRWgHiSHUbk5iX1yg0l4aOxv26UGBxq/yrt9V64pNIEHywcM0eKrLNSHM5Iq4r1dj8=
X-Received: by 2002:a05:6402:21cc:: with SMTP id bi12mr3845917edb.294.1588970967648; Fri, 08 May 2020 13:49:27 -0700 (PDT)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: Mihir Bellare <>
Date: Fri, 08 May 2020 13:48:51 -0700
Message-ID: <>
To: Neil Madden <>
Cc: CFRG <>
Content-Type: multipart/alternative; boundary="00000000000015e66f05a5292254"
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: Fri, 08 May 2020 20:49:35 -0000

Public-key authenticated encryption is, I think, what in the literature is
called Signcryption.
While early formulations were single recipient, a multi-recipient
formulation is given in Section 3 of
This defines security goals of privacy, authenticity, and one that combines
them, in two forms, insider and outsider, depending on whether or not the
adversary is a key holder.
It sounds from what you say that what you want may be insider security.
The above paper does not give schemes of the form you give. My question is
that, perhaps, do the definitions capture what you want to target?


On Mon, Apr 27, 2020 at 7:12 AM Neil Madden <> wrote:

> Hi all,
> I am working on an enhancement to the JOSE standards and would like
> feedback from members of CFRG about solutions to a particular issue if any
> of you have time.
> In JOSE currently if you wish to create a message that has both
> confidentiality and sender authentication using public key cryptography
> then the only option is to both sign and then encrypt the message. This is
> expensive because it involves multiple passes over the message and results
> in a very bulky nested message structure with two layers of base64-encoding.
> Given that many uses of this sign-then-encrypt pattern do not require the
> strong security properties of signatures, I have proposed [1] a public key
> authenticated encryption mode based on NIST’s one-pass unified model from
> SP 800-56A. This avoids the nested structure and means that you don’t need
> multiple cryptographic primitives. The proposed algorithm uses two ECDH key
> agreements: one between the sender’s ephemeral private key and the
> recipient’s long-term public key; and a second between the two parties’
> long term keys. The two shared secrets are concatenated and passed through
> a KDF along with some context arguments. For a single recipient this
> achieves sender authentication (subject to replay), and the single
> recipient case is what I am primarily concerned about.
> (If you squint this is also roughly similar to the Noise framework “K”
> one-way pattern, but my hands are waving quite a lot here).
> To support multiple recipients I copied the existing pattern used in
> JOSE’s ECDH-ES+A256KW algorithm family in which the message is encrypted
> using a random Content Encryption Key (CEK) and then the CEK is encrypted
> for each recipient using AES-KeyWrap with the ECDH-derived key. As I then
> mention in the security considerations this leads to any recipient being
> able to produce a forgery using that CEK and claim it came from the
> original sender:
>    When Key Agreement with Key Wrapping is used, with the same Content
>    Encryption Key (CEK) reused for multiple recipients, any of those
>    recipients can produce a new message that appears to come from the
>    original sender.  The new message will be indistinguishable from a
>    genuine message from the original sender to any of the other
>    participants.  To avoid this attack, the content SHOULD be encrypted
>    separately to each recipient with a unique CEK or a nested signature
>    over the content SHOULD be used.
> Because I am primarily interested in single-recipient use cases, this
> seemed like an acceptable trade-off. However, I have since been contacted
> by people who would like to use this draft for multi-recipient messages and
> would not like to fall back on a nested signature structure.
> An initial proposal was to solve this by simply including the MAC tag from
> the content encryption in either the per-recipient payload (encrypted using
> AES-KeyWrap) or as an additional context field to the KDF. But the MAC is
> computed using the CEK that is known to all recipients, so for this to be
> secure would require second preimage resistance of the MAC with a known
> key, which cannot be guaranteed for JOSE because it supports content
> encryption using AES-GCM for which second preimages can be trivially
> computed if you know the key.
> Assuming that a per-recipient MAC is too much overhead, an alternative
> would be to include a collision-resistant hash of entire ciphertext (and IV
> and associated data) in the KDF. This is unfortunate as it requires another
> pass over the entire message when we’ve already encrypted and MACed, but it
> appears to be a solution and at least is no more inefficient than the
> original signed-then-encrypted approach which also needs to hash the entire
> message.
> So two questions:
> 1. Is including a hash (e.g., SHA-512) of the ciphertext (assuming
> symmetric AE) in the per-recipient KDF calculation sufficient to prevent
> forgeries in the multi-recipient setting?
> 2. Are there more efficient alternatives that don’t assume 2nd preimage
> resistance of the underlying symmetric MAC?
> [1]:
> Kind regards,
> Neil Madden
> _______________________________________________
> Cfrg mailing list