Security Cryptography Whatever

Has RSA been destroyed by a quantum computer???

• Security Cryptography Whatever • Season 2 • Episode 9

Share episode

There's a paper that claims one can factor a RSA-2048 modulus with the help of a 372-qubit quantum computer. Are we all gonna die?

Also some musings about Bruce Schneier.

Errata:
Schneier's honorary PhD is from the University of Westminster, not UW.


Transcript:
https://securitycryptographywhatever.com/2023/01/06/has-rsa-been-destroyed-by-a-quantum-computer/

Links:

https://arxiv.org/pdf/2212.12372.pdf
https://eprint.iacr.org/2021/232.pdf
https://github.com/lducas/SchnorrGate
https://sweis.medium.com/did-schnorr-destroy-rsa-show-me-the-factors-dcb1bb980ab0
https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html
https://scottaaronson.blog/?p=6957



"Security Cryptography Whatever" is hosted by Deirdre Connolly (@durumcrustulum), Thomas Ptacek (@tqbf), and David Adrian (@davidcadrian)

Deirdre:

Hello. Welcome to Security Cryptography Whatever. I'm Deirdre.

David:

I'm David.

Thomas:

I'm Thomas.

Deirdre:

Yay. Welcome back, Thomas. We haven't talked to you in a while.

Thomas:

I'm here!

Deirdre:

Today we're talking about, a new quantum attack on RSA. Is RSA 2048 bit broken? Question mark. Question mark. Question mark. Spoilers: it's not broken. Sorry. Sorry, it's not broken, but we wanted to talk about it because lots of people have asked us about what the fuck is this? Is this real? People have written blog posts about it. People have tried to make takes, I guess, on it. And so we crammed and now we're making our take on it. Thomas.

Thomas:

My first response to this is stop asking us for this stuff.

David:

So what happened this week?

Deirdre:

I think it

David:

So what was released this week or last week or,

Deirdre:

it wasn't released this week. I think it was released, uh, just before Christmas. Um,

David:

that's still within the realm of this past week in my, in my worldview that counts as this

Deirdre:

In the smudging of time, that is the, the new year in the holidays. the paper is called"Factoring integers with sublinear resources on a superconducting quantum processor." And it alleges that you can use a, quantum circuit with 372 physical qubits, which is like, Pretty much kind of what we have currently, uh, for, for, for normal, uh, like ibm, Google, quantum computers in numbers of qubits, which is what a lot of people think is all you need, would break, has an algorithm uses using that would break aka factor the modulus of, RSA 2048.

Thomas:

Right. So for like a moment here, I'm gonna pretend like I know what I'm talking about, but I have to give my disclaimer that to an extent surpassing even previous podcasts of ours, I don't know what the fuck I'm talking about here, but, but all right. So like, there's like the well understood notion that like one of, like the big thing that quantum computing theoretically breaks is RSA, right? And the reason.

Deirdre:

and discreet log.

Thomas:

Yeah, basically all conventional, like previous, I, I always have the wrong terms for like F F D H and things like that, right? But like elliptic curve, RSA, all that stuff, like they, they break it because of an algorithm called Shor's- confusingly, Shor's algorithm,

Deirdre:

Correct, yes.

Thomas:

So like we, we all know quantum computers break RSA, if you can get a quantum computer of, you know, that size, um, which I don't believe they exist, but whatever. Um, with, with Shor's algorithm, right? So the problem with that is that the, the computers that you need, the quantum computers that you need to use Shor's algorithm are huge. They're much, much bigger than anything that we've got even on the horizon. Right. So the confusing thing here with this paper, the news in this paper is that rather than using Shor's algorithm at all, they're using Schnorr's algorithm Schnee's

Deirdre:

with an n

Thomas:

Yes, Schnorr with an the, the Schnorr of Schnorr's signatures, right? Like the fa, the famous Claus Schnorr. Um,

David:

The S in RSA?

Deirdre:

No, No. SH- RSA is[altogether now]: Rivest, Shamir, and Adelman.

David:

Uh, I can't keep track, man. I once got yelled at, so I once got yelled at by Shamir and then I just kinda merged all older cryptographers. I got yelled at by Shair for, uh, because I was doing internet measurement incorrectly, which I was not. Um, uh, nothing about cryptography. and then accosted by one of his students at Black Hat. And so I've merged all of the older'S' cryptographers, um,

Deirdre:

into one.

David:

one thing

Deirdre:

Shamir,

David:

that people

Deirdre:

Schnorr,

David:

largely ignore,

Deirdre:

They're all that same and they're all mean to me.

David:

more or less.

Thomas:

So like, okay, so Schnorr's algorithm is not a quantum algorithm, right? Schnorr's algorithm is a, it's a conventional or classical algorithm for factoring, that has a long history. It's a big part of the history of the factoring problem is Schnorr's algorithm. So we've known about Schnorr's algorithm for forever, right?

