Reaping and breaking keys at scale: when crypto meets big data

Presented at DEF CON 26 (2018), Aug. 11, 2018, 1 p.m. (20 minutes).

Public keys are everywhere, after all, they are public. These keys are waiting to be reaped by those who know their real value. Hidden behind this public face lurks some potentially dangerous issues which could lead to a compromise of data and privacy.

Leveraging hundreds of minion devices, we built a public key reaping machine (which we are open sourcing) and operated it on a global scale. Collected keys are tested for vulnerabilities such as the recent ROCA vulnerability or factorization using batch-GCD. We've collected over 300 million keys so far and built a database 4 to 10 times bigger than previous public works.

Performing the initial computation on over 300 million keys took about 10 days on a 280 vCPU cluster. Many optimizations allow our tool to incrementally test new RSA keys for common prime factors against the whole dataset in just a few minutes.

As a result of our research, we could have impersonated hundreds of people by breaking their PGP keys, mimicked thousands of servers thanks to their factored SSH keys and performed MitM attacks on over 200k websites relying on vulnerable X509 certificates.

In the end, we were able to do this in an entirely passive way. Going further is possible, but it would lead us to the dark side. Would big brother hesitate to go there?

Presenters:

• Yolan Romailler - Security Researcher at Kudelski Security
  Yolan Romailler is a Security Researcher at Kudelski Security, where he delves into (and dwells on) cryptography, crypto code, blockchains and other fun things. He has spoken at Black Hat USA, BSidesLV and DEF CON's Cryptovillage on automation in cryptography, vulnerability research, and presented at FDTC 2017 the first known practical fault attack against EdDSA. Yolan tweets as @anomalroil.
• Nils Amiet - Security Engineer at Kudelski Security
  Nils Amiet is a Security Engineer at Kudelski Security, where he performs big data analytics, leveraging Spark, Hadoop and Chapel clusters to analyze large datasets. He designed a data pipeline to snapshot the whole IPv4 address space for selected network protocols, allowing automated and reproducible offline data analysis. He also built an automated country security ranking. Nils likes open source software, data analytics, distributed systems and data processing.

Links:

• https://defcon.org/html/defcon-26/dc-26-speakers.html#Romailler
• https://infocon.org/cons/DEF CON/DEF CON 26/DEF CON 26 video and slides/DEF CON 26 - Romailler and Amiet - Reaping and breaking keys at scale when crypto meets big data.mp4
• https://infocon.org/cons/DEF CON/DEF CON 26/DEF CON 26 video and slides/DEF CON 26 - Romailler and Amiet - Reaping and breaking keys at scale when crypto meets big data.srt (subtitles)
• https://www.youtube.com/watch?v=Z7cLRE6t1Q8

Similar Presentations:

• ToorCon San Diego TwentyOne (2019) / Ethercombing - Blockchain brute force cryptanalysis
• DEF CON 29 (2021) / The Mechanics of Compromising Low Entropy RSA Keys
• DEF CON 31 (2023) / Assessing the Security of Certificates at Scale