The Mechanics of Compromising Low Entropy RSA Keys

Over the past decade, there have been a number of research efforts (and DEFCON talks!) investigating the phenomenon of RSA keys on the Internet that share prime factors with other keys. This can occur when devices have poorly initialized sources of “randomness” when generating keys; making it trivial to factor the RSA modulus and recover the private key because, unlike large integer factorization, calculating the greatest common divisor (GCD) of two moduli can be fast and efficient. When describing their research, past hackers and researchers have attested that they “built a custom distributed implementation of Batch-GCD;” which seems like one hell of a detail to gloss over, right? This talk will detail a hacker's journey from understanding and implementing distributed batch GCD to analyzing findings from compromising RSA keys from network devices en masse. REFERENCES: Amiet, Nils and Romailler, Yolan. “Reaping and breaking keys at scale: when crypto meets big data.” DEF CON 26, 2018. Heninger, Nadia, et al. "Mining your Ps and Qs: Detection of widespread weak keys in network devices." 21st {USENIX} Security Symposium ({USENIX} Security 12). 2012. Hastings, Marcella, Joshua Fried, and Nadia Heninger. "Weak keys remain widespread in network devices." Proceedings of the 2016 Internet Measurement Conference. 2016. Kilgallin, JD. “Securing RSA Keys & Certificates for IoT Devices.” https://info.keyfactor.com/factoring-rsa-keys-in-the-iot-era. 2019 Daniel J. Bernstein. Fast multiplication and its applications, 2008.