A flaw was found in the RSA cryptosystem, which is widely used on the Internet for encryption, authentication and digital signatures. Researchers have found a way to forge certain RSA signatures without breaking down the corresponding keys. This attack mode does not pose a threat to today’s common RSA implementations, but the results of this study are cause for concern because they show that forging RSA signatures does not always require recovery of the private key.
Photo credit: Sasun Bughdaryan / unsplash.com
This approach actually works with 1024-bit RSA keys, which are considered obsolete; it also reduces the strength level of 2048-bit and 4096-bit keys when applied to vulnerable blind signing systems. RSA security has traditionally relied on the difficulty of factoring a large number into two prime factors: the public key contains that large number, and the private key is calculated from its factors. Previously, it was thought that in order to create a valid signature, an attacker would have to consider the number first. The new study used a different approach—a variation of special number-field sieves and oracle algorithms used in some blind signature protocols. By executing a large number of queries and analyzing the results, an attacker can gather enough data to generate a valid signature.
Decomposing a 1024-bit RSA key takes approximately 280 operations and processor computing power of 500,000 to 1 million “core years”; to conduct a signature forgery attack, you need to execute 265 operation, equivalent to 1380 nuclear years of calculation. For keys of length 2048 and 4096 bits, these numbers will be 290 and 2119 Perform the appropriate operations. The researchers believe these indicators can improve in the future. The algorithm was implemented without resorting to GPU architecture or artificial intelligence tools, which “almost certainly” will make similar attacks easier in the future.
This attack only works on systems that use a blind signature mechanism, sometimes called “textbook RSA”. Such systems allow you to sign material without knowing its content. But most implementations of RSA use PKCS or PSS data padding, where the information is modified before being encrypted or signed. An example of blind signature technology in action is the Privacy Pass protocol – which allows users to confirm their credentials without revealing their identity. Apple and Cloudflare use this technique, to attack such systems the publisher must request 243 Token. Although large in size, it is comparable to the scale of activities of large online services. In many Privacy Pass systems, keys are updated regularly, which makes attacks more difficult because it reduces the time available to collect tokens. But that doesn’t completely eliminate the risk.
If you find an error, select it with your mouse and press CTRL+ENTER.
