[WhoCares]

The following one is also interesting, though a little bit old.


The website is https://factorable.net. It showcases one of the more famous large-scale RSA key-cracking studies in cryptography, based on something called Batch GCD.

The discovery was made in 2012, when two independent research teams published their findings almost simultaneously:

The paper “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices”

This was published by researchers from the University of Michigan and the University of California, including Nadia Heninger and J. Alex Halderman. They scanned the entire IPv4 address space, collected tens of millions of TLS/SSL certificates and SSH keys, and set up Factorable.net to publish their findings.

The title “Ps and Qs” is a nice double entendre. In English, “mind your Ps and Qs” is an expression meaning to be careful about your behavior or what you say. Here, it also refers to the two prime factors, p and q, that make up an RSA key.

The paper “Ron was wrong, Whit is right”

This was published around the same time by a group led by renowned cryptographer Arjen Lenstra. “Ron” refers to Ron Rivest, one of the inventors of RSA, while “Whit” refers to Whitfield Diffie, one of the inventors of the Diffie-Hellman key exchange.

The paper pointed out that, because of flaws in how keys were generated on real-world devices, RSA could actually be more vulnerable to catastrophic attacks than DH key exchange in some environments.

The vulnerability and how the attack works

RSA relies on the fact that factoring a sufficiently large integer is computationally hard. An RSA public key contains a huge integer N, which is the product of two secret prime numbers: N = p × q. Normally, knowing only N isn't enough to recover p and q with practical amounts of computing power.

The problem was that a lot of real-world embedded devices — routers, firewalls, IoT devices, and so on — generated their cryptographic keys automatically the first time they were powered on.

Right after boot, however, the device's pseudorandom number generator (PRNG) often didn't have enough “entropy.” In other words, it simply didn't have enough unpredictable input to produce genuinely independent random numbers.

And that's where things went badly wrong.

Two devices on opposite sides of the world could end up with very similar random states and, by sheer chance, generate exactly the same prime p, while generating different primes q1 and q2.

Suppose an attacker collected the public keys from both devices:

N1 = p × q1
N2 = p × q2

At this point, there is no need to factor either of those huge numbers directly.

Just compute their greatest common divisor:

GCD(N1, N2) = p

GCD is extremely fast to compute, and the researchers used an algorithm called Batch GCD to do this efficiently across a huge collection of keys.

If the result isn't 1, you've found a shared prime factor p. From there, getting q1 and q2 is just a matter of division, and the attacker can immediately reconstruct the private keys.

That's the really nasty part of the attack: the computational cost is tiny compared with actually factoring an RSA modulus.

Using this technique, the researchers were able to recover the private keys of tens of thousands of real-world devices on the Internet.