Crypto is Not Broken
By Patrick Ball
On 14 February 2012, the New York Times reported that a Swiss team had found a weakness in a key algorithm used to make secure connections online. We were worried because the algorithm (called RSA) is also a central part of Martus, our self-encrypting database that backs itself up to a network of servers.
The bottom line: We've consulted with cryptographers and studied the Martus code, and we do not believe that there is a weakness affecting Martus users. The flaw turns out to be related to a design error in the implementation of RSA in specific "embedded" devices, specifically firewalls and routers. It's not a general problem with RSA, and there's no current risk to Martus users. The way this flaw emerged has motivated us to review Martus's security model, and we are pleased with how well it has stood up.
I've organized the detailed discussion as a series of questions.
- What exactly is the problem?
- How did this happen?
- Does it affect Martus?
- What's the big picture?
- Acknowledgements
What exactly is the problem?
In public key cryptography, there are two keys that complement each other. If one of the pair is used to encrypt a message, a website, or a Martus bulletin, the other key can be used to decrypt it. This is useful because a user can freely distribute one of her keys (called the public key) so that others can encrypt information that only the other key (called her private key) can decrypt. In Martus, sometimes users share bulletins by giving each other copies of their public keys (which we call "headquarters keys"). For websites and secure email, millions of public keys are published online so that people can make secure connections (Martus keys are not published, but they are exchanged directly among users who want to collaborate).
The kind of public key math most commonly used for most applications, including Martus, is called RSA. In this algorithm, the public key consists of two very large numbers (e, n), and the private key is three very large numbers (d, p, q), where n = p ⋅ q. P and q are prime numbers, and much of the strength of the cryptography depends on the mathematical fact that even if you know n, it is hard for a computer to figure out what p and q are. This means that even if n is public (which it is because it's part of the public key), the private key (including p and q) is still a secret.
Calculating p and q from n is called factoring n, and it is very difficult. A key with an n with 232 digits (768 bits) was factored in 2009 using many years of computing time and dozens of computers spread around the world. The smallest keys in use now, 1024 bits, are approximately one thousand times harder to factor than 768 bit keys. Most secure projects use much larger keys; Martus keys are 2048 bits long.
However, in order for the keys to be secure, they must be impossible to guess; being very large is only part of the security. That means that p and q must be chosen randomly. On Tuesday, a paper by researchers from a Swiss team (Lenstra et al.) showed that thousands of public keys published on the Internet in key servers shared a divisor, that is, p or q. This represents thousands of keys out of the millions tested: approximately 0.2% of the keys they harvested shared either p or q. If two public keys can be found to share a divisor, it's easy to figure out the other divisor, and thereby have factored both keys' n's. If this can be done, neither key is secure, and that's very bad news.
On 15 February 2012, another team (Heninger et al.) released similar results. However, the Heninger et al. results were focused on keys generated by very specific models of electronic devices, especially routers and firewalls. This contained the beginning of an explanation of what the Lenstra et al. study had really found.
Heninger et al. showed that specific kinds of devices produced keys for which p and q were chosen from a limited range. Although p and q are very, very large numbers hundreds of digits long, only a relative small range of possible numbers were being used to choose p and q. Experts we've talked with have told us that the analysis by Heninger et al. is of essentially the same data that Lenstra et al. are examining. This means the findings from both projects are pointing to the same weakness.
Both Heninger et al. and Lenstra et al. determined that many public keys published online include n's that shared p or q. This was detectable, and the keys were factored to yield their p and q (there are good, not-so-technical explanations of how this works at BoingBoing and at Ben Adida's blog).
The problem comes back to the selection of p and q, and it involves how computers choose random numbers. There are two parts of serious, computer-based random number generation: a "seed," or starting point, and a pseudo-random number generator. I'll take the latter first.
A pseudo-random number generator (PRNG) takes some number (the seed) and makes it into a sequence of new numbers (the random numbers we want to use). The trick is that a good PRNG produces a sequence of numbers such that even if you know the numbers it has generated recently, the next number is unpredictable.
However, PRNGs are deterministic. If you start from exactly the same seed, they will generate the same sequence of numbers. If you start from a very slightly different seed, the sequence will be totally different. Nonetheless, an identical starting seed will produce an identical sequence.
Therefore, we need to start from a really hard to predict place, and here's where the experts think those little devices failed. The seed for random number generation is usually created by looking at parts of a computer that are under constant change: how the hard disk is reading or writing; keystroke patterns; mouse movements; noise from a microphone or images from a web cam. Mix all this stuff up together in an equation (called a hash function), and you have a seed with high "entropy," stated simply, a lot of randomness.
The little devices Heninger et al. studied didn't get much entropy into their seeds. Their problem was that they were programmed to generate keys the very first time they were unwrapped and booted up. They're not user-driven machines, instead they're designed to be plugged in and basically run themselves. They didn't wait to collect enough churning info to seed their PRNG. On many occasions, they had only the same few bits of information in their seed, and that led to a limited range of results for p and q. We know this because in more than 12,000 cases (out of millions), the devices chose the same p or q values -- leading Lenstra et al. and Heninger et al. to be able to factor the n's of the public keys into the p's and q's of the corresponding private keys.
In short, this problem does not affect Martus. We use the Java programming language's mechanism for getting a high-entropy seed (SecureRandom) from the operating system, whether it's GNU/Linux, Windows, or Mac OS X. Then we pass the seed through Java's PRNG, and generate the key from the result. (Ok, we don't really do all that, the cryptography library we use -- BouncyCastle -- does most of it for us, but that's the process.) No weak seeds, no repeated p's or q's.
One more detail for security and programmer types: long ago, Java had some problems with seeding the PRNG, though the bug has been fixed since the Java Runtime Engine (JRE) version 1.4.1. We shipped the first production version of Martus (1.0) in December 2002 with JRE version 1.4.1.
We think the Times's conclusions, and those of Lenstra et al., are too strong. It's clear that the keys that Heninger et al. and Lenstra et al. identified have weaknesses; solid analysis is becoming available. The flaws come from the way certain devices created their keys, not in the RSA algorithm itself. We do not think that RSA should be discarded in favor of other public key algorithms, as some have suggested. The cryptographic software most commonly used for email security (PGP and gpg) does not seem to be compromised. We think this was a very useful lesson to all of us who publish crypto software ("mind your p's and q's," Heninger wrote), and we are taking the opportunity to review the last ten years of Martus security thinking. It stands up remarkably well, and we're proud of the code: since 1.0, there has not been even one security-related bug. We're pushing ahead, and we look forward to helping human rights groups keep their data safe in more ways and on more platforms.
The Martus team is grateful for helpful pointers and insight from cryptographers Phil Zimmermann (Zfone), Ben Adida (Mozilla), Ian Goldberg (University of Waterloo), and Seth Schoen (EFF). Any errors of fact or reasoning that remain are my (Patrick's) responsibility.
Comments