SSL

The New York Times published an article by John Markoff a couple days ago, “Flaw Found in an Online Encryption Method.” Sadly, the article is behind the Times paywall. Irritatingly, it’s a very good article except for the headline, which is wrong. The flaw isn’t found in the encryption, but in some key generation.

A better (and freely available) article is Dan Goodin’s article in Ars Technica, “Crypto shocker: four of every 1,000 public keys provide no security” or Elinor Mill’s article, “Researchers find flaw in key generation with popular cryptography” in CNet.

Let me get right to the bottom line. This does not affect any Entrust certificates. We checked all of our issued certificates and if you are one of our customers, you’re safe. Take a deep breath now, and relax.

(We also are grateful to and profusely thank the authors of gmp and gmpy without whom we could not have done our own analysis so quickly.)

The full paper of this is available here, and quite readable.

Here is how it works. RSA keys are made from two prime numbers that are multiplied together. The security of the RSA algorithm relies on the fact that it’s hard to factor the big number into the two little ones.

However, it is relatively easy to check for the greatest common divisor of two numbers — it’s a lot easier than factoring the numbers. Since both of those numbers are the result of two numbers multiplied together, a common factor unrolls them all.

The authors of the paper: Arjen Lenstra, James Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, and Christophe Wachter, surveyed about seven million certificates and found about 27,000 that they could find a common divisor for some of them.

That means that the code somewhere that generates the RSA keys for something isn’t very random. But where and why?

This is not the only work in this area that has been done. At the PETS conference in 2004, Ben Laurie and Matthias Bauer did the same analysis of PGP keys and found no duplicate factors in them.

This morning, Nadia Heninger published her analysis on the Freedom to Tinker blog, “New research: There’s no need to panic over factorable keys–just mind your Ps and Qs.”

Henniger says that she, along with Zakir Durumeric, Eric Wustrow, Alex Halderman, also analyzed many certificates and found similar results. However, they manually examined the flawed keys and found that they were generated by embedded devices such as “firewalls, routers, VPN devices, remote server administration devices, printers, projectors, and VOIP phones,” not by web servers or other like systems.

Heninger’s post has wonderful detail — I’m not going to do anything more than post a link to her article again. Read it. Her team is contacting the people who have vulnerable devices so they can fix the problem on their device.

I think that this check should become a standard part of all key certification, comparing against the known bad keys.

In the mean time, we can stand down for most of what we do on the Internet. This is a serious problem that needs to be fixed where it exists, but it’s not the end of the world.