Post-Quantum Cryptography

you're listening to Ping, a podcast by AP MIG, discussing all things related to measuring the Internet. I'm your host, George Michelson. This time, I'm talking to Jeff Houston from APNIC Labs again in his regular monthly spot on Ping. This episode is the last for 2024. We'll be back early in 2025. Jeff and I discuss the strange world of post quantum cryptography or PQC. We've discussed this a couple of times on ping already, with Caspar and Ralph from SIDN Labs talking about their test bed.

And Peter Thomason from SSE and Jason Gertzen from Sandbox AQ who talked about their implementation. Jeff is interested in how we've arrived in a belief we need to deploy these new post quantum cryptographic methods. What this looks like on the wire and in terms of key lengths and the impact on operations in TLS and DNS sets. Are we investing all this effort for something which may still not come to fruition? How far ahead do we have to look to see significant likelihood of risk?

the existing RSA and elliptic curve cryptography and why does this matter?

Jeff, welcome back to Ping. What should we talk about this time? Uh George, um, thank you and good, you know, morning, afternoon, evening or whatever it is happens to be. Um what should we talk about this time? Look, I have had my head buried deeply in this strange world of quantum mechanics. And quantum computing and cryptography and what a triumvirate.

Ah, this this is gonna tickle every funny bone in my brain, Jeff, because I consider myself functionally illiterate in all advanced levels of mathematical concepts. But you know what? We've done some quantum related stuff here on ping. We've done post quantum crypto in the DNS with a couple of people. So

Let's go there. What have you been thinking about here? Let's indeed let's go there. So we we start with with the fact that I think it was sort of Einstein, but modern physics turned voodoo weird at the start of the twentieth century. This this whole idea that, you know No, it wasn't gravity. It was space getting warped. No, time doesn't move in consistent ways. Time is relative to you and what you're doing. You know, the whole world got inverted and odd things started happening.

And and from there, it only got worse. And we started getting into this strange, strange world that at the ultra-small. The universe is truly bizarre. Um quantum entanglement. simply blows my mind. And I think it, you know, for most folk out there, it blows their mind too. It just strikes me as bizarre. I don't know what it it is kind of weird how simultaneously we've got a word which literally means units, packets, chunks, items of things.

And something that says, uh, two things might be one thing. Hmm, depends. Two things might interfere with each other. That's a bit odd. They don't normally do that except for in mechanical ways. W it's weird. It's weird, you know. We learned, and that was one of the earlier rules of Einstein, nothing travels faster than the speed of light.

And and we all played around with it this at the time, the Michelson-Morley experiments and similar, trying to find the ground reference for this speed. And then physics said no, there's no ground reference. The speed of light is a constant no matter how fast you're moving, and the speed of light relative to you is always the speed of light. So my brain's just exploded. Yes.

So I just I just wanna I just wanna say at this point the Michelson in Michelson Morley is spelt differently to my name and there is no family relationship. Can't claim any fame here. Oh and for you Americans, Sam Houston's no relation to me either. So there we go, we're even. Ha ha. Anyway, um yeah, where where I was heading w was this idea that this has turned almost voodoo.

That you take a pair of sort of items of information that normally can't communicate with each other faster than the speed of light, because you know that's what we've been taught. But if you entangle them, And don't know their state. Once you separate them, when you ever discover the state of one of these entangled bits. The other one takes on a known state as well. It sort of eerie affects it.

And and folk who are much, much cleverer than I have taken these things and started to build quantum computers and quantum networks. This is bizarre. This is weird. Um The kinds of things that they're trying to entangle, um, are not, you know, a bunch of electrons traveling through a conductor as we do with silicon. Oh, nothing nothing so obvious. Um They're trying to do this with super supercomputing systems held at sort of one degree absolute. They're trying to do it with individual apps.

Or even electrons or photons? So so this space for me divides up into two things. They're really the same story, but it has two qualities. One is the quantum computing side. And the other is the quantum entanglement side. On the quantum computing side, I kind of believe the theory and I buy the story. It is theoretically possible to construct systems of calculation based on this behaviour, which may be able to do some things that are extremely hard to do in classic computing manner.

Having said May, I am a sceptic that anyone's demonstrated it yet. I'm sure we'll come to that later. The other one, the quantum entanglement, What I'm hearing from attending sessions in the crypto research working group at IETF is that people have successfully managed to use this to perform key exchange. over fiber optic networks and over spree free space lasers. And the thing here is that

They can not only tell the known states of the system, they can tell if somebody else snooped along the way. And so for the unique property of doing a key exchange, secure key exchange. You get this value add out of the mechanism. You know if anybody saw what you were doing. That one, that actually seems quite beneficial. I don't really want to talk about quantum computing and quantum networking. You know, in some ways, I don't know anywhere near enough other than to crack a few jokes about.

you know, a and and the state of the art with quantum computers is is not exactly impressive. Um, I understand that the most recent announcement is that we've actually managed to construct a quantum computer that can find find the prime factors of twenty one. Yeah. Yeah. Great theory, not very practically useful for cryptography in the current state. And we've been slaving away for a couple of decades on this, so you know, the work is running at full pace, absolutely. However

