badkeys

GitHub security update: revoking weakly-generated SSH keys

"There is no haveibeenpwned for public keys as far as I know"

(User jornane on lobste.rs commenting on the keypair bug)

Bugs can lead to insecure cryptographic keys

It can be useful to be able to detect such insecure keys

(services like Github, certificate authorities, pentesters)

Weak public keys

  • 2008 Debian OpenSSL bug
  • 2012 RSA shared prime factors
  • 2017 Return of Coopersmith's Attack (ROCA)
  • 2021 keypair/Gitkraken vulnerability
  • More? Default keys, Fermat vulnerability

2008 Debian OpenSSL bug

Debian patched an issue with uninitialized memory in OpenSSL and made a mistake that caused the random number generator being initialized only with the process id (PID)

Attack: Generate all possible private keys

RSA shared prime factors

RSA public keys contain a modulus (N) that is the product of two secret primes (p, q)

What if...

N1 = p1*q1

N2 = p1*q2

Calculating a greatest common divisor (GCD) is fast

GCD(p1*q1, p1*q2) = p1

With that we can trivially break both keys

Bernsteins algorithm allows finding such vulnerable key pairs in a large set of keys

Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices (Heninger et al 2012)

Ron was wrong, Whit is right (Lenstra et al 2012)

Attack already contemplated by Ben Laurie in 2004/2006

Why would that happen?

  • Linux boots up
  • Random number generator is weak, not enough entropy
  • Software generates first prime (weak)
  • Random number generator gets more entropy
  • Software generates second prime (good)

Usually this happens on embedded devices that automatically generate cryptographic keys on boot

Today the Linux kernel does a lot to prevent these scenarios (but plenty of people - especially in the IoT world - don't use current Linux versions)

If you look at keys in the wild, this is by far the most common vulnerability you will find

Detection requires large sets of keys and is slow

But there's a somewhat weaker detection method that is fast and does not require having large key databases around

We can pregenerate a list of known shared prime factors, multiply them and calculate GCD with N

ROCA

In 2017 researchers discovered a Key generation vulnerability in Infineon chips widely used e. g. in TPM chips, smartcards

It is infeasible to create a list of all vulnerable keys, but they can be detected algorithmically

2021: I found valid, current certificates used by Yahoo being affected

Some issues reporting this responsibly...

Fermat Factorization

If the two primes in RSA (p, q) are "close" then there is an efficient algorithm to factor N, discovered by Pierre de Fermat

This is well-known in the literature, but up until now there is no documentation of such keys having been found in the wild

I'm in the process of disclosure with some vendors of printers who were vulnerable to this flaw

Public Private Keys

Sometimes people will not generate their own keys, but will use existing private keys that are public

Static keys in firmware/software, example keys etc.

Generate blocklist of as many "public private keys" as possible

RSA public key consists of two values (N, e), it's better to generate a blocklist of the N value and not the full key

Gitkraken/keypair vulnerability

This vulnerability is in a javascript library that due to a bug used only the strings 0-9 as an input for the random number generator, with 0 being far more likely
Unfortunately it is not feasible to generate all possible keys. Best thing I came up with is generating many keys and create blocklist from keys that show up more than once.

So what do I want to do about it?

Goal 1

Create a tool (available as a library, command line tool, web service and web API) that allows easily checking public keys for as many known vulnerabilities as possible

Goal 2

Apply this tool to large sets of public keys and see what we will find

Current state

badkeys.info/