Re: [lamps] [EXTERNAL] Re: hashed public key for "BSI" KEMTLS

["Markku-Juhani O. Saarinen" <[e-mail]>]

On Thu, Mar 25, 2021 at 2:42 PM Panos Kampanakis (pkampana) <
[e-mail]> wrote:

> > The core question here is whether externalized public keys (and
> signature values?) as a hash+url is worth spending effort on given the
> expected size of PQC algs? Does the footgun-ness outweigh the potential
> usefulness?
>
>
>
> Personally, I would like to avoid drastic changes to (D)TLS/QUIC/SSH etc
> altogether unless there is no other choice. But as I have said before, if
> one or two of the PQ lattice based signatures don’t get standardized we
> will have to get creative. That could include externalized public keys in
> DNS or URLs with fancy caching mechanisms, KEMTLS with fancy caching
> mechanisms and more. These come with their complications of course.
>

Hi Panos,

Yep.. I'd note that KEMTLS has performance advantages too with the
structured lattice algorithms likely to be selected for mainstream use --
which can be faster to compute than pre-quantum algorithms. They have pk
and ct sizes of only up to 2kB so referencing/caching makes little sense
for them. I personally expect KEMTLS to see use with the big cloud
providers.

I wouldn't push the public key cache mechanism to TLS/QUIC/SSH itself,
while I'd hope/expect KEMTLS to be there. However, if the cache mechanism
is just an encoding in the cert, using off-band techniques (a la CRLs) to
fetch the pk blob, then it doesn't modify the protocol spec too much to
facilitate this admittedly niche application.

The caching / pk size complexities here arise just from the specific types
of use cases that we're dealing with right now. Since proprietary solutions
for these PQC use cases already exist, perhaps it would still be preferable
to document it within IETF too (at least the cert format).


> Nothing wrong with investigating options now of course. Another question
> about the hash+url proposal is the rest of the cert chain. Is it
> big_heavy_sig_algo with hash+urls? Is it cached and fetched occasionally as
> well? More complications there, but worth thinking about it.
>

Apologies for discussing national standards and detailed use cases again..
I appreciate that these requirements are just one part of the picture, but
I also think that it's appropriate that IETF PKI engineering is informed by
such things.

So.. to recap, the Germans have already chosen the PQC KEM algorithms and
parameters that they recommend [1], NIST has already released the final SP
800-208 [2], and XMSS and LMS have a likely-pass NSS [3] status. These are
not algorithms that I would necessarily personally prefer, but here we are.

So an ultra-conservative customer is seeking long-term quantum resilience
for trusted comms links. They have a "PQC" PKI with an XMSS root, and
possibly an XMSS immediate too. All XMSS ops are with an HSM that can
manage the state. This signature solution is also used for other purposes,
such as system updates.

In comms they can live with a limited number of signatures -- signatures
are only in these certificates and endpoint authentication is with KEM
decapsulation in KEMTLS.  XMSS signatures are 2500 bytes, public keys are
64 bytes, so the cert chains are long but manageable if the subject public
key is referenced with a hash.

The caching mechanism is not particularly fancy (essentially a web cache --
integrity checking of the blob is via the hash).  Wrt DoS;  if the URL is
invalid as that would mean that the CA has signed the invalid URL. An
attempt to fetch the final subject public key is performed only after cert
signature verification. There will be a full handshake retry if this fetch
is successful.

Cheers,
- markku

[1]
https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.pdf
[2] NIST, "SP 800-208: Recommendation for Stateful Hash-Based Signature
Schemes", October 2020. https://doi.org/10.6028/NIST.SP.800-208
[3]
https://www.nsa.gov/What-We-Do/Cybersecurity/NSAs-Cybersecurity-Perspective-on-Post-Quantum-Cryptography-Algorithms/

Dr. Markku-Juhani O. Saarinen <[e-mail]> PQShield, Oxford UK.