There are some sort of expectations flying around here around the advent of quantum computers and what might Because you see, if we apply our recent past to the near-term future of quantum computing, There are some pretty astounding things going on. Moore's law and and we say that because it it was no law, it was just a supposition.

But it's an observation of the behaviour of technology under our ability to construct things with it. And you've talked about it several times here, about the amazing benefits we've secured. as a technology community scaled on the back of Moore's Law. Right. Now it's been going since about nineteen sixties. And the basic benchmark is that across sort of 18-month periods, we've been able to increase the density of transistor gates on a silicon chip by doubling.

So every 20, every every 18 months or so, you can put twice as many gates on the chip. And the processees that put them on. Scale in terms of a chip costs the same to make, or roughly. So the unit cost of these gates declines massively every eighteen months. At the same time We can actually run faster and faster computer clocks.

More gates, faster clocks. This whole thing gets out of control. And not only does it double every eighteen months, but the cost seems to come down by a comparable factor. Now we got very used to the idea this was a law. Not an observation of behavior, but this was a law. The law of Moore says it will always be faster and it will always be cheaper. Amen. So, in 20 years' time, if this law holds as a law, then

Computers that are everyday accessible in 2045, 2044, right? Will be around ten thousand times more capable than today. Ten thousand. It's kind of that's just not, you know, one more laptop. That's you know, a room full of laptops working on the same problem. It's it's a big factor.

So okay, let's just park that thought and now go to the world of cryptography and secrets. When I encrypt something and call it a secret, I typically have some expectation as to how long it should remain a secret. And and you know, I I'm not a government um and I don't pretend to work for them, but they certainly classify the level of secrecy and some stuff they realistically say We'd like this to remain a secret for twenty years.

Yeah. And and we've encrypted it with the world's best technology. And and what that means is that the computers. Twenty years from now, we'll be unable to break the cryptography that created that secret. that not only are you looking to make something a secret so that today's computers can't break it. looking to create a secret that tomorrow's and tomorrow's and all of those tomorrows up to 20 years from now, 10,000 times more capable, can't break that secret.

Now you go, God, how do we do that? How do we make things that are kind of a secret that even if the computers are phenomenally powerful, and and you know, 20 years and 10,000 times is a big one. How do you make something that's a secret that can withstand that? It might have been tenable. back in the forties and fifties, to think forward about the pace of technology change before people

codified their idea of Mil Moore's law, they probably had good reason to believe the technology they were using could sustain some level of protection for a forward window. But we've arrived at a point where we now have much less confidence that the future will not be able to do things faster. Well let's just sort of And in parallel.

Just dismantle that that thought, George, because this is exactly where I'm heading. How do you make a problem that, if you will, is resistant to something 10,000 times better, faster, more capable. And one of the easiest ways that we could do that, and there are easy ways to do it, is to make the problem only solvable by enumeration. You've got to start at one and keep on counting. Now, if you choose a number that's say 30 digits long.

Then a number that's 31 digits long is actually 10 times harder because you're counting to a number that's 10 times bigger. So if you can create a problem that demands inuberation, then it scales.

Even if you say, well, I'll get two computers on, well, that's a scaling factor of two. I'll get ten. I'm still only a scaling factor of ten. Parallelism is linear. And so if I can create an enumeration problem, that ten thousand times more capable. Is actually not that bad, is it? If I take a very, very large number and try and find its prime factors, then if I add four more digits to that very, very large number, it's a ten thousand times harder problem.

Right? And so in some ways we took this requirement from, you know. The uh security people make it a secret for twenty years and said, Well, if I create an e a enumeration style problem, I can tick that box. So we actually envisaged an attitude, a feeling around encryption that this was achievable. That this was not just achievable, it was what we do. It's commonplace.

Yeah, we kind of have we've kind of had the lived experience because this cryptography standard space has been active long enough that we know when we said back then it would last this long, we were able to test the hypothesis. And if we reached a point where the technology looked weaker than we thought, we bootstrap the process of choosing a new key length, choosing a new algorithm.

Designing new systems and carrying it forward into the into the future. We haven't actually had a crisis moment where somebody stood up and said, I successfully broke that crypto. Here's what I was able to do with it in the wider public now. Right. So i in the world of prime number arithmetic. Which is the world that the RSA algorithm lives? Uh Rivist Rivist? I don't know how he's pronounced Shamir and Adleman.

the only pure mathematicians that ever made money out of being a pure mathematician. Um widely, widely envied by everyone else in the mathematics department of every campus, I'm sure. Um, RSA was basically working along this theory that The Euclidean is it Euclidean prime number sift was still the only way to find prime factors of a very, very large composite number. So if you take two very, very large prime numbers. Multiply them together and

Then that resulting composite number only has one prime factoring. And if you didn't know either of those prime numbers, you're in a world of pain. Is one, is two, is three, is four. Come back in a million zillion years. And and so we relied on RSA for years. 512-bit keys, 1024-bit keys. We're currently up to 2,048-bit keys. So this is an example of us choosing a suite of algorithms that have this weird asymmetric property. relatively speaking, easier to do certain operations one way.

