Root Causes 344: Introducing the PQC Onramp

Tim Callan

I don’t know how long it’s been since we’ve had a post quantum crytpo episode but today is a post quantum crypto episode.

Jason Soroko

Good stuff.

Tim Callan

Good stuff. As we all remember, the NIST Round 3 left us with one KEM and three digital signature algorithms that we could all move forward and start to standardize with, The KEM of course was CRYSTALS-Kyber and the digital signatures were CRYSTALS-Dilithium, FALCON and +SPHINCS. And at this point, we have draft standards for Kyber, Dilithium and FALCON, and +SPHINCS is still on the way. So that’s it, right? All done? All done, finished. Right, Jay?

Jason Soroko

Oh heck no. We are not done here at all.

Tim Callan

Correct.

Jason Soroko

And you know, I think the spirit of what we are saying here, Tim, is well, first of all, look guys, we got to the draft standards list. Right? So, in other words, we know what’s going off to become standardized. There’s a ton of work. Whoever is sitting in those rooms – they are working hard. They’re burning calories, those folks.

And then there’s also, Tim, my God, we ended up with a bunch of lattice. And that’s nice but I know that NIST is gonna want more than that.

Tim Callan

We had a whole big head of lattice. I’ve been waiting to say that forever.

Jason Soroko

Ha! Ok.

Tim Callan

So many of our eggs in a way are in this lattice basket. And NIST is not very happy about this and so what they’ve done is they have created basically an entire new competition – what they call the On Ramp. The On Ramp is a whole new initiative, a whole new competition focused on getting digital signatures, and while they do allow lattice-based signatures to be submitted and some of them have been, the real ask for NIST is non-lattice signatures. They want more options. They want their eggs in more baskets.

And so, let’s go a little on the timeline. In July of 2022, there was a call for additional signatures. Now this was obviously well in advance of the Round 3 finalists being announced, but they already knew what they were

going to need to do. The final deadline for submission for this contest was June 1, 2023. So people had nearly a year to get that together and there are some interim milestones in there where you could get things vetted by them, and NIST said a lot of people took advantage of that. They sent their papers in, and NIST gave them feedback and sent them back. And then as of July 17, 2023, they put those submissions out in the world so people could start to work on them, and I think 40 algorithms were submitted, if I’m getting that number right and they cover a variety of different strategies. And like I said, some of them are lattice. In fact, a decent number of them are lattice.

I’ve got the numbers actually. So there were 50 submissions received by the final deadline. Ten of them were knocked out because they were not deemed sufficient according to the criteria for one reason or another. It took them down to 40. So there are now 40 new algorithms that are going into the new On Ramp process. And these cover a variety of different strategies.

Jason Soroko

They sure do. There’s a number of them here. Some of which, you could look back at previous podcasts where we actually listened to me butcher the math and oversimplify the math. We’ve explained before, what’s the math behind RSA? What’s the math behind ECC? Well, now we’ve gotta ask the question – what’s the math behind lattice? What’s the math behind isogeny? And we’ve covered some of those. And that’s what we are referring to here when we are talking about the categories of these candidates.

Tim Callan

So, let me rattle off these categories just so we are on the same page.

So, there is isogeny-based. There is MPC-in-the-Head. Which by the way, that’s my new insult for you, Jay. If you are upset, I’m gonna tell you you have MPC-in-the-Head. Ok?

Jason Soroko

I probably do.

Tim Callan

Multivariate-based crypto. Code-based crypto and symmetric-based. And those are the main categories. And then, of course, we still have lattice on the list. And then there’s a category they call “other”. And in “other”, there literally are one, two, three, four, five – there are five algorithms in the “other”. So these are things that don’t even qualify with any of those other major categories.

So, they’ve got a lot of variety here and that’s what they were going for. And if I count real quick, the lattice is one, two, three, four, five, six, seven in lattice. Which means that there are 33 that are not. So, there’s a bunch of stuff and that’s the real focus.

Now you might also say, “Why are there lattice algorithms? I thought we had too many eggs in the lattice basket.” And the idea was NIST said, look, if you can show us a better lattice signature algorithm, then ok. We’ll consider it.

