Do not panic about weak RSA keys - just take care of your P and Q

You may have already seen a preprint published today by Lenstroy et al. ( Discussion in Habré ) about problems with entropy in public-key cryptographic systems. Zakir Durumerik , Erik Vustrov , Alex Halderman , and I (Nadia Heninger) waited to reveal similar results. We will publish the full article after all involved manufacturers will be notified. Meanwhile, we want to provide a more complete explanation of what is actually happening.

We were able to remove compromised about 0.4% of all public keys used by web sites for SSL. All the compromised keys were incorrectly generated, using predictable "random" numbers, which, moreover, were sometimes repeated. In total, we can distinguish two types of problems: keys generated with predictable randomness, and a subset of these keys, for which the lack of randomness allows an attacker to quickly factor the public key and get the secret key. Having a secret key, an attacker can impersonate a website and may be able to decrypt encrypted traffic sent to this site. We have developed a program that in a couple of hours can factor public keys and issue secret keys for all hosts vulnerable to this attack.

However, do not panic, since the problem mainly affects embedded systems, such as routers and VPNs, and does not apply to full-scale servers. (In any case, this is definitely not a reason to lose the power of attorney for e-commerce, as the New York Times suggests). Unfortunately, we found devices with this problem in almost every manufacturer, and we suspect that about 200,000 devices, representing 4.1% of all the keys in our data, used bad entropy to generate keys. Any weak key found by the device assumes that the entire class of these devices is vulnerable to attack with proper analysis.
')
We will not provide a complete list of vulnerable devices before we contact all manufacturers, but using already published materials you can quite easily replicate the attack. Therefore, we are currently working on a web site that will determine whether your device is vulnerable.

Do not worry, the key of your bank is likely to be safe.

SSL is used by every large site on the Internet, but as our analysis shows, these keys are not subject to the problems described in this post.

So which systems are in danger? Almost all vulnerable keys were generated and used in embedded systems, such as routers and firewalls, and were not used on websites for banks or e-mail. Only one of the vulnerable SSL keys was signed by a certification authority and it has already expired. We also found several signed certificates using duplicate keys; some of which were generated by vulnerable devices, others were submitted for signature by site owners as obviously weak and for some we cannot come up with a good explanation.

Everyone knows that in embedded systems there are problems with entropy. However, up to the current time it was not clear how these problems were common in real devices connected to the Internet.

Key Generation

Web sites and network computers use public-key cryptosystems for identification. Next we will talk about the type of identification, when the server provides the client with a certificate in order to certify the client that he is the one to whom the client wants to connect. If the attacker knows the secret key, he can impersonate the real system or, in most cases, decrypt the traffic between the client and the server.

RSA is the most commonly used cryptosystem for this purpose. RSA cryptosystem protection is based on factoring large numbers. The RSA public key consists of a pair of integers: the open exponent e and the module N , which is the product of two large primes p and q . If the adversary can factor N back into p and q , then he will also be able to decrypt any text encrypted with the public key. However, even using the fastest algorithms for factoring, no one has yet been able to factorize a 1024-bit module.

An important part for key security is the availability of random input data at the key generation stage. If the entropy is not enough in these inputs, then the attacker will be able to guess them, and thus obtain the secret key, without agonizing factorization of the number N.

On modern computers and servers, key-generation programs use random input from many physical sources (most often using the operating system): mouse movements, keyboards, hard drives, network events, and other unpredictable sources. However, if there are few sources, there will be a lack of entropy, and the key may be vulnerable to attack. Gathering strong entropy and testing its strength is a very complex problem that has generated many vulnerabilities over the years.

Two versions of the problem

To investigate how common this problem is, we scanned all IPv4 addresses and collected copies of each SSL certificate and SSH key. It took us less than a day to collect keys and certificates: at first we used standard nmap to find hosts with the corresponding open ports, and then we used our optimized program to poll these hosts. In total, we collected 5.8 million SSL certificates and 10 million SSH keys.

As we discovered, entropy problems lead to two different kinds of weaknesses:

Duplicate public keys.

About 1% of all RSA keys were met again, most likely due to entropy problems. If two devices have the same public key, then they also have the same secret key. In reality, all devices with the same key are in the same position - the attacker can compromise the weakest of these devices and get the keys to all the others. It has long been known about this problem, but until now, no one has documented in the open literature how common it is.

We manually verified that 59,000 keys were repeated due to entropy problems, which represent about 1% of all certificates, or 2.6% of all self-signed certificates. We also found that 4.6% of all devices (585,000 certificates) used default certificates. And although these devices did not use keys generated with bad entropy, they are subject to the same attack, since their secret keys are the same on all models. We manually checked all these keys, because a large number of sites use duplicate keys in the right conditions and therefore does not pose a danger to the user.

