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.

---

This transcript has been edited for length and clarity.

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???

No, this paper does not break 2048-bit RSA.

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: It wasn’t released this week. I think it was released, uh, just before Christmas.

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 for normal, like IBM, Google, quantum computers in numbers of qubits, which is what a lot of people think is all you need, has an algorithm 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 all right. So, there’s the well understood notion that one of, like the big thing that quantum computing theoretically breaks is RSA, right?

Deirdre: And discrete log.

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

Deirdre: Correct, yes.

Thomas: So, we all know quantum computers break RSA, if you can get a quantum computer of that size (which I don’t believe they exist, but whatever) with Shor’s algorithm, right? So the problem with that is that 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

Deirdre: With an ‘n’

Thomas: Yes, Schnorr with an- the Schnorr of Schnorr’s signatures, right? Like the famous Claus Schnorr.

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), 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, into one thing.

Deirdre: Shamir, Schnorr, they’re all that same and they’re all mean to me.

David: More or less.

Thomas: So Schnorr’s algorithm is not a quantum algorithm, right? Schnorr’s algorithm is 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.

Thomas: There’s this conventional algorithm for factoring called Schnorr’s algorithm, which, ostensibly it’s supposed to be competitive with the fastest, superior to, the fastest, kind of conventional factoring, in the numeric field sieve and all that stuff, right? It’s not, but that’s the idea, right? If you can get it working.

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-

Deirdre: Yeah, ‘quantum approximate optimization algorithm’, which is like a thing that people keep trying to throw at problems in a similar way to this.

Thomas: 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 gotta say before we go further: so the idea here is that this is an attack that you could carry out with a quantum computer, “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) you can’t take the numbers, the qubit numbers that we have on those computers at face value, right?

Deirdre: There are 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: 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 need three [or more] physical qubits, 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 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 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? Do, we wanna talk about like the Schnorr approach, like this, tangent kind of conventional approach to factoring? Or do you wanna talk more about quantum computers and circuit depths?

Deirdre: I will say that, 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 thing you’re attacking, which is like 2048 bits in the case of RSA or some other security factor, it’s actually either, subexponential 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 doing factoring classically. So.

Thomas: This is in the supposed quantum-

Deirdre: Yeah, yeah, yeah. So, it’s both based on flimsy assumptions about, our current quantum computers, [and] 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[es] 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, 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.

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: Rigetti

Thomas: Okay. 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 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 1024 qubit, like physical qubit or logical qubit, computer and you weren’t able to run Shor’s algorithm and factor like RSA 1024, that would be pretty huge. I think the current record is like RSA, like 520, but, they’re not.

Thomas: So 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, kerfuffle. So I actually, 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, there was that thing like last year or the year before last, where Claus Schnorr submitted a new iteration of his paper, his lattice approach to factoring, where like it had a note saying this “destroyes” the RSA cryptosystem.

Deirdre: A typo. And we were all like, what?

Thomas: And that’s like, that was headlines everywhere. Like, “this destroyes RSA”

Deirdre: from Claus Schnorr, yeah.

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

Deirdre: The SVP problem is the shortest vector problem.

Thomas: Yeah, if you wanna tell people what a lattice is and what the shortest vector problem is-

David: Or we could say, just go listen to our episode with Chris Peikert

Deirdre: Yes,

Thomas: I wasn’t on that episode, so

Deirdre: Please refer back to, lattice based crypto episode with, Chris Peikert. It also mentions Michigan beating Ohio or something like that.

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, 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 assumption.

And then if we mention the closest vector problem, it is related but not exactly the same, where you’re trying to find the closest, with some measure of close, to another vector in a similar setting.

Thomas: So, I gather that, 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; there was a theory paper posted in 91, 93, something like that, right?

And then 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 sieve, right. It certainly doesn’t destroy RSA, right. It’s actually 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 seems like it was a super valuable contribution to the science, if not to anything in practice, but, 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: Trying to find the right heuristics that will make it work and it hasn’t panned out.

Thomas: And the last iteration of this was like a year and a half ago, the “Destroyes RSA” paper, which is kind of sad, right? A bunch of people went at that paper. ‘Cause I mean, it said it destroyed RSA, like a bunch of cryptographers went at it. There were, basic, basic errors that were found in it.