Jason Soroko

Yeah. And, Tim, look, I also think whereas RSA and ECC were just so darned applicable for the use cases at hand and of course, other cryptographic primitives that we still use for encryption and other things which are not gonna be affected by post quantum situation, I think that part of what you are also seeing here in all the names that you just said is there probably will be some of these methodologies and categories that are ideal for specific use cases. Hence, why not have a happy moment of discovering, geez, you know, one of the 10 or so multivariates that are out there might just be great for X. And I think, Tim, as the knowledge of those kinds of things pans out, that will be some really important future podcasts to start talking about, hey guys, if you are looking at some kind of signing or you are looking whatever it happens to be in terms of a specific use case then let’s talk about which of these categories apply. And some of these are gonna be surprising. I mean, the biggest one that you and I will be talking about is TLS handshakes. Which is gonna be the big SSL use case. I see lattice in there in a big way even just with the currently selected ones that are going to standards. Those are not unknown, but I think there will be a very different style of thinking about how to apply cryptography down the road.

Tim Callan

Absolutely. And so, I’ve seen some interesting research on this recently and there’s a couple takeaways. I can’t like quote numbers and things but one of them is if you look at the existing set of new primitives and a sample of the obvious strong candidates, you’ll see that there is nothing that is equally performative in all aspects as RSA and ECC.

Jason Soroko

Yeah.

Tim Callan

So something has to get worse. Now to some degree, the question is well you get to choose what gets worse. So, you might have something for instance that is fast to encrypt, fast to decrypt, but has a really big key length. And maybe you don’t care. Maybe you say, look, for this particular use case, I don’t care if the keys are huge. Or, maybe you have something that has a comparable key length but it’s lacking in one of those other areas and now you turn around and you say, ok, well, I have a very constrained environment and the key length really, really matters to me.

Like a lot of IoT applications. And therefore, I have to consider that. And so, it’s what you said. There’s this idea of saying, look, we’re gonna think more clearly, or more specifically let’s say, about the use case, the device, the bandwidth, the environment and we may have a menu of options that you can choose, and you can choose them based on what you’re looking for for your outcome and what you are trying to build. And that might be the new world order. It may be the case where today we’ve got this kind of situation where more or less it’s RSA everywhere with a little dusting of ECC. That may not be our future at all. It might be much more dealer’s choice in terms of figuring out which crypto is going to sit in which environment and how I’m going to use it.

Jason Soroko

Yeah. I think with that being said, we’ve gotta be fair to Dilithium, right?

And as a main signature algorithm, yeah, it’s probably gonna take the biggest chunk of the pie regardless of how we cut it, but the pie will not look the same as it is today. That’s for sure, Tim.

Tim Callan

Yeah. That’s for sure.

So, how long is this gonna go? This is gonna go for a long time. Right?

Jason Soroko

Yeah.

Tim Callan

This is gonna probably be a couple of years and we should just expect it’s a couple years before these things come out the other end. And also, the other thing that NIST has been clear on is they want to keep the number of final winners relatively small. So, one of the philosophies they have is too many options impares standardization. So the reason NIST isn’t gonna come out with five KEMS or 10 signatures is because it interferes with our ability to standardize. They think we need to have a relatively small number of choices, easy choices so that the industry can support them. And if you make too many options or you make it too hard, what will happen is some of these will be deemed not worth it and people won’t write there and when you do that, interoperability falls apart. And so, they will try to narrow it down to, like, a couple. It’s hard to see them at the end of the day picking more than two or maybe three of these but that’s it. That’s what they are going for.

Jason Soroko

It totally makes sense. Look, just in the isogeny category, right, where so much hope was until SIKE was broken - and you and I covered this on a podcast by the way for those of you who want to look it up. To me, that exceptionally fantastic property of isogeny having the small keys, small signatures, you know, everything about it is just ideal except for the fact that it’s quite slow. A lot of really good aspects are there about it. And the math is phenomenal. The problem is figuring out what is the good implementation that doesn’t leak data that could be hacked.

