Migrating X.509 PKI to Post-Quantum Cryptography Using Composite Certificates - Srilakshmi Geetha

We live in a world where we live more digitally than physically. A world where our phones recognize us even before we recognized ourselves in the morning. A world where everyday trust now moves through screens, networks, invisible cryptographic systems. A world where behind every click, tap and login, there is mathematics working round the clock to keep everything secure for you. We have long assumed no classical computer can solve this math in practical time. But what if I told you that quantum computers completely shatter that assumption? And that's where postquantum cryptography comes in because our job is to secure the infrastructure before today's trust becomes tomorrow's weakness. Today I bring to you my evaluations on composite certificates, a pragmatic real

world bridge to safely migrate our X.509 infrastructure into the postquantum world. So before we go further a little about me, I'm Shri Lakshmi. I'm a developer at workday and I'm also pursuing my masters in cyber security from TU Dublin. So this work sits at the intersection of what I do during the day and what I'm researching in the night. The day the math stood still. Modern PKI rests on asymmetric cryptography which means that the problems are easy oneway but hard in reverse. For RSA it's integer factorization. For ECDSA and diffy helman it's elliptic curve discrete logarithm. Different math same oneway property and the certificates we trust today rest on both of them. So Shor's algorithm gives quantum

computer a practical way to solve this impossible to solve mathematical problems. Symmetric cryptography like AES will survive this quantum transition simply by doubling their key sizes. But our asymmetric infrastructure is unsafe long-term against a cryptographically relevant quantum computer. But the threat isn't waiting around for this computer to be built. The second more immediate threat is harvest now decrypt later. If you haven't already heard of this, what it means is that attackers are stealing our data, our encrypted information just to wait for the quantum capability to unlock it tomorrow. Scary, isn't it? Because of this, government standards aren't just theoretical deadlines. If your migration isn't finished well before then your legacy data will be a ticking time bomb.

So what's in the blast radius? There are three things. First infrastructure that is CAS, HSM, libraries, clients all need to handle the new algorithms, new oids, new certificate formats. Second, authentication. RSA and ECDSA both fall to shores and that puts every certificate chain of trust at risk. Third key establishment the part of every TLS handshake where both parties agree on a session key today that's diffy helmet or ECDH again both fall to shores. MLM is the postquantum replacement and it's an equally large migration in its own right. This talk focuses only on signatures and certificates beyond the prime. To defeat a quantum adversary, we must move beyond classical mathematics. This brings us to MLDDSC, our knight in

polomial armor. The title, it's not just decoration. RSC was the night for public key cryptography for 40 long years until quantum changed the rules of the DL. So MLDDSA is our new knight and it's armor it's made of latises. A lattice is essentially a repeating grid of points. So in two dimensions you can picture a graph paper. In cryptography you take that same idea into hundreds of more dimensions. See, you cannot even visualize it. And that's where the security lives. The hard problem here is a shortest vector problem, which is find the shortest nonzero vector between latis points. EC in low dimensions, but computationally infeasible in high ones. NIST standardized MLDDSAF SIPS 204, MLCM SIPS 203 and both are latisbased.

So, NIST has handed us the algorithm, but knowing what to deploy is the easy part. Knowing how to deploy, now that's the milliondoll question. And quite literally. So, this brings us to the quest for a migration path. There are three deployment parts, dual stack, composite, and postquantum only. Let's go with dual stack first. Dual stack runs two certificates in parallel. There is one classical and one postquantum. Older clients continue to use the classical one. Newer clients continue start to use the postquantum one. It's great for compatibility, but it's highly policy dependent. You rely on the client to make the right choice and it can actually lower your security if the client defaults to classical. Composite combines both keys into a

single certificate and your certificate will only pass if both keys and signatures are valid. This provides an absolute safety net. Our traffic will remain secure even if either RSA or MLDDSA suffer a catastrophic break. Essentially the major difference between dual and composite is that for dual stack protection from a downgrade attack depends entirely on your server configuration. With composite downgrade protection is baked directly into your certificate math and finally postquantum only which is the ultimate end state. No classical fallback at all. That is the cleanest path from a future perspective. However, it will only work once the surrounding environment and ecosystem catches up. So, this is more realistic for green field and tightly controlled environments rather than for a broader

PKI migration. PKI migration in general is a two-layered architecture. The bottom layer has the leaf end entity certificates that live on our actual service. The top row consists of the trust anchors that lie on our trusttos which is the root certificates. So we just discussed our options for the bottom row that is end entity certificates. You can either go dual or you can go composite in between the transition phase. So for the top row in between classical root and postquantum route there are three deployment options. First is a cross signing which could be the bridge model. The existing route signs a new postquantum route. So legacy clients will still chase a chain up to a

trusted anchor that is already there in the trust. The second is parallel roots where you have two trust anchors in the trust and you let the client pick either the classical or the postquantum. Composite roots put both algorithms into one trust anchor. So if you ask me why did this research focus on composite leaf certificates because there are no real numbers yet. Postquantum only and dual stack both have deployed data and publish data as well but composite certificate still has only IETF drafts and vendor blog posts. So this research was to fill that particular data gap. The forge We move from theory to prototype. I built this prototype end to end in Java 17 and Bouncy Castle 1.83. This is

one of the first libraries to ship native MLDDSA against the FIPS 204 standard. I measured the environment in two distinct layers. First, the raw cryptographic primitives in isolation and then I built the X.509 509 infrastructure on top of it just to get a better clearer view and all of this is based on the IATF lamps draft 13. I benchmark all the operations against JM. So what does this hybrid certificate look like under the hood? You can see here we have two of everything. We have two keys, two signatures in a single certificate. Verification relies on a strict and logic. Both signatures must validate successfully for this certificate to pass. And the total certificate size it roughly goes up by

