Researchers at the University of California, San Diego have developed an advanced attack technique on the RSA algorithm, allowing for the forgery of digital signatures without the need to factor the underlying RSA prime numbers or recover the private key. The resources required to conduct an attack on a 1024-bit RSA key are estimated at 1380 years of computation on a single CPU core, which, on the university's cluster, allowed the parameters necessary for generating fake RSA signatures to be determined in 5 months (AI accelerators and GPUs were not used in the experiment, but their application could significantly reduce computation time). In comparison, the classic factorization method requires between 500,000 to 1 million years of computation on a single CPU core to reconstruct the RSA-1024 private key.
To carry out the attack, it is necessary to have the ability to repeatedly send requests for signing the data generated by the attacker, for example, by contacting an authorization service or HSM module. To determine the parameters for RSA-1024, it is sufficient to send 232 such requests, and for attacking RSA-2048 keys used in the Privacy Pass protocol, 243. After obtaining a collection of signed data, a lengthy computation process is initiated to calculate the parameters (for RSA-1024, this takes about 265 operations), after which the attacker can generate fake signatures for any data, spending about 180 hours of computation on a single core for each signature.
The method is only applicable to RSA signatures, where no formatting and additional padding are used before encryption. The attack is vulnerable to blind signature implementations, including those used in the Privacy Pass protocol. Most common RSA implementations, including PKCS#1v1.5 and RSA-PSS (used in TLS and SSH), use additional padding and are not susceptible to this attack.
The basis of RSA encryption is the operation of exponentiation modulo a large number. The public key contains the modulus and the exponent. The modulus is formed based on two random prime numbers, known only to the holder of the private key. The proposed method is based on a study published in 2007, which proved that extracting the root in the exponent specified by the public key from the encrypted message, without information about the secret multipliers, is a less resource-intensive operation than factoring the multipliers themselves.
By using a special number field sieve (SNFS) method, researchers have managed to reduce the complexity of compromising RSA-1024 keys to 265 operations, enabling practical attacks on modern clusters. For 2048-bit RSA keys, the attack complexity is estimated at 290, which is theoretically feasible for large corporations or intelligence agencies. For 4096-bit keys, the attack complexity stands at 2119 operations, which is currently unachievable in practice, but below the minimum of 2128 recommended by the NSA, the National Institute of Standards and Technology, and the European Union Agency for Cybersecurity.
Source: opennet.ru
