Researchers Revive 2007 RSA Signature Forgery Attack
A 2007-era attack against RSA's pure signature scheme has been reimplemented, enabling the forging of digital signatures without recovering private keys.
A research team has successfully reimplemented a theoretical attack against the RSA cryptosystem, originally detailed in 2007, which allows for the forging of digital signatures. This renewed focus on the attack highlights a potential weakness in specific, albeit less common, implementations of RSA.
The core of the attack bypasses the traditional method of breaking RSA, which involves factoring the large prime numbers that form the public key. Instead, this technique targets the signature generation process itself. Crucially, it only affects 'pure' RSA signatures, meaning those that are implemented without any form of padding or formatting schemes, such as PKCS#1 v1.5 or PSS.
While the attack does not recover the private key, its ability to forge valid signatures presents a significant concern for systems relying on unpadded RSA for integrity and authenticity. The researchers demonstrated the feasibility of this attack by successfully forging signatures for 1024-bit RSA keys. This feat required a substantial computational effort, estimated at 1380 CPU core-years, which translated to approximately five months of continuous processing.
It is important to note that this is not a polynomial-time algorithm, meaning its computational complexity grows significantly with the size of the key. However, the researchers indicate that it is more efficient than brute-force factoring for certain key sizes. The practical implications are tempered by the fact that modern cryptographic practices strongly advocate for and implement padding schemes, which are designed to thwart such signature forgery attacks.
The original research dates back to 2007, with the new implementation serving as a proof-of-concept to demonstrate the continued theoretical viability of the attack. The researchers have made their findings and the context of the attack publicly available, providing detailed explanations and the technical paper for those interested in the cryptographic nuances.
While the direct impact on current, properly implemented RSA deployments is likely minimal due to the widespread adoption of padding, this research serves as a valuable reminder of the importance of adhering to cryptographic best practices. It underscores the need for developers and security professionals to ensure that RSA signatures are always implemented with robust padding schemes to maintain their security guarantees against known and theoretical attacks.