And, people had to say like, Claus Schnorr, he’s in his, what, late seventies now? But, 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 thing, right? So, this is one of the big stories in RSA and conventional cryptography for the past, it’s, holy shit, it’s like 2023 right now, for like 20 years, right, has been this story, “does this approach work?”

And the answer is, no, right? The conventional algorithm here doesn’t work at all. Right. And then the quantum fairy dust 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, worse, than that of Schnorr’s algorithm, right? Like, doesn’t do anything at all, right? 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 help with convergence when trying to do factoring” or whatever. And we’ll just throw some quantum at it and it’ll speed up that part. And, that’s actually not really panned out.

David: So, 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 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? ‘Cause 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 you go back to the Chris Peikert episode that we had, which I will claim to have listened to, but 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 super weird, right?

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, 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 quantum circuit. But either way, yeah.

So tl;dr: 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?

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.

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 saw it come across our radars and we’re just like, ‘Ooh’, and then people looked at it for a few minutes and were just like, this seems suss. And then multiple people looked at it for more than five minutes and said, this seems suss. But not everyone has, you know, enough cryptography 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, “I saw a paper that claims it breaks RSA”, like ‘wat’, and people have been writing…things.

Thomas: Yeah. I’m gonna read the start of an article right now. 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 to take 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 already know.

Thomas: Roger Grimes!

Deirdre: No

Thomas: No, I’ve barely had idea who Roger Grimes is. But 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

David: Bruce Schneier, the cryptographer from the deep.

Deirdre: Who is Bruce Schneier?

