Researchers from the University of California at San Diego have developed an improved attack technique on the RSA algorithm. This technique allows for forging digital signatures without the need for factorization of the underlying RSA primes or the recovery of the private key. The resources required to carry out an attack on a 1024-bit RSA key are estimated at 1380 years of computation on one processor core. Using an existing university cluster, researchers were able to determine the parameters necessary to generate fake RSA signatures in just 5 months. It’s important to note that AI accelerators and GPUs were not used in the experiment, and utilizing them could significantly reduce the computation time. In comparison, the traditional factorization method for recreating an RSA-1024 private key requires between 500,000 to a million years of calculations on a single processor core.
To execute an attack using this new technique, it is necessary to send repeated requests to sign data generated by the attacker, such as through an authorization service or HSM module. Approximately 232 requests are needed to determine RSA-1024 parameters, and 243 requests are necessary to attack RSA-2048 keys. Once a series of signed data is obtained, a complex process of parameter calculation is initiated (about 265 operations for RSA-1024). This enables the attacker to create fraudulent signatures for any data, requiring around 180 hours of calculations on one core for each signature.
This attack method is specifically applicable to RSA signatures that do not utilize formatting or additional padding before encryption. Implementations of blind signatures, like those in the Privacy Pass protocol, are vulnerable. However, most RSA implementations currently in use, including PKCS#1v1.5 and RSA-PSS (utilized in TLS and SSH), employ padding and are not susceptible to this attack.
The RSA encryption relies on exponentiation modulo a large number