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.

keyfactor

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.

keyfactor

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.

Banner


10th Google Code-in Sets New Records
11/02/2020

The winners of Google Code-in 2019 have been announced. The Grand Prize winners, who represent 21 countries, will get to enjoy a 4-day trip to Google HQ to meet with mentors from the open source proje [ ... ]



Java 8 Remains Dominant
06/02/2020

While a quarter of Java developers and running the most recent Long Term Support version Java 11 in production, almost two thirds still use Java 8 and only 4% have adopted Java 12.


More News

Last Updated ( Thursday, 02 January 2020 )