The last attack I want to talk about is a very recent observation

that was observed by Heninger et al and Lenstra et al

that shows that RSA key generation can be problematic when it's done with bad entropy.

So here's how things go wrong. So the way open SSL generates RSA keys is as follows.

Well, it starts by basically seeding the pseudo random number generator.

And then it uses random bits from a pseudo random number generator to generate the first prime p.

Then it will go ahead and seed the random number generator some more,

and will generate bits from the pseudo random number generator to generate q.

And finally, it will output the product of p and q.

Okay so the two steps, where we see the seed the pseudo random number generator.

Now suppose that this is implemented on a router or a firewall of some sort,

and suppose that the key generation happens right after the firewall starts up.

So the firewall boots up. At the time of the boot, there's not a lot of entropy

in the pseudo random number generator, and as a result

the firewall is likely to generate a prime p that comes from a very low entropy pool.

Which means that this p is gonna be one of a small number of possibilities.

However, after we've generated p, generating the prime actually takes a little bit of time,

a few microseconds. And so, by then the firewall will have generated more entropy

and so after we add more entropy to the entropy pool,

the prime q say is generated from a much larger entropy pool and is therefore unique to this firewall.

Now the problem is that many different firewalls if they generate an RSA key

in this way many of them will actually end up using the same prime p but a different prime q.

So what this says is that if we look at two RSA moduli from two different firewalls, N1 and N2.

If we compute the GCD of N1 and N2, well both of them had different q's but the same p.

So if we compute the GCD, actually we will end up with a factorization of N,

of both N1 and N2 and then we can actually figure out the private key both for N1 and for N2.

So this has actually been observed in practice.

Both of these groups, what they did is they scanned the web

and recovered all of the public keys out there that are used on various web servers.

They then ran a massive GCD, using some arithmetic tricks

they were able to compute this massive GCD of all pairs of public keys N1 and N2.

And lo and behold, they actually realized that a fair number of these keys have a common factor.

So they were actually able to factor these moduli.

So in the experiment, they were actually able to factor about .4% of all public SSL keys.

This is an amazing fact, that, in fact, so many web server public keys out there

are vulnerable just because they happened to generate the RSA key using low entropy.

So they have a common factor with somebody else's factor

and GCDing the two together gives you the factorization.

So, the lesson from all this is when you generate keys,

no matter whether they are RSA keys or ElGamal keys or symmetric keys,

it's crucial that the number--, that your generator is properly seeded.

So don't generate keys immediately after start up. You have to kind of make sure

the seeding of the generator has had enough time to actually generate enough entropy.

And only then you can start generating keys. So this is a really nice example

of how a, a bad random number generator can mess up your RSA public keys.