[Cfrg] Multi-recipient public key authenticated encryption

Neil Madden <neil.e.madden@gmail.com> Mon, 27 April 2020 14:12 UTC

Return-Path: <neil.e.madden@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 4C6D93A0B43 for <cfrg@ietfa.amsl.com>; Mon, 27 Apr 2020 07:12:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.097
X-Spam-Status: No, score=-2.097 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, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=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 WFE9SmUm7g3A for <cfrg@ietfa.amsl.com>; Mon, 27 Apr 2020 07:12:11 -0700 (PDT)
Received: from mail-wm1-x330.google.com (mail-wm1-x330.google.com [IPv6:2a00:1450:4864:20::330]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4B6E13A0B42 for <cfrg@irtf.org>; Mon, 27 Apr 2020 07:12:11 -0700 (PDT)
Received: by mail-wm1-x330.google.com with SMTP id e26so19721331wmk.5 for <cfrg@irtf.org>; Mon, 27 Apr 2020 07:12:11 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:mime-version:subject:message-id:date:to; bh=pG1lcuglik04X6HexjpUiwzZzffHS0ZYwWqyjgsNz9k=; b=lru3ZlM1R3vf0rkwibHCflq9S7at5NqOwFiu7k1gu/SjcRHi1JREOCpcMhVrT6YtBG pfXAsNzOzdIv9qS27ZN9cO4IdAlmt6eHOUep5RjtIs+9ImPG9Ou1Y/TEwAMm6lauOw82 P2yn77AH7ROqIIUb2owpHHzPtRoxTvfpwZSaCGdis3g5UaNTeTV4rIAAcXwgfjyzJ4e0 iZ1n+4WhGarJEVCY51hx4/COYQfO3j/qbg/5htSmDx/R20+1LNWV3AGKMEmcTj0LYsld q+v6smZu3MWHSAq8obytISnFCbIUokCYbabaWzTYTgNcDn/jQy1iZOjOU6IkjpUxp6vE r0XQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:mime-version:subject:message-id:date:to; bh=pG1lcuglik04X6HexjpUiwzZzffHS0ZYwWqyjgsNz9k=; b=Sa5DlaRkBvayumrP4B8VepcJ6a+h59MdCES9tybrgH3kT9gyghy/49yExgTZv82Dwj rBVRwO+pL0MQFCLl2FcZe5b18VYY/R7hVWkHG0PHQY1MC/a9v0na+wOsNsIlz6kD4DKg bZ7IV5zc2x/7n0uwiQoI1LJvWsDKkwy2YP5TlOos91TRceZuvVg/eTGh4YY2+2V/2fR6 sY38rz7yAkl27+9fwHp2x+DpUepuAZGQmt21dM5MiPdOByZl6IJki3c/iJieMTCDKD3C U0q3zELMpl6pHdFjQBcUuwkPLnarsDQNfrDNpz+PC4afaMoc07moEaEN/3xZIAqUJ9hV xqcA==
X-Gm-Message-State: AGi0Pubd0kS+34RYOGP60tQcSbNO7rDStL3B23hNMapOuTnYEcfeakFp E+Jicvwe/e8q6QNeE9KZKHyyD31H2aE=
X-Google-Smtp-Source: APiQypKjkPsBXK2VmEBjwVBrHLxODwIu2xO/Vave+/mqco+O1Zyqiw+JCmLsrlfPnP6W0/ykFJ8XNw==
X-Received: by 2002:a1c:3c08:: with SMTP id j8mr26372436wma.30.1587996729162; Mon, 27 Apr 2020 07:12:09 -0700 (PDT)
Received: from [] ( []) by smtp.gmail.com with ESMTPSA id g6sm21297058wrw.34.2020. for <cfrg@irtf.org> (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Mon, 27 Apr 2020 07:12:08 -0700 (PDT)
From: Neil Madden <neil.e.madden@gmail.com>
Content-Type: multipart/alternative; boundary="Apple-Mail=_808AAE2C-A8D2-42BB-8195-2192BEDF12A8"
Mime-Version: 1.0 (Mac OS X Mail 13.0 \(3608.\))
Message-Id: <AD42E3BB-8AF2-4FC9-9407-9A8D8D5130B4@gmail.com>
Date: Mon, 27 Apr 2020 15:12:07 +0100
To: CFRG <cfrg@irtf.org>
X-Mailer: Apple Mail (2.3608.
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/iNoSj9g2cQ0JvDbHs4I70bfhrRc>
Subject: [Cfrg] Multi-recipient public key authenticated encryption
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 27 Apr 2020 14:12:14 -0000

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]: https://tools.ietf.org/html/draft-madden-jose-ecdh-1pu-03 <https://tools.ietf.org/html/draft-madden-jose-ecdh-1pu-03>

Kind regards,

Neil Madden