And then the other direction without complete knowledge is significantly astronomically harder. One and two, we've already said, well, we'll start at five twelve. Oops, that isn't working. Let's shift to one oh two. Two rounds of being advised you need to improve the length of the unit we're talking about here to retain that level of protection. Keep the algorithm, just change the length.

And and currently the the advice is if you want twenty years of standard computing, two oh four eight bits should get you through. We don't know how to crack that on using conventional computing in real time. The enumeration task is not quite the age of the universe, but it's pretty damn long. We just don't think you can you can crack it.

Now, at some point, those keys get big. And if we continue to think that that Moore's Law will still deliver, that we'll still make more powerful, let's call them linear computers. Then we need to think about 2048. We need to think about ever longer key sizes, but that's kind of messy. Kinda messy.

What about if we just jump to a different algorithm that gives us a higher density? And oddly enough, that's exactly what we're doing right now. We're moving, and in particular, the biggest move is coming over in the DNS for DNS. We're moving from prime number cryptography, RSA, into integer logic around elliptical curves.

elliptical curve cryptography. And the basic property of this family of algorithms around elliptical curves is that they're harder problems with smaller keys and smaller signatures. Same asymmetry that if you know the components of input to the system, although it is complicated, you can compute the outputs, but if all you know is the output and the public component of two things, it's logistically almost impossible in tractable time.

Right. But at the same time, I mean if you compare RSA two oh four eight to uh E C D S A P two fifty six Yes, I'm speaking geek and I swore I'm terribly sorry. Um the private key in RSA 2048 is 1776 bytes. the private key in ECDSA, which is actually a slightly stronger encryption algorithm, stronger that it takes more operations to break it. Only uses a tenth of that, roughly, 187. And the output signature, the the output state.

that we then have to look at using this cryptography on the wire in signature packets in the DNS or in checksum packets over the integrity of things, they get smaller by that amount Well, the products we test have got small All of a sudden it fits back in the DNS. DNS sec is not the nightmare of massive packets. The whole thing about, you know, keys and encryption is not carrying a truckload of data, you can still keep it relatively efficient. There's more projects.

This is a good news story. This is unlike you. Well hang on a second, because we started talking about quantum computers computers. So now let's let's stop the linear story. of you know, linear systems whose only real strength is you up the clock speed or up the number of processes, but you never get a leap. Quantum computing is different. Um, did you ever play with analog computers?

Oh I did, yes. Um f for those who haven't, analog computers as distinct from binary computers are very, very odd. You actually program the algorithm as a circuit. As an electronic circuit. Or water or air. Or water, yes. I remember seeing a water computer somewhere. And and the phenomenal thing is you can actually solve remarkably complex simultaneous equations.

By just simply setting up the experiment as a circuit or as a set of, you know, water valves, etc., and wait for the thing to equilibrium. And and in in theory, I suppose, you could scale this a long way, but you know, we stopped doing this years ago and turned digital. But those systems don't use ones and zeros. Their internal state is is is actually

Almost like a flow function, an equilibrium o of importance. Yeah, they're they're uh they're almost computing over continuous val variable states. It's a different nature of computation. They enter a stabilizing state. But they don't enter a digital here is the sum state. It's like the thing equilibriates. Right. Now I'm gonna start using some long words again and swear.

Um I'm sorry, but you know, it's it's a lot easier just to say it than to explain how. But quantum computers are based around a thing called a cube. Which in comparison to a bit in our digital computers, which is either the zip value of one or zero. A bit's a bit. A qubit is a superimposition of those two states simultaneously. So it's sort of neither one nor zero, it's kind of both at the same time.

And with that, I'm gonna go, yeah, right, let's move on. Um, because when you can create a sort of an algorithm that works using cube. This quantum computer consisting of these qubits can effectively solve all the parallel branches in a classical algorithm at once. It's exponentially parallel. It explores all the possible solution states.

In uh uh it's hard to actually understand what a cycle is in a quantum computer, but it's in one step, in one cycle. It just goes, this is the new state. This is where I've equilibriated. Voodoo. Magic. I don't understand it either. No, the part of this that's always sort of freaked me out is that if it's computing all the possible states this system can be in.

sort of simultaneously, finding what we might call the local optimum, the one that you actually want, is a bit like saying, well, here is this haystack with a needle in it, and therefore by definition, I have found the needle. It's in this haystack. But we actually need a more useful answer, which is the specific solution to the problem.

A quantum computer can see not all the possible answers, the one we're looking at And I haven't quite got my head around how you suck that out of the soup of all the answers were computed all the time.

In parallel. But you know what? That's someone else's problem at this point. I'm taking it on trust. It works. That someone else was Peter Shaw. And the some time else was actually thirty years ago, nineteen ninety four. So Shaw's algorithm is a statement of what would this look like as a way of doing this computing. An algorithm for a quantum computer that finds the prime factors of an integer.

