Thread by @matthew_d_green

For most of my life I’ve waited for someone to post a credible claim that they’ve broken a major cryptosystem like RSA, and I’m pretty sure tomorrow I’ll still be waiting.

But that doesn’t make it any less fun to think about what a real (implemented) RSA break would look like. Imagine you were a genius who found an efficient factoring algorithm. You have so much opportunity for drama.

Obviously you could just post your algorithm but that’s boring and anyway practical people won’t be able to tell if it works, especially if it’s complicated and you’re not one of a very small number of researchers.

Fortunately back in the early 90s, RSA security posted a bunch of factoring challenges of which many remain unsolved. So obviously you’d pick some of the big ones and just start blasting out factors. en.m.wikipedia.org/wiki/RSA_Facto…

Your paper “Answers to some of the RSA factoring challenges” picks five of the big ones, gives their factors, and drops the mic. You post it to IACR ePrint.

At this point it’s very important to take a long vacation where nobody knows how to contact you. This is essential to making things more exciting.

A week later, in a fit of irritation, you repost your paper with two more factoring challenges answered. This time someone actually reads it.

By now people are talking about your results on Twitter. It’s gotten to the top of HN. The NYT is interested but doesn’t quite know what to say. Since you haven’t posted your algorithm there’s doubt about whether this is real or a trick.

A trick is possible. After all someone made those RSA challenges, and presumably at some point they knew the factorization. Maybe they kept it? Seems unlikely but so is a polynomial time factoring algorithm.

I’ve always assumed at this point you want to start breaking some really diverse keys. This is harder now that RSA is dying out on the Internet, but DKIM still uses it and so do some older TLS certificates. So break them all. At this point you might be doing some damage.

Sorry I should rephrase. So do lots of TLS certificates. Actually this is great. So now you’re selectively breaking major parts of the Internet and people are really getting nervous.

While this sounds fun, the trick here is not to break things. It’s to be dramatic enough that everyone takes you seriously enough to start ripping a lot of plumbing out of the Internet and replacing it fast, but before the bad guys get you or your algorithm.

(I had it stupidly in my head that RSA was going away because TLS did away with it in the handshake but the signatures are still everywhere. Yikes a real factoring breakthrough would be super bad.)

I want to be clear that you really have to break some stuff. You can’t just be nice and responsibly disclose this, or provide proof that you have people’s keys.

https://twitter.com/ciphergoth/status/1366956799673335809

It took the industry something like 15 years to get rid of the hash function MD5 even as we knew it was getting broken, and even after it was *publicly* broken a spy agency used the break to get Microsoft to sign their malware. google.com/amp/s/arstechn…

A real (hypothetical) break of RSA is a million times worse than a break of MD5 in terms of how urgently the solution has to be rolled out. People need to scared. The IETF has got to be convening emergency meetings.

I’m not saying you should break anything important. Break Sharepoint.

Ok so this is still my favorite “exciting crypto research” scenario and I hope if anyone ever does come up with such a result they’ll be as dramatic as possible about how they reveal it. It sure won’t be me :)

Ok I want to shift away from fantasy to pass along something my friend @nadiaheninger calls “real talk about factoring”. This is all her from here on out, she just doesn’t like to use Twitter.

She points out that the running time of the number field sieve, our best factoring algorithm, is L_n(1/3, (64/9)^(1/3)).

The first number is the exponent of the ln n in the exponent. The second is the constant in the exponent.

She notes that if you change the second one to (32/9)^(1/3) it takes 1024-bit factoring from "still probably out of reach of academic computing power for a few years" to "was done pretty easily in 2007 by some academics".

Says Nadia: the 1/3 is more interesting. The quadratic sieve has a 1/2. It was in the early 90s that mathematicians figured out how to improve the 1/2 to a 1/3.

Again Nadia: The impact of improving the 1/3 to a 1/4 depends quite a lot on the constant, but a back of the envelope calculation shows that an L(1/4) factoring algorithm would likely bring 2048-bit RSA into feasible range.

And so she concludes: Now everyone who is freaking out about factoring... how confident are you that the number field sieve is the best factoring algorithm out there? Does that look like a natural running time?

As a note, she reminds me that in 2013 there was a series of breakthroughs for the function field sieve for discrete log for small characteristic finite fields that changed the running time from L(1/3) to L(1/4) and then to quasipolynomial.

For more than two decades before that the running time had been the same as for large-characteristic discrete log and factoring.

So (Matt again): as “fun” as it would be for someone to break RSA, it’s a lot more fun to think about when it’s completely implausible rather than when it’s a thing that isn’t totally outside of the realm of possibility.