Factoring "short-sleeve" RSA keys with polynomials
Researchers identified a cryptographic vulnerability in the wild where 'short-sleeve' RSA and DSA keys contain heavily biased zero bits, allowing rapid factorization using polynomial-based cryptanalysis. The flaw was traced to a type mismatch in the key generation code of older CompleteFTP versions, prompting the release of detection and remediation tools.
Detection / HunterGoogle
What Happened
Security researchers found a flaw in how some computer systems generate secret keys used to protect data. Because of a programming error, these keys have predictable patterns of zeros, making it easy for attackers to guess the secret key and potentially access secure communications. This specific error was found in older versions of the CompleteFTP software, as well as some other unnamed systems. If you use CompleteFTP, you should use their provided tool to check if your keys are vulnerable and generate new ones if necessary.
Key Takeaways
- Researchers discovered 'short-sleeve' RSA and DSA keys in the wild that can be easily factored due to heavily biased zero bits.
- A polynomial-based cryptanalytic technique was developed to exploit this mathematical structure and recover private keys.
- A specific vulnerability was traced to CompleteFTP versions 10.0.0-12.0.0 (RSA) and 10.0.0-23.0.4 (DSA) caused by a type mismatch in big-integer generation.
- CompleteFTP has released updates and tools to detect and regenerate vulnerable keys.
Affected Systems
- CompleteFTP versions 10.0.0–12.0.0 (RSA key generation)
- CompleteFTP versions 10.0.0–23.0.4 (DSA key generation)
- NetApp software (unspecified versions)
Attack Chain
The vulnerability originates during the key generation phase where a type mismatch in the random number generator output causes limbs of the big integer to be partially filled with zeros. This creates a 'short-sleeve' pattern in the resulting RSA or DSA public keys. An attacker observing these public keys can apply a polynomial-based cryptanalytic technique to factor the modulus. Once factored, the attacker recovers the private key, enabling decryption of intercepted traffic or impersonation of the affected server.
Detection Availability
- YARA Rules: No
- Sigma Rules: No
- Snort/Suricata Rules: No
- KQL Queries: No
- Splunk SPL Queries: No
- EQL Queries: No
- Other Detection Logic: Yes
- Platforms: badkeys, CompleteFTP standalone tool
The badkeys open-source project and a standalone tool provided by EnterpriseDT (CompleteFTP) can scan and detect vulnerable short-sleeve RSA and DSA keys.
Detection Engineering Assessment
EDR Visibility: None — EDR tools do not typically analyze the mathematical properties of cryptographic keys generated or stored on disk. Network Visibility: Low — While public keys are exchanged over the network (e.g., TLS/SSH handshakes), standard network monitoring tools do not perform polynomial factorization or check for short-sleeve modulus patterns. Detection Difficulty: Hard — Detecting this requires specialized cryptographic analysis tools (like badkeys) to parse public keys and check for specific sparse modulus patterns.
Required Log Sources
- Vulnerability Scanner Logs
- Certificate Management Logs
Hunting Hypotheses
| Hypothesis | Telemetry | ATT&CK Stage | FP Risk |
|---|---|---|---|
| SSH or TLS servers in the environment may be using weak RSA/DSA keys generated by older versions of CompleteFTP. | Certificate inventory, SSH public key inventory | Reconnaissance | Low |
Control Gaps
- Cryptographic key strength validation
- Automated certificate rotation
Key Behavioral Indicators
- RSA or DSA public keys exhibiting regularly spaced blocks of all zeros in their modulus representation
False Positive Assessment
- Low
Recommendations
Immediate Mitigation
- Verify against your organization's incident response runbook and team escalation paths before acting.
- Consider scanning your public-facing infrastructure with the badkeys tool to identify vulnerable short-sleeve RSA or DSA keys.
- If using CompleteFTP, evaluate running the vendor-provided standalone tool to check for vulnerable host keys.
Infrastructure Hardening
- Consider regenerating any RSA or DSA keys identified as vulnerable and revoking the old certificates.
- Evaluate upgrading CompleteFTP to version 26.1.0 or later, which includes automatic key validation.
- Where supported by your tooling, transition away from DSA keys to more modern cryptographic standards like Ed25519 or ECDSA.
User Protection
- If applicable, ensure client applications are configured to reject weak or deprecated cryptographic algorithms.
Security Awareness
- Consider incorporating checks for cryptographic implementation flaws into your secure software development lifecycle (SDLC).
MITRE ATT&CK Mapping
- T1552.004 - Unsecured Credentials: Private Keys
