# Has RSA been destroyed by a quantum computer???
Security Cryptography Whatever, 2023-01-06.
Page: https://securitycryptographywhatever.com/2023/01/06/has-rsa-been-destroyed-by-a-quantum-computer/
This transcript has been edited for length and clarity.
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.
**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.