Build1 publisher2 min readPublished
UC San Diego and Inria oracle attack cuts textbook RSA-2048 security by 22 bits
UC San Diego and Inria researchers report an attack, not yet peer reviewed, that cuts textbook RSA-2048 from 2^112 to 2^90 operations. It needs billions of queries against a raw RSA private key, so unmonitored HSMs and key-management services are the first place to look.
The Engineer · Build desk
What happened
- Researchers at UC San Diego and Inria Nancy published a paper describing a new attack on textbook RSA, and its findings have not yet been through peer review.
- Reported operation counts fall from 2^80, 2^112, 2^128 and 2^144 to 2^65, 2^90, 2^105 and 2^119 for 1024-, 2048-, 3072- and 4096-bit keys.
- The researchers ran the attack against Thales Luna hardware security modules, both as physical devices and in their online-service form.
- Tom's Hardware says textbook RSA is used in Cloudflare Privacy Pass, iCloud Private Relay and Apple's Private Cloud Compute.
Compiled by The EngineerSomething wrong?How this is made
Why it matters
- exposure Anyone who records traffic under a raw RSA key today and also gathers oracle responses could decrypt it later, within weeks or months by Tom's Hardware's estimate as hardware improves.
- precedent The paper calls its own algorithms far from optimized, so the published counts are a first result that GPU and AI-assisted tuning could push lower.
- decision Raising a raw key from 2048 to 4096 bits buys back 29 bits under the attack but lands only 7 bits above the old 2048-bit figure, a weak stopgap next to replacing raw RSA.
Every count in the paper assumes the attacker already has an oracle for the target key. Tom's Hardware describes an oracle as a service that takes a number in, runs it through a computation involving the private key, and returns the result without revealing the key [14]. The textbook variant accepts any number as input, and the attack depends on that [14]. The steps, in order:
1. Query the oracle a very large number of times, often billions, against a live server or a standalone hardware device [5]. 2. Run the paper's computation over the collected responses [14]. 3. Use the result to read captured traffic that was encrypted under the same key [3].
The reduced counts hold only if the attack's conditions are met [2]. For a given system, that means step one has to be possible there. Billions of queries against a live service will almost certainly draw an IP ban, Tom's Hardware argues, and Cloudflare and Apple can reasonably be assumed to run such controls [8]. The publication's concern is key management services that nobody watches closely, hardware ones included [8].
The cuts are 15 bits at 1024, 22 at 2048, 23 at 3072 and 25 at 4096 [1]. At 1024 bits the work drops by a factor of 32,768 [3]. In Tom's Hardware's judgement, the remaining 2^65 is within reach of entities with large resources, such as some state actors [12]. At 2048 bits the factor is about 4.2 million [2], though 2^90 is still 25 bits above the 1024-bit figure [4]. A raw 3072-bit key under the attack, at 2^105, sits 7 bits below the pre-attack figure for 2048 bits [6].
PKCS #11 equipment is on the same list of raw-RSA users, according to the article: many smart cards, USB security tokens, code-signing pipelines, HSMs and TPMs [7]. The claim is broad, and the article does not test it product by product. I would use it as a checklist of places to look.
Starting that check before peer review costs little, and I think it is the right call. A wholesale RSA migration justified by this paper alone goes past the evidence. The attack covers only the raw variant, which the article says is not widely used for website certificates and remote access [4]. RSA in general was already deprecated in favor of ECC and post-quantum algorithms while still running in a substantial share of services [13]. Inside that existing migration, this result moves one class of key to the front of the queue: raw RSA keys that answer arbitrary queries from callers nobody meters.
What to watch
- Peer review of the UC San Diego and Inria paper, and whether the 2^65 to 2^119 operation counts survive it.
- Guidance from Thales on limiting raw RSA queries to Luna HSMs, in hardware or as a hosted service.
- Confirmation from Cloudflare and Apple that Privacy Pass, Private Relay and Private Cloud Compute cap queries per key.