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

Dan Brown <danibrown@blackberry.com> Mon, 27 April 2020 16:38 UTC

Return-Path: <danibrown@blackberry.com>
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 5A1DD3A0DF1 for <cfrg@ietfa.amsl.com>; Mon, 27 Apr 2020 09:38:02 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, 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=blackberry.com
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 wYut6dq3F50Y for <cfrg@ietfa.amsl.com>; Mon, 27 Apr 2020 09:37:56 -0700 (PDT)
Received: from smtp-pg10.blackberry.com (smtp-pg10.blackberry.com [68.171.242.226]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id F2BF63A0A10 for <cfrg@irtf.org>; Mon, 27 Apr 2020 09:37:54 -0700 (PDT)
Received: from pps.filterd (mhs400ykf.rim.net [127.0.0.1]) by mhs400ykf.rim.net (8.16.0.27/8.16.0.27) with SMTP id 03RGbnto041730; Mon, 27 Apr 2020 12:37:49 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blackberry.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : mime-version; s=corp19; bh=RFjbfqrlzPiEson3DbCgbAeKZ4fyiSdJ3QM3HDARn3Q=; b=ZXPwCvaSNgGL3n7nLdlpu62HZEPOzBjnzLfgzHEIm63gEGwQNnpTDpw4vaG/9I8fS8x4 FDqmj53VtFfR8jrKwUKPr4nfhbfhxOPb+UWbxdyDYb5e2aoZIwVaF29AZsysIrPRO6DE KM/8ib8wrAUOcEZykJOYoXtVSyerhEfAZzz9Kqjj7RM351+K+gnRIVlwD/UPg+3UDcR6 Rgy9vkAUyWLR1/vS/64S/uptClbBDI+1c6I8CvnOlwAxVaJM5EzS2pHLdwOisbcq5f8s suxf5/h0kyGAeNVhffqw/uzjDhmFDibYh++QKxxX5552zYqptVPI+C6qHIikVmxg2Rh0 hw==
Received: from xch213cnc.rim.net (xch213cnc.rim.net [10.3.27.118]) by mhs400ykf.rim.net with ESMTP id 30mhd5cf1c-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT); Mon, 27 Apr 2020 12:37:49 -0400
Received: from XCH210YKF.rim.net (10.2.27.110) by XCH213CNC.rim.net (10.3.27.118) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1913.5; Mon, 27 Apr 2020 12:37:48 -0400
Received: from XCH210YKF.rim.net ([fe80::81ca:ad34:fc3:5ce8]) by XCH210YKF.rim.net ([fe80::81ca:ad34:fc3:5ce8%5]) with mapi id 15.01.1913.007; Mon, 27 Apr 2020 12:37:48 -0400
From: Dan Brown <danibrown@blackberry.com>
To: Neil Madden <neil.e.madden@gmail.com>
CC: Paul Grubbs <pag225@cornell.edu>, CFRG <cfrg@irtf.org>
Thread-Topic: [Cfrg] Multi-recipient public key authenticated encryption
Thread-Index: AQHWHJ3sAo0Oxh6TOE2cxrrC/lIO9KiNVcmAgAAMF4D//734oIAARyWA///CQcA=
Date: Mon, 27 Apr 2020 16:37:48 +0000
Message-ID: <aa28d6f3189943929c112cc4355f1841@blackberry.com>
References: <AD42E3BB-8AF2-4FC9-9407-9A8D8D5130B4@gmail.com> <CAKDPBw_CDUpwtPTbvxW9xSb3Yhgv=RNoAsOwyaZJRBNVvaHg1A@mail.gmail.com> <6532256B-18E2-47E3-91EF-D18FBF339742@gmail.com> <e2394c5d2bbd441ab8222cf6831bdc5c@blackberry.com> <EB54637D-7D05-4133-A221-7E47C4974241@gmail.com>
In-Reply-To: <EB54637D-7D05-4133-A221-7E47C4974241@gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [100.64.97.99]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=2.16.840.1.101.3.4.2.1; boundary="----=_NextPart_000_0202_01D61C90.A7BBA810"
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.138, 18.0.676 definitions=2020-04-27_12:2020-04-27, 2020-04-27 signatures=0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/wwrQfDSryIrbEaXgr1yUMOHIyDI>
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: Mon, 27 Apr 2020 16:38:03 -0000

Hi Neil,

My bad.  On KCI, I think you are right.  Oops, I forgot this, sorry!

If Alice wishes to deny sending the message, one way is to have Bob equally able to generate it.  But this exposes Bob to KCI.  

Maybe the state-of-the-art has a better way to solve this.

Dan

 

From: Neil Madden <neil.e.madden@gmail.com> 
Sent: Monday, April 27, 2020 12:12 PM
To: Dan Brown <danibrown@blackberry.com>
Cc: Paul Grubbs <pag225@cornell.edu>du>; CFRG <cfrg@irtf.org>
Subject: Re: [Cfrg] Multi-recipient public key authenticated encryption

 

