Facilitating the spread of knowledge and innovation in professional software development



Choose your language

InfoQ Homepage News Poor Random Number Generation Makes 1 in Every 172 RSA Certificates Vulnerable

Poor Random Number Generation Makes 1 in Every 172 RSA Certificates Vulnerable

This item in japanese


Research report by firm KeyFactor shows many IoT and network devices are using weak digital certificates that make them vulnerable to attack. Researchers Jonathan Kilgallin and Ross Vasko analyzed 75 million RSA certificates and found 1 in 172 keys share a factor with another, which means they can be easily cracked.

Indeed, if two keys share a common factor, this can be known by calculating their greatest common divisor (GCD). This in turns enables calculating the rest of the divisors of those keys. Since calculating the GCD is rather easy, this approach may be scaled to a large number of public keys that are publicly available on the Internet. In other words, mining public keys and calculating the GCD of pairs of them opens the way to easily breaking them if a common factor is found.

This result, and the possibility of launching an attack to break RSA key leveraging it, was already known, although it was not considered to be a major concern in practice:

Despite the large number of keys broken by this attack previously, it is still unlikely that a key that has been properly generated with a sufficient amount of entropy could be broken with this technique.

Kilgallin and Vasko have now shown the assumption that keys are generated with enough entropy is not verified in a worryingly high number of cases. Specifically, this seems to happen specifically with IoT appliances, which may not easily have enough entropy available to generate keys with a high level of randomness.

With modest resources, we were able to obtain hundreds of millions of RSA keys used to protect real-world traffic on the Internet. 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.

There are a number of additional reasons that make IoT devices specifically prone to this kind of attack, besides the lack of sufficient entropy. One such reason is the probability of succeeding in this kind of attack grows with the number of certificate pairs available to analysis, which has drastically increased due to the growth of the IoT market. Additionally, IoT devices are harder to patch, which makes it more likely to find vulnerabilities in devices that are no longer actively supported.

Although KeyFactor researchers focused on RSA, their results could be extensible to other algorithms relying on random number generation, such as Elliptic-Curve Cryptography (ECC), they say.

It is not the first time concern about IoT security is raised, with the latest disclosed vulnerability affecting a vast class of IoT devices being only week old. Kilgallin and Vasko's work bring again the focus on the importance of using security best practices from the inception of a project and to include support for timely updating both software and cryptography in IoT devices.

We need your feedback

How might we improve InfoQ for you

Thank you for being an InfoQ reader.

Each year, we seek feedback from our readers to help us improve InfoQ. Would you mind spending 2 minutes to share your feedback in our short survey? Your feedback will directly help us continually evolve how we support you.

Take the Survey

Rate this Article


Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Community comments

  • If two primes share a common factor … ?

    by Jon Wolski,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    You lost me at "if two prime numbers share a common factor." If two primes share a common factor (other than one) then they are the same prime number or they are not prime. Is that a typo? What did you mean?

  • Re: If two primes share a common factor … ?

    by Van Uriel,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    I'm also confused. The only common factor shared by two prime numbers is nothing but 1, right?

  • Re: If two primes share a common factor … ?

    by Giovanni Cuccu,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    The linked article explains the problem correctly:

    "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."

  • Re: If two primes share a common factor … ?

    by Sergio De Simone,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    Thanks for pointing at this -- it is the keys that may share a common factor, not the prime numbers. I have amended the article.

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p


Is your profile up-to-date? Please take a moment to review and update.

Note: If updating/changing your email, a validation request will be sent

Company name:
Company role:
Company size:
You will be sent an email to validate the new email address. This pop-up will close itself in a few moments.