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?
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 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.