Researchers forged RSA signatures without ever cracking the key

Researchers have discovered a method to forge specific RSA signatures without factoring the associated key, challenging the conventional belief about the security of this widely used public-key cryptosystem. The study does not appear to jeopardize the most commonly employed RSA implementations, including those protected by PKCS or PSS padding. However, the findings have garnered attention due to the revelation that breaking RSA signatures may not always necessitate uncovering the private key.

The technique proved effective against 1,024-bit RSA keys, which are presently considered outdated. Additionally, it diminishes the estimated security of 2,048-bit and 4,096-bit keys when utilized in vulnerable blind-signature systems. If validated through peer review, this result could be considered a significant conceptual breakthrough, as it suggests that it may be possible to practically compromise RSA without cracking its key.

RSA's security is traditionally grounded in the difficulty of factoring a large number into its two prime constituents. The public key contains this large number, while the private key is derived from the factors. Traditional wisdom held that an attacker would need to factor the number before constructing a valid signature. The new research approaches the problem differently, employing a variant of the special number field sieve algorithm in conjunction with an oracle available in certain blind-signature protocols.

An oracle is a system feature that provides useful information in response to specific requests. By making a considerable number of requests and analyzing the outcomes, an attacker can accumulate sufficient information to generate a valid signature. Factoring a 1,024-bit RSA key is estimated to require approximately 2^80 operations and between 500,000 and 1 million CPU core-years.

The researchers conducted their forgery attack using an academic CPU cluster over several months, which involved about 2^65 operations and 1,380 CPU core-years.

The study was led by Nadia Heninger, a professor at the University of California at San Diego. She emphasized that the result contradicts the prevailing expectations among cryptographers. According to Heninger, cryptographers had believed that the sole method to generate valid RSA digital signatures was to first compute the private key through factoring and then apply the private key to compute the signatures.

For 1,024-bit RSA, this process was considered extremely costly, albeit potentially feasible with the computational resources of large tech companies or the NSA – estimated at tens of millions of dollars worth of computation time for a single key. For 2,048-bit RSA, the task was deemed entirely beyond reach.

The authors estimate that this attack reduces the effective security of 1,024-bit RSA to around 2^65 operations. For 2,048-bit and 4,096-bit keys, they project the figures to be 2^90 and 2^119, respectively. The National Security Agency, the National Institute of Standards and Technology, and the European Union Agency for Network and Information Security recommend a minimum of 128 bits of security.

The research team asserts that their estimates may be refined further. They also noted that their implementation was manually coded and did not utilize GPUs or artificial intelligence tools, which are anticipated to significantly reduce the cost of future attacks. However, the attack is confined to blind-signature implementations, also known as textbook RSA, which allow a party to sign information without accessing its contents.

Most RSA deployments, on the other hand, utilize PKCS or PSS padding, which modifies the data before encryption or signing and prevents the behavior exploited by this attack.

Most RSA systems in use do not exhibit this behavior, as they employ PKCS or PSS padding, which alters the data prior to encryption or signing and prevents the behavior exploited by this attack. Privacy Pass, a protocol utilized by Apple, Cloudflare, and other organizations, employs blind signatures to enable users to prove their authorization without disclosing their identity.

The researchers estimate that attacking such a system would necessitate requesting approximately 2^43 tokens from an issuer. While this volume may appear substantial, it is roughly equivalent to the network traffic handled by major online services like Cloudflare in a single day.