Full Report
ArsTechnica is reporting on a “new” attack against RSA, one that bypasses factoring. First, this attack isn’t new. The original research is from 2007. What is new is the implementation. Second, it is a forgery attack. It allows an attacker to forge digital signatures. It does not recover the private key from the public key. Third, the attack only works against pure signatures. That is, signatures without any formatting or padding. This is not generally how we use RSA in practice. Fourth, speed is all relative. This is not a polynomial-time algorithm; it’s a subexponential-time algorithm. But it is somewhat faster than factoring. The authors were able to forge messages for 1024-bit RSA with 1380 CPU core-years (over five real-world months)...
Analysis Summary
# Vulnerability: RSA Signature Forgery via Subexponential Factorization Bypass
## CVE Details
- **CVE ID**: Not Assigned (This is a theoretical cryptographic research implementation rather than a specific software bug).
- **CVSS Score**: N/A (Theoretical/Research)
- **CWE**: CWE-347: Improper Verification of Cryptographic Signature / CWE-327: Use of a Broken or Risky Cryptographic Algorithm.
## Affected Systems
- **Products**: Cryptographic libraries and custom implementations utilizing the RSA algorithm.
- **Versions**: N/A.
- **Configurations**: Systems using **"Pure" RSA signatures** (signatures generated without standard formatting or padding schemes like PKCS#1 v1.5 or RSA-PSS).
## Vulnerability Description
This vulnerability is an implementation of a forgery attack originally theorized in 2007. Unlike traditional RSA attacks that focus on recovering the private key by factoring the modulus ($n=pq$), this attack focuses on **forging digital signatures** without knowing the private key.
The attack utilizes a subexponential-time algorithm that is computationally faster than General Number Field Sieve (GNFS) factoring. It exploits the mathematical structure of "raw" or "pure" RSA, where a message $m$ is signed simply as $s = m^d \pmod n$. By bypassing the need for full factoring, an attacker can generate a valid signature $s$ for a chosen message $m$ that will pass verification against the target's public key.
## Exploitation
- **Status**: Proof of Concept (PoC) demonstrated by researchers.
- **Complexity**: High (Requires significant computational resources).
- **Attack Vector**: Network (Targeting signature verification endpoints).
- **Resource Requirement**: Forging a signature for a 1024-bit RSA key required **1,380 CPU core-years** (approximately five months of real-time computation on a high-performance cluster).
## Impact
- **Confidentiality**: None (The private key is not recovered).
- **Integrity**: **High** (Allows for the creation of fraudulent messages/documents that appear to be legitimately signed).
- **Availability**: None.
## Remediation
### Patches
- No specific software patch is applicable as this is a protocol-level weakness in unpadded RSA.
### Workarounds
- **Implement Padding**: Ensure all RSA implementations use industry-standard padding and formatting schemes, such as **RSA-PSS** (Probabilistic Signature Scheme) or **PKCS#1 v1.5**. The attack is ineffective against padded signatures.
- **Key Length**: Transition from 1024-bit RSA keys to **2048-bit or 4096-bit keys**, which exponentially increases the computational cost of the attack beyond feasibility.
## Detection
- **Indicators of Compromise**: Difficult to detect via logs as the forged signature is mathematically valid.
- **Detection Methods**: Security audits should scan codebase and cryptographic configurations for "Raw" or "None" padding settings in RSA signature modules.
## References
- **Original Research (2007)**: [h]xxps://link.springer[.]com/chapter/10.1007/978-3-540-77451-8_13
- **ArsTechnica Report**: [h]xxps://arstechnica[.]com/information-technology/2023/09/new-rsa-attack-bypasses-factoring/
- **Slashdot Discussion**: [h]xxps://it.slashdot[.]org/story/23/09/01/2117215/new-attack-on-rsa-signatures-bypasses-factoring