Researchers discover weakness in IoT digital certificates

IoT devices are using weak digital certificates that could expose them to attack, according to a study released over the weekend.

Researchers at online digital certificate management services company Keyfactor studied millions of digital certificates found online which were produced using the RSA algorithm. They found that 1 in every 172 certificates was crackable because of insecure random number generation.

RSA’s encryption algorithm is the basis for modern asymmetric encryption, which uses a pair of keys (a public and private key) to encrypt information and prove the sender’s identity. Part of the public key production involves multiplying two prime numbers (known as factors). It is computationally prohibitive to calculate the two prime numbers in reverse from the result. You can only decrypt the information by combining the private key (known only to the owner) and the public key.

If two public keys share a common factor, it becomes a lot easier to discover their other factors by calculating the Greatest Common Divisor (GCD) for their results.

The best way to avoid this vulnerability is to ensure that the numbers used to create the public key are as random as possible to avoid duplication. Highly random keys with few duplicates are known as high-entropy keys, but producing them requires two things: lots of random input data, and the computing power to turn that input data into a key.

Your desktop computer or laptop has computing power in spades. Unfortunately, the devices that make up the vast Internet of Things (IoT), which far outnumber desktop computers and run everything from petrol pumps to street lights, often don’t. The sensors and other devices connected to the IoT often rely on very low power to operate, which makes it more difficult to generate high entropy. The result is a lot of devices with common factors.

The researchers built a database of over 60 million RSA keys available on the internet, and then used logs produced by Google’s Certificate Transparency project to find another 100 million. After analysing the keys for shared factors, they found that at least 435,000 of them shared factors, representing one in every 172 certificates.

The researchers didn’t just identify the certificates with shared factors; they used the GCD algorithm to calculate the second unique factor for each of these keys, effectively cracking the certificate wide open. Keyfactor researcher JD Kilgallin, who wrote the report, explained that in many cases he was also able to trace the certificates to specific devices on the internet.

Still, it must have taken lots of computing power to do all that, right? Wrong. Or, more accurately, right, but that power is a lot cheaper these days. The industry already knew about this weakness, and Kilgallin points to several other studies in his report, ranging from 2012 to 2016. But this is the first time that someone has analysed so many keys, he said.

The biggest contribution that we can have made over the previous publications on the topic is the ease with which this can be pulled off with modern resources.

The company broke the keys using Microsoft’s Azure cloud service in a day for around $3,000.

So, does this mean that the RSA algorithm is insecure? Not at all. Ron Rivest, one of the algorithm’s three inventors, told Naked Security:

It looks like an implementation issue.

RSA, the company that Rivest helped create to commercialise the RSA algorithm, no longer owns it. The patent expired in September 2000, and BSAFE, one of the most popular implementations of the original algorithm, is in the public domain. Still, RSA CTO Dr. Zulfikar Ramzan has some views on this research. He told us:

… there are a variety of techniques from increasing the number of entropy sources in a device to waiting until enough entropy is gathered, to embedding high entropy key material during manufacturing that can help tremendously. While there are potentially design constraints to consider, this problem of starting with good cryptographic keys is well understood and feasible to solve with today’s technology.

Kilgallin is sceptical about pre-loading devices with keys during manufacturing, because it opens up devices to supply chain attacks in which an untrustworthy manufacturer or logistics company tampers with the keys en route.

Certificates also expire, he points out, meaning that they’d have to be re-generated periodically on the device anyway. An alternative, he suggests, is to get better random input during an onboard key generation process. Because IoT devices are network connected, they can easily get true random data from various sources, he says. That would let them generate higher-entropy keys even with limited computing power and memory.

Nadia Heninger, an associate professor at the University of California in San Diego, conducted two of the research studies cited in the Keyfactor report. She suggests that the problem with low-entropy IoT devices is about more than just low computing power:

There was a specific problem with the Linux RNG [random number generator] failing to seed itself promptly after boot on headless devices that was patched in the Linux kernel in 2012. This was the flaw that seemed to lead to most of the vulnerable keys. It seems that a lot of device manufacturers seem to use old kernel versions so I expect the problems won’t really go away anytime soon.

The upshot of these conclusions is that these problems have been known for eight years, and that IoT device vendors could easily solve this problem if they just got a clue.

Heninger continued:

These are not “high-value” keys – most of them are self-signed, so if an attacker wanted to man-in-the-middle the HTTPS connection they could anyway.

What should IoT users do to keep their devices safe? If your device comes with a default password or key, change it to something hard to guess.