badkeysDuring #39c3 Nadia Heninger introduced me to Keegan Ryan, and we talked about things that could go wrong in RSA, and how to detect keys with suspicious patterns created by defect RNGs. At some point, Keegan said: "You could check the Hamming Weight of the Modulus." And I replied: "I don't know what that means."
But it's actually quite simple. The Hamming Weight is the ratio of symbols, if we look at bits, how many 0s vs 1s are there. For a "proper", randomly generated RSA key, the ratio should be close to 0.5. If it's significantly different from that, it's likely not randomly generated.
We ended up finding some keys with repeating zero-byte patterns.It is possible to represent those as polynomials. Unlike integer numbers, polynomials can be factored efficiently, which means these keys can be broken.
We found SSH host keys that we could trace back to a software called CompleteFTP (which, furthermore, had another RSA vulnerability in its Linux version and also generated vulnerable DSA keys - all fixed in the latest version of CompleteFTP, but keys need to be regenerated). We furthermore identified another class of vulnerable keys (with a different width of zero byte patterns) in TLS certs (both self-signed and WebPKI-signed, but all expired, so no revocations), most of them from Verizon+Yahoo, but we were unable to identify the vulnerable RSA implementation.
If you're interested in the details of the attack, check Keegan's blog post:
https://blog.trailofbits.com/2026/06/12/factoring-short-sleeve-rsa-keys-with-polynomials/
The latest badkeys version 0.0.18 detects all affected vulnerable keys.
Byron C Clark
jonny (nonvenomous)
Dan Ports
Signal
Regendans