Deirdre:

it's, gone through iterations. It's gone through like 30 years almost of Schnorr trying to attack the factoring problem, in several ways that will continue to go into

Thomas:

Maybe, or we'll just bounce around it and like, give you a sort of quantum understanding of what this is. But anyways, there's this conventional algorithm for factoring called Schnorr's algorithm, which is like a, ostensibly it's supposed to be competitive with the fastest, you know, superior too, the fastest, you know, kind of conventional factoring, in the numeric field sieve and all that stuff, right? It's not, but that's the idea, right? Is that if you can get it working Yeah. Schnorr would say that if you could just get it working with the right parameters, that it's gonna be much, much faster. And we'll get into that in a second. Right? But anyways, the nut of this paper is forget Shor, forget building, you know, quantum computers of unusual size, and instead, take the simple quantum computers that we have right now and use them with an algorithm, I think it's QAOA or q o a,

Deirdre:

Yeah. Yeah. Uh, quantum algorithm for, oh, sorry, sorry. Quantum approximate optimization algorithm, which is like a thing that people keep trying to throw at problems in a similar way to this.

Thomas:

right? It's, it's, it's quantum fairy dust, right?

Deirdre:

Yes.

Thomas:

take this conventional algorithm plus some quantum fairy dust and you can make Schnorr's algorithm super fast, right? And the big news there would be that that would be a way of attacking RSA without building a serious quantum computer. You could use just a dumb quantum computer. I, I gotta say before we go further, right? Like, so the idea here is that this is an attack that you could carry out with a quantum computer, kind of quote, unquote, of the size that we have right now with IBM Osprey or whatever, right? But like, And again, remember, I don't know what I'm talking about. Right. But, but like, you can't take the numbers, the qubit numbers that we have on those computers at face value, right? Like there's like the nominal

Deirdre:

asterisks,

Thomas:

Yeah. There's like the nominal number and then there's like the amount of extra qubits you would need for error correction to do different kinds of problems with different tolerances.

Deirdre:

Um, the computers that we have now, the quantum computers we have now are, are called NISQ, quantum computers, noisy intermediate scale quantum computers. They're noisy because they are not fault tolerant. you need to use quantum error correction to get any kind of guarantee that, like you, you, you need three physical cubits. To get one error corrected, logical qubit. there's issues about, you know, fault tolerance. There's issues about coherence, there's issues about circuit depth, which this paper only hand waved at and got addressed at the very end of their appendices, which is my kind of bug bear. There's a lot of asterisks behind those 300 something, 400 something physical qubits for computers nowadays. And I would say that this technique of combining a, a quantum part of your algorithm and your classical part of an algorithm is not novel. Like there's a lot of more uh venerable, papers that are considered true threats to say isogeny-based systems. These are called hybrid attacks where they take some of your your attack is using some sort of quantum part, and you do the rest of it with like a well trod, classical part. And then you like, use the best of both worlds to get the best attack that you can. But this one is sort of taking a not well established classical attack and trying to speed up the part that you would want to be sped up with with some quantum fairy dust. And it's, we don't think it gets there A lot of people don't think it gets there.

Thomas:

Yeah. What's the part that you want to go at here? Right? Like, or, or which part do you wanna go at first? Right. Do, do we wanna talk about like the Schnorr approach, like this, this tangent kind of conventional approach to factoring? Or do you wanna talk more about quantum computers and circuit depths, which is like,

Deirdre:

I

Thomas:

could keep talking cause I won't be able to say anything.

Deirdre:

I will say that like one part of this paper that people keep pointing to is these authors go out of their way to avoid talking about the runtime of this attack when you actually run it with classical computers and you know, existing quantum computers. because the running time is not polynomial in the size of the, the thing you're attacking, which is like 20, 48 bits in the case of RSA or some other, uh, security factor, it's actually either, uh, sub exponential or possibly exponential. which means it's not a very good attack and it's actually not, it's doesn't beat the state of the art that we actually have for attacking RSA and attacking RSA, and doing factoring classically. So,

Thomas:

the, this is in the supposed quantum.

Deirdre:

Yeah, yeah, yeah. So it's, it both is, based on, flimsy assumptions about, our current quantum computers, flimsy, Schnorr, factoring attack. And also even if all these things actually worked, it would not actually, be very fast at all. So it just kind of does not destroy RSA.

David:

There's also possibly a securities fraud connection.

Deirdre:

What, what

David:

Well, in terms of what quantum computers do. So there's a company called Rigetti, founded by, um, someone named Rigetti. and I just realized apparently they went public via SPAC. Um, and they claimed that at the time they had like eight and then maybe 80 bits of quantum computers. And then they said, we're gonna get to a thousand by 2024, and they SPAC'd at$10 and their stock is currently at 75 cents. Um, so I'm getting the feeling we're not gonna get a, uh, a thousand bit, quantum computer from them in the next year, or two.

