Millions Of RSA Key Exposes Serious Flaws That Can Be Exploited

A disturbing security vulnerability has been uncovered affecting RSA encryption keys used across the internet, with researchers discovering that approximately 1 in 172 certificates found online are susceptible to compromise through a mathematical attack.

This widespread vulnerability primarily impacts Internet of Things (IoT) devices but could potentially affect any system using improperly generated RSA keys.

The vulnerability stems from inadequate random number generation during key creation, particularly in devices with limited entropy sources.

When RSA keys are generated without sufficient randomness, they may share prime factors with other keys, making them vulnerable to factorization attacks.

Keyfactor Security researchers identified this critical issue after analyzing over 75 million RSA certificates collected from across the internet.

Their analysis revealed that 435,000 certificates were compromised using a relatively simple mathematical technique, representing a significant security risk to affected systems.

The attack exploits a fundamental property of RSA cryptography: if two different RSA keys share a prime factor, both can be broken by computing the Greatest Common Divisor (GCD).

While the standard factorization of large RSA moduli is computationally infeasible, calculating the GCD between two numbers that share a factor is trivial. Once a shared factor is found, the private key can be completely reconstructed.

Technical Details Behind The Attack

The researchers implemented an efficient GCD computation using the GNU MultiPrecision (GMP) library on a single cloud-based virtual machine.

Rather than performing quadratic numbers of pairwise GCD calculations, they used a product tree and remainder tree approach that runs in sub-quadratic time. The algorithm can be expressed mathematically as:-

GCD(nᵢ, n₁ * … * nᵢ₋₁ * nᵢ₊₁ … * nₘ) = GCD(nᵢ, (n₁ * n₂ * … * nₘ mod nᵢ²)/nᵢ)

The research found that IoT devices were particularly vulnerable, with approximately 50% of compromised certificates containing the name of a large network equipment manufacturer.

Many affected devices continued to use vulnerable keys even after previous security warnings, underscoring the challenge of patching IoT systems in the field.

The implications are especially concerning as IoT devices proliferate in sensitive settings like operating rooms, vehicles, and industrial control systems.

Researchers emphasize that device manufacturers must ensure their products have sufficient entropy sources and adhere to cryptographic best practices to protect users from these preventable vulnerabilities.

Are you from SOC/DFIR Teams? – Analyse Malware Incidents & get live Access with ANY.RUN -> Start Now for Free.