Factorable public keys.

More surprisingly, we found that entropy problems may allow a remote attacker, without special access, to factor a significant portion of all RSA keys used on the Internet. We were able to factor 0.4% of all RSA keys in SSL certificates. To do this, we calculated the largest common divisor (gcd) for all pairs of modules from RSA public keys on the Internet.

We identified 1,724 common dividers, which allowed us to factorize 24,816 SSL keys and 301 common dividers to factorize 2422 SSH keys. This means that we were able to calculate the secret keys for almost 0.5% RSA keys used for SSL. Next we will explain how our calculation works.

Specific vulnerable devices

Embedded systems often generate cryptographic keys when they are first loaded, when all their state can be predefined at the factory. What can lead to such problems with entropy, as described in this study.

We were able to use the information from the SSL certificate to identify the type of devices that are prone to generating weak keys. Probably there are also many other devices, the keys of which we could not factor, but which are still inclined to produce weak keys and which can be compromised by a stubborn attacker. The complete list of vulnerable devices that we were able to identify consists of more than 30 manufacturers, including almost all the major manufacturers in the industry. Types of devices with a problem include firewalls, routers, VPN devices, devices for remote administration of servers, printers, projectors, and VOIP phones.

We will not list the device names until we notify, but below you can see a few examples:

Firewall X :
52.055 hosts in our SSL data
6.730 with the same keys
12.880 with factorizable keys

User-level router Y :
26.952 hosts in our SSL data
9.345 with the same keys
4.792 with factorizable keys

Solution for remote access Z, for enterprises :
1.648 hosts in our SSL data
24 with the same keys
0 with factorizable keys

How could this happen?

It is not entirely obvious how problems with entropy can lead to problems with keys that are easily factorized. Now we will explain why this happens for our more inquisitive readers.

Here's how a programmer can generate a module for RSA:
prgn.seed(seed)
p = prgn.generate_random_prime()
q = generate_random_prime()
N = p*q
If the grain for a pseudo-random number generator has a predictable value, then several different devices may have the same N module, but we do not think that a good pseudo-random number generator can produce two different N modules with the same common factor.

However, some implementations also add an additional randomness between the generation of prime numbers p and q , with the idea of ​​improving security:
prgn.seed(seed)
p = prgn.generate_random_prime()
prgn.add_randomness(bits)
q = generate_random_prime()
N = p*q
If the first grain was generated with bad entropy, this can lead to the fact that several devices will have different modules consisting of the same factors p and different factors q . Therefore, we can factorize both modules using GCD: p = gcd (N1, N2).

RSA key generation in OpenSSL works as follows: after each use of random bits from the entropy pool to generate the prime numbers p and q , the current time in seconds is added to the pool. Many, but not all, vulnerable keys were generated using OpenSSL and OpenSSH, which uses OpenSSL to generate RSA keys.

GCD calculation for all key pairs

If any pair of RSA modules N1 and N2 has the same factor, then you can just factorize both modules using gcd. On my desktop computer, the gcd calculation operation for two 1024 RSA modules takes about 17 micro seconds.

For people who are addicted to mathematics, I’ll now explain how we can use this idea to factor a large number of keys.

A simple approach to key factorization involves calculating gcd for each pair of RSA modules. But if we estimate how much time these calculations will take, we will get about 24 years on my desktop computer.

Instead, we use the idea of Dan Berstein , published in the Journal of Algorithms in 2005, which allows us to factorize a group of integers into mutually simple numbers and which will allow us to make our calculations in just a couple of hours, with the implementation occupying only a few lines in Python. The algorithm is not a big secret: a large number of published papers have worked to improve the algorithm.

The main mathematical review in this problem is that we can calculate gcd for the N1 module along with all the other modules using the following equation:
gcd(N1, N2 ... Nm) = gcd(N1, (N1 * N2 * ... Nm mod N1^2)/N1)
The big problem is how to make this equation miscalculate quickly - notice that the first step of this calculation is to find the product of all the keys, the number consisting of 729 million digits. We were able to factorize all SSL data in 18 hours on a single core processor and factorize SSH data in 4 hours on a four core processor.

Conclusion

This is certainly a problem, but not the one about which the average user should worry. However, there is a lot of work to be done by embedded system manufacturers, and some system administrators should be concerned. This should be a wake-up call for people in security, and a reminder to us all about how vulnerabilities are sometimes hidden in front of everyone.