Thomas:

Wait, Wait, hold on. What's the connection between spaghetti and

Deirdre:

with

Thomas:

big red and not big head. Okay. What's the, what's the connection between that company and this attack?

David:

Oh, just that, like if we're talking about, oh, you could do it with a 300 whatever bit, uh, computer. Like those don't actually exist, and the company that was claiming to have a thousand is not going to get a thousand anytime soon. And presumably, I don't know, maybe didn't even, didn't even have 80.

Thomas:

I'm very, I'm very sad. I was hoping you were to say that, like put out a press release saying,"By the end of the year we'll have computers that can break RSA," which would've been awesome.

Deirdre:

I mean, if they put out a 10 24 qubit, like physical qubit or logical qubit, computer and you weren't able to run Shor's algorithm and factor like RSA 10 24, that would be pretty huge. I think the current record is like RSA, like 520 but they're not.

Thomas:

So I'm gonna, like, I'm gonna take us on a short voyage of adventure here, right? Because this actually, this ties in like really neatly to the last big RSA, like Curfuffle. Um, so I, I actually, I, I had forgotten this and put it completely out of my memory, and only like in the middle of preparing for this realized this is like the, this connects, but there was that thing like last year or the year before last, where Claus Schnorr submitted a new iteration of his paper. Um, you know, his lattice approach to factoring, um, where like it had a note saying this"destroyes"

Deirdre:

Yeah.

Thomas:

RSA cryptosystem.

Deirdre:

A typo. And we were all like, what?

Thomas:

yeah. And that's like, that was headlines everywhere. Like, this destroys RSA, signed

Deirdre:

from Claus nor, yeah. Yeah.

Thomas:

Yeah. There's this long history to this kind of approach, right? Where like, I, I think you, you can find papers going back to, I, I think I've got one from 91 on my screen right now, right? Where just the idea that you can reduce, the factoring problem; you can find a bunch of like almost intuitive explanations for how this works, just like, you know, kind of congruence relationship factoring, you know, like the j just as the factoring identity right. Um, to the SVP problem. So,

Deirdre:

The SV problem is the shortest vector problem.

Thomas:

yeah, I guess, I mean, if you, if you wanna tell people what a lattice is and what the shortest vector problem is,

Deirdre:

uh, okay. Lattice, uh,

David:

Or we could say, just go listen to our episode with, uh, Chris Piker from last.

Deirdre:

Yes,

Thomas:

I wasn't, I wasn't on that episode, so,

Deirdre:

Uh, please refer back to, lattice based crypto episode with, Chris Peikert. It also mentions Michigan beating Ohio or something like that. uh, yeah, but shortest vector problem is you're in a lattice with a defined basis, and you're trying to find the shortest vector in that lattice, approximately. This is supposed to be an NP-hard problem. So all of the, crypto systems that reduce to uh, shortest factor problem are actually reducing to an approximation of the shortest vector problem, which is pretty good enough in things like, learning with errors and other, lattice based crypto systems that we think are quantum resistant, are based on this sort of fundamental, uh, assumption. And then if we mention the closest vector problem, it is related but not exactly the same, where you're trying to find a closest, with some measure of close to another vector in a similar

Thomas:

So like, like, I kind of, I gather that like the approach of reducing factorization to a lattice SVP problem, is kind of super interesting and has been for like the last 20 years and like the 1990s were spent with people trying to get this, like there was a theory put paper posted in 91, 93, something like that. Right? And then like by the end of the nineties, somebody had like a working implementation of it. But it turns out when you go to implement it that it's just, it's not competitive. with the numeric field si. Right. It certainly doesn't, it certainly doesn't destroy RSA. Right. It's, it's actually, it's less good than the conventional techniques that we have right now. It's interesting though, when people have done other research that was kind of based off of that idea. It's like a, it seems like it was a super valuable contribution to the science, if not to anything in practice, but it's like, you know, one of the back stories here is that Claus Schnorr has been like a mad scientist tinkering in his laboratory for the past 15 years, like trying to find the one set of parameters where, you know, the Schnorr, lattice based factorization thing outcompetes, the numeric field sieve whatever,

Deirdre:

like trying to find the right heuristics that will make it work and it hasn't panned out.

Thomas:

