Random Number Weakness Exposes Devices
Written by Kay Ewbank   
Thursday, 02 January 2020

A report analyzing RSA certificates has identified a weakness that means they can be easily cracked, exposing network and IoT devices that rely on digital certificates based on RSA certificates.

The researchers from KeyFactor looked at 75 million RSA certificates from the Internet, and found that 1 in 172 certificates have keys that share a factor with another. In contrast, only 5 of 100 million certificates found in a sample from Certificate Transparency logs are compromised by the same technique. KeyFactor is a provider of secure digital identity management solutions that can be used for authenticity checking, and for ensuring devices are interacting correctly.


RSA is used in the process of encrypting data to send across a network. The server transmits its RSA public key to the client as a part of an SSL or TLS handshake. Part of the RSA public key contains the modulus n = p * q, where p and q are two randomly chosen primes of similar size. The primes are kept secret, and need to be selected with sufficient randomness to make them hard to guess. If the keys are generated with poor randomness, that can lead to two public keys sharing a factor once enough keys are generated. If two share a prime factor, then computing the Greatest Common Divisor (GCD) of the two will reveal the value of the shared prime. This computation can easily be performed in practice, and once found the other factors of the keys can easily be found. 

The researchers used this technique on the data they collected. It was analyzed on a single virtual machine in the Microsoft Azure cloud, using the researchers' scalable GCD algorithm for shared factors. The analysis revealed that at least 435,000 weak certificates – 1 in 172 of the certificates they found on the Internet – are vulnerable to this attack.

The researchers say that RSA keys are at risk of compromise when using improper random number generation. Weak keys can be discovered and subsequently compromised by finding reused prime factors in a large data set. This is particularly a problem in IoT devices because many generate keys that don't have enough randomness. This is combined with a large number of certificate pairs available for analysis because of the increase in devices accessible on the IoT. The researchers said they were able to obtain hundreds of millions of RSA keys used to protect real-world traffic on the Internet. They said that:

"Using a single cloud-hosted virtual machine and a well-studied algorithm, over 1 in 200 certificates using these keys can be compromised in a matter of days."

The researchers conclude that device manufacturers must ensure their devices have access to sufficient entropy and adhere to best practices in cryptography to protect consumers.

However, thy also conclude that it is still unlikely that a key that has been properly generated with a sufficient amount of entropy could be broken with this technique.


More Information

KeyFactor Report

Related Articles

RSA Encryption Cracked By Careless Implementation

Public Key Encryption

Public Key Cryptography Set To Fail In Five Years

RC4 Stream Cypher - 75 Hours To Crack

25 GPUs Crack Passwords In Minutes

Canada's RAND Immigration Lottery Not Random!

LOGJAM - Can The NSA Break 1024-bit DHM Keys?

What Does The NSA Think Of Cryptographers?

Poodle Is A Very Different Sort Of Security Breach

Stick Figure Guide To AES Encryption

Crypto Made Easy


To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.


AWS Introduces A New JavaScript Runtime For Lambda

Amazon has announced the availability, albeit for experimental purposes, of a new JavaScript based runtime called Low Latency Runtime or LLRT for short, to bring JavaScript up to the performance throu [ ... ]

Run WebAssembly Components Inside Node.js With Jco

Jco 1.0 has been just announced by the Bytecode Alliance.It's a native JavaScript WebAssembly toolchain and runtime that runs Wasm components inside Node.js. Why is that useful?

More News

Last Updated ( Thursday, 02 January 2020 )