Novel attack slashes computing power needed to crack textbook RSA cryptography

A new cryptographic attack could drastically reduce the computing power required to break RSA encryption, according to a paper from UC San Diego and Inria Nancy. This is concerning as RSA encryption is still employed in many services, even though it has been largely replaced by ECC and post-quantum algorithms. The attack cuts the number of necessary operations for cracking an RSA-encrypted key from 2^80 to 2^65 for 1024-bit keys, and still more for 2048, 3072-, and 4096-bit keys.

While this is still a large number, it is now within the range of feasibility for entities with significant resources, such as state actors. The attack only works on the textbook version of RSA, which is not commonly used in everyday computing like website certificates and remote access, but is found in certain services like Cloudflare Privacy Pass, iCloud Private Relay, and Private Cloud Compute.

It uses PKCS #11, which is present in smart cards, USB security tokens, code-signing pipelines, hardware security modules, and trusted platform modules. However, performing the attack is easier said than done. The attacker must perform a vast number of queries against the key, collecting data points from the key's oracle. This usually involves repeatedly querying a live server that uses the key to encrypt traffic, or a standalone hardware device.

In practice, this would likely result in an IP ban. Despite this, the paper suggests that the algorithms used are not yet optimized and could potentially be sped up, perhaps with the help of AI tools and GPUs. The attack conditions are also quite challenging to meet, requiring billions of queries against the key. While the practical application of this attack remains high, the findings nonetheless show that it is possible that collected oracle data could be used to decrypt saved traffic in the near future, thanks to advancements in hardware.