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.

Posted on September 28, 2026 at 7:02 AM • 14 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.

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.

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

Clive Robinson • September 29, 2026 11:38 AM

@ iAPX,

With regards your “two fears” of,

  1. An Eureka moment from a genius, and boommm, pans of cryptographic security is gone without warning
  2. Corrupt pseudo RNG, again and again

What happens when you consider the two being coincident?

I call it a “nightmare” and one that has for many years kept me awake when thinking about the issues to do with “Key Generation”(KeyGen) in production systems with high throughput required.

In theory quantum noise sources have both,

1, flat probability.
2, High independent output.

But that does not fix

  1. No vector should be ever reused.
  2. The average of the set and clear bits should be close to 50:50.

Whilst the second can be fixed by a couple of tricks such as, shuffling algorithms, bit flipping, and bit dropping.

The first issue of no KeyMat “reuse” is actually much harder to solve and in effect becomes similar to the “Password no reuse” issue.

That is you can try the impossible of keeping a database not of the actual values but the crypto secure hash of them.

Or you can split the key into two parts one of which is a “salt” made by using a crypto algorithm in CTR mode. It should be used for only about 1/4 of the bits. That way each random output from the generator is guaranteed to be unique but only under certain strict conditions (such as no subsequent dropping or flipping of any of the CTR stream bits and that their positions within the vector should not be changed.)

Celos • September 30, 2026 5:08 AM

@iAPX:

“True” RNG is possible and actually cheap. A Z-Diode or reversed transistor PN junction produces quite a bit of quantum-tunneling avalanche noise (i.e. one electron tunnels and then that causes a large “avalanche” amplifying that signal). The avalanche signal is large enough to be measured cheaply. What you do is sample generously and crypto-hash together for “true” (i.e. quantum effect based) randomness and to eliminate the Brownian (“deterministic”) noise.

Note that I put “true” in quotes because nobody actually knows how quantum effects like tunneling work and hence they are currently regarded as truly random by Physics.

Cost is something like $5 per device at mass-scale or a bit more for a high-bandwidth version. The problem is nobody is willing to pay for it.

References:
ElCheapo: google(“white noise generator circuit”)
High BW: https://www.analog.com/en/resources/design-notes/building-a-lowcost-whitenoise-generator.html

Clive Robinson • September 30, 2026 7:36 AM

@ Celos, iAPX, ALL,

With regards,

““True” RNG is possible and actually cheap. A Z-Diode or reversed transistor PN junction”

And very inadvisable to use without a lot of supporting circuitry to detect it is still working correctly.

Basically the circuit is very fragile and you should not use a zener but avalanche diode.

They are also highly susceptable to “Fault Injection Attacks by EM Radiation” that can kill the entropy down to just a few bits at best. And would turn your idea into a very poor PRNG that would be worse than the on chip RNG junk Intel tried fobbing people off with for years.

But consider, a few years back now, a couple of students from the UK Cambridge Computer Lab won a best paper award at USENIX for taking a very expensive IBM TRNG and just pointing a CW EM source of moderate power at it. The entropy went down from 32bits to around 7 bits.

You can have even better results by using an appropriately modulated EM source as I’ve talked about here and other places in the past.

I’ve “done work” in the area of EM Fault Injection Attacks since the 1980’s when the 1802 COSMAC was the CPU of choice for mil and industry systems. When one “safety test” for Industrial controllers was to hold a VHF 1-2watt Hand held radio’s antenna up against the case the 1802 was in and just press the PTT and move it around. All to often the 1802 “would take a walk in the park or just hang up” so would fail the “Factory Acceptance Test”(FAT).

Leave a comment

Blog moderation policy

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.