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

Andreas Hülsing <ietf@huelsing.net> Wed, 06 May 2020 09:51 UTC

Return-Path: <ietf@huelsing.net>
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 C659E3A0895 for <cfrg@ietfa.amsl.com>; Wed, 6 May 2020 02:51:12 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.798
X-Spam-Level:
X-Spam-Status: No, score=-1.798 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
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 kBzriKk5BV6C for <cfrg@ietfa.amsl.com>; Wed, 6 May 2020 02:51:09 -0700 (PDT)
Received: from www363.your-server.de (www363.your-server.de [78.46.179.9]) (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 86E833A07EA for <cfrg@irtf.org>; Wed, 6 May 2020 02:51:09 -0700 (PDT)
Received: from sslproxy03.your-server.de ([88.198.220.132]) by www363.your-server.de with esmtpsa (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (Exim 4.89_1) (envelope-from <ietf@huelsing.net>) id 1jWGhm-0006AJ-7F for cfrg@irtf.org; Wed, 06 May 2020 11:51:06 +0200
Received: from [77.173.230.115] (helo=[192.168.2.83]) by sslproxy03.your-server.de with esmtpsa (TLSv1.3:TLS_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from <ietf@huelsing.net>) id 1jWGhm-0005HK-34 for cfrg@irtf.org; Wed, 06 May 2020 11:51:06 +0200
To: cfrg@irtf.org
References: <AD42E3BB-8AF2-4FC9-9407-9A8D8D5130B4@gmail.com> <429061fff35b4c3a910c948360ddd552@blackberry.com> <D33D73A2-BD9C-48F4-BF87-604E7B9A28C0@gmail.com>
From: =?UTF-8?Q?Andreas_H=c3=bclsing?= <ietf@huelsing.net>
Message-ID: <933ca5df-d5a7-166e-c2c3-0c2c2838d6db@huelsing.net>
Date: Wed, 6 May 2020 11:51:05 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.7.0
MIME-Version: 1.0
In-Reply-To: <D33D73A2-BD9C-48F4-BF87-604E7B9A28C0@gmail.com>
Content-Type: multipart/alternative; boundary="------------684E1B07199259BB4F8645D5"
Content-Language: en-US
X-Authenticated-Sender: ietf@huelsing.net
X-Virus-Scanned: Clear (ClamAV 0.102.2/25803/Tue May 5 14:19:25 2020)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/Loj0fizKQlGmN9LhAJaR08sOUmQ>
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: Wed, 06 May 2020 09:51:13 -0000

I might miss something, but you also require collision resistance for
the KDF in this case (which is non-standard afaik), right?

Best,

Andreas

On 28-04-2020 14:30, Neil Madden 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
>> <mailto: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
>> <mailto:cfrg-bounces@irtf.org>> *On Behalf Of *Neil Madden
>> *Sent:* Monday, April 27, 2020 10:12 AM
>> *To:* CFRG <cfrg@irtf.org <mailto: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