RSA is not destroyed, but do remain vigilant and be crypto-agile!

During the last couple of weeks, a little shake went through parts of the security community. This was caused by a preprint by Professor Dr. Claus Peter Schnorr titled “Fast Factoring Integers by SVP Algorithms”, published on the IACR’s E-print Server.

The article describes a new method to find the prime factors p and q of an RSA modulus n, and claims that it is dramatically faster than the so-called General Number Field Sieve, which to this date is the best factoring algorithm for cryptographically-sized moduli. Indeed, the closing sentence of the article’s abstract reads: “This destroys the RSA cryptosystem.”

The proposed factoring method uses a mathematical structure called lattices, and Professor Schnorr is a longstanding and highly recognized expert in the field of the mathematics of cryptography, and on the use of lattices in cryptography and computational number theory in particular. Which is to say that his preprint had to be taken seriously: If Schnorr’s claims are correct, this would mean the end of the cryptographic use of the RSA algorithm!

While Schnorr’s novel approach had been circulating in the research community already for at least several months, the newly posted preprint gave it a new and scary twist. So people quickly went to work, analyzing and discussing the paper (e.g., Does Schnorr's 2021 factoring method show that the RSA cryptosystem is not secure? - Cryptography Stack Exchange and No, RSA Is Not Broken - Schneier on Security), and cryptographer and lattice expert, Leo Ducas, did a SAGE implementation of the core idea. A few (long) days later, the conclusion of the mathematical analysis has been that an important bound in the paper (on a specific lattice determinant) was fatally underestimated, and the rogue implementation showed that the claimed performance was not even close to hold in practice.

Phew!

This is somewhat reminiscent of the Fall of 1998 when at the Second Elliptic Curve Cryptography Workshop in Waterloo, Joseph Silverman outlined his Xedni Calculus Attack on the Elliptic Curve Discrete Logarithm Problem. This algorithm, if practical, would not only have broken elliptic curve cryptosystems but also could easily have been modified to render DSS (Digital Signature Standard) and RSA insecure! Given the sophisticated ideas and subtleties in the algorithm’s running time analysis, it took us several weeks to solidly establish that Silverman’s attack was completely failing both asymptotically and in the practical range.

While for the time being, the “all clear” signal is still given for RSA, researchers may further investigate in the weeks to come whether Schnorr’s idea can be turned into a practically useful algorithm after all. What surely stays on is the reminder of the possibility that from one day to the next, some new breakthrough discovery can make a cryptographic algorithm less secure, or even insecure!

The take-away from happenings like this is: being crypto-agile is of uttermost importance! You need to be able to apply rapid changes to your crypto parameters or crypto algorithms without disrupting the business processes.

See our recommendations on how to architect a resilient and agile cryptographic infrastructure.