the, and the last iteration of this was like a year and a half ago the"Destroyes RSA" paper, which is kind of sad, right? Like a bu a bunch of people went at that paper. Cause I mean, it said it destroyed RSA, like a bunch of cryptographers went out. Like there were like basic, basic errors that were kind of found in it. And it's like, you know, people had to say like, like Claus Schnorr is, he's in his what, late seventies now? Um. And so everyone doing this has to say like, I'm not, like, you know, I have no problem with people that are old doing, we're all, I'm old, I get to say this, right? Not as old as Claus Schnorr apparently. But, um, Yeah, so like there was this whole sad thing about like, you know, there's typos in this paper and basic errors, and nobody understands why this paper was actually submitted, but like he's standing by it. He revoked the paper, he retracted the paper, but then he put it back up and this is this whole weird paper thing, right? So like, this is one of like the big stories in, in, in RSA and conventional cryptography for the past, it's, holy shit, it's like 2023 right now for like 20 years, right? Like, has been this story, like, does this approach work? Right? and, and the answer is, no. Right? Like that, the, the conventional algorithm here doesn't work at all. Right. And then like the quantum, now the quantum fairy dust that we're, that we're talking about sprinkling on the system, the QAOA thing or whatever, right? Again, I have no idea what the fuck I'm talking about, but the reputation there is, um, worse than that of Schnorr's algorithm, right? Like, doesn't do anything at all, right? Am I, am I off on that?

Deirdre:

No, you're correct. apparently this is a thing where people keep trying to sprinkle QAOA onto problems like this. That's like, ah, this will just, you know, help with convergence or whatever when trying to do factoring or whatever. And we'll just throw some quantum at it and it'll speed up that part. And then like, that's actually not really panned out.

David:

So the paper, the Schnorr's paper from a year and a half ago, Steve Weis has a very nice breakdown as to why it doesn't destroy RSA. And then this paper from this past Christmas, more or less, is sprinkling quantum onto the Schnorr's paper to try and make it go even faster so that you can do it on tiny, tiny quantum computers. The issue with that to me is it's weird that a paper that uses the hard problem that we use for post quantum cryptography would ever have a speed up, on a quantum computer, right? Cuz SVP is the problem in Schnorr factoring and it's also the hard quantum cryptography problem. So why would a quantum computer make Schnorr's factoring algorithm go any faster, even if it did work better?

Thomas:

Right. It's like if, if you go back to the Chris Peikert episode that we had, which I will claim to have listened to, but I, I know some of the background here, right? Like, all of post quantum lattice cryptography reduces to the hardness of SVP or problems generalized from SVP. Right? So it's, it is, it's super weird, right? You could, it seems like you could like look at it just on its own terms and see like, okay, well this involves you solving SVP, which is like a known quantum hard problem. So,

Deirdre:

I do know that using lattices to attack stuff and like solving lattice problems to attack other crypto systems is like a thing. But, if you can reduce to the shortest vector problem and speed up that reduction in solving it, you're basically trying to use a quantum speed up to that algorithm to break, the problem that underlies quantum resistant cryptosystems. So it would be bad if that succeeded, but it doesn't look like it has succeeded. So we're happy ish about that.

Thomas:

Yeah, it seems like the stretch claim I would make here where somebody's gonna tell me I'm just completely off, is that if that paper was true, it would also be saying something pretty important about post quantum cryptography.

Deirdre:

Yes. I don't understand this fully to, pick out which part of Schnorr's solving, factoring with this algorithm is being accelerated with the, the quantum circuit. but either way, yeah. So tldr no, this paper does not break 2048-bit RSA

Thomas:

yeah, I guess we could move on to the question of why are we talking about this?

David:

Why did we just have a podcast about two papers that are wrong? Let me tell you, as someone who did a PhD, many papers are wrong. So why are we talking about these two?

Deirdre:

one because people, we, we saw it come across radars and we're just like, Ooh. And then people looked at it for a few minutes and were just like, this is, this seems suss. And then multiple people look at it for more than five minutes and said, this seems suss. But not everyone has, you know, enough cryptography, background attack, background knowledge of the state of quantum computing, knowledge of Schnorr's attempts to solve, factoring via lattices, to know that, and people have been asking us, and also people have been asking other people for their comments on,"I saw a paper that claims it breaks RSA", like'wat', and people have been writing, things.

Thomas:

Yeah, I'm, I'm, I'm, I'm gonna read the start of an article right now. It's, the headline of the article is,"Breaking RSA with a Quantum Computer." And the lede is:"a group of Chinese researchers have just published a paper claiming that they can, although they have not yet done so, break 2048 bit RSA. This is something to take seriously." This is something, this is me, not the thing. This is something to takes serious seriously."It might not be correct", might not be correct,"but it is not"[wait for it]"obviously wrong." Would anyone like to guess the source?

Deirdre:

Well, I, I already know

Thomas:

Roger Grimes

Deirdre:

No,

Thomas:

No, that's, I've barely had idea who Roger Grimes is. But that, that, that's a, that's a quote from the reason everyone's talking about this. Right. Which is, Schneier's blog.

Deirdre:

Hmm. Bruce Schneier.

Thomas:

