New RSA Signature Forgery Attack Explained
A recent report highlights a ‘new’ attack against the RSA cryptosystem, focusing on digital signature forgery rather than the traditional challenge of factoring large prime numbers. This research, while building on concepts from 2007, presents a novel implementation that allows an attacker to forge digital signatures under specific conditions. It is important for security professionals to understand the nuances of this attack to properly assess their exposure and plan future cryptographic strategies, according to Schneier on Security.
Technical Details and Analysis of RSA Pure Signatures Vulnerability
The core of this attack targets what are termed ‘pure signatures’ or ‘textbook RSA’ — signatures generated without any formatting or padding. In typical real-world applications, RSA is almost always used with padding schemes (e.g., PKCS#1 v1.5 or OAEP for encryption, PSS for signatures) to enhance security and prevent such structural attacks. Consequently, most contemporary RSA implementations are not directly vulnerable to this specific method.
However, the analysis notes that some real-world systems continue to employ blind-signature or textbook RSA. A prominent example cited is the Privacy Pass protocol, used by entities such as Apple and Cloudflare, which utilizes blind RSA signatures. The attack against Privacy Pass blind RSA security would necessitate an attacker requesting an extremely large number of tokens—specifically, 2^43. While this is computationally feasible for an attacker with immense resources, the practical hurdles are significant. Apple’s rate-limiting of one token per minute per device means a single device would require 17 million years to complete the queries. Even when parallelized across Apple’s estimated 2.3 billion active devices, it would still take approximately 2.3 days and incur an estimated cost of $13 trillion at current API rates. This makes direct, widespread exploitation highly impractical for Privacy Pass.
The attack operates as a subexponential-time algorithm, making it somewhat faster than factoring for certain key lengths, but it is not a polynomial-time algorithm. The researchers demonstrated forging messages for 1024-bit RSA keys using 1380 CPU core-years, translating to over five real-world months of computation. This underscores the diminishing security of shorter key lengths and the need to move towards stronger cryptographic primitives.
The fundamental takeaway is that this research reinforces a long-standing principle in cryptography: the security of RSA is not equivalent to the difficulty of factoring. While the immediate practical threat from this specific attack is low due to its reliance on pure signatures and significant resource requirements, it serves as a critical reminder of cryptographic best practices and the potential for new attack vectors against less-than-ideal implementations.
Mitigating RSA Forgery Attacks in Practice
Defenders should prioritize actions that enhance their cryptographic posture, especially concerning RSA implementations. The source material and expert commentary provide clear guidance:
- Eliminate 1024-bit RSA Keys: Organizations still using 1024-bit RSA keys must accelerate their migration to longer, more secure key lengths, such as 4096 bits, as a minimum. Many servers already enforce this, as noted by the SSH configuration requiring
RequiredRSASize 4096. - Implement Modern Padding Schemes: Ensure all RSA signature operations utilize modern, secure padding schemes like Probabilistic Signature Scheme (PSS). Avoiding ‘pure’ or ‘textbook’ RSA is fundamental to preventing structural attacks.
- Embrace Cryptographic Agility: Plan for and implement cryptographic agility, allowing for the rapid rotation of keys and transition to new algorithms as cryptographic landscapes evolve. Systems that rely solely on RSA without a migration path face increasing long-term risks.
- Regular Key Rotation: Implement a policy of regular key rotation. While not a complete defense against all attacks, it significantly reduces the window of opportunity for an attacker even if a weakness were to be exploited.
- Diversify Authentication Methods: Consider diversifying authentication methods beyond a single RSA key, for instance, by requiring multiple keys and different algorithms (e.g., ED25519, RSA, ECDSA) for critical services like SSH.
Related: LLMs Achieve Novel Cryptanalysis: Implications for Digital Security, Securing Digital Identity: Essential Certificate & Key Inventory