Broken cryptographic keys in embedded devices

Public Key Cryptography

We have a public and a private key

Depending on the algorithm these can be used for encryption or digital signatures

The most common public key algorithm is RSA, which can be used for both encryption and signatures

Common uses of public key cryptography

• TLS certificates (host authentification)
• SSH keys (host authentication and user authentication)

Part 1: Static Keys in Firmware

What if everyone uses the same private key?

It is surprisingly often that embedded devices come with a static key embedded in the firmware

/dev/ttyS0, 2010

Sec Consult, 2015

Demo using Binwalk

What are these keys used for and what is the risk?

Certificates for HTTPS

Host key for SSH

Allows Man in the Middle attacks

Risk level: Medium

SSH user authorization key

Allows remote login via SSH by anyone who extracts the key!

Risk Level: Very High

• CVE-2022-25569: Bettini GAMS Video Cameras
• CVE-2021-40119: Cisco Policy Suite
• CVE-2016-1561: Exagrid Storage device
• CVE-2015-0936: Ceragon FibeAir IP-10
• CVE-2012-1493: F5 BigIP

Cryptographic private keys should never be part of any firmware or software, instead a new key should be generated when needed!

Questions?

Part 2: Common Prime Factors

RSA Key Generation

During RSA key generation two large prime numbers get created, they are usually called p and q

These primes are secret and part of the private key

An RSA public key contains a value called the Modulus or N, which is the product of the secret primes p and q:

N = p * q

Factoring N - which means calculating p and q from N - is a difficult problem and not practical if they have been properly generated

Imagine we have a random prime generation function that is not working properly and sometimes produces the same prime for different keys

We could end up with two different RSA keys with:

N₁ = p₁ * q₁

N₂ = p₁ * q₂

N₁ = p₁ * q₁

N₂ = p₁ * q₂

p₁ is a common divisor of N₁ and N₂

Euclid's algorithm allows fast computation of greatest common divisors

Let's look at an example:

The numbers 2021 and 1591 have a common divisor.

Calculating a GCD is fast even for very large numbers, therefore if we have two RSA keys with one shared prime number we can break both keys quickly

It is also possible, although a bit more complicated, to efficiently calculate pairwise GCDs for a large number of inputs

(Batch GCD / Bernstein's algorithm)

We can use this to search for vulnerable RSA keys

Step 1: Get a lot of RSA keys (e.g. from Internet wide scans)

Step 2: Get all their N values

Step 3: Calculate GCDs

Step 4: Break RSA keys

This was done independently by two research teams in 2012

We were able to remotely obtain the RSA private keys for 0.50% of TLS hosts and 0.03% of SSH hosts because their public keys shared nontrivial common factors due to poor randomness. (Heninger, Durumeric, Wustrow, Halderman, factorable.net)

Why does this happen?

Early boot time entropy

The analysis done by the researchers showed these keys were mostly created in embedded Linux environments directly after boot

Embedded devices have limited sources for randomness (no keyboard, no mouse etc.)

Bad key generation:

• Linux boots, not a lot of randomness
• Key generation starts, p is created with bad randomness
• More randomness comes in
• q is created with better randomness
• Result: A key with a "bad" (=repeated) and a good prime

Lots of improvements happened in the Linux kernel to avoid such situations, it is unlikely that such keys will be generated on a modern Linux kernel

A new API call getrandom() was introduced that allows blocking if the system's random number generator was not properly initialized

When generating keys directly after boot you need to make sure the random number generator is properly initialized!

Questions?

Part 3: Fermat Factorization

In 1643 Pierre de Fermat described a factorization algorithm in a letter that works well for composite numbers that are the product of two "close" primes

RSA N

N = p * q

p, q: secret prime numbers

N = p * q

N = (a+b)(a-b)

a: Middle between p, q

b: Distance of p, q to middle

N = (a+b)(a-b)

N = a^2 - b^2

b^2 = a^2 - N

*If* the difference between the two primes p, q is small then a is close to the square root of N

We can make guesses for a, starting with the rounded square root of N

b^2 = a^2 - N

If b^2 is a square then we found the right a (and can calculate b, and from that p, q)

Can we break real RSA keys with this?

This algorithm is widely known in the literature, but to my knowledge up until recently no attacks against production RSA keys have been described

I checked large sets of public RSA keys for vulnerable ones

155 self-signed TLS certificates in Internet-wide TLS scans

(Most with very similar common names, so likely same source)

Tracing back the IPs via Censys I could access some web interfaces and learned they were created by Fujifilm printers

17 keys in publicly trusted TLS certificates in Certificate Transparency logs

I tried to contact all owners of the corresponding domain names, in two cases I learned they were created by Canon printers

Certificates, as far as they were still valid, were reported to the responsible certificate authorities and revoked

These printers in both cases used the Safezone cryptographic module from the company Rambus

How does this happen?

Idea 1: Neighboring primes

We can imagine a flawed RSA key generation algorithm like this:

• Create random number X
• Search for next prime after X and use it as p
• Search for next prime after p and use it as q

This would create p, q with a small difference (thousands or less) - factoring N is easy

Idea 2: Static bits

• Create two random primes, but with all the upper bits set to the same value

(seems less likely to happen by accident)

All keys I found were neighboring primes

What does "close" prime mean?

With a 2048 bit RSA key the primes are 1024 bit. With 100 rounds of Fermat factorization we can break primes with a difference up to 517 bit.

Rule of thumb

If roughly the upper half of the bits of the two primes are identical we can break it

It is worth looking for well-known flaws in large sets of cryptographic keys

Such vulnerabilities tend to show up in obscure cryptographic libraries, it is usually better to use well-tested standard libraries like OpenSSL

Questions?

badkeys

A tool to identify vulnerable cryptographic keys

• Debian OpenSSL bug (CVE-2008-0166)
• Common prime factor vulnerability ("Mining Your Ps and Qs", 2012)
• Return of Coopersmith's attack / ROCA (CVE-2017-15361)
• keypair / Gitkraken bug (CVE-2021-41117)
• Fermat Attack (CVE-2022-26320)
• Various "Public Private Keys"

Demo

Questions?

Try it out:

badkeys.info