Re: [CFRG] How will Kyber be added to HPKE (9180)?
Thom Wiggers <thom@thomwiggers.nl> Tue, 29 November 2022 11:28 UTC
Return-Path: <thom@thomwiggers.nl>
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 E2D83C14F722 for <cfrg@ietfa.amsl.com>; Tue, 29 Nov 2022 03:28:33 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.096
X-Spam-Level:
X-Spam-Status: No, score=-2.096 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, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=thomwiggers.nl
Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id fsJs2lV04NpF for <cfrg@ietfa.amsl.com>; Tue, 29 Nov 2022 03:28:29 -0800 (PST)
Received: from mail-pj1-x1032.google.com (mail-pj1-x1032.google.com [IPv6:2607:f8b0:4864:20::1032]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 7776AC14CE5C for <cfrg@irtf.org>; Tue, 29 Nov 2022 03:28:29 -0800 (PST)
Received: by mail-pj1-x1032.google.com with SMTP id v3-20020a17090ac90300b00218441ac0f6so1177407pjt.0 for <cfrg@irtf.org>; Tue, 29 Nov 2022 03:28:29 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=thomwiggers.nl; s=google; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=CSwutWBNwW00NVu6jTEFL1YosJ4fSL532ruxv6PjS9g=; b=Wx4rGYGzzb517uYeru0f4tvexNW8vQBQnvGpjQbpIbPxqLP+IMzbzOe3RL2ibrZu7p tG4LEWyzLiEWWqudJz9LOCP0Em4WwUUxvdX2BNJG7+ryVTJIFiGXlDxs2PXjBRvHi/RX +iS1XCYMDxa6jvLJ7OPbQ9VNknggdLPU/RMro=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=CSwutWBNwW00NVu6jTEFL1YosJ4fSL532ruxv6PjS9g=; b=odLqd8cGtIE4z/TWoX49UEHNQo7BD9Q0hpE5ctw25dLc+57jmjlFBL4T8wAcw3V7Fk 1TgqpcrfsNF/o77RUyIi0S42X2FkT5Fe4RbKaZ3bqiDufnwBt7cDHmAnjg2eqq/94YAq I3o3b6/eRiU/B4LIxM16/k4QzbNbh9RFJXkDj2YE0J0iigZRB4dNCHo6DYSyZZEpWno9 KZptsZ/OUEAgEY1L9AtjvHJHu5r/Uc02NGLMuDp401xRYWabQ2mjWf6FwD40DQpb/sdw 74ivo7L97YYCda+giJeqY8+3yJyMibc7rWbcZTE1pbc1TaZFQYWVu59zUBWBpqrESTFT KGBg==
X-Gm-Message-State: ANoB5pn8GR0hQk4fzFhh5EjbDEspIv/pBCbYUtSCZ9/XoJkdXzFsWkbQ CvO5UqVXwRQGnQE8AOpQ4fYCS2AZoJNaj8T1G2PMjQ==
X-Google-Smtp-Source: AA0mqf7uxjUnpb8BcX01feVSPXEXE0He8ZG9KRs6pnM3vnC1wliOPCaI5fguRyy9EtxODlrdJbYCpGPN3giw14du2ic=
X-Received: by 2002:a17:90a:990d:b0:212:d909:a41e with SMTP id b13-20020a17090a990d00b00212d909a41emr17413150pjp.48.1669721308365; Tue, 29 Nov 2022 03:28:28 -0800 (PST)
MIME-Version: 1.0
References: <CAN8C-_KwT8M6-8_xA5mCCHrDWja3s1tH-RQjGz5eskYhNaa63w@mail.gmail.com> <61BCC306-CF0E-421C-A6A1-32226D9E417C@gmail.com> <CAN8C-_+CqLMNsbhvVdw=i7Ne8Xsin58JZPKASS-MQ-8+gpqAdA@mail.gmail.com>
In-Reply-To: <CAN8C-_+CqLMNsbhvVdw=i7Ne8Xsin58JZPKASS-MQ-8+gpqAdA@mail.gmail.com>
From: Thom Wiggers <thom@thomwiggers.nl>
Date: Tue, 29 Nov 2022 12:28:11 +0100
Message-ID: <CABzBS7mY8EMeaQYRBWU-F8FBiu+oedpeV-x+h3Gz+4ftnpoaFQ@mail.gmail.com>
To: Orie Steele <orie@transmute.industries>
Cc: Neil Madden <neil.e.madden@gmail.com>, John Mattsson <john.mattsson=40ericsson.com@dmarc.ietf.org>, CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="00000000000075a79a05ee9a499e"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/32YiTqTdeUmrWh2oJNSNmzvvy6M>
Subject: Re: [CFRG] How will Kyber be added to HPKE (9180)?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.39
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: Tue, 29 Nov 2022 11:28:34 -0000
Hi Orie, As nobody responded to your question yet, let me briefly answer them: Op ma 28 nov. 2022 om 15:59 schreef Orie Steele <orie@transmute.industries>: > Is there a generic way to convert a KEM to a DSA? > > No. Unfortunately, the days are over where "signing" and "encrypting" were basically the same algorithm (like RSA, where signing is "encrypting with the secret key"). > It would be sad to be forced to use a composite scheme with kyber in order > to use an AKEM with HPKE. > > You can't use Kyber for sender authentication in HPKE. It is simply incompatible with the API. The Diffie–Hellman-based authenticated HPKE instantiations rely on DH being a NIKE, as discussed below. > > Noting the blog post: > https://blog.cloudflare.com/hybrid-public-key-encryption/ > > Which says: > > > For example, for most post-quantum KEM algorithms there isn’t a private > key authentication variant known. > This observation is correct. In fact, many applications of "private key authentication variants" that you see in DH-based protocols are actually fundamentally incompatible with the typical encapsulate/decapsulate API of a KEM. Combining the sender's static authentication key with an ephemeral key from the receiver (sender/receiver roles per HPKE) requires that the primitive is a non-interactive key exchange (NIKE) algorithm [1]. (EC) Diffie–Hellman is a NIKE (pk_a=g^a, pk_a^s works fine), KEMs are not (encapsulate(pk_b) does not take the private key). You trivially turn a NIKE into a KEM, but the other way is not generally possible. The currently best-known PQ NIKE is CSIDH (and variants like CTIDH). CSIDH is not in the NIST standardization project, and people don't exactly agree on the security level provided by the CSIDH-512 instantiation. Additionally, CSIDH is quite computationally intensive. Hope this clears up some of your questions. Cheers, Thom [1] See https://eprint.iacr.org/2012/732.pdf for a nice formal discussion > Regards, > > OS > > > On Thu, Nov 24, 2022, 1:13 PM Neil Madden <neil.e.madden@gmail.com> wrote: > >> Not with just a KEM, no. You either need a KEM and a signature scheme or >> a richer primitive like Diffie-Hellman. >> >> I wrote a blog post about this a year ago: >> https://neilmadden.blog/2021/02/16/when-a-kem-is-not-enough/ >> >> — Neil >> >> On 24 Nov 2022, at 19:03, Orie Steele <orie@transmute.industries> wrote: >> >> >> I think I'm hearing there is no way to build something like ECDH-1PU with >> KEMs... Right? >> >> https://datatracker.ietf.org/doc/html/draft-madden-jose-ecdh-1pu-04 >> >> OS >> >> On Thu, Nov 24, 2022, 12:40 PM Neil Madden <neil.e.madden@gmail.com> >> wrote: >> >>> Right. As others have said, if all you have is a Kyber certificate then >>> you are stuck doing interactive authentication (as far as we know). If you >>> care about non-interactive authentication then getting into a situation >>> where all you have is an non-auth KEM certificate would be a bad idea. >>> >>> (If you were going to do what I suggested then the public keys for the >>> KEM and signature scheme should be combined and thus you’d have a single >>> cert for the combined algorithm rather than separate certs). >>> >>> — Neil >>> >>> On 24 Nov 2022, at 18:31, Mike Ounsworth <Mike.Ounsworth@entrust.com> >>> wrote: >>> >>> >>> >>> John Mattsson said: >>> >>> >>> >>> > I think that is a good idea. But I think the construction should >>> probably be: >>> >>> >>> >>> - Add the recipient identity to the message. >>> - Sign the message with Dilithium >>> - Encrypt [recipient ID, message, signature] with HPKE-Kyber >>> >>> >>> >>> > That is probably a good solution for CMPv3 >>> >>> >>> >>> I disagree. >>> >>> >>> >>> Take for example a Kyber certificate trying to authorize/authenticate a >>> request to the CA for its own revocation, key update, or cert renewal. All >>> you have is a KEM certificate; where do you get a Dilithium key from? >>> >>> Of course you could create an ephemeral Dilithium key, but a signature >>> from an ephemeral key is fairly useless. >>> >>> >>> >>> Some PKIs will always issue pairs of KEM / Signature certificates, but >>> you don’t get to assume this in general when designing the certificate >>> management protocol – this will be especially true if TLS AuthKEM takes >>> off and demand for KEM authentication certificates skyrockets. Plus, if >>> you’re using CertA to authorize management operations for CertB, then you >>> have to strongly establish co-ownership of the two certs, which may be >>> possible in some PKIs (for example if the CA has a consistent DN structure >>> that strongly identifies both certs as belonging to the same entity / >>> device / hardware key storage container, whatever the PKI administrator has >>> deemed to be the definition of “co-ownership” for that environment), but >>> requiring PKIs to be able to determine co-ownership of certificates would >>> be a departure from current requirements of the CMP protocol where >>> mechanisms exist for all cert types to self-administer. >>> >>> >>> >>> --- >>> >>> *Mike* Ounsworth >>> >>> >>> >>> *From:* CFRG <cfrg-bounces@irtf.org> *On Behalf Of *John Mattsson >>> *Sent:* November 24, 2022 12:01 PM >>> *To:* Neil Madden <neil.e.madden@gmail.com>; Ilari Liusvaara < >>> ilariliusvaara@welho.com> >>> *Cc:* cfrg@irtf.org >>> *Subject:* [EXTERNAL] Re: [CFRG] How will Kyber be added to HPKE (9180)? >>> >>> >>> >>> WARNING: This email originated outside of Entrust. >>> DO NOT CLICK links or attachments unless you trust the sender and know >>> the content is safe. >>> ------------------------------ >>> >>> Nail wrote: >>> >Isn't there a straightforward generic construction of an >AKEM from a >>> normal KEM plus a (PQ) signature scheme >that could be used here? i.e., >>> run the KEM and then sign >the encapsulated key? Obviously this would >>> produce quite >large encapsulations, and a "key-pair" for such an AKEM >would >>> then be two key-pairs encoded into one (with a >covering self-signature >>> to prevent tampering). In principle >this seems doable? >>> >>> >>> >>> I think that is a good idea. But I think the construction should >>> probably be: >>> >>> >>> >>> - Add the recipient identity to the message. >>> - Sign the message with Dilithium >>> - Encrypt [recipient ID, message, signature] with HPKE-Kyber >>> >>> >>> >>> That is probably a good solution for CMPv3 >>> >>> >>> >>> Cheers, >>> >>> John >>> >>> >>> >>> *From: *CFRG <cfrg-bounces@irtf.org> on behalf of Neil Madden < >>> neil.e.madden@gmail.com> >>> *Date: *Thursday, 24 November 2022 at 17:00 >>> *To: *Ilari Liusvaara <ilariliusvaara@welho.com> >>> *Cc: *cfrg@irtf.org <cfrg@irtf.org> >>> *Subject: *Re: [CFRG] How will Kyber be added to HPKE (9180)? >>> >>> >>> >>> On 24 Nov 2022, at 15:36, Ilari Liusvaara <ilariliusvaara@welho.com> >>> wrote: >>> >>> >>> >>> On Thu, Nov 24, 2022 at 02:49:33PM +0000, Mike Ounsworth wrote: >>> >>> Hi CFRG! >>> >>> Background: we are working to add KEM support to Certificate >>> Management Protocol v3 (CMPv3) (draft-ietf-lamps-cmp-updates, which >>> will eventually be 4210bis). We are planning to accomplish this by >>> supporting HPKE (RFC 9180) as a new message protection mechanism in >>> CMPv3 and hoping that we can inherit Kyber more-or-less for free once >>> HPKE supports it. >>> >>> Question "how": How will Kyber be added to HPKE? I assume there will >>> be an equivalent to section 4.1 that defines KyberKEM with its own >>> Encap(pkR), Decap(enc, skR), AuthEncap(pkR, skS), and >>> AuthDecap(enc, skR, pkS) - ie the same interfaces as for DHKEM (4.1), >>> but making use of Kyber internally? The Kyber2018 paper [1] figure 3 >>> defines an authenticated Kyber exchange that looks like it should >>> easily fit into the existing HPKE APIs. In other words, will >>> supporting 9180 now with abstractions around those 4 functions allow >>> for easy drop-in of Kyber later? >>> >>> >>> Kyber does not support AuthEncap/AuthDecap. The whole reason why Auth* >>> interfaces is optional is to allow for KEMs that do not allow non- >>> interactive authentication, like the post-quantum ones. >>> >>> In fact, the only possibly-PQC algorithm to support AuthEncap/AuthDecap >>> is CSIDH (not to be confused with totally broken SIDH/SIKE), and >>> security of that in both classical and quantum settings is subject to >>> debate. >>> >>> >>> >>> Isn't there a straightforward generic construction of an AKEM from a >>> normal KEM plus a (PQ) signature scheme that could be used here? i.e., run >>> the KEM and then sign the encapsulated key? Obviously this would produce >>> quite large encapsulations, and a "key-pair" for such an AKEM would then be >>> two key-pairs encoded into one (with a covering self-signature to prevent >>> tampering). In principle this seems doable? >>> >>> >>> >>> -- Neil >>> *Any email and files/attachments transmitted with it are confidential >>> and are intended solely for the use of the individual or entity to whom >>> they are addressed. If this message has been sent to you in error, you must >>> not copy, distribute or disclose of the information it contains. Please >>> notify Entrust immediately and delete the message from your system.* >>> >>> _______________________________________________ >>> CFRG mailing list >>> CFRG@irtf.org >>> https://www.irtf.org/mailman/listinfo/cfrg >>> >> _______________________________________________ > CFRG mailing list > CFRG@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg >
- [CFRG] How will Kyber be added to HPKE (9180)? Mike Ounsworth
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Ilari Liusvaara
- Re: [CFRG] [EXTERNAL] Re: How will Kyber be added… Mike Ounsworth
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Neil Madden
- Re: [CFRG] [EXTERNAL] Re: How will Kyber be added… Mike Ounsworth
- Re: [CFRG] [EXTERNAL] Re: How will Kyber be added… Karthik Bhargavan
- Re: [CFRG] [EXTERNAL] Re: How will Kyber be added… Ilari Liusvaara
- Re: [CFRG] [EXTERNAL] Re: How will Kyber be added… John Mattsson
- Re: [CFRG] [EXTERNAL] Re: How will Kyber be added… Mike Ounsworth
- Re: [CFRG] How will Kyber be added to HPKE (9180)? John Mattsson
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Mike Ounsworth
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Neil Madden
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Orie Steele
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Neil Madden
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Kampanakis, Panos
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Mike Ounsworth
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Ilari Liusvaara
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Blumenthal, Uri - 0553 - MITLL
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Peter Gutmann
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Mike Ounsworth
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Peter Gutmann
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Mike Ounsworth
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Richard Barnes
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Bas Westerbaan
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Orie Steele
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Blumenthal, Uri - 0553 - MITLL
- Re: [CFRG] [EXTERNAL] Re: How will Kyber be added… Mike Ounsworth
- Re: [CFRG] How will Kyber be added to HPKE (9180)? Thom Wiggers