New Attack Against RSA

ArsTechnica is reporting on a “new” attack against RSA, one that bypasses factoring.

First, this attack isn’t new. The original research is from 2007. What is new is the implementation.

Second, it is a forgery attack. It allows an attacker to forge digital signatures. It does not recover the private key from the public key.

Third, the attack only works against pure signatures. That is, signatures without any formatting or padding. This is not generally how we use RSA in practice.

Fourth, speed is all relative. This is not a polynomial-time algorithm; it’s a subexponential-time algorithm. But it is somewhat faster than factoring. The authors were able to forge messages for 1024-bit RSA with 1380 CPU core-years (over five real-world months).

The authors have a webpage that explains the context much better than the article. And here’s the paper.

EDITED TO ADD: Slashdot thread.

Tags: academic papers, cryptography, forgery, RSA

Posted on September 28, 2026 at 7:02 AM • 11 Comments

Comments

Billy Jack • September 28, 2026 7:21 AM

For ssh, my servers all require a minimum 4096 bit key for RSA: RequiredRSASize 4096.

They also require three separate keys, not just one: AuthenticationMethods publickey,publickey,publickey. Usually, the three keys are ED25519, RSA, and ECDSA.

Clive Robinson • September 28, 2026 7:32 AM

@ Bruce,

What was it you once said about attacks never get worse with time?

😉

Rontea • September 28, 2026 9:11 AM

If these results hold, we’re looking at a fundamental shift in how we think about RSA security. Signature forgery without full factoring is a conceptual game-changer. The practical risk is limited today, but research like this is exactly the kind of thing that reinforces why cryptographic agility is critical. Systems still using 1024-bit keys or textbook RSA need to take a hard look at their exposure. Rotating keys and moving to modern padding schemes like PSS isn’t just best practice—it’s survival. And for everyone else, this is another reminder: don’t wait for the emergency to start planning your post-RSA future.

David in Toronto • September 28, 2026 9:35 AM

@Rontea in short – the building is going to burn down so we should walk, don’t run to the exit.

RSA has been a wee bit precarious for a while due to the exponential growth in key lengths. I haven’t checked in a while but is anyone supporting keys longer than 4096 bits?

Clive Robinson • September 28, 2026 10:20 AM

@ All,

Don’t try saying “NSNFSSSFSFN” it will sound like you are suffering from a sleepless night 😉

But more importantly,

“[T]he attack only works against pure signatures. That is, signatures without any formatting or padding. This is not generally how we use RSA in practice.”

It needs to be said that as a general rule of thumb in crypto you do not use padding, formatting, or linear codes –error correction– at what would be the “plaintext” level as it can easily give rise to short cuts or distinguishers around which attacks can be improved or automated (Structural Attacks).

As a general rule protection against transmission errors and the like is carried out at or above the ciphertext level specifically to the transmission channel. To avoid “structural attacks”.

In the past people have tried to incorporate error correction and ciphering. Mostly it’s been rejected with the only one to “clear the grass” being the work from the late 1970’s by Robert McEliece.

However a cautionary note about McEliece is that whilst you can use many different linear error correcting codes (‘C’), nearly all have failed to structural attacks, leaving the originally suggested Linear Goppa Codes.

However due to ‘C’ McEliece has made it as a candidate for “Post Quantum Cryptography”(PQC).

KC • September 28, 2026 11:38 AM

Hat tip to Bruce, Clive, and Dan
Great FAQs on the authors’ webpage.

From Dan:

“some real-world systems continue to use blind-signature, also known as textbook, RSA.”

This includes the Privacy Pass protocol in Apple, Cloudflare, and many others. However, an attacker would need to request 2^43 tokens.

And from the paper:

“Apple appears to rate-limit token issuance to one per minute [11], so completing 2^43 queries would require 17 million years to complete on a single device. Parallelized across the 2.3 billion active Apple devices that Apple claimed in a 2025 earnings call [18] it would take 2.3 days to complete 2^43 queries at a rate of one per minute per device. Persona charges per API call; at their published rate of $1.50 per call [58] the cost to carry out the queries would be $13 trillion. Apple’s iCloud Private Relay [4] also documents a protocol which uses blind RSA signatures to anonymously authorize web users.”

Another hat tip to Hacker News. There’s a poem at the end of the paper.

Anonymous • September 28, 2026 12:12 PM

It was well-known that RSA is not equivalent to factorization. Rabin’s signature is equivalent to factorization but size is twice as large. https://en.wikipedia.org/wiki/Rabin_signature_algorithm

Clive Robinson • September 28, 2026 6:02 PM

@ ALL,

From the Dan Goodin article in ARSTech,

