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

[Mike Ounsworth <[e-mail]>]

I don’t have any data, but I imagine that over time we’re seeing an increased usage of TLS in closed networks where you’re doing repeated connections to the same peers. Taking public keys out of certs and allowing them to be cached or delivered out of band seems like a bandwidth win for this “zero-trust, mutual-auth TLS everywhere” backend deployment model that’s becoming popular.

Example: you could imagine a Kubernetes ServiceMesh issuing to each container a hash+url cert, and it mounts to each container a keystore file with everybody’s public keys. In this example since the keystore is mounted from the host filesystem, you wouldn’t even need a url in the cert, just the hash, and you could get away with Rainbow or GeMSS with super tiny signatures.

---
Mike Ounsworth

From: Spasm <[e-mail]> On Behalf Of Panos Kampanakis (pkampana)
Sent: March 25, 2021 3:20 PM
To: Markku-Juhani O. Saarinen <[e-mail]>
Cc: [e-mail]
Subject: Re: [lamps] [EXTERNAL] Re: hashed public key for "BSI" KEMTLS

Hi Markku,

> 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 mechanism is not particularly fancy (essentially a web cache -- integrity checking of the blob is via the hash). […]

If I am not misunderstanding you, that means the client will fetch the server cert out of band with every connection. In that case that is new TCP handshake and multiple round-trips to the web cache, which I will admit is probably closer than the server. Worse case, pushing a McEliece cert in a typical Internet scenario it will be a new connection plus 6-7 round trips from client to web cache instead of 5-6 round trips from client to server (if you were not using web caches). Which one is faster? Probably the former, but I am not 100% sure, it depends on the client-to-cache or client-to-server paths. Now if you cache the server cert locally on the client and you don’t fetch it every time, you have some other concerns brought up previously.

Just bringing some concerns up. The method could work overall based on the usecase and the algorithms you can play with, as Ryan S. pointed out.

Generally speaking, I am a little skeptical about KEMTLS because of the drastic changes it brings with implicit/explicit auth, and encrypting before fully authenticating. I am also skeptical about the significance of the advantages it brings over lattice based sig finalists too. I brought these points up in Sofia & Thom’s post as well http://disq.us/p/2ehcccj . I see KEMTLS as a potential TLS 1.4 with new security analyses, state machines etc.



From: Markku-Juhani O. Saarinen <[e-mail]<mailto:[e-mail]>>
Sent: Thursday, March 25, 2021 2:32 PM
To: Panos Kampanakis (pkampana) <[e-mail]<mailto:[e-mail]>>
Cc: [e-mail]<mailto:[e-mail]>
Subject: Re: [lamps] [EXTERNAL] Re: hashed public key for "BSI" KEMTLS

On Thu, Mar 25, 2021 at 2:42 PM Panos Kampanakis (pkampana) <[e-mail]<mailto:[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]<mailto:[e-mail]>> PQShield, Oxford UK.




From: Spasm <[e-mail]<mailto:[e-mail]>> On Behalf Of Mike Ounsworth
Sent: Thursday, March 25, 2021 12:33 AM
To: Panos Kampanakis (pkampana) <pkampana=[e-mail]<mailto:[e-mail]>>; Markku-Juhani O. Saarinen <[e-mail]<mailto:[e-mail]>>
Cc: [e-mail]<mailto:[e-mail]>; Ryan Sleevi <[e-mail]<mailto:[e-mail]>>; Russ Housley <[e-mail]<mailto:[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]<mailto:pkampana=[e-mail]>>
Sent: March 24, 2021 10:10 PM
To: Markku-Juhani O. Saarinen <[e-mail]<mailto:[e-mail]>>
Cc: [e-mail]<mailto:[e-mail]>; Russ Housley <[e-mail]<mailto:[e-mail]>>; Ryan Sleevi <[e-mail]<mailto:[e-mail]>>; Mike Ounsworth <[e-mail]<mailto:[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]<mailto:[e-mail]>> On Behalf Of Ryan Sleevi
Sent: Wednesday, March 24, 2021 7:09 PM
To: Mike Ounsworth <Mike.Ounsworth=[e-mail]<mailto:Mike.Ounsworth=[e-mail]>>
Cc: [e-mail]<mailto:[e-mail]>; Markku-Juhani O. Saarinen <[e-mail]<mailto:[e-mail]>>; Russ Housley <[e-mail]<mailto:[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]<mailto:[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]<mailto:[e-mail]>> On Behalf Of Russ Housley
Sent: March 24, 2021 12:49 PM
To: Markku-Juhani O. Saarinen <[e-mail]<mailto:[e-mail]>>
Cc: [e-mail]<mailto:[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]<mailto:[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]<mailto:[e-mail]>> PQShield, Oxford UK.
_______________________________________________
Spasm mailing list
[e-mail]<mailto:[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]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/spasm