RSA, a widely used asymmetric cryptography system, appears to be more vulnerable than previously thought. Under certain circumstances, researchers can create valid digital signatures without obtaining the private key. This shows that a key assumption about RSA’s security does not always hold true.
Ars Technica reports this. The research does not mean that RSA security can be cracked on a large scale. The attack only works on specific implementations that use so-called blind signatures. Systems using the PKCS or PSS padding commonly used today are not vulnerable.
The discovery is particularly interesting because cryptographers have long assumed that an attacker would first need to obtain the private key in order to forge an RSA signature. This requires factoring very large numbers into prime factors. It is precisely the enormous amount of computational work required for this that forms the basis of RSA’s security.
The researchers, including Nadia Heninger of the University of California, San Diego, have now found an alternative route. Using a variant of the number field sieve algorithm, they can directly construct a valid signature. Factorization of the RSA key is not necessary in this process.
Significantly less computational power
The difference in the computational power required is significant. Factoring an outdated 1,024-bit RSA key is estimated to take between 500,000 and one million CPU-core-years. The researchers needed 1,380 core-years for their attack. When run on an academic computer cluster, this took several months.
The computational cost also changes for larger keys. According to the researchers, the estimated security level amounts to 2 to the power of 90 (2^90) operations for 2048-bit RSA and 2 to the power of 119 (2^119) for 4096-bit RSA. Both values fall below the 128-bit threshold currently used as the baseline for strong cryptography.
Furthermore, the method has seen little optimization so far. For example, the team did not use GPUs. Further technical improvements could therefore reduce the amount of computing power required even further, according to Ars Technica.
No problem for standard RSA
For organizations, there is little cause for concern at this time. Modern RSA implementations add extra data to the cryptographic processing using PKCS or PSS. The new technique is ineffective against these.
One application the researchers are looking at is Privacy Pass. This protocol allows users to prove they are authorized without revealing their identity. Apple and Cloudflare, among others, use it. An attack would require approximately 2^43 requests to a single organization. Furthermore, regularly rotating cryptographic keys makes exploitation significantly more difficult.
The most important implication of the research, therefore, does not lie in an immediate security vulnerability, but in the theory behind RSA. It appears possible to attack its security without solving the mathematical problem on which RSA traditionally relies.
This matters now that organizations are already preparing to replace classical cryptography with algorithms that can withstand future quantum computers. The new method does not make that migration urgent, but it does show that even with ordinary computers, new ways can still reduce RSA’s security margins.