“Most Privacy Pass implementations rotate keys regularly, a measure that greatly reduces, but doesn’t automatically eliminate, the chances of attacker success.”

Read that carefully because the first half “rotate keys regularly” can and often does negate “greatly reduces”.

The reason is that under all the crypto magic lies “integers” that in reality are vectors of bits.

In crypto for such things you have four primary but virtually incompatible requirements in a major implementation,

1, No vector should be ever reused.
2, Every vector should be fully independent of all others.
3, There should be no determinism or structure in bit selection.
4, The average of the set and clear bits should be close to 50:50.

(There are other requirements such as length of bit runs but they just make the problem worse).

Whilst there are ways to meet these four requirements they are generally slow and not suitable for high through put production systems.

The result is thus often somebody “invents a method” by “Home-Brew” system that all to often uses a weaker crypto algorithm as a short cut or to save resources.

Or breaks other security requirements such as properly disposing of used “Key Material”(KeyMat) and auditing new KeyMat as part of “Key Management”(KeyMan).

All such “Home-Brew” systems are thus likely to be more susceptible to new attack methods than “factoring” will be.

Thus I fully expect to see further successful “non factoring attacks” in the future.

But something for people to mull over. I’ve mentioned on the odd occasion that Current AI LLM Systems have a “Digital Neural Network”(DNN) at their heart. Further I’ve indicated that in reality the DNN is actually a “Digital Signal Processing”(DSP) system that acts as an “adaptive filter” the purpose of which is to draw coherent signals from seemingly random noise[1].

Now imagine how with a little tweaking such a network could be used to find any statistical pattern in otherwise thought to be “random” noise.

[1] There is a myth that most noise signals, in particular “Average White Gaussian Noise”(AWGN) shaped noise is “truly random”…

The bad news is outside of certain fairly rare physical processes noise is actually not really random at all.

A coherent signal diminishes with range and other “Shannon Channel” issues. These signals “add” in linear channels and multiply in non-linear often “Square Law” channels.

We know from research done on codes using plaintext books, back quite a bit into the last century that after four or five plaintext book additions the resulting character stream “looks random” enough to use as a “stream cipher – key stream”.

However more modern techniques will enable such additive stream noise to be decompiled back into the constituent plaintexts. It’s something that a lightly modified Current AI system could do.

Thus layer by layer the supposedly random noise can be stripped back to individual signals and removed one by one.

This signal decomposition is an issue that comes up in the design of “True Random Bit Generators” where cross modulation from the power supply and other signal sources causes deterministic signals to get mixed together and appear to give randomness that is in fact “faux-entropy” and in effect swamps any “true-entropy” below a useful level.

We know this to be the case due to “EM Signal Fault Injection” on the likes of IBM True Random Bit Generators where the measured output entropy dropped from more than 32bits down to around 7bits.

A fault that Intel “on chip” “random number generators”(RNGs) suffered from as well (something I’ve discussed here in the past). And why Intel and other manufacturers always add a crypto algorithm after the actual “on chip” RNG, but do not allow you access to the actual raw RNG output for “fault testing” (which is a very major “No No” security wise, and fairly suspicious as a PRNG based around a crypto algorithm in CTR mode will look statistically better in the usual canon of tests,

https://webhome.phy.duke.edu/~rgb/General/dieharder.php ).

אני כאן • September 28, 2026 7:24 PM

Many moons ago, sometime towards the end of 1991, so almost 35 years ago, an unnamed asset of an unnamed country, him and I discussed some advanced methods of signal discovery and how certain responses some/certain plant/flora species offer/give off, only to certain frequencies. I was a young recruit then, with only a couple-three years of “experience” and boy was I Impressed with that advanced research and many other methods of covert communications use/discovery in the beautiful world of SigInt. And it downed upon me that I must be one of the very few chosen ones on this planet called Earth, to have been selected to serve a higher purpose.

God bless Israel.

Celos • September 29, 2026 2:50 AM

Yes. Essentially another incremental step. No need to throw RSA away or to panic, although this is not quite the mirage that “Quantum Computing” still is and is likely to remain.

iAPX • September 29, 2026 6:37 AM

@ Clive Robinson, All

Totally agree, for different reasons and different purposes, RNG are not True RNG. I wonder if True RNG is ever possible.

For RSA, I am in no way scared by this attack on signatures w/ 1024 bit keys.
Actual 4096 bit keys are only 4 times the length, but they are theoretically up to 2^1536 times stronger !
Many of us use 8192 bit keys nowadays.

I have two fears:
– An Eureka moment from a genius, and boommm, pans of cryptographic security is gone without warning
– Corrupt pseudo RNG, again and again

New Attack Against RSA

Comments

Leave a comment Cancel reply