[lamps] Hybrid-for-the-sake-of-security, and Composite vs Non-Composite

[Mike Ounsworth <[e-mail]>]

Thanks Dr. Alison Becker (Ali?) for the presentation on your framework. It's great to have some independent analysis here to guide the design discussions!




Point #1: Risk model:

First, I'm struggling to understand the risk model that underpins your second slide, which gives the conclusion that hybrid is not for security; only for backwards compatibility.
Could you please expand on how you reached that conclusion? I'll explain how we got to the conclusion that Hybrid-for-the-sake-of-security is highly desirable.

I understand that by the end of the NIST "competition", theoretical confidence in the winning algorithms will be high. Theoretically, in a perfect world well vetted algorithms won't contain any overlooked weaknesses, and standards bodies will produce precise specifications that everyone will implement perfectly. In the real world there were 18,000 CVEs filed in 2020 because somebody overlooked something in an implementation. Once there are FIPS specs for the PQ algorithms, how many open and closed source implementations will we be written? How many of those will have buffer overflows or timing-invariance issues or other bugs that can lead to key leakage, plaintext leakage, signature forgery, etc? How many XMSS or LMS implementations will have race-conditions or poorly thought-out backup and restore procedures that lead to private state re-use in some bizarre corner-case? How long until we stop seeing new CVEs in both PQ crypto implementations and applications that (mis)use them? If Bleichenbacher's oracle attack against RSA PKCS#1 v1.5 padding can provide a historical example, that was published in 1998, and 19 years later, a new research effort (https://robotattack.org) found a pile of implementations that were still vulnerable because implementors (and many of the big-name ones) didn't follow the spec perfectly.

I guess I'm arguing that Hybrid-for-the-sake-of-security would increase the chances of closed- and open-source PQ implementations getting the maturing time the time they need without a devastating breach in the meantime. Expect bugs, design in some defense-in-depth to give us time to patch the bugs that come up. I think dual signatures and hybrid encryption is the optimal place to build in that resiliency.
And yes, I would propose applying this equally across PQ algorithms; just because we like hash functions doesn't mean that SPHINCS+ is immune from implementation error, and strong hybrid modes would also mitigate the consequences of bungling the state-management of your XMSS private key; yes if you produced two signatures with the same state then you would still need to revoke it for key compromise, but with a layer of EC, you would have days - weeks to safely notice and take action as opposed to hours.

I also understand that backwards compatibility, ease-of-migration, ease-of-adoption, etc are in fact security goals themselves (fewer reasons to stay on the old broken stuff), so in a conflict between migratibility and cryptographic strength, migratibility wins. But I don't believe there is a conflict here; I don't believe it's Composite VS Multi-Cert; I believe the two play harmoniously together, which brings me to the next point.




Point #2: Are composite and multi-cert competing or complementary in TLS and IKE?

I would like to clarify what I (speaking for myself, not necessarily my co-authors) see as the posture for composite public keys, signatures, and content encryption:

The point is well-taken that negotiated protocols want full flexibility to negotiate and don't want to send large PQ keys to legacy clients who won't use them. Really though, nobody is proposing doing that (at least not since draft-truskovsky-lamps-pq-hybrid-x509, which was abandoned in 2018).

I think we're all imagining a similar thing where TLS servers are provisioned with multiple certs, for example an RSA cert chain + a PQ cert chain; runtime negotiation gets to choose to use one or the other or both. The question is whether the PQ cert chain should itself be composite, ie PQ := {EC, PQ} to protect against the cryptologic and implementation risks that I outline above until we have confidence in both the algorithms and their implementations.

So in my mind composite and multi-cert are complementary: do multi-cert for backwards compatibility, and bury an Ed25519 inside your PQ cert for good measure. Given the size and CPU of most PQ algs, you won't even notice it's there.



Point #3: Offline protocols
As mentioned in the LAMPS meeting, I would love to see your analysis extended to cover offline protocols (aka non-negotiated, or what I think Russ called "Sign-and-store" or "encrypt-and-store"). I propose that good subjects for this analysis are: the Microsoft X.509-based code-signing infrastructure, document (PDF) signing infrastructures, and S/MIME infrastructures.

For this section I'm going to assume a risk model that a code-signed binary or a signed/encrypted document has a security shelf-life of 30 years, during which time we can expect RSA to fall to quantum computers, or the particular PQ alg used to have a bug found in it, or both (though the "both" case is a bit hopeless unless you want to go to hybrid models with more than 2 algs).


Research / design questions for offline use-cases:
In the signing case, how does a recipient know that there should be two signatures when it only sees one? (aka stripping attacks, assuming one alg is vulnerable to forgery attacks due to the above risks).


With PQ hybrid content-encryption (I hate that PQ has overloaded this term.. maybe "multi-key encryption" would be better?), the big risk I see is that it is not the key-holder who gets to decide security, but the sender. Ex.: it is not [e-mail]<mailto:[e-mail]> that gets to choose how its encryption public keys are used, but rather the mail client that [e-mail]<mailto:[e-mail]> used to encrypt the super-secret email. In fact, the recipient doesn't even know that somebody is using their keys until the encrypted content has already crossed the internet. If we're proposing a multi-cert model here, then how does the sender know that the recipient actually has two certificates that are expected be used together? You could imagine cross-linking certs (or CAs) with some kind of extension, but A) nobody, as of yet, has proposed a spec for that, and B) that would count as new cert verification logic, which I think goes against your "Non-Composite PRO: Computational processes remain unchanged (but perhaps multiple iterations)".

I would love to see your analysis framework extended to cover these sorts of long shelf-life non-negotiated protocols because these are the ones that I feel benefit the most from composite certs.

---
Mike Ounsworth
Software Security Architect, Entrust

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.