>
>
>
>
>
> *From:* Spasm <[e-mail]> *On Behalf Of *Mike Ounsworth
> *Sent:* Thursday, March 25, 2021 12:33 AM
> *To:* Panos Kampanakis (pkampana) <pkampana=[e-mail]>;
> Markku-Juhani O. Saarinen <[e-mail]>
> *Cc:* [e-mail]; Ryan Sleevi <[e-mail]>; Russ Housley <
> [e-mail]>
> *Subject:* Re: [lamps] [EXTERNAL] Re: hashed public key for "BSI" KEMTLS
>
>
>
> Thanks Ryan and Panos.
>
>
>
> I wasn’t really intending this draft to be a formal submission, just a
> hastily-written thing to illustrate the concept. I take your points that
> this is a simple concept with a ton of implementation landmines.
>
>
>
> The core question here is whether externalized public keys (and signature
> values?) as a hash+url is worth spending effort on given the expected size
> of PQC algs? Does the footgun-ness outweigh the potential usefulness?
>
>
>
> ---
>
> *Mike* Ounsworth
>
>
>
> *From:* Panos Kampanakis (pkampana) <pkampana=[e-mail]>
> *Sent:* March 24, 2021 10:10 PM
> *To:* Markku-Juhani O. Saarinen <[e-mail]>
> *Cc:* [e-mail]; Russ Housley <[e-mail]>; Ryan Sleevi <
> [e-mail]>; Mike Ounsworth <[e-mail]>
> *Subject:* RE: [lamps] [EXTERNAL] Re: hashed public key for "BSI" KEMTLS
>
>
>
> > There are other elements to think through, such as the aforementioned
> document/email signing case. Since domains and URIs come and go, the CT
> problem isn’t really a “CT” problem: it’s a problem with offline scenarios.
>
>
>
> I would also add the concerns spelled out in Section 5 and the Sec
> Consideration of https://tools.ietf.org/html/rfc7924#section-7
>
>
>
>
>
> *From:* Spasm <[e-mail]> *On Behalf Of *Ryan Sleevi
> *Sent:* Wednesday, March 24, 2021 7:09 PM
> *To:* Mike Ounsworth <Mike.Ounsworth=[e-mail]>
> *Cc:* [e-mail]; Markku-Juhani O. Saarinen <[e-mail]>; Russ
> Housley <[e-mail]>
> *Subject:* Re: [lamps] [EXTERNAL] Re: hashed public key for "BSI" KEMTLS
>
>
>
> I’m not sure I fully understand the GeneralName approach. Are you
> imagining a situation where a user is going to look up within EDI or an
> X.400 directory? Since few implementations support anything other than LDAP
> and HTTP URIs, and since the various GREASE efforts (and X.509 itself) have
> shown arbitrary extensibility continues to be a security and
> interoperability tirefire, we should keep it as simple as possible. We can
> always use an extra OID if we need to, and any new transport will require
> updating clients anyways, so there’s no harm.
>
>
>
> The only other GeneralName that even makes sense is otherName, but you
> already have extensibility via URI schemes, so it’s a superfluous encoding.
> Several of these are vestigial carryovers from X.509 that don’t make any
> sense in a “PKIX” world of the Internet.
>
>
>
> I’m definitely with Russ that the principle here is easy, and I think this
> draft more or less gets close, but I would strongly encourage just
> IA5String for a URI. This seems like it should fully cover the non-TLS
> cases mentioned.
>
>
>
> The other concern I would have is that 2.1 and 2.2 are unnecessarily
> ambiguous and flexible. If the goal is to model after RFC 5280, then it
> should be explicit about the transport coding (and mime types, as
> appropriate). “DER or Base64” is a bit awkward, even when constrained to
> just HTTP URIs.
>
>
>
> This was some discussion of this approach in the past. For example, IETF
> 101’s minutes for LAMPS tracks some of that context and discussion,
> including the “like LogoTypes” suggestion.
>
>
>
> While I don’t really expect IETF drafts to cover the implementation
> challenges, I think it’s worth thinking carefully about the protocol state
> machine through all of this. For example, you’d have to decide early on in
> the handshake, before the peer has proven their possession of the key even,
> to both verify a certificate and de-reference a potentially Very Large
> Blob. Depending on your threat model, such verification could be a huge
> amplification of work factor, creating DoS possibilities.
>
>
>
> Even if you “only” support HTTP as a transport, you still have to figure
> out a caching story and the relevant headers (e.g. as RFC 5019 had to do),
> since those can also have application impact, even if it’s “just” an
> implementation detail.
>
>
>
> There are other elements to think through, such as the aforementioned
> document/email signing case. Since domains and URIs come and go, the CT
> problem isn’t really a “CT” problem: it’s a problem with offline scenarios.
>
>
>
> On Wed, Mar 24, 2021 at 4:58 PM Mike Ounsworth <Mike.Ounsworth=
> [e-mail]> wrote:
>
> Hi Russ,
>
>
>
> Yeah, that’s exactly the structure I came up with also, though I would use
> a GeneralName for the location to give the same amount of flexibility as
> AIA does.
>
>
>
> While chatting with Markku, I threw my thoughts into I-D format just to
> write out the ASN.1 and security considerations that come to mind.
>
>
>
> https://datatracker.ietf.org/doc/draft-ounsworth-pq-external-pubkeys/
>
>
>
> At this point WE ARE NOT asking for review of this draft. WE ARE NOT
> looking for a debate on specific PQC algorithms.
>
>
>
> WE ARE asking if anyone can remember historical discussions of
> externalized pubkeys or signatureValues in certificates. What were the pros
> / cons? WE ARE asking if this is a problem space worth re-visiting in light
> of the pubkey and sig sizes we expect to see with PQC algorithms.
>
>
>
> References:
>
> The only similar work I’m aware of is IKEv2 (RFC 7296) which supports “Hash
> and URL of X.509 certificate” over HTTP (ie the whole cert, not just the
> pub key / sig). Though we did find this 2018 paper by Panos, Dan Van Geest,
> et. al [1] which says
>
>
>
> > To address these concerns, RFC7296 defines the use of a hash and an URL
> that serve the certificate in order to avoid sending it over UDP. This
> method is almost never used in IKEv2 deployments today.
>
>
>
>
>
> [1]: https://eprint.iacr.org/2018/063.pdf
>
>
>
> ---
>
> *Mike* Ounsworth
>
>
>
> *From:* Spasm <[e-mail]> *On Behalf Of *Russ Housley
> *Sent:* March 24, 2021 12:49 PM
> *To:* Markku-Juhani O. Saarinen <[e-mail]>
> *Cc:* [e-mail]
> *Subject:* [EXTERNAL] Re: [lamps] hashed public key for "BSI" KEMTLS
>
>
>
> WARNING: This email originated outside of Entrust.
> DO NOT CLICK links or attachments unless you trust the sender and know the
> content is safe.
> ------------------------------
>
> Markku:
>
>
>
> I would like to avoid discussion of the algorithms that are supported by
> various governments around the world.  It is clear that they will not make
> the same choices.  However, so far, I have not see algorithm identifiers
> assigned for PQC candidate algorithms.
>
>
>
> RFC 3709 does something like you are talking about for logos.  The idea is
> that the certificate contains a hash of the object that will be obtained
> from the URI.  In this way, the web server cannot swap the public key.  I
> am assuming that the object returned will be a SubjectPublicKeyInfo.
>
>
>
> A structure like this will work:
>
>
>
>    PublicKeyReference ::= SEQUENCE {
>
>      hashAlg AlgorithmIdentifier,
>
>      refHash OCTET STRING,
>
>      refURI IA5String }
>
>
>
> Russ
>
>
>
>
>
> On Mar 24, 2021, at 1:13 PM, Markku-Juhani O. Saarinen <[e-mail]>
> wrote:
>
>
>
> Hello,
>
> We've been doing some engineering for a customer who has a requirement for
> post-quantum cryptography using the German BSI recommended algorithms
> (category 3 or 5 FrodoKEM or Classic McEliece [1-2]). Yes, I'm aware of
> their respective statuses in the NIST PQC competition -- but this is
> essentially an active German government requirement.
>
> The KEMTLS [3] mechanism would allow certificate-based authentication (in
> addition to the key establishment) using a KEM such as these two.
>
> Classic McEliece has particularly large public keys (261,120 to 1,357,824
> bytes) but only 128 to 240-byte ciphertexts. The transmission of those
> large public key is only required as a part of the public key certificate.
>
> QUESTION: We'd like to transmit certificates still, but replace the big
> public key subject blob (subjectPublicKey) with an appropriate construct
> that contains just a secure hash of the key a reference (such as an URL)
> from where that data can be obtained off-line (if it is not cached).
>
> What would be the "best" way of doing this?  Mike Ounsworth has already
> kindly proposed an encoding for it (that he may choose to share on this
> list), but we're wondering if this sort of thing has been done before and
> how/where.
>
> Rationale: This would knock off 1MB from certificates, making them match
> current certificate sizes and flows. As noted, the ciphertext itself is
> shorter than an RSA ciphertext. The same "compressed"/"cached" certificate
> format could also be used for other PKI applications in that same "McEliece
> BSI user" scenario (e.g. e-mail and messaging).
>
>
>
> Note that there is also a PQC finalist signature algorithm with a similar
> profile; Rainbow has 60,192 to 1,930,600 byte public keys but 66 to
> 212-byte signatures. We don't have a current engineering requirement for it
> though, and its fate and parameter selection looks a bit uncertain in view
> of some recent analysis (also NSS folks have expressed reservations on it).
>
>
>
> Cheers,
> - markku
>
> [1] BSI. "Cryptographic Mechanisms: Recommendations and Key Lengths."
>  Technical Guideline TR-02102-1. March, 2020.
> https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.pdf
> <https://urldefense.com/v3/__https:/www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.pdf__;!!FJ-Y8qCqXTj2!PVS70xPSSnZiShFmeREght7e7BmADK2MzBPEEeUsPQkkeoDd6sbURJYHV_ayRXadVA3DXryp5A$>
> [2] BSI. "Migration zu Post-Quanten-Kryptografie." Handlungsempfehlungen
> des BSI. August, 2020.
> https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Krypto/Post-Quanten-Kryptografie.pdf
> <https://urldefense.com/v3/__https:/www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Krypto/Post-Quanten-Kryptografie.pdf__;!!FJ-Y8qCqXTj2!PVS70xPSSnZiShFmeREght7e7BmADK2MzBPEEeUsPQkkeoDd6sbURJYHV_ayRXadVA0WO3wkOQ$>
>
> [3] P. Schwabe, D. Stebila, and T. Wiggers. "Post-quantum TLS without
> handshake signatures." ACM CCS 2020, October 2020. https://ia.cr/2020/534
> <https://urldefense.com/v3/__https:/ia.cr/2020/534__;!!FJ-Y8qCqXTj2!PVS70xPSSnZiShFmeREght7e7BmADK2MzBPEEeUsPQkkeoDd6sbURJYHV_ayRXadVA1C5JeFYg$>
>
>
>
> Dr. Markku-Juhani O. Saarinen <[e-mail]> PQShield, Oxford UK.
>
> _______________________________________________
> Spasm mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/spasm
> <https://urldefense.com/v3/__https:/www.ietf.org/mailman/listinfo/spasm__;!!FJ-Y8qCqXTj2!PVS70xPSSnZiShFmeREght7e7BmADK2MzBPEEeUsPQkkeoDd6sbURJYHV_ayRXadVA3sKApRXA$>
>
>
>
> _______________________________________________
> Spasm mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/spasm
>
>