And and not just in the age of the universe, not just enumerating. It finds them then, in real time, now. Then when you go back to, well, the whole reason why RSA is a strong algorithm is that you have to enumerate counting one by one by one up to an impossibly big number. And that just takes forever. But Peter Shaw said, if I have a quantum computer with enough qubits, whatever that might be, I can solve this now.

What for a really, really big number? Well if I had a really, really big quantum machine, yes. In now. And so if I present to that algorithm Something that's been encrypted using RSA or ECC, which supposedly has a good twenty years of of sort of secrecy life left in it, it goes, yeah, solved that. Next one. Ah, so you Everybody thought Shaw's algorithm was a statement against RSA and if we shifted to the elliptical curves we'd get out of jail free. You've just slipped something in there, Jeff.

The technology behind this kind of approach is probably going to apply to elliptical curve as well as RSA.

are certainly all, to one degree or another, susceptible to breaking by that algorithm one way or another. You know, so so we have this this new term and and there is a lot of new terms coming, and this one I like. A cryptographically relevant quantum computer. C RQC, otherwise known as a crocodile. A cryptographically relevant computer. So not solving some other problem in mechanics or fluid dynamics.

But solving the cryptography problem in an adversarial sense, solving here means cracking. Getting cracking. Getting the prime factors of twenty one is not cryptographically relevant. But getting the prime factors of a 60 digit composite number is quantum you know is quantum relevant, cryptographically relevant. And that's the kind of thing. You need scale to make this work. And and the next kind of question is.

While that we know how to build qubits into computers, the real question is: how long is it going to take to make one of these Crocs, these cryptographically relevant quantum computers?

We don't know. So whenever we get confronted as a society with we don't know, you do the first thing. Ask people the wisdom of crowds, the the caucus, and and get a whole bunch of opinions. Some more expert than others, just a whole bunch of opinions and go, well, that's obviously the answer. So here's my here's my answer. May not like it, but it's mine. I don't think we're gonna do it next year. Well

Next year, let's say within five years. Um maybe, but I'm doubtful. Okay. Um the optimists say uh ten percent of the optimists say within five. Wow. Most people speak not within five. That's interesting. How about ten? Well, I don't believe you can actually predict ten years on anything, Jeff. I think it's a mistake. But nonetheless, on the assumption that there is somewhat um progression and a belief in more than voodoo magic to get there.

I'd be a little less certain it won't be done in ten. Might say it's a bit more fifty-fifty. Well, not quite fifty-fifty, but uh this study, this study done by the Global Risk Institute, um puts it at around one-third of optimum. Say, yeah, ten years that'll that'll happen. Now they are optimists. The pessimists it's about, you know, fifteen percent, seventeen percent of the pe pessimists go ten years from now. But either way it kinda says we're good.

of solving engineering problems over time and money. Now, the interesting thing is if you look at twenty in this same study. Now it's not fact, it's future. We're all getting it. Yeah. But this I would be much less I would be much less certain than fifty fifty. If you go out twenty years, I'd say I think it's actually more important to believe it could happen than it won't.

I'm happy to say it won't happen in one year. I don't think it'll happen in five years, unlikely in ten years, twenty years. I would be stupid to depend on this. I'd really not want to depend on it. Three quarters of the optimists go, Yeah, twenty years. Yeah.

Within twenty years. So if we circuit back to what you said at the beginning, twenty years is around the length of time that people at national strategic levels say I think we should try to preserve this thing into the future for somewhere around twenty years. So we've just hit a problem here, Jeff. It goes to risk, likelihood, consequence. What's the risk? The risk is somebody makes one of these things that works. What's the likelihood? That's exactly what you've been talking about.

What's the consequence? Well if you The consequence is twenty years is not available to keep something secret. If you've got a secret that needs to be a secret for the next twenty years. RSA and even you know ECC is not a very good approach because it won't be. Now, when I say it won't be, that's wrong. It is likely, it is thought, we all think that.

may not happen. But there is a strong body of view that within 20 years we'll get something that's qu cryptographically powerful enough to break what we do. That's our expectation. And the more we pump money into it, the more we engineer around it, the more likely that is going to be.

I guess. Right. So for some class of technology that we use now Sitting here and saying don't have to worry about that for twenty years has a bunch of people in risk consequence world jumping up and down, saying, No, no, no, no. The risk is actually right. If you're encoding stuff right now, you've got a problem.

'Cause if I want my secret to remain a secret for twenty years, even if it's gonna take twenty years to build one, at the end of the period where I still need it to be a secret, it's no longer a good secret. It's blunt. Now, that then led one of the, I think, champions in this entire area of cryptographic study, the US National Institute of Standards and Technology. that embarked on its post quant quantum cryptography project in twenty sixteen. And what they said was, look,

As we're talking about here and now, we're interested in not just secrets today, but long-term secrets that can last across technology, you know, evolution in 20 years. So we need new algorithms. That don't rely on naive enumeration. Algorithms that leak beyond the linear that we're currently relying on. for scaling leap beyond that and are actually a difficult problem even if you had a you know cryptographically relevant quantum computer, it's not solvable easily. It's resistant.

