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

["Panos Kampanakis (pkampana)" <[e-mail]>]

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

 

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. 

 

 

 

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] <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://urldefense.com/v3/__https:/www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Krypto/Post-Quanten-Kryptografie.pdf__;!!FJ-Y8qCqXTj2!PVS70xPSSnZiShFmeREght7e7BmADK2MzBPEEeUsPQkkeoDd6sbURJYHV_ayRXadVA0WO3wkOQ$> https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Krypto/Post-Quanten-Kryptografie.pdf

[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