In the IEEE conference publication, Factoring RSA Keys in the IoT Era, we showed that many of the IoT and network devices in use today are leveraging weak digital certificates that could expose them to attack.
Our team studied millions of active digital certificates that rely on the RSA algorithm. Spoiler alert: we found that 1 in every 172 certificates are vulnerable to attack due to poor random number generation.
Randomness Required
RSA is a widely adopted algorithm used to secure everything from Internet traffic to IoT devices, yet it can often seem cryptic, even to those who use it every day. At a high level though, it uses a pair of different, but mathematically related keys — a public and a private key — to encrypt data and authenticate connections.
Producing the public key involves multiplying two large, randomly generated prime numbers (known as factors) — a calculation that is computationally infeasible to reverse-engineer from the result.
However, there’s a catch.
If the prime numbers used to create the public keys are not truly random, it is possible there could be a duplicate. And if two public keys share a common factor, it takes nothing more than a few microseconds of computation and simple mathematics to find the other factors, and compromise both keys.
So how were we able to break nearly a quarter million RSA keys?
How We Cracked the Keys
In our efforts to continuously monitor and improve Internet security, we set out on a mission to determine exactly how widespread this vulnerability is — the results are staggering.
Our team built a database of over 75 million digital certificates available on the Internet using SSL/TLS discovery capabilities of the Keyfactor platform, combined with 100 million certificates produced by Google’s Certificate Transparency (CT) log project. After analyzing the database for shared factors, we found that one in every 172 digital certificates have RSA keys that share a factor with another.
From here, all it took was simple mathematics to calculate the other unique factors, effectively breaking nearly 250,000 unique RSA keys. In many cases, these vulnerable keys were used by multiple certificates, sometimes, even thousands.
Not the First Time
The industry has known about this vulnerability for years. Several studies — from 2012 to 2016 — have uncovered weaknesses in random number generation, so what makes this study different?
More Keys, More Risk
The number of RSA keys available on the Internet has grown exponentially, and with it, the risk of compromise. Running the GCD algorithm against a larger dataset, pulled from the Internet and publicly accessible CT logs, increases the odds of finding keys with a shared factor.
Cloud Computing
There are only two things we need to do this effectively: (1) find lots of public keys, and (2) an efficient method to mine and analyze keys at scale. Cloud computing has made it much easier for an attacker to access the resources they need to pull this off. Using a single Microsoft Azure virtual machine, at a cost of about $3,000, our team was able to break nearly 250,000 RSA keys in about 18 hours. Today, this attack isn’t just possible, it’s practical and feasible.
The Rise of the IoT
Most of the vulnerable digital certificates were not found on publicly trusted websites, but in embedded Internet of Things (IoT) devices and network appliances — routers, firewalls and switches. In many cases, we were able to trace certificates back to specific IoT devices.
Unlike traditional IT, including servers and laptops, modern IoT devices have design constraints that prevent them from producing highly random keys. These lightweight devices often operate on very low power and compute resources required to generate high entropy — statistical randomness. The result is thousands of devices that are vulnerable to attack.
Life-Critical & High Risk
Many IoT devices today include things like medical devices, connected vehicles, and commercial aircraft.
Think about a pacemaker. It’s implanted in the human body, has limited computer power, intermittent bandwidth, is constantly mobile and moving, and has a battery life that could last anywhere from 5 to 10 years. Generating highly random keys isn’t just challenging, it’s critical to human health and well-being.
Quantum is Coming
It’s not the RSA algorithm that’s insecure, but rather poorly implemented random number generation. That said, it’s worth noting that quantum computing could threaten to undermine many of the algorithms we rely on today, including RSA. NIST predicts that even 8192-bit RSA keys could be vulnerable within the next decade, as advances in large-scale quantum computers continue.
Manufacturers Must Make It Right
The fact that a quarter million RSA keys from the past five years are vulnerable to this attack, even for an attacker with limited resources, is seriously troubling. Huge fractions of these keys live on next-generation IoT and embedded network devices being adopted by enterprises and consumers today.
What’s the course of action then? It starts at design. Device manufacturers must architect security into their devices during design and development, and ensure that the software and cryptography on the device can be updated securely throughout its lifecycle.
