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
Related Articles
RSA Encryption Cracked By Careless Implementation
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
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.