Yes, this is also discussed in the security considerations in section 4 of the draft.

 

I’m not aware of a solution to KCI in a single message without using signatures, but would be interested if there is anything out there.

 

The first version of the draft suggested how a two-message interactive handshake can be built from the basic ECDH-1PU construct that is roughly similar to the Noise KK two-way handshake pattern and would also prevent KCI. I was encouraged to drop that part as liable to corrupt the youth.

 

PS - thanks for the two references in the previous message, they are very useful and describe exactly the same problem.

 

— Neil





On 27 Apr 2020, at 17:00, Dan Brown <danibrown@blackberry.com <mailto:danibrown@blackberry.com> > wrote:

 

Hi Neil,

I recall that “unified model” is well-known to lack some security property. Maybe, key-compromise impersonation (KCI)?

If Eve has Bob’s private key, can Eve impersonate Alice?

E.g. replace ECDH(alice_private, bob_public) by ECDH(bob_private, alice_public)?

Dan

 

From: Cfrg <cfrg-bounces@irtf.org <mailto:cfrg-bounces@irtf.org> > On Behalf Of Neil Madden
Sent: Monday, April 27, 2020 11:54 AM
To: Paul Grubbs <pag225@cornell.edu <mailto:pag225@cornell.edu> >
Cc: CFRG <cfrg@irtf.org <mailto:cfrg@irtf.org> >
Subject: Re: [Cfrg] Multi-recipient public key authenticated encryption

 

The details of the original proposed scheme are in the linked draft or are in NIST SP 800-56A. To summarise, if Alice wants to encrypt a message and send it to both Bob and Charlie she carries out the following steps (with some minor details of syntax elided):

 

1. Generate a random CEK and use it to encrypt the message content using some symmetric AEAD scheme producing authenticated ciphertext, C.

2. kek_bob = KDF(ECDH(ephemeral_private, bob_public) || ECDH(alice_private, bob_public) || context_bob)

3. kek_charlie = KDF(ECDH(ephemeral_private, charlie_public) || ECDH(alice_private, charlie_public) || context_charlie)

4. bob_box = AES-KW(kek_bob, CEK)

5. charlie_box = AES-KW(kek_charlie, CEK)

6. Send bob_box || charlie_box || ephemeral_public || C

 

Here the context arguments are typically the public keys involved and any additional identifiers for the parties involved. The new proposal is to also mix in SHA-512(C) into this KDF calculation as additional context.

 

The threat model here is that Alice sends a message to Bob and Charlie stating that Bob is in charge while she is on holiday. Charlie uses the shared CEK to create a new message saying “Oops, I meant that Charlie is in charge.” and sends that to Bob with the original encrypted keys (i.e., Charlie just replaces C). This new message from Charlie validates as if it came from Alice. I’d like to stop this kind of attack.

 

My assertion is that if you mix SHA-512(C) into the KDF calculation then Charlie needs to find a 2nd preimage of SHA-512 to pull off this attack. (I’m using SHA-512 as an example, actually JOSE already uses SHA-256 in its KDF so I’ll probably use that).

 

— Neil






On 27 Apr 2020, at 16:10, Paul Grubbs < <mailto:pag225@cornell.edu> pag225@cornell.edu> wrote:

 

This sounds like a really interesting question, but I'm having trouble understanding your proposed scheme - can you give a bit more detail? 

 

I also don't quite understand the threat model. Are you trying to prevent a malicious receiver from "forging" a new payload that looks like it came from the sender?

 

On Mon, Apr 27, 2020 at 10:12 AM Neil Madden < <mailto:neil.e.madden@gmail.com> neil.e.madden@gmail.com> 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]:  <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=KlOwyf9hUXlVGjlgt8Wi940vBk4gshSudWFblTPOqqw&s=hl600UzfUwE0mwdBn12J1fBTXatCOOKthaRGKw9n6ZM&e=> https://tools.ietf.org/html/draft-madden-jose-ecdh-1pu-03

 

Kind regards,

 

Neil Madden

_______________________________________________
Cfrg mailing list
 <mailto:Cfrg@irtf.org> Cfrg@irtf.org
 <https://urldefense.proofpoint.com/v2/url?u=https-3A__www.irtf.org_mailman_listinfo_cfrg&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=mf6j6fOClApRsArWE9wqI1rEGUVkfxZ0aXWmn35nK_c&m=KlOwyf9hUXlVGjlgt8Wi940vBk4gshSudWFblTPOqqw&s=Zsd48TBtVxnczibcn8zmbWpsdpRyprK6NbobiMEqaec&e=> https://www.irtf.org/mailman/listinfo/cfrg

 

  _____  

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.

 

----------------------------------------------------------------------
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.