In 2017, Google spent hundreds of thousands of dollars proving to the world SHA1 is insecure, and in doing so, they forced certificate authorities to stop using the SHA1 algorithm on root certs.

I don’t have Google money to prove you can break into 11,000 GitHub accounts by factoring prime numbers, but this post should demonstrate beyond a reasonable doubt you can.

GitHub allows users to authenticate to its API via SSH, for which they expect users to generate their own secure keys.

This method of authentication has no role-based access control (RBAC) and allows full access to all repositories the user has access to.

We analyzed 57 million GitHub user’s SSH keys, and found tens of thousands that were not generated securely and can be broken.

This puts millions of end-users at risk of backdoors and supply chain attacks because a subset of the 11,000 weak SSH keys uploaded to GitHub can push to code repositories regularly ran by millions.

Keys with >1025 bits of security (log scale)

Additionally, we looked at what organizations these accounts could push code to, and discovered some very high impact organizations which are now at risk, as a result of these users having weak and factorable SSH keys.

Our take away from this research is clear: if you’re a platform that can generate secure keys on behalf of your users, it’s critical you do so and not trust your user base to generate their keys.

Methodology:

GitHub prevents users from uploading SSH keys  with less than 1024 bits. However, despite a warning that keys must be at least 2048 bits, nothing stops users from uploading keys between 1024 and 2048 bits. 

To test this out, we asked ChatGPT to generate a 1024-bit RSA key pair and then we uploaded it to a GitHub account. 

Generating a 1024-bit RSA key pair

GitHub accepted it without even a warning.

Uploading the 1024-bit RSA public key to GitHub without issue

Since users don’t always make the most secure choices, we figured some portion of GitHub users’ SSH keys would be insecurely generated. 

Using a few different public sources, like GitHub’s Events API, we built a database of 57 million GitHub usernames. GitHub provides developers with an API endpoint to query users’ public SSH keys /<user>/keys.

Event api: https://api.github.com/events?page=1

SSH public keys: https://api.github.com/users/dustin-decker/keys

We then queried the public SSH keys for each user.

For each key, we then ran an openssl command to extract the bit length.

After analyzing all 57 million user keys, we found 11,554 accounts with public keys containing 1024 bits.

Factoring a 1024 bit key

In 2020, a small team of researchers factored an 829 bit key. It took them 2700 CPU core-years, using a 2.1 GHz Intel Xeon Gold 6130 CPU, using a Number Field Sieve algorithm.

This lets us calculate how long it will take to factor a 1024 bit key (i.e. the 11,000 keys in question).

The complexity of factoring an integer n with the algorithm used by the team is given by:

https://en.wikipedia.org/wiki/General_number_field_sieve

We can then compute the relative complexities of the factored 829 bit key, to a 1024 bit key using the above formula:

import math
def L_N(bits, c):
    N = 2**bits
    log_N = math.log(N)
    log_log_N = math.log(log_N)
    return math.exp((c * (log_N)**(1/3) * (log_log_N)**(2/3)))
# Parameters for NFS complexity
c = (64/9)**(1/3)
# Calculate L_N for 829 bits and 1024 bits
L_829 = L_N(829, c)
L_1024 = L_N(1024, c)
# Scaling factor
scaling_factor = L_1024 / L_829
print(scaling_factor)
200

This means, it will take 200 times more computational power to factor a 1024 bit number than what was used to factor a 829 bit number. This should be setting off alarm bells, for anyone who knows how easy it is to spin up 200x the compute power to do something in a public cloud.

Further, as computing power continues to advance we can expect the price to do this to drop. (Ex: a few weeks ago NVIDIA announced Blackwell, which is 25x cheaper than its predecessor by computational power). 

We also calculated how many FLOPS (floating point operations) it takes to factor a 1024 bit key, and there are actually modern large scale computing efforts that have used more computational power. For example, almost any way you run the numbers, it’s cheaper to factor a 1024 bit number than it was to train LLAMA2 or GPT 3.5

Despite no one having done it before, it’s not a future threat, it’s a threat today. 

Other considerations

If you’re a service provider, the only way to ensure secure keys for your user base is to generate keys for them. GCP, for example, typically generates a private key on your behalf when interacting with service accounts.

While GitHub could (and probably should) prevent users from uploading weak SSH keys, they don’t. Had they been more opinionated about generating SSH keys on user’s behalf from the get-go, we likely would not be in this situation.

Unfortunately, changing bit length requirements on GitHub today would be quite difficult, since it would immediately disrupt thousands of users. But unless GitHub takes a more firm stance on insecure key generation, these types of vulnerabilities will only grow in quantity and impact as computational power increases. So it’s likely this will not be the last cryptographic vulnerability GitHub users self inflict at the hands of their own key generation.