Re: [CFRG] How will Kyber be added to HPKE (9180)?

Thank you for this post.

I had this reply buffered, for a while, hopefully it's not too late to ask.

Is there a generic way to convert a KEM to a DSA?

It would be sad to be forced to use a composite scheme with kyber in order
to use an AKEM with HPKE.

I'm also not sure the AKEM in your post and the auth modes for HPKE are
consistent.

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.

...which leads to a lurking suspicion about composite schemes for HPKE.

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