Researchers from the University of California, San Diego, have developed an advanced technique to attack the RSA algorithm, allowing them to forge digital signatures without factoring the underlying prime numbers of RSA and without needing to recover the private key. The resources required to execute an attack on a 1024-bit RSA key are estimated at 1380 years of computation on a single processor core, which allowed researchers to determine the parameters necessary to create fake RSA signatures within 5 months using the university's cluster (AI accelerators and GPUs were not used in the experiment, and their application could significantly reduce computation time). In comparison, the classical factorization method requires from 500,000 to a million years of computation on a single processor core to reconstruct the RSA-1024 private key.
To carry out the attack, it is necessary to have the capability to repeatedly send requests for signing the data being generated by the attacker, for example, by accessing an authorization service or HSM module. To determine the parameters for RSA-1024, it is sufficient to send 232 such requests, while for attacking RSA-2048 keys used in the Privacy Pass protocol, 243 requests are needed. Once a batch of signed data is obtained, a lengthy computation process is initiated (approximately 265 operations for RSA-1024), after which the attacker can create fake signatures for any data, spending about 180 hours of computation on a single core per signature.
The method is applicable only to RSA signatures that do not use formatting and additional padding before encryption. The attack is susceptible to implementations of blind signatures, including those used in the Privacy Pass protocol. Most commonly used RSA implementations, including PKCS#1v1.5 and RSA-PSS (used in TLS and SSH), apply additional padding and are not vulnerable to this attack.
At the core of RSA encryption is the operation of exponentiation modulo a large number. The public key contains a modulus and an exponent. The modulus is formed based on two random prime numbers that are known only to the owner of the private key. The proposed method is based on a study published in 2007, which proved that extracting the root specified in the public key exponent from an encrypted message without information about the secret factors is a less resource-intensive operation than factorizing the factors themselves.
By using a special method of number field sieving (SNFS), researchers have managed to reduce the complexity of compromising RSA-1024 keys to 265 operations, making practical attacks possible 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 is 2119 operations, which is still practically unattainable, 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