Thomas: Bruce Schneier is somebody who has forgotten more about block cipher cryptography than I will ever bother to learn. So he’s, a famous cryptography…I’m looking for the right term famous cryptography person, is the term I’m gonna choose there. But he has, probably the world’s most read cryptography blog, the ostensible authoritative source for news about (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 I think big.

Deirdre: I’ve heard of several of his books including 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, not ‘cause I have any real problem with Bruce Schneier, who, like, there’s a lot of things that Bruce Schneier is that I respect.

But Bruce Schneier’s influence on kind of, the engineering profession’s understanding of cryptography, is, what’s the word I’m looking for? Um, [REDACTED], right? Bruce Schneier is most notable for writing Applied Cryptography, which is probably, without a doubt, the most famous book in cryptography. 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 Menezes, that came out right before his, and it had a similar name like Handbook of Applied 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, 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.

So I guess I have a couple of different ways to come at this, right? One of them is just, ‘frustrating’ is not the word, but, it’s frustrating to, 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, a starting point as 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. So, I’m not putting myself ahead of anybody here.

David: We’re all putting Deirdre as the podcast cryptographer.

Deirdre: Aw.

Thomas: Fair enough. Yes. So, there’s a general kind of, people have like a bit set in their head, just, 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, that’s kind of, pretty much never been true, 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 now.

Thomas: Yeah, yeah. So, cryptography is super specialized, right? Just a starting point, with a couple of exceptions, if you’re a person who does block cipher designs where, one of your block ciphers is super widely used, chances are, you’re not an asymmetric crypto person. You don’t do a lot of number theory research, or you’re not doing, Diaphontine equations and elliptic curves, just, it’s a different set of things, right? If you read attack papers about block ciphers, and then you read attack papers about, elliptic curves, they’re not the same things, right? 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, that is what gets me excited and I get very, very into- the block cipher stuff, even hashes, like symmetric stuff, I know enough about them to be like, that’s a good one. I like that one. I’m more interested in block cipher modes and things like that, and I just do not have the depth on that side as I do on the asymmetric side, just, because.

David: 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 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? And it’s not like we’re lacking, and we have a particularly high density of cryptography knowledge on this podcast.

Deirdre: Right. I know enough about quantum computers, just so that I can model the adversary for my favorite, you know, squidgy isogeny-based, theoretically quantum resistant, 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 large, error-corrected, very efficient quantum computer that’s gonna try to attack me, but 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 [laughing]

David: Whenever this stuff happens.

Thomas: Well, let’s put a pin in that. I wanna come back to that in a second. Schneier’s a block cipher guy, right? Schneier’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 a practitioner in the sense that I am, I don’t know actually what Schneier’s background is. I don’t know if he’s got like a graduate degree in any of this stuff or, the way he’s published, and I’m not published at all here, right? But like Schneier has 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 [University of Westminster], presumably, ‘cause he wrote that book with Yoshi. And then, has a policy appointment in one of the Harvard associated think tank thingies.

Thomas: Yeah. He’s responsible for Blowfish, which was a really popular block cipher. He was responsible for Twofish and then like a hash based on Twofish, which I forget the name of- and hashes and block ciphers, closely related disciplines. If you look at like the absolute state of the art in hash breaking stuff right now, it’s modernized, refined versions of the differential cryptanalysis attack, right, of the same line of research- I’m not talking down this line of research, it’s incredible research. But it’s a very specific set of research that applies in no sense whatsoever to RSA. There’s just no application to it. They’re not similar problems.

And Schneier has like written for a long time. He wrote, 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 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, but-

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, was he the patient zero for that sentiment, or was that just sort of 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 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-

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. The math, I don’t know how much there is to trust about it.

Deirdre: For elliptic curves?

Thomas: Yeah. Just the basic idea.

Deirdre: It’s just algebra. It’s kind of nice. If you have high school algebra, you’re good to go.

Thomas: With what we know now about elliptic curves and how things are attacked and all that, and, 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 curves, ‘cause it’s not susceptible to- the index calculus!

Deirdre: Yeah, yeah

Thomas: If you read through the index calculus stuff and why it doesn’t apply to elliptic curves and all that, it’s not super controversial, right? But, 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? Elliptic curve is much better than RSA.

Deirdre: And better than finite field, primes that we were using before, especially for things that were Diffie-Hellman.

Thomas: So what’s weird to me about the blog post, the primary weird thing to me is that like you’re confronted with this wacky paper, and, 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, you presume he had like a minute to go call somebody, right?

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.

Deirdre: 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, maybe the short summary here is, if there’s big news in like SHA-1, there’s a story where if Schneier’s writing about it, I’ll probably pay attention to what Schneier’s saying about it. Because, sure. He’s, he’s done block cipher designs and work on that stuff.

And I sound dismissive here, I’ve done none of this work, but, on a story like this, where the lattice reduction math goes over my head, well, okay, but, the lattice reduction math that we’re talking about here, it’s not new quantum math. It’s one of the biggest stories in the analysis of RSA since 1991, predating Applied Cryptography by about four or five years.

And, it’s fine. It’s fine that that’s not his thing, that’s not what he’s doing. It’s not my thing either, right? but why not just call somebody whose thing it is?

Deirdre: Yeah. I went directly to the, what are they actually running on this quantum circuit and, how big is the circuit? What are the target architectures that they’re theoretically gonna run this on? What is the circuit depth? 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, at all for us to worry about for several more years. So I 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’re a lot of people, including 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 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 opinions about like a Schneier story that I just read and, opinions I have about how Schneier is as a cultural figure here. 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.

We’re picking more than a bit on Schneier here, but he’s not the only person that this kind of phenomena of, 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- the NIST quantum computing FOIA

Deirdre: God, yeah.

Thomas: Where it’s in the public consciousness, like Voldemort and I guess it’s probably more fair in Voldemort’s case, right? 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, Voldemort is a notable counter example, right? In the public consciousness there’s Voldemort who is the acknowledged expert and internet cryptography hero, and nobody else, right? So, if Chris Peikert had said, this Voldemort lawsuit is complete fucking bullshit, everyone would be like, ‘who the fuck is this Chris Peikert guy? Voldemort says so, and we’re all the death eaters, so, we gotta go with it.’

Deirdre: At least in the general technical engineering, 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 have, not popular science books on cryptography, but they’re definitely, popular…names as opposed to real researchers, real cryptographic engineers, uou 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: Exactly right. And so, when the story comes out, it’d be helpful if people understood that, 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, you can probably name more, I can only name those two

David: Steven Galbraith, who was on our pod, and Thomas forgot

David: You were on that episode.

Thomas: No, I know. I apologize to Steven Galbraith. But yeah, 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. And here with 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, giving a hedged thing about, maybe this works, but probably it doesn’t work. But maybe it doesn’t work.

Deirdre: And he’s updated this post like five times, which is good. But also, the first cut that everyone sees was very, ‘I think we might need to worry about this.’ And, 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, t’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 ago.

Deirdre: Yeah, I just think he’s not aware, which is not great.

Thomas: 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 each other.

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

David: Exactly. I will say, 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, 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: This 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, 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?

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

David: I don’t know, man. 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– Polar coordinates.

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.