The Mechanics of Compromising Low Entropy RSA Keys

Presented at DEF CON 29 (2021), Aug. 6, 2021, 12:30 p.m. (20 minutes)

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.

Presenters:

• Austin Allshouse - Staff Research Scientist / BitSight
  Austin Allshouse is a Research Scientist at BitSight where he applies information security, statistical modeling, and distributed computing concepts to develop quantitative methods of assessing security risk. He has a decade of experience researching the technologies and methodologies underpinning digital network surveillance systems. @AustinAllshouse

Links:

• https://defcon.org/html/defcon-29/dc-29-speakers.html#allshouse
• https://infocon.org/cons/DEF CON/DEF CON 29/DEF CON 29 presentations/Austin Allshouse - The Mechanics of Compromising Low Entropy RSA Keys.pptx
• https://infocon.org/cons/DEF CON/DEF CON 29/DEF CON 29 video and slides/DEF CON 29 - Austin Allshouse - The Mechanics of Compromising Low Entropy RSA Keys.mp4
• https://infocon.org/cons/DEF CON/DEF CON 29/DEF CON 29 presentations/Austin Allshouse - The Mechanics of Compromising Low Entropy RSA Keys.pdf (slides)
• https://infocon.org/cons/DEF CON/DEF CON 29/DEF CON 29 video and slides/DEF CON 29 - Austin Allshouse - The Mechanics of Compromising Low Entropy RSA Keys.srt (subtitles)
• https://www.youtube.com/watch?v=BRsXsUEIU70

Similar Presentations:

• DEF CON 31 (2023) / Assessing the Security of Certificates at Scale
• The Last HOPE (2008) / Crippling Crypto: The Debian OpenSSL Debacle
• DEF CON 26 (2018) / Reaping and breaking keys at scale: when crypto meets big data