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
>