from 1.2 kilob to 6.5 kilobyt. Everything here is tied to a single oid or object identifier. I have mentioned here the oid for the composites. This is according to the IEF lambs draft. So to understand oid a little better, you can think of it like a cryptographic barcode. So this the clients try to scan this barcode and then they don't recognize this because this is a bar a brand new barcode and then they immediately drop connection. The trial of size and speed. We have the algorithm. We have the deployment path. The prototype. Now let's look at some real empirical data. This brings us directly to our first major evaluation cost size. Moving to a composite makes a leave certificate

approximately 5 and a half times larger. The critical engineering takeaway here isn't that it got bigger, but why the vast majority of this growth is pure unavoidable postquantum cryptographic material that is the MLDDSA signature and the public key. Only a tiny fraction of it is the ASN1 wrapping overhead. This means this payload tax is entirely structural. You cannot optimize it with cleaner encoding or better software development. With this size delta, it introduces real world downstream constraints for our migration in the sense that you need to architect around it for network handshake latency certificate distribution system even your database widths you need to architect around them. Now let's look at performance. The biggest takeaway here is that compute is

not the bottleneck. As you can see from the large numbers on the bottom, post quantum algorithms are blazingly fast. Key generation is thousands of times faster than RSA. Signing is six times faster. So the only real overhead happens when you use the composite certificates, which is understandable because composite certificates have two signatures in the same certificate. So the issuance and the uh signing both go up. If we handle the verification in parallel, I noticed that there is again a significant drop in the latency. So that is something to note. The conclusion here is clear. The CPU is not the bill you're going to be paying here. Cryptography works beautifully as expected in the code. But when we

transition to enterprise infrastructure, we hit the hardware wall. So these are some tidbits from my research while reading the IEF lambdas hidden in all of the drafts. I identified three major bottlenecks. First is HSM readiness. Major vendors like Tails do ship postquantum firmware today but upgrading your production fleet of HSM it can sometimes take quarters sometimes even years and requiring FIPS reertification is a major operational hurdle that you have to factor in secondly seedbased key generation under FIPS 204 an MLDDSA private key is a tiny 32 into byte seed which can then be enlarged into the full key on demand. So this completely breaks the traditional RSA model of storing the enlarged keys. If your HSM only supports

the old key formats, your key escro recovery migration all will silently fail. This brings us to our ultimate goal crypto agility. Postquantum migration isn't a one-time patch. It's a multi-year discipline. The new cryptographic primitives are already in the pipeline. So, you should treat this algorithm rotation as a routine automated maintenance event and not a catastrophic engineering event. The verdict. Two things surprise me here. First at the algorithm level everything is ready that is bouncy castle fips 204 end to end issuance verification all of them work all of them are ready second what blocks deployment isn't really cryptography it's the seams between cryptography and your existing PKI stack which is the PKIX the HSM a spec that's stable but

not yet published so the verdict is less is the math ready, but rather is the plumbing ready. From what we've understood so far, composite certificates are more attractive for controlled ecosystems like internal MTLS, VPNs, and device identities where you own both ends of the wire and you can upgrade the infrastructure together. This is especially because composite certificates are not backward compatible by itself. Legacy clients do not understand the composite certificate format will simply reject it. And to wrap up, the big takeaway is clear. Composite certificates are practical, but the bottleneck is operational and not computational. The math is blazingly fast. Verification stays under a millisecond. But the size explosion, it is a permanent tax on your

network. While the software works well today, real world deployment could hit the hardware wall that we spoke about earlier. To extend my research, the next phase can focus on more advanced certificate management operations. So this is my recommended migration road map anchored to official NIST and CNSA 2.2 timelines. The phase one which is 2026, we're already here to 2027. It's the inventory and pilot phase. You should audit your crypto assets and measure this hardware wall in your lab. You need to know your bandwidth and you need to know your HSM limits even before you start architecting a solution. Phase 2 is from 2027 to 2030 which is a hybrid deployment phase. Start issuing your hybrid or composite sets for all

new systems. Then comes phase three from 2030 to 2033 which is a strict enforcement phase. This is where we face out legacy only thrust. Phase 4 is a 2033 plus which is a quantum ready error. Migration is complete the but the goal remember it's crypto agility and one final recommendation if your environment touches federal national security systems your effective deadline isn't 2035 it's 2033. So a quantum winter is coming and we must forge our keys before the first fall of snow. Thank you.

>> Any questions? >> We talked about servers. Do we know of clients already? People making system attached to this. >> Can you be a little louder? Sorry. people making clients that were attached to servers like are there any tested clients >> um for composite certificates? Not yet. It's all very in progress today. Yeah. >> If your mathematics is based on dimensional lyses through is there a risk that improved platforming algorithms kind of reduce the

So uh your question is that uh because the math is based on latises uh is there a path that it could reduce the performance? >> Is there is there a risk for like solves problem with an optimized algorithm >> for lises? Yeah.

>> Uh that's a good question. So today uh MLDDSA and MLCM are based on modular latises. So uh the SVP that is a shortest vector problem is is one of the hard problems. So they have MSISS which is the short integer solution and then module learning with errors MLWE which means that you inject some error in your equation so that you don't get the value the secret the private key. So there are multiple layers of defense for latis at the moment but it is always possible that somebody finds some way to work around it like we didn't know there will be a quantum computer today that's why composite certificate is a good option because MLDDSA is not publicly deployed

yet in the whole broad migration scope so if you use composite certificate even if RSA or MLDDSA get compromised your traffic is still secure. So that's why composite certificate is a good option if you're not very un very sure about how MLDDSA will far. >> Yeah, cool. Thank you. If you want to learn more about quantum or have any other questions, I'll hang around for a bit.