And so NIST, the National Institute of Science and Technology, said look, the world, um Give us some give us some proposals. Tell us what we should be. They've been running competitions to design algorithms for a long time now and usually they set criteria of their goals so The last round, the one that's emerged as something called AES, they said as a criteria there's gonna be a lot more small devices out there using

different instruction sets to the ones we normally have. Can you make your algorithms both secure and efficient to compute on the instruction set for a thing like an R?

You know, the chip setter inside the phone or a watch. And and so setting the parameters around the competition, I think it's something NIST does really well. So you're saying NIST put the call out saying Can you design algorithms that will not be easy to crack using Shaw's Well it not be easy to crack using quantum computing, quantum you know, quantum computing, and can you make it so that posing

If you have the knowledge, you know, solving it if you have the knowledge is actually efficient even on something like a watch. But if you don't have that seed knowledge, you're up the creek. It just ain't gonna be. It is not going to be crackable. And and so a year afterwards, twenty seventeen, they had sixty-nine candidate algorithm.

And and then there was this long process of of winnowing. Uh the winnowing I said either, you know, this isn't good enough. It you know, it isn't it isn't tenable on on low-end computing, or it's cracked.

Yeah, that introduces this really interesting game where we all like to pretend it's a lovely, amicable world out there, but there is a moment in the history of cryptography where people in this space have said secret agents in the black helicopter offices sometimes walk in and say, Yeah, not and then walk out of the room again and they're not prepared to say why it is they don't want you to use that class of algorithms.

The other side of the deal is they also sometimes walk into the room and they say that one, we want to diddle six bits. And people go, Oh, they must be weakening it. But I've been told by mathematicians what they actually did was strengthen it. They liked the design, they knew it had to be a bit better. There is this strange artifact that there are in National cryptographic alphabet.

And and you know, there is a certain amount of of um finger pointing of suspicion around the United States and elliptical curve cryptography. around the Russian Federation and a swam of algorithms called GOST and algorithms And and all of them, you know, to some extent and another, w would cheerfully claim that the other algorithm

have been broken already and have been released to the public in a pre compromisable state and therefore should not be used. And you know, they all say that about each other. I'm not qualified to make any judgment whatsoever, but you kind of see there's a certain amount of A national pride and B a huge amount of hubris and and mystical doubt surrounding all of this. But, you know, NIST in their process for quantum algorithms is down a similar path. And they'd got this 69 candidates down to four.

Um one of the four is is for key exchange. And the other three is for digital signatures. Um however there's nothing like use, nothing like you know. Trying it out, kicking the tires. And oddly enough, the four became three because one of the digital signature algorithms was indeed found to be breakable.

Now we're left with three and and the issue is we don't know how good they are. Although that is the space that some people who've also been on ping have been exploring. We've had Peter Thomason, who's been working on actually deploying some of the candidate algorithms. Into PowerDNS and bind. And we've had people from SIDN who got a research project going to build the test bed. uh virtual machine environment saying, why don't you put your algorithms in into play inside this machine?

And let's see how things work. So some people have been looking at this, particularly in the context of the DNS. Well it it's beyond the let's see if it works, it it's back to the mathematicians again going, can you break And and you know, the algorithm is now public.

And it's kind of, well, invent your own keys and see if you can rip apart this algorithm, see if you can break it. And and that's what's going on. Now the issue is we've got these three algorithms that are effectively uh so-called quantum resistant. You can't solve them readily and quickly using a quantum computer that doesn't exist. You can't solve them. But we actually don't know how robots. So what do you do?

Well the current approach that we're actually doing in in real deployment Um, because we need this today for secrets that need to be secret for 20 odd years, is to actually combine both the classical algorithm, ECC with a big key, RSA 3072. Yeah. one of these cryptographic, you know, like MLDSA, uh a cryptographically um post quantum algorithm. So So we've we've almost been here before because back in the days of an algorithm called D

DES, the data encryption standard, when it was discovered that it was starting to become tractable to attack DES, they came up with the cunning idea. Let's use DES three times. And it became triple bez, which was do the same thing, but do it three times. And that did have the magic effect of spanning out the time to decrypt to plain text because you had to perform

An exhaustive kind of search three times over the body. So with this one, what you're saying is it's not do the same thing three times. It's combined two existing ways of doing things, one of the new ones and one of the old ones, to get double the benefit. It's a belt and brace. It it is, you know, and if you have a scalar computer, then

You really you really have a problem even using today's scalar cryptographic algorithms. You know, RSA 3072 is a hard nut to crack. So even if this quantum this quantum algorithm is broken. It's still protected by the scale. And and don't forget too, we don't have cryptographically relevant, you know, crocs yet to those computers.

So in essence if you can encrypt using that and it isn't broken, then it's going to be good for at least until these machines get up and get to the point where, you know, they start to grapple with the these issues. So the hybrid approach, even though it's bigger keys, etc., does give you that 20 odd years. And you know, this is happening today.