So therefore this is what you are saying, Tim. I’m just repeating it in a different way. You really want to narrow it down to which one truly has the best implementation and then you triple down on that implementation and kick the tires as hard as you can.

Tim Callan

Dr. Dustin Moody from NIST has also weighed in on the point about this, which is to say, look, we appreciate that given more time and additional years of study, it may be that we can find a better implementation even in the existing winners that we have. But there’s also a time problem and we have to move forward.

So one of the things that they are trying to balance over there is to spend the time to get the best result we can and also get the result that’s good enough to stave off real disaster quickly enough that we can actually use it to stave off the disaster. And that’s another tension in all of this and it’s an interesting and difficult tension in that nobody really knows. Right? You start to say, well, what day is too late?

Jason Soroko

Exactly.

Tim Callan

Maybe now.

Jason Soroko

Look, folks. Here’s the reality. The tire kicking will never stop on any of the selection. Tire kicking hasn’t stopped on RSA. It will never stop.

Tim Callan

That’s actually another thing that NIST has been explicit about, which is that, look, this might never be done. We might just always be doing this.

Jason Soroko

It shows you - - you know, Tim, look, maybe this is off on a tangent here but sometimes you listen to physicists on television. You watch a PBS documentary on X, Y, Z of the universe and you listen to this guy that’s just ridiculously brilliant and you think, oh my God, all this stuff is just solved. These people are just so smart it’s just crazy. Ok. Truth - fast forward to the truth - human beings suck at math and the reality is we are beginners at even beginning to understand some of this stuff.

Now some of you will say to me, you’ll throw the pie and say forget it Jay. You are an idiot. Some of these things are actually very, very well studied and they’ve been studied for years. Well, ok. Combine that with the implementation. Combine that with the pragmatic usage of it. It’s exactly

what Dustin Moody said to you. And to me, it shows you the level of humility we have to have about what we know about the math and the implementations of these things. This is not easy. And yes, a line has to be drawn in the sand somewhere and that’s a good attitude to take because waiting for proven perfection – we’ll be waiting an awfully long time.

Tim Callan

Yeah. And we are not waiting, right? To your point, we are moving forward with Kyber and Dilithium as the main KEM and main signature and no matter what else goes on, Kyber and Dilithium, that train is out of the station.

Jason Soroko

Yep.

Tim Callan

Because it needs to be. And that’s definitely - - the first time you get production post quantum crypto on your machine, those are gonna be the primitives. That’s where we’re going.

Jason Soroko

Yeah. You got it, Tim.

Look, I am excited to see the width of the categories being considered here. We really do need to - - and it shouldn’t just be our voices. I think we’ve gotta have some other people from the industry talking about post quantum with us to really get into what are the pluses and minuses of using each one of these.

Tim Callan

Yeah.

Jason Soroko

Because you and I, Tim, have called for it is time to get your hands dirty on post quantum.

Tim Callan

Yes.

Jason Soroko

It is time. And just simply walking the journey with us to know what these categories are, you know, are they large key sizes? Are they small signatures? What are they good for? What are they not good for? Knowing these things – first of all, it’s gonna make you really hip. You are gonna be a hit at every party.

Tim Callan

You are definitely gonna be a cool kid for sure.

Jason Soroko

No question. But on the other hand, that’s the best way to get your hands super dirty at this point is to have those kinds of things in your head.

Tim Callan

Yep. I agree, and this is the time. You and I have been talking about this for years and now all of the sudden, there’s a lot of momentum for this, things are happening and 2024 is probably the year that you are getting your hands dirty.

Jason Soroko

Let’s declare 2024 hands in the pot when it comes to post quantum. Everybody.

Tim Callan

I love it. It is declared.

So, anyway, that’s big. That’s exciting. Most people I find don’t know about this which is why I wanted to bring it up today. They kind of know about the Round 4 but this isn’t Round 4. This is something else and, you know, NIST continues to be active and again, I think there will probably be something else after the On Ramp and something else after that because this is the new normal.