Yes. not Claus Schneier Scheyer

Deirdre:

different.

David:

Schneier, the cryptographer from the deep.

Deirdre:

Who is Bruce Schneier? Bruce

Thomas:

Bruce Schneier is somebody who has forgotten more about block cipher cryptography than I will ever bother to learn. Um, so he's, you know, a famous cryptography, I'm looking for the right term famous cryptography person. Is the, is the, is the term I'm, I'm gonna choose there. Right. But he has, You know, probably the world's most read cryptography blog. Um, you know, the ostensible authoritative source for news about, you know, in the sense of hard sci-fi, like hard cryptography, like not crypto as in cryptocurrency. I'm not saying it's the best source. I'm saying it's the source everyone goes to.

Deirdre:

It's interesting because when I've started getting into cryptography, which was post Snowden, I never found his blog to be. But I am coming to cryptography much later,

David:

Well, you were like 10 or 15. You're 20 years late to when Schneier's blog was, uh, I think big.

Deirdre:

I've heard of his, several of his books including a, a book, called Applied Cryptography, and I almost bought that book until people told me, that book is no longer useful to you, and is perhaps actively harmful in today's day and age.

Thomas:

yeah, I mean, I have been throwing shade, you know, I try to not be snotty about throwing shade, but I've been throwing shade at Bruce Schneier for probably a decade now. Maybe a little bit more. Um, not cuz I have any real problem with Bruce Schneier, who, like, there's a lot of things that Bruce Schneier is that I respect. Right. But Bruce Schneier's influence on kind of, the engineering profession's understanding of cryptography is, what's the word I'm looking? Um, Right. So, um, I think, I think he's pretty upfront about that too, right? Like, so Bruce Schneier is most notable for writing Applied Cryptography, which is probably, without a doubt, the most famous book. in cryptography, like not among cryptographers, right,

David:

it's the big red one,

Deirdre:

right.

Thomas:

but not-cryptographers, outnumber, cryptographers by like 5,000 to one. Right? So just on the numbers,

David:

It was also like the first book, I think on cryptography basically.

Deirdre:

Okay.

Thomas:

There there was the Koblitz book that came out, or Men- Menezes, uh, that came out right before his, and it had a similar name like Handbook of Appli Cryptography.

Deirdre:

Oh, yeah. That's a good one.

Thomas:

Yeah, there was drama back, you know, back when Applied Cryptography came out. Cause it had a similar name to the Menezes handbook of- Nobody cares about this. I don't know why I'm bringing this up.

Deirdre:

this is cool. This is like back in the day er, when things were more hardcore, as it were.

David:

Oh, that's a cute story, Thomas. Okay, now go sit down grandpa.

Thomas:

You guys are the worst, right? so I guess like I, I have a couple of different like, ways to come at this, right? Like, One of them is just, frustrating is not the word, but like, let's just say I'm, I'm, it's, it's frustrating to kind of, you know, be kind of steeped in Mastodon Twitter, hacker news, kind of engineering culture and see the kind of mental model that people have of who Schneier is, or actually not who Schneier is so much, just how cryptography works, like who cryptographers are. You know, apropo, this podcast like a starting point is your mental model of me and cryptography should be, Thomas is not a cryptographer. I'm not, right. I'm not a cryptography engineer. I'm just a doofus who like, looks for bugs and knows a little bit of cryptography. Right. Um, so like I, I'm not putting myself ahead of anybody here. Right. But like, there's a, I.

David:

we're all putting Deirdre as the podcast cryptographer.

Deirdre:

Aw,

Thomas:

Fair enough. Yes. So like, there's a general kind of, people have like a bit set in their head, just one like the boolean, you know, Schneier knows cryptography, right? Ergo, if there's a subject involving cryptography, it's good to get Schneier's take on that cryptography. Right? But, but that is kind of. Pretty much never been true. Um, and the reason for that is not that Schneier is terrible at what he does, he's not right.

Deirdre:

There's just a lot of cryptography

Thomas:

Yeah. Yeah. So like, cryptography is super specialized, right? So like, as just a starting point, like if you're like, With a couple of exceptions. If you're a person who specializes in, like if you're a person who does block cipher designs where like one of your block ciphers is like super widely used, chances are you're not an asymmetric crypto person. Like you don't do a lot of like number theory research or you're not like doing like Diaphontine equations and elliptic curves, just, it's a different set of things, right? Like if you read, like if you read attack papers about block ciphers, And then you read attack papers about like elliptic curves. They're not the same things, right? It's not the Not at all,

Deirdre:

Yeah. And like when I got started getting into cryptography, I definitely came through the asymmetric way. I came through algebraic geometry and elliptic curves and isogenies and like that is where, that is what gets me excited and I get very, very into- the block cipher stuff, even hashes, like symmetric stuff, I'm just sort of like, I know enough about them to be like, that's a good one. I like that one. I'm more interested in like block cipher modes and things like that, and like I just do not have the depth on that side as I do on the asymmetric side, just because,