Um right now Google Chrome in Release thirteen point one is putting in a quantum uh a post-quantum cryptographic algorithm in into Chrome uh for use um for key exchange. because that ML multi lattice uh key exchange uh algorithm, they need it to be a secret for twenty years. And so when you say key exchange in crime

Is that really addressing mechanisms like TLS or QUIC as we understand them now? Is this basically saying the things that you have to perform to make a protected web session? We're now implementing the algorithms to let you do it in a post-quantum. Let's let's answer that by actually going back to the work of the codebreakers in the Second World War. Because you didn't break it in real time, you recorded the signal.

And then you post processed the signal with the best equipment you could. And the real question is, I suppose, when you encoded with Enigma was, how long did you want it to be a secret for? Now we've already given you the answer 20 years. And we know that there are people recording entire sessions.

You know, collect it now, analyze it later. And so the thing is if you're encrypting using a session key. If you can Subsequently break the generation of that session key, that recorded conversation then becomes open text. You can break So the thing that may not the thing that may not be clear. is that typically these really complex algorithms like RSA or EC DSA aren't used to encrypt the whole of a message that gets sent on the wire. They're used to encrypt something a lot smaller.

which is what we call a symmetric key. So the session is protected by a symmetric key. And from speaking to cryptographers, I've been told symmetric keying algorithms actually aren't amenable to post-quantum break. They're going to be okay. The problem is that key exchange element that has to happen across the life of the session.

So we're okay having a symmetric key. The actual data packets using a symmetric key are fine, but it's how you share the key that's going to cause us the problem. And that's the bit that we're now talking. So so establishing that session key is the dance. And don't forget, when you and I are trying to do this, we haven't met. We can't pre-configure ourselves.

We have to do this on the open network. Somehow we need to use a very limited amount of To establish each other's bona fides, you know, you are who you claim to be, I am who I claim to be, and also exchange information using this asymmetric. Cryptography. Yeah. To establish a session key and then to back off and go, everything from now on is a session key encrypted. We're good.

If someone else is recording that conversation, they're going to record the encrypted exchange, and they're going to record the initial exchange of public keys, etc. If that recorder can even a year later, even twenty years later. Break those keys, those asymmetric keys. They can then effectively observe the establishment of the session key and know its value.

And at that point the entire conversation is is sort of you know opened up. So this is why Chrome and a bunch of others have a similar interest in long-term secret. are basically moving to deploy what used to be kyber, what's now M L K E M for use in production, you know, browser software and other production software today. Because the 20 year problem.

So this is actually a good news story. Characteristically unlike you, Jeff. This is good. People are doing what we need them to do. But you've said they're doing it in the brown. And the thing is that we spend a lot of time talking about the DNS. Oh no, let's before necessarily relevant to the DNS. Before before we go to the DNS, let's just sort of look. It's not quite as simple as you think.

I make the key sizes around conventional RSA are four kilobytes. The key sizes with uh MLDSA are 22 kilobytes. If I'm in five times bigger. If I'm in TCP, how many segments So all of a sudden, this whole let's do a handshake and establish an encryption session is not just a couple of round trip times and yes, she'll be right.

It's actually a hefty exchange of data. You actually move from slow start to congestion, avoidance, and so on. And if you were ever thinking that TLS over UDP, that DTLS spec, was ever viable. You can't do massive keys in DTLS. It's a dud protocol. Because you can't reliably transfer the fragments of data you need over a UDP set. DTLS is fragmentation in toll. Right. So is quick. So we so we so this whole thing about So is quick.

So this whole thing about one RTT, get data, get sessions started as quickly as possible, that goes completely out the window. You've got to do ten packets worth of exchange. To get boot strapped into a secure state. The yes. Negotiating, you know, these post quantum algorithms is is not trivial. And so before we even move to the DNS, you start to think, wow, there's actually some work going on here if we want to make it fun.

etc and and we're not there there's there's a lot to think about and and some protocols like DTLS we need to just give And even quick, I think, needs to have, you know, go into the corner and have a long, hard look at itself to figure out how to handle quite large keys and quite large signatures in its encrypted session. Because this is not, you know, just a little bit of RSA, couple of packets, no problem.

So let's move then to the big one, DNS. And and for reasons, and they're buried in history, the DNS likes everything to be under 512.

Yeah, it's a mess. And and even when the first sort of round of security for DNS, DNSS It was pretty clear that that was never going to happen. Now oddly enough, with elliptical curve, we're actually getting close to that and we're actually able to put the genie back in the bottle. But the initial idea with DNSEC was, well, let's just negotiate really large UDP And allow fragmentation, because obviously fragmentation is is really robust and work.

Yeah right. Um hysterical laughter from everyone and when V6 came along the laughter became not only hysterical but you know insanely hysterical. Uh we can't do that. It just doesn't work. So with DNSSEC, we kind of went into this really big packet area with fragmentation and then found this is a really bad idea. So

We do full back. We do fall back to TCP. The whole thing takes time. No one's very happy. And and the end result is Only recursive resolvers do DNSEC validation out there in The actual U and I, the endpoints, the so called stubs of the DNS, just simply trust our recursive resolve. Which for a secure protocol and a secure framework is is tantamount to swearing. This is just nonsense.

