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

Paul Grubbs <pag225@cornell.edu> Thu, 07 May 2020 20:38 UTC

Return-Path: <pag225@cornell.edu>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C9CFA3A0D6B for <cfrg@ietfa.amsl.com>; Thu, 7 May 2020 13:38:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
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, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=0.1, 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=cornell.edu
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ZBD7KBBmKlxA for <cfrg@ietfa.amsl.com>; Thu, 7 May 2020 13:38:06 -0700 (PDT)
Received: from mail-qk1-x736.google.com (mail-qk1-x736.google.com [IPv6:2607:f8b0:4864:20::736]) (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 05F3E3A0D79 for <cfrg@irtf.org>; Thu, 7 May 2020 13:38:05 -0700 (PDT)
Received: by mail-qk1-x736.google.com with SMTP id f13so1110265qkh.2 for <cfrg@irtf.org>; Thu, 07 May 2020 13:38:05 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cornell.edu; s=g.20171207; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=aGdGn48+fO4rXIUpt36Nck/ezTLNe6coGvfisOfklEo=; b=Xmk64g5nc8clsfbQEdNNoS2HcA7sVKcxxCM8IS8ehS9TxrQ3zxMaMTZyhx/u9Nlbi4 IlXlmU99RJO+WA5jyOcSrVIXSGtTD7bP8Mati3eNGudj/aGCPPpips19zUXxXuWfXvkn oZ809lcZzBQEYh+7c5+HSQbeiHPROOkZUAd8KevpwYAI84P0DlBroOWKs/VvMNohguFg pfoDSU0Cta3xA9XRNkPigu0W60qJkBPSpznKFapVhb7iOsdyimPyba2VH0BYAR6GCgoa 2a1ghDjo9fnouWNi+i2EWv7sdkKN2Gkc4XrhMJDWK3IHRP+OihGSg4EgisvLxejEfSBL d8Ng==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=aGdGn48+fO4rXIUpt36Nck/ezTLNe6coGvfisOfklEo=; b=JvdjwAUlLBAsKmOv4s1N3YDN/9kr3SheTHgUCR5W0HeTQ0ggfi4F190Wvgev1vZ9bB r36Ci72pfbMyqv0SrZRg12m4kIW655a550XnVdok+NXFyqVcfUSE8qwdHM5Xl1oIoI4K kkjEIiTkGp3c1g7auMEK5co/SgX7F5MtWOAuPInXnhkW/mFs5qU4ppXn9vcUqWXtoGin eDbt2AMotyFH8Z3uPqRpjRxCfX2P4CMGEP8bzCa0SZ2+n7cICqMhdVsCogqDCBbkuswZ NgT56DDzXFQoRavnStGuZFPPspKWuVW6x9xZpViATwJZxJdkrVvT0xUNBBNk2eqVUKNl gZ8Q==
X-Gm-Message-State: AGi0PubGEf82sx5Dp07e7wTcWleVTeVoiRyFBCXC0vT5sdKFXwC+kBMX 8B5OLfTqtqN2JxqeZ1DdLaLIoPAukd16Ukn7ogUBRg==
X-Google-Smtp-Source: APiQypLvRdvHUa9yuLO0E6IvJ5bbrwoUucGiiSwcS33ezjbLDBsNh9elvTOB8nv0U+lzEUGeXs7Dabs3EfDXeJqAisg=
X-Received: by 2002:a37:a886:: with SMTP id r128mr16125514qke.148.1588883884531; Thu, 07 May 2020 13:38:04 -0700 (PDT)
MIME-Version: 1.0
References: <BY5PR00MB067649378A2A81223287AFACF5A50@BY5PR00MB0676.namprd00.prod.outlook.com> <D3787AE7-37D5-41DC-AB66-1FB2EE192031@gmail.com>
In-Reply-To: <D3787AE7-37D5-41DC-AB66-1FB2EE192031@gmail.com>
From: Paul Grubbs <pag225@cornell.edu>
Date: Thu, 7 May 2020 16:37:53 -0400
Message-ID: <CAKDPBw_pRy9JW2AWgehoxg1dRPM5g+vB6wJJymvSUaMnRc4GKg@mail.gmail.com>
To: Neil Madden <neil.e.madden@gmail.com>
Cc: Mike Jones <Michael.Jones@microsoft.com>, CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="00000000000086f7b405a514db22"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/TtawgHaPTgHD4suYJaP0CO0IJTw>
Subject: Re: [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: Thu, 07 May 2020 20:38:14 -0000

Oops - Neil, I interpreted your earlier message to mean that JOSE does
indeed only support GCM. (My apologies for not checking this before
replying.)

On Thu, May 7, 2020 at 11:16 AM Neil Madden <neil.e.madden@gmail.com> wrote:

> The issue is not that JOSE only supports GCM (it doesn’t). The issue is
> that JOSE supports GCM and allows that choice independently of the key
> agreement algorithm. Hence if GCM is not appropriate for this new algorithm
> then I need to add text forbidding it in this context - i.e. that
> implementations MUST reject a JWE with “alg”:”ECDH-1PU+A128KW” and
> “enc”:”A256GCM” for example.
>
> On 7 May 2020, at 16:10, Mike Jones <Michael.Jones@microsoft.com> wrote:
>
> I’m confused by the statement “JOSE only supports GCM”.  There’s an IANA
> registry for JOSE algorithms at
> https://www.iana.org/assignments/jose/jose.xhtml#web-signature-encryption-algorithms
>  and any additional desired algorithms can be added there.
>
>                                                        -- Mike
>
> *From:* Cfrg <cfrg-bounces@irtf.org> *On Behalf Of *Neil Madden
> *Sent:* Thursday, May 7, 2020 7:27 AM
> *To:* pag225@cornell.edu
> *Cc:* CFRG <cfrg@irtf.org>
> *Subject:* : [Cfrg] Multi-recipient public key authenticated encryption
>
> That is interesting, thanks. JOSE does also support AES-CBC + HMAC (EtM),
> so it may perhaps then be simpler to forbid the use of GCM for
> multi-recipient messages in this spec and save myself a lot of trouble. It
> seems from your papers that CBC+HMAC is one of the schemes you looked at
> and it would be compactly committing, so this is fortunate.
>
>
>
> On 7 May 2020, at 14:39, pag225@cornell.edu wrote:
>
>
> Oh ok, it’s too bad JOSE only supports GCM. You should be careful with
> using plain GCM in these multi-receiver settings - because it’s
> non-committing, it’s possible to craft a single ciphertext that different
> receivers decrypt to different plaintexts.
>
>
> On May 7, 2020, at 7:28 AM, Neil Madden <neil.e.madden@gmail.com> wrote:
>
> Apologies, I forgot to respond to this. I think the ccAE approach is a
> nice way of solving the problem. Unfortunately, JOSE allows specifying the
> key exchange algorithm and AEAD cipher entirely independently so I have to
> have a solution that works with the AES-GCM based AEADs that are already
> part of the standard. But I will read these papers closely, because I do
> think the security notions are very similar to what I’m trying to achieve.
>
> — Neil
>
>
> On 28 Apr 2020, at 16:14, Paul Grubbs <pag225@cornell.edu> wrote:
>
> I think you can get away without the additional hash of the ciphertext
> entirely if you use a compactly committing AEAD (ccAE) scheme [1]. A ccAE
> has a two-part ciphertext C = (C1, C2) with the property that C2 is a
> binding commitment to the plaintext and key. At least intuitively, then,
> using C2 in the KDF prevents a receiver from modifying the message. (This
> is morally similar to including the MAC tag in the KDF, as suggested, but
> sidesteps questions about MAC security and may be faster if optimal-rate
> schemes like HFC [2] are used.) I haven't analyzed this construction
> formally, though, so take this advice with a bit of salt.
>
>
> [1] https://eprint.iacr.org/2017/664
> [2] https://eprint.iacr.org/2019/016.pdf
>
> On Tue, Apr 28, 2020 at 8:30 AM Neil Madden <neil.e.madden@gmail.com>
> wrote:
>
> Thanks, section 5 of the eprint is very useful. In that you discuss the
> solution of including the MAC tag in the KDF and you say that this requires
> collision resistance of the MAC, where I had previously assumed only 2nd
> preimage resistance would be enough. As I understand it, the potential
> attack is that if Charlie has access to an Alice-oracle by which he can get
> Alice to authenticate arbitrary messages to himself and Bob then he can use
> this to perform a collision search to find two messages with the same MAC
> tag (if the MAC is not collision resistant).
>
> I think this active attack would also apply to my proposed solution using
> a hash of the authenticated ciphertext as input to the KDF. So my assertion
> that 2nd preimage is enough is only valid for passive attacks, and full
> collision resistance would be needed in general. That also means that if I
> do pick SHA-256 to be consistent with existing use in JOSE then the
> security against such attacks would be limited to ~128 bit level. Perhaps
> that’s an incentive for me to also change the KDF in the scheme from JOSE’s
> existing Concat-KDF to HKDF with SHA-512.
>
> I think the same attack would also apply to saltpack [1], if I understand
> correctly? In saltpack a per-recipient MAC is calculated over a SHA-512 of
> the ciphertext.
>
> [1] https://saltpack.org/encryption-format-v2 (scroll down to Payload
> Packets)
>
> Best,
>
> Neil
>
>
> On 27 Apr 2020, at 16:19, Dan Brown <danibrown@blackberry.com> wrote:
>
> Hi Neil,
> I too have encountered this interesting and well-known (perhaps not
> widely-known) problem.
> See https://eprint.iacr.org/2005/056.pdf. (Section 5).
> See https://tools.ietf.org/html/rfc3278#section-4.1.2 the very short
> “note”.
>
> I forget the details of the various claimed past solutions, but will try
> to remember, maybe in a couple weeks.  Meanwhile, since the problem is
> fresh in your mind, and you might try to make sense the couple of old
> suggestions above, though I expect your knowledge has already advance past
> this old stuff.
>
> Best regards,
>
> Dan
>
> *From:* Cfrg <cfrg-bounces@irtf.org> *On Behalf Of *Neil Madden
> *Sent:* Monday, April 27, 2020 10:12 AM
> *To:* CFRG <cfrg@irtf.org>
> *Subject:* [Cfrg] Multi-recipient public key authenticated encryption
>
> 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://urldefense.proofpoint.com/v2/url?u=https-3A__tools.ietf.org_html_draft-2Dmadden-2Djose-2Decdh-2D1pu-2D03&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=mf6j6fOClApRsArWE9wqI1rEGUVkfxZ0aXWmn35nK_c&m=pABr2aBl1c_ofW8vypgq6rz4tGVZWkxu0IU_RSNb_L4&s=E_agQvNgeBlLsyPF6xyJ1TFQLBAJsGTY1FJf7EK3iqs&e=>
>
> Kind regards,
>
> Neil Madden
> ------------------------------
> This transmission (including any attachments) may contain confidential
> information, privileged material (including material protected by the
> solicitor-client or other applicable privileges), or constitute non-public
> information. Any use of this information by anyone other than the intended
> recipient is prohibited. If you have received this transmission in error,
> please immediately reply to the sender and delete this information from
> your system. Use, dissemination, distribution, or reproduction of this
> transmission by unintended recipients is not authorized and may be unlawful.
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>
>
>