[MUSIC]

Hi, in this video we're going to study an interesting attack which takes

advantage of many different devices using encryption.

And the fact that sometimes there is insufficient randomness, so to say,

to generate the keys when they are generated.

So this attack was invented by Heninger et al., and Lenstra et al., and

this is actually a practical attack.

So they used public keys from a set of different devices and

they used them to decipher some of the private keys.

And the experiments resulted in 0.4% HTTPS keys were factored,

which is not a big percentage, but this is actually a pretty big number.

So a lot of communication that was considered to be secure turned

out to be decipherable using public keys from different devices

which used the same algorithm to encrypt.

So this is the code, which is not the exact code, but

some code that resembles the OpenSSL popular program, RSA key generation.

So first, we initialize the number generator rng as an instance of class

random number generator and then we seed it rng.seed with some random seed.

And we need to get the seed from somewhere if we just hardcode some fixed number

like 12345 as a seed then it won't actually be a random number generator.

It will always create the same sequence of numbers because it is not a real random

number generator, it's a pseudo random generator and they work as following.

They get some initial seed and then they generate some sequence of numbers

which looks like random but it is determined by the initial seed completely.

So typically what programs like this do if they work on someone's

computer they ask the user to maybe move the mouse for

some time to get some randomness from the timings of the mouse.

Or if this is, for example, on the router, then it can take the current time

as the seed or some of the contents of the network packages that it has listened to.

So we seeded our random number generator, after which we generate

the first random prime number p as rng.generate big random prime, please.

Then we further improve random number generator maybe,

by adding some randomness, like take some bits from memory and

seed our random number generator even more with these bits,

which hopefully collected some more information from

outside which could be treated as random bits.

So then we generate another big random prime number Q.

And then we compute n which is equal to p times q, and

publish this n as a public key.

So what can the problem here, the problem is what if the seed is not random enough?

Well, it is hard to measure randomness.

So these are truly just words, but

the example of what I'm referring to is that keys can be, for example,

generated by the network router immediately after startup.

So no incoming network packages were accumulated yet.

So we cannot use any external information sent to the router as

a source of randomness.

And on some of the routers, they don't use any hardware randomness generators

which use some physical processes, to get some real randomness from.

So in this case, nothing is left as to use something like time, as the Seed.

And there are not so many variance of value for time.

So it can happen that sometimes, not very often, but sometimes, the same prime

number p will be generated as the first number, just right after seeding.

Because sometimes, the seeds will coincide on different devices.

So then random p is the same on two different devices.

After that, our random number generator is again seeded with something,

maybe with time again or some network packages came in through the router so

something changed and now we generate another random number q.

And although it can happen that q will also coincide this is not very likely.

I mean if the first number is only 0.1% likely to coincide and

the second number is also 0.1% likely to coincide.

So if the first number already coincided with 99.9% probability,

the second number will not coincide across these devices.

So what we'll get in the end and that one public key will be

generated as p times q1 and another public key on another router

will be generated as same p times q2 which is different.

So what can we get from there?

If the public keys n1 and n2 are generated on different devices using the same p but

different q, then the greatest common divisor of those two public keys n1 and

n2 is equal to p, because p is prime and it is a common divisor but q1 and

q2 are different.

So the only common divisor is just p.

And using the simple Euclid's algorithm we can compute

the greatest common divisor of n1 and n2, which is going to be p.

After that we can just divide n1 and n2 by p and factorize both n1 and n2.

After that our public keys break into private keys and

our encryption scheme is broken.

So can take keys from may routers and try to combine all pairs.

We don't know which router is generated n1 and

n2 with the same prime, but if we just try to take all pairs and

try to compute quickly their greatest common divisor,

at some point some of the pairs will give us the coinciding p and

we will be able to decipher these public keys.

And this is what actually the scientist who came up with this attack,

did with public traffic and public keys and

they were able to decipher 0.4% of all HTTPS keys.

So to avoid this attack, this is much more subtle as you probably noticed,

you need to make sure that random number generator is properly

seeded before you start generating your prime numbers.

And there are many ways to do that on the routers,

you can use some hardware physical randomness generator, or

you can avoid generating keys right after start up.

You can first listen to some incoming network traffic to

get some random bits from the incoming messages and so on.

And if you're for example writing a software for

a personal computer then some research can be with problems that need to generate

keys to ask the user first to move the mouse for some time to get randomness.

And then they rely on the actual person to do some random movements with the mouse

with some random timings and random positions.

And then they get the random number generated,

seeded using that kind of randomness.

[MUSIC]