Hack the heck out of RSA

Imagine a world with no internet. Well, that article won't explain how to achieve that but will show you a few simple things you can do to understand how fragile the web is.

TL;DR:

• Get millions of domain names
• Extract the certificates
• BatchGCD the heck out of the public keys

How to get millions of domain names?

The first step is to gather millions of SSL certificates to achieve that we need to find a way to collect unique domain names. Most of the websites allowing you to download this informations are asking for a financial contribution.

However, you can download 10 million domains on this link for free, but that won't be enough.

We are going to take a look at CommonCrawl, which is a repository of billions of web pages that have been crawled, representing petabytes of data. You could download the entire catalog and then parse it, but that would require thousands of euros of investment in a new computer.

Fortunately for us, Common Crawl has an S3 Bucket that can be crawled easily using Amazon Athena

AWS Athena

Amazon Athena is an interactive query service that makes it easy to analyze data in Amazon S3 using standard SQL. Athena is serverless, so there is no infrastructure to manage, and you pay only for the queries that you run.

Athena is easy to use. Point to your data in Amazon S3, define the schema and start querying using standard SQL. Most results are delivered within seconds. With Athena, there's no need for complex ETL jobs to prepare your data for analysis. This makes it easy for anyone with SQL skills to analyze large-scale datasets quickly.

• Open the Athena query editor.
• Select us-east-1 as your location
• Run the Query CREATE DATABASE ccindex

This will create a database

• Create a new table with the following Query

CREATE EXTERNAL TABLE IF NOT EXISTS ccindex (
url_surtkey                   STRING,
url                           STRING,
url_host_name                 STRING,
url_host_tld                  STRING,
url_host_2nd_last_part        STRING,
url_host_3rd_last_part        STRING,
url_host_4th_last_part        STRING,
url_host_5th_last_part        STRING,
url_host_registry_suffix      STRING,
url_host_registered_domain    STRING,
url_host_private_suffix       STRING,
url_host_private_domain       STRING,
url_protocol                  STRING,
url_port                      INT,
url_path                      STRING,
url_query                     STRING,
fetch_time                    TIMESTAMP,
fetch_status                  SMALLINT,
content_digest                STRING,
content_mime_type             STRING,
content_mime_detected         STRING,
content_charset               STRING,
content_languages             STRING,
warc_filename                 STRING,
warc_record_offset            INT,
warc_record_length            INT,
warc_segment                  STRING)
PARTITIONED BY (
crawl                         STRING,
subset                        STRING)
STORED AS parquet
LOCATION 's3://commoncrawl/cc-index/table/cc-main/warc/';

This will map the table ccindex that you created with the location of the S3 bucket where the data is stored

• Run

MSCK REPAIR TABLE ccindex

Note that you need to rerun this command every month as the CommonCrawl foundation adds new data.

• Run

SELECT DISTINCT(url_host_name)
FROM "ccindex"."ccindex"
WHERE crawl = 'CC-MAIN-2018-05'
AND subset = 'warc'
AND url_host_tld = 'no'

This will return all the hostname from Norway that were crawled in May 2018

SELECT COUNT(*) AS count,
url_host_registered_domain
FROM "ccindex"."ccindex"
WHERE crawl = 'CC-MAIN-2018-05'
AND subset = 'warc'
AND url_host_tld = 'no'
GROUP BY  url_host_registered_domain
HAVING (COUNT(*) >= 100)
ORDER BY  count DESC

This Query will return all the url_host_registered_domain count from Norway

Mother of all queries -> How to get 27M domains in 30seconds:

SELECT DISTINCT(url_host_name)
FROM "ccindex"."ccindex"
WHERE subset = 'warc'

With this request, we managed to get 27M unique domains in less than a minute.

Now let's move to part 2

Get the certificates

Github Repository: https://github.com/StanGirard/GoSSL

Javascript Hell

Requesting millions of certificates isn't an easy task. As a javascript developer, I never encountered such a job. It needs to be fast and efficient. I got to experience my first memory leak in Nodejs, out of memory. I also experienced a low request per second (40 per second).

You can check index.js in the trash code folder if you want to see the implementation on JS.

Let's Go Python

I decided to move to python3 to avoid many of the headaches that I got with Nodejs. The results were not as expected (60-70) per second. No memory issues this time!

You can check test.py if you want to see the implementation in Python.

Go for the win

Python was not good enough; Goland seemed like a good fit. Never used before but seemed like the right choice.

The program can be found in src/main.go

cat domainnames | go run main.go

You need to have one domain per line. But that should not be an issue because we managed to gather one certificate per line with AWS Athena

Batch GCD

Now it is time to hack! We have millions of public keys. It is time to find GCD with those keys.

I created a python notebook MultiplyCerts to see the basic implementation and complexity of a Batch GCD implementation. I found out that the complexity of the basic implementation of Batch GCD is X^2. You can find the results in MultiplyCerts.html

Batch GCD Implementation

It can then be used (for example) by a project like batch-GCD, which implements the algorithm from here developed by DJ Bernstein to find weak primes.

(C++)+GMP implementation of the Batch GCD algorithm by Daniel Bernstein. This algorithm, described in How To Find Smooth Parts Of Integers, allows pairwise computing GCDs of a list of integers in quasilinear time and memory. See e.g., factorable.net, which also provides source code.

Conclusion

I will not share the results publicly, but you should be able to reproduce and find some impressive results with the BatchGCD algorithm.

It is easier to find GCD from millions of public keys than to try to find the factors of a public key.

News about protecting the web

• Let's Encrypt new implementation of validation - February 19th, 2020