But you know Yeah, it's security it's security theatre, it's pantomime. It's not actually secured. And and we don't even know how to push existing cryptographic algorithms, you know, keys and signatures, down to these But never underestimate the power of research funding. Because if I use the words quantum and security,

Uh and in particular DNS security, in the same sentence in a research funding proposal, it's pretty likely I'm gonna get the Moolah. I'm gonna get the money. And as insane as this concept sounds, they're gonna start working on it. 'Cause you know money. Now there's a lot of problems. There's a lot of problems. Um because pushing extremely large signatures into the DNA Doesn't work very well. Just doesn't.

And yeah, it confronts this problem with the underlying transport technologies and their systematic behaviour. Right. We've already seen this. You start with UDP, that's too big. I need to set on the truncated bit, I need to go to T C P and you kinda go, Well, okay, from stub to recursive where I'm asking the same other point all the time I can probably get away with TCP.

But when the recursive is asking all of those funny uh authoritative servers, just single questions, TCP is is horrible. It's incredibly inefficient. But what else can we do? If we want to push large signatures around and large, large keys, this thing is is extremely difficult.

Well, along comes Merkel Merkel Trees. Along comes the mathematicians to make our life horrendously hard. Now it wasn't the same people, but the same mathematicians that gave us NSEC 5. a a form of denial of ex a proof of denial of existence which I think only one person, Sharon, thank you, understood, and the rest of us were sitting there going, Wow, Sharon, I hope you're right,'cause we don't understand how the hell this could possibly work.

Well we're not sure. But they've come up with they've come up with another way of dealing with this problem. Uh a and it kind of tries to make the packets all within the kind of reasonable grounds of not within five twelve, but certainly within fifteen hundred, but at the same time convey The same information that you need to convey for these post quantum cryptographic algorithm keys. No one can understand how it works.

And the other question is aside from the funding people that gave them the money, why is this a relevant problem? Now, you see, if I'm trying to create a secret I want to last for 20 years, I'd really need to think about this today. Sure. But DNSec doesn't encrypt. DNS at least we're solving we're solving a different problem in the DNS. We're solving the integrity of the state of information right now.

I am the authoritative server you thought you were talking to, and the answer comes from my zone. It's authentic. Now I can record that. And play it back in 20 years. And oddly enough, very little DNS information is even relevant 20 years later, let alone accurate and authentic. It doesn't need longevity. DNSEC is actually a here and now problem.

Right. We don't need to solve the twenty years hence problem. We actually only need the ability to say right here, right now, this is demonstrably as it should be. Now if I had A cryptographically relevant quantum computer brought back through the time machine tunnel, all working with his huge number of qubits, and used it today. Against folk doing, you know, RSA two hundred four eight in the DNS, I could break DNS sec and pretend to be someone else.

I could. I could send you false answers that would realistically look like they were good. I could do that. But what I can't do is record what's going on today. and take that data twenty years into the future. Break the keys and then do anything useful with it. Cause the DNS has come and gone. That was a transaction that happened twenty years ago. And no matter what you know twenty years hence, it won't help you.

Because it doesn't need to be a secret for that long. So the first kind of issue around post quantum cryptography in DNS sec is why today? Yes, I can understand that when these computers get out there, you might want to think about that, because it's something that we need to think about. But until then, unlike unlike the sort of the Google process.

Of twenty years of secret, the DNS doesn't have twenty years of longevity in this space. You don't need to solve the problem that's going to occur twenty years from now. That's the first issue.

The second issue is actually Moore's law, prodigious as it is, has lulled us into a funny way of thinking. In the era of valves, valve computers, Not only was it big and expensive to build a machine, but each process, each cycle, each instruction cost a large amount of money. That you only ever use these computers to solve expensive problems because they're expensive. Yeah, the national computer problem where will we put?

the national computer because people thought that'd be wild. I want to store my shopping list on the national computer. I'm sorry dude. You know, the value of what you're trying to solve and the value of this computer don't match. So in those days essentially computers were state managed. the people who had capability to use computers to b break cry cryptography were state actors. It was state against state. Roll the machine forward. Well the state actors haven't gone away.

But people who are motivated to break cryptography include guys who just rent machine time in Amazon because they want to hack someone's Bitcoin. Now it's actually a commercial domain. Now the issue around these linear computers, silicon chips is We've been able to make prodigious leaps, not only in its performance, but in its unit cost of processing, because in effect, all we've been doing is nothing fundamentally different. We've just been making them smaller. It's the same process.

Yeah. Nothing nothing's changed. There's been no sort of change in the physics required to build this stuff in terms of the computing technology. Yeah, making it smaller has at times been a mind-warpingly difficult problem. But each time we've been able to get the per gate costs down, to get the processing costs down, so that we've had this expectation that bigger is cheaper. But in quantum computing, what makes you think that's true? And there is no answer to that.

