RESEARCHERS have described a new classical-computing attack that can forge signatures from some RSA keys without first factoring them. The technique targets “textbook” or blind-signature RSA, which relies on an oracle that provides yes-or-no responses to queries. It uses a variant of the special number field sieve to extract information through a very large number of operations.
The researchers estimate that forging a signature for a 1024-bit key requires 2^65 operations and about 1,380 CPU core-years, compared with an estimated 2^80 operations and 500,000 to 1 million core-years to factor such a key.
The work, presented in a research paper by Nadia Heninger and colleagues, reduces estimated security levels to 2^65, 2^90 and 2^119 for 1024-, 2048- and 4096-bit keys respectively. Those figures are below the 128-bit minimum generally required by the NSA, NIST and ENISA, although the authors and outside experts say the attack is not an immediate practical threat. The researchers performed the work without GPUs or AI-assisted coding, so optimisation could lower the costs further.
The attack does not apply to the PKCS or PSS padding used by most RSA deployments, which removes the oracle involved. However, some systems still use blind-signature RSA, including Privacy Pass implementations used by Apple, Cloudflare and others. An attack there would require compromising a relevant server and obtaining 2^43 signatures; regular key rotation reduces, but does not automatically eliminate, that possibility. The findings add urgency to migration away from vulnerable RSA designs and towards systems intended to withstand future quantum attacks.