David:

I mean, this podcast is a great example of Thomas's point because like everything Deirdre just said, Thomas is nominally like an attack person. and then, I am more of like a networks secure transports person. And all of us are effectively out of our depth on today's episode talking about factoring in quantum computers. Right? Um, and it's not like we're lacking and, and, uh, we have a particularly high density of cryptography

Deirdre:

Right. and like I know enough about quantum computers, just so that I can model the attack, the adversary for my favorite, you know, squidgy isogeny based, theoretically quantum resistant, uh, crypto systems and the problems that they're underpinning. I have to know enough about the adversary and their capabilities, aka they have in theory a, a large, error corrected, very efficient quantum computer that's gonna try to attack me, but like kind of beyond that, I leave it to the, like, computer scientists who do quantum computing, because I don't have to know everything about those to understand enough to design a crypto system that should be resilient against a, you know, strongly modeled adversary.

David:

Yeah, I just ask Nadia,

Deirdre:

Yeah,

David:

whenever this stuff happens,

Thomas:

well, let's put a, put a pin in that. I wanna come back to that in a second. Right. But like, but Schneier's a block cipher guy, right? Schneier's, like, he's, he's really well known for, he's, he's a couple of things, right? He's a block cipher guy. And I mean, he's a pundit, right? But he's also like, he's a, he's a practitioner in the sense that I am, I don't know actually what Schneier's background is. Like, I don't know if he's got like a, you know, a graduate degree in any of this stuff or like, you know, the, the way he's published, and I'm not published at all here. Right? But like Schneier does, like or has, you know, led companies that do like just IT security stuff, like stuff that has nothing to do with cryptography. He's just like a security guy,

David:

Schneier has a master's degree in computer science and honorary PhD from U-Dub, presumably, cuz he wrote that book with Yoshi. And then, is, has a policy appointment in one of the Harvard associated think tank thingies.

Thomas:

Yeah. And he's like, he's responsible for Blowfish, which was a really popular block cipher. He was responsible for two fish and then like a hash based on two fish, which I forget the name of, but like, so he's a, and hashes and block ciphers, closely related disciplines and like. You know, if you look at like the absolute state of the art in hash breaking stuff right now, right. It's just, it's, I'm saying it's just right, but it's not just, but it's like, it's modernized, you know, refined versions of the differential cryptanalysis attack, right. Like of the same line of re it's, there's nothing, there's nothing, I'm not talking down this line of research. Right. It's incredible research. Right. But it's like, it's a very specific set of research that applies in no sense whatsoever to RSA. There's just no application to it. There's, they're, they're not similar problems. Right. And Schneier has like written for a long time. Like he, he wrote, um, Applied Cryptography, which has some stuff about RSA in it. And then he is a co-author of Practical Cryptography, which is a much better book, right? And, and Practical Cryptography has some pretty decent for the time advice about RSA. So certainly it seems clear that he knows his shit when it comes to the basics of RSA and kind of using RSA safely. But he is also kind of notorious. Maybe he's only notorious with me, but he's notorious for like,"I don't trust the math on elliptic curve cryptography," which is like a statement that first of all clearly didn't age well. Right. But it's also like

David:

Well, that was what everybody thought in like the late nineties, early two thousands,

Deirdre:

That's what I was trying to ask is like, was he the, the, the patient zero for that sentiment, or was that just sort of a, a common sentiment and he was also voicing it, but he had a popular blog?

Thomas:

I don't remember it being a common sentiment, like I'm the person on this, on this recording that was there for that, and I don't remember that being a common sentiment so much as the pervasive miasma of ignorance about cryptography at the time. Like nobody having these conversations, at least the ones that I saw at the time would've had any business having an opinion about elliptic curve cryptography, with very few exceptions, the people talking about this stuff like, I don't understand. You know, at the time in those conversations,"I don't trust the math" is equivalent to,"I don't know what the fuck this math is." Right. And the math isn't that complicated. Right. The math, it's not like a, I don't know how much there is to trust about it.

Deirdre:

for elliptic curves?

Thomas:

Yeah. Just the basic idea

Deirdre:

Algebra. It's kind of nice. If you have high school algebra, you're, you're good to go.

Thomas:

With, with like, with what we know now about elliptic curves and how things are attacked and all that, and, you know the, what's the, the stupid, ah, the linear algebra attack on conventional Diffie-Hellman, the name of that stupid thing. the reason why we have elliptic curve, cuz it's not susceptible too, the index calculus!

Deirdre:

Yeah. yeah,

David:

Mm-hmm.

Deirdre:

yes.

Thomas:

Right. It's like, but, but you, you, you can understand, like if you read through the index calculus stuff and why it doesn't apply to elliptic Curve and all that, it's like, it's not super controversial, right? Like, but, but yeah, like that's kind of, that was, that was his thing, right? Like, my advice is I don't trust elliptic curves, so maybe you guys shouldn't use elliptic curve, which is, by the way, terrible advice, right? Like, elliptic curve is much better than RSA.

Deirdre:

and better than finite field, uh, primes that we were using before, especially for things that were Diffie-Hellman.

Thomas:

So what's what's weird to me about the blog post, like the, the primary weird thing to me is that like you're confronted with this wacky paper and I, I can't believe anyone's beating down his door to like, you know, settle for once and for all is this paper actually valid or not. It wasn't like there was a huge conversation before this about like, maybe this paper is valid, right? Maybe I'm wrong about that. But like, you presume he had like a minute to go call somebody, right? Like, he's not

David:

He called Roger Grimes.

Thomas:

Why, why was that his call? Why- Call Steve Weis-, by the way, it's Steve Weis?

Deirdre:

Weis, Steve

Thomas:

I always, I, I would've said Vice, but.

Deirdre:

Scott Aaronson, who does quantum computing and wrote like the first book on

David:

we did it. We found it. It's in the emergency that only Scott Aaronson save. say.

Deirdre:

Like I don't often- Scott Aaronson has a blog that is, he writes about everything, and that includes things beyond quantum computing. So I don't often say, go read Scott Aaronson's blog post about thing. But when it's about quantum computing, including quantum attacks, at least in this case, Someone should have asked Scott Aaronson about this attack,

Thomas:

So, yeah, like maybe the short summary here is like, if there's like big news in like SHA-1 is like a, you know, a story where like if Schneier's writing about it, I'll probably pay, I'll, I'll pay attention to what Schneier's saying about it. Right? Because like Sure. He's, he's done block cipher designs and work on that stuff. And I, I sound dismissive here. I've done none of this work. So, but, on a story like this, where it's like the lattice reduction math goes over my head. Right. Well, well, okay, but like the lattice reduction math that we're talking about here, it's not new quantum math. Right. It's one of the biggest stories in the analysis of RSA since 1991, predating Applied Cryptography by about four or five years. Right. And it's, it's fine. Like it's, it's, it's fine that that's not his thing. Like, that's not what he's doing. Like why, why? It's not my thing either, right? but why not just call somebody whose thing it is? it is

Deirdre:

Yeah, because I went directly to the, like, what are they actually running on this quantum circuit and like, how big is the circuit? what are the target architectures that they're theoretically gonna run this on? What is the circuit depth? Like? What do you, how long must this thing be able to like stay alive for on this quantum computer, for it to be successful and have a useful result to go to this attack. And I was like, they have assumptions in here that I don't think are gonna be, uh, at all for us to worry about for several more years. So I'd went directly to that and I'd completely skipped over the fact that this was trying to speed up Schnorr's, RSA factoring paper that everyone was like, we know you're trying to do this for years and you're not succeeding. So the fact that, this attack is trying to speed up that, like there is a lot of people, including well versed, uh, you know, Leo Ducas who does lattices, like lots of people who are full on cryptographers in this space saying, this doesn't work, this Schnorr paper, this attack doesn't work, if you're trying to throw some quantum fairy dust on it, it still doesn't work. And that's been in the, in the ether on the internet, on Eprint, presentations given about how this doesn't work. You could do a quick Google and you would find them. So I'm surprised that you wouldn't go either pick that up, or go look for that before you start writing about it.

Thomas:

these are like, these are opinions about like a Schneier story that I just read and like opinions I have about and kind of how Schneier is as a cultural figure here. Like there could be more to this that I don't understand and all that. But I'm less interested in the Schneier part of this. Um, I mean, we're picking a bit on, we're picking more than a bit on Schneier here. Right. But he's not the only person that this kind of phenomena of like the collapse of cryptography into a single subject has happened with, we saw this just a few months ago, with Voldemort and the lawsuit against, like the quantum, the, the NIST quantum computing FOIA

Deirdre:

God. Yeah,

Thomas:

where it's like in the public consciousness, like Voldemort and I guess it's prob, it's probably, it's probably more fair in Voldemort's case, right? Like we're talking about people who like, specialize. There's that too, right? But like we're talking about people who like specialize in block cipher cryptography, not specializing in, you know, asymmetric number theory, cryptography and all that. And like, Voldemort is a notable counter example, right? Like, but like, you know, but in the public consciousness there's Voldemort who is the acknowledged expert and internet cryptography hero, and nobody else, right? So like, if Chris Peikert had said like, you know, this Voldemort lawsuit is complete fucking bullshit, right? Like, everyone would be like, who the fuck is this Chris Peikert guy? Like, you know, Voldemort says so, and we're all the death eaters. So like, we gotta go with.