And Mike, if this is all about trying to get an extraordinary amount of energy and complexity to create this entangled state, if you do it 10,000 times. Is it ten thousand times more expensive? Or is it even worse, a hundred thousand times more expensive? You know? Linear scaling experiences and doubling experiences based on Moore's law just may not be applicable in a quantum computing era. We don't know what the effective cost time budget is.

to do these computations. We don't know. We don't know. A and if if it really is the case that this is not going to get any cheaper The costs will remain exorbitant, eye water. Then the only 20-year secrets that you want to protect, because the only thing that quantum computers are going to get deployed against, are, if you will, problems and data of comparable value, the trillion-dollar data.

And you and my DNS you know, DNS meanderings The awesome power of quantum computing is never going to get thrown against And and so that's the other scale of this. It's the economic aspects of it's great to think about and great to work on, but is it real? Yeah. What's the applicability to the problem of signing and protecting DNSA? both in current time and into the future. And what cost burdens are we going to incur supplying services on the network if we react to this emerging problem?

And incur the cost of making ten packet exchanges happen just to even bootstrap talking to someone. Right. And breaking it using a quantum computer might cost us billions of dollars. And it's kind of dude, it ain't ever. And so we're in this sort of unknown area right now where quite frankly there is a strong level of curiosity, certainly on the part of large public institutions, where the job is to keep a secret.

And they're funding a whole bunch of research work and the researchers are heading off going, We all need to be aware in the commercial world about this problem of longevity of secrets. And the real answer is not sure I agree with you. I admit, you know, the folk in the business of keeping secrets, and we know who they are, certainly have a problem. And fine. And quantum computers will no doubt, if they ever get built, be deployed against them and by them.

You know, for that very reason. But for the rest of it I I I'm not sure I buy it. That Yeah, so so this is work that's important and it's a risk that would have enormously high consequence if it came true, and there is a level of eyes that should be on this and a level of funding that should be available to researchers. But if you bring likelihood to the table and consequence to the table in the DNS

We might take a different view on this. We might say, keep alert, don't be alarmed. How about we don't pervert the protocol so far that the DNS stops being useful? Well, on a final note of heresy. ABSLUT HERESY LET ME POINT OUT THAT THE QUES BEEN USED IN DNS SEC are slowly and definitely migrating from RSA 1024 to 2048. Why? Because NIST has said that if you consider a 20-year lifetime of longevity of secrets, RSA 1024 is not good enough anymore.

In that twenty year horizon it is likely it will get broken. We need RSA to open. So the new keys in DNSEC at the root are now 2048. Why? Because we overreacted? Have we have we actually misapplied our own sense of importance to say, Oh, NIST has spoken, we must change and nobody sat back and said, hang on. Maybe this isn't about us. Maybe the KSK, if they do indeed do the right thing and and ever get back to their five year lifetime.

You don't need a twenty year piece of crypto, and in fact if they rolled every year, which we can do. then you don't even need that. And it's it's part of this sort of mythology and misuse of some of these long principles about going, well, secret's a secret, therefore if the DNS uses this, it must keep the same secret. It does. I think life would actually be a lot simpler in this world if we went back into smaller keys. Ah yes, but they won't last twenty years. That's not the point.

They would last for their operational lifetime of these keys, and that's what we need to be concerned about. So I I You know, Jeff. I I think that this is a a really interesting operational reality. reality check. It's kind of, can we just talk about this that is absent from some of the discussion about security in the DNS? I I think this is a very useful thing to flag.

Well, I I think so too. And and we spend all this effort making things harder for ourselves in chasing security goals that are not relevant to this application. We're we're busy applying someone else's principles to to the DNS and going, Wow, this is really stressing out the DNS and then the real question is, but why are you doing it?

I need to have a twenty year secret in the DNS? No, just roll the keys. Stop thinking that keys are eternal. They're not. Move them around and you don't have this problem.

So but that I think is food for thought that the world of cryptography has a lot more facets to it than just let's encrypt it and make it a super secret forever. There's actually a whole bunch of considerations about lifetime, use, etc., that sort of impinge on that thinking, and though worry about the blind application of rigid rules.

Well we might be better off by thinking about the problem and the nature of what we're trying to solve before we sort of took to the tool set and bash it into shape. Um and I'd leave you with that thought as a parting gift from twenty twenty four. Well, I think that this is one of those useful contrarian moments.

Jeff, which we should reflect on in twenty forty-four and see whether or not this came to fruition. Thank you. That's been absolutely fascinating. And thank you, dear listeners, for hanging around this long. I hope you've had some fun with me wandering through this Thank you. Well, that's the last episode of Ping for 2024. I hope you've enjoyed listening and will be back with us early in 2025 as we resume after a break.

If you've got a story or research to share here on Ping, why not get in contact by email? to ping at apnick.net or via the APNIC social media channels. Also, remember that Measurement at APNIC.net mailing list on orbit is there to discuss and share relevant collaborative opportunities grants and funding opportunities, jobs and graduate placings, or to seek feedback from the community on your own measurement project.

Be sure to check out the APNIC website for all your resource and community needs. Until next time.