Deirdre:

at least in like the general technical kind of general engineering like space. there's specific names that people think of when they think of either cryptography or, I don't know, Schneier writing about blah because they kind of have kind, not kind of popular science books on cryptography, but they're definitely like popular... names as opposed to real researchers, real cryptographic engineers. You know what I mean? Not saying that Voldemort isn't a real researcher, real cryptographic engineer because they are,

David:

But Voldemort's talking at CCC every year, and Chris Peikert is not.

Thomas:

E Exactly right. And so like, when the story comes out, it'd be helpful if people understood that, like, you know, if you're talking about post quantum cryptography, some names of people who you should be super interested in hearing from would be Chris Peikert, Luca DeFeo. Um, I mean, you can probably name more, I can only name those two yeah, so it's like,

Deirdre:

Yeah, who who was on our pod

Thomas:

I, I, I had Galbraith's

David:

and

Thomas:

name

David:

forgot.

Thomas:

No, I,

David:

You were on that episode.

Thomas:

no, I know. It's just, I'm not, I'm not gonna get into the thought process I went into of whether or not she used to. I apologize to Steven Galbraith. Right. But yeah, it's, it's helpful to know like a set of names in each of these. It's helpful to know roughly what the fields are or the sub fields are, and it's helpful to know some of the other names. Um, and here with the, uh, the RSA attack thing, it would've been very helpful to know the names of some people whose reactions you would want to get long before you know Bruce Schneier's.

Deirdre:

Mm-hmm.

Thomas:

and that has nothing to do with Bruce Schneier, although I would fault him for not reaching out to any of those names to get a quote for the article that he put out that scared the shit out of everybody and had reporters calling him up and him telling him, like giving a hedged thing about like, maybe this works, but probably it doesn't work. But maybe it doesn't, it doesn't work.

Deirdre:

And he, he's updated this post like five times, which is good. But also like the first cut that everyone sees was very like, I think we might need to worry about this. And it's like, yeah. No matter how many times you kind of amend, amend, amend, and issue corrections, that's not the first signal that goes out.

Thomas:

it's to me a little damning that the blog post, which got a lot of coverage, like a lot of traction. Right. It's a little damning to me that the blog post doesn't talk about, though,"this destroyes RSA" controversy from a year and a half

Deirdre:

Yeah, I just

Thomas:

It seem, it's, yeah,

Deirdre:

not great.

Thomas:

it's, I don't know if he's aware or not. I'm certainly not making claim there, but it seems pretty important to the story. This is part of that line of research, which has not panned out. It's not there. long story short, just understand there are lots of different experts in different subjects and they don't, as a rule, kind of cross over with with each

Deirdre:

each other yeah. And like,

Thomas:

for podcast hosts. We have to be experts on, on everything.

David:

Exactly. I, I will say, you know, every field needs a couple people who you send to testify to Congress when your field needs to testify to Congress. And I'm happy that Bruce Schneier can do that. And I'm happy that Matt Blaze can do that. Um, there are official people to send to congress.

Thomas:

I think the world, I mean, I like Bruce Schneier too, but I think the world of Matt Blaze and certainly have no commentary about Matt Blaze.

Deirdre:

Matt Blaze is a good egg.

David:

Matt Blaze has the keys to your house.

Thomas:

Deirdre, we did it. We came in at a tight 42 minutes.

Deirdre:

yes. So I would guess, I guess my, my conclusion would be, no, this is not destroys RSA with some quantum fairy dust

Thomas:

doesn't destroy RSA in a funny kind of way.

Deirdre:

Kind of funny. Yeah, just kind of frustrating.

Thomas:

I find it funny.

Deirdre:

Yeah. And two, we need a little bit more understanding of there's a diversity of cryptography like quantum computing is like a whole nother thing. So like, try to be aware of the diversity of expertise.

Thomas:

yeah, there's the abstract algebra kind, and then there's the statistics kind.

Deirdre:

Sure

Thomas:

David, would you like to sign off on my unified theory?

David:

I, I don't know, man. I, I don't believe in continuous math. I don't think it's real. You ever see in half a bit? Exactly.

Deirdre:

Ha. Half a qubit, Well, kind of, I'm making vectors with my fingers about the fucking, yeah. Polar coordinate. So no RSA is not destroyed. Yet. Cool. That's it.

Thomas:

Okay.

Deirdre:

Bye

David:

Security Cryptography Whatever is a side project from Deirdre Connolly, Thomas Ptacek, and David Adrian. Our editor is Netty Smith. You can find the podcast on Twitter@scwpod and the hosts on Twitter@durumcrustulum,@tqbf, and@davidcadrian. You can buy merchandise at merch.securitycryptographywhatever.com. Thank you for listening.