In-Depth
The RSA Key Kerfuffle: Why Randomness Is Hard
Just how much of a problem is the RSA key kerfuffle? Two research teams weigh in about encryption schemes.
Two separate teams of research teams recently raised concerns about the security of the encryption schemes used by popular security protocols such as secure sockets layer (SSL).
According to a report issued by a team of U.S.- and EU-based researchers, two out of every 1,000 keys generated by the popular RSA encryption algorithm are "insecure." A separate group of researchers, working primarily out of the University of Michigan (UM), says the risk is higher: as many as four out of every 1,000 RSA keys are insecure.
The two research teams came to different conclusions about the impact of their findings, however. The UM-based group limits the scope of its advisory primarily to embedded devices; the first group, on the other hand, sees the problem as much more widespread.
RSA Security Inc., for its part, claims that neither team has discovered a flaw in the RSA algorithm itself. The problems, RSA maintains, are strictly on the implementation side.
"[T]he data does not point to a flaw in the algorithm, but instead points to the importance of proper implementation, especially regarding the exploding number of embedded devices that are connected to the Internet today," said RSA in a statement.
Widespread Panic?
The report prepared by the multinational team is based in part on information collected by the SSL Observatory project of the Electronic Frontier Foundation (EFF).
EFF describes SSL Observatory as an attempt to collect and study the certificates used to encrypt HTTPS traffic on the IPv4 Internet; as part of its SSL Observatory effort, EFF maintains a dataset of all publicly-visible SSL certificates. The multinational team used these certificates, along with a separate dataset of other credentials (chiefly PGP keys), as the basis for its research.
The title of the team's report,Ron Was Wrong, Whit Is Right, is a cheeky allusion to two giants of public key cryptography: Ron Rivest and Whitfield Diffie. The former is the "R" in RSA.
According to the report, there's every reason to panic.
"[A]mong the 4.7 million distinct 1024-bit RSA moduli that we had originally collected, 12,720 have a single large prime factor in common," notes the report, a collaboration of security researchers Maxime Augier, Arjen K. Lenstra, James P. Hughes, Joppe W. Bos, Thorsten Kleinjung, and Christophe Wachter. "[I]t does not seem to be a disappearing trend: in our current collection of 11.4 million RSA moduli[,] 26,965 are vulnerable, including ten 2048-bit ones," the report continues. According to researchers, successful exploitation "could affect the expectation of security that the public key infrastructure is intended to achieve."
The team's findings seem to be at odds with the underlying math of the RSA algorithm, which is premised on the idea that the output of (i.e., the keys produced by) an input process using multiple (pseudo-)random values should be prohibitively difficult to factor. In other words, the keys produced by encryption schemes such as RSA should be, practically speaking, "secure."
The team doesn't necessarily take issue with the math underlying the RSA algorithm. It instead focuses on the practical difficulty of implementing any encryption algorithm that requires a pseudo-random value as input. It does, however, contrast the RSA algorithm -- which (in its default configuration) uses multiple (pseudo-)random values to produce its output -- with those of other schemes, such as Diffie-Hellmann, ElGamal, and the digital signature algorithm (DSA), which instead use a single (pseudo-) random value.
"We do not question the validity of this conclusion, but found that it can only be valid if each output is considered in isolation. When combined[,] some outputs are easy to factor because the above assumption sometimes fails," the report explains. "Cryptosystems such as RSA that require ... multiple secrets are more affected by the apparent difficulty to generate proper random values than systems ... that require a single secret."
Connect the dots and you have a widespread problem, the research team concludes. "We were surprised ... by the extent to which public keys are shared among unrelated parties. For [encryption schemes such as] ElGamal and DSA[,] sharing is rare, but for RSA[,] the frequency of sharing may be a cause for concern," the report notes, suggesting that its findings won't come as a surprise to "agencies and parties that are known for their curiosity in such matters."
The National Institute of Standards and Technology (NIST) proposed DSA for the digital signature standard (DSS) in 1991. At the time, this move was seen as controversial.
According to the report, however, there may have been more to this decision than was then known. The report does emphasize that DSA, ElGamal, and similar schemes likewise require a sufficient degree of randomness, although -- unlike default-RSA -- they require only a single (pseudo-random) input value to generate a key.
The Zero Effect
How might an attacker go about exploiting this vulnerability? It's easier than you might think.
As part of its testing, for example, the UM-based team developed a tool that can generate private keys for "all the hosts vulnerable to ... attack ... in only a few hours." (See below.)
What's more, says a CISSP with a prominent public sector-oriented services firm, the problem itself isn't unknown. "It's called a birthday attack. It's called that because if you pick a room of 'X' number of people, it's almost guaranteed that a higher percentage of them than you might expect will have the same birthdays," this security professional explains.
The findings show that the algorithms or methods used to generate keys in the affected implementations are insufficiently random, this CISSP says. ("Randomness" in this context applies to the selection of the large prime numbers used to generate keys in the first place.) In other words, some keys -- i.e., a higher proportion than one might reasonably expect -- share the same birthdays. This CISSP summarizes the problem by quoting a line from the circa-2000 film The Zero Effect. "If you're searching for something specific," he quotes, "your chances of finding it are very low. If you're searching for anything at all, your chances of finding it are very high."
In this case, "anything at all" refers to the set of known (or predictable) prime numbers.
A posting on the group blog "Freedom to Tinker" by Nadiah Heninger, post-doctoral fellow in the department of computer science and engineering at U.C. San Diego, and a member of the UM-centered team, describes just such a Zero Effect-like scenario.
"The keys we were able to compromise were generated incorrectly -- using predictable 'random' numbers that were sometimes repeated. There were two kinds of problems: keys that were generated with predictable randomness, and a subset of these, where the lack of randomness allows a remote attacker to efficiently factor the public key and obtain the private key," she writes. "With the private key, an attacker can impersonate a [W]eb site or possibly decrypt encrypted traffic to that [W]eb site. We've developed a tool that can factor these keys and give us the private keys to all the hosts vulnerable to this attack on the Internet in only a few hours."
Unlike the multi-national team, Heninger and the UM-based team see the scope of the problem as comparatively limited. "[T]here's no need to panic as this problem mainly affects various kinds of embedded devices such as routers and VPN devices, not full-blown [W]eb servers," she writes, dismissing speculation -- in The New York Times and elsewhere -- that the findings could or should undermine confidence in Web commerce.
"Unfortunately," she concedes, "we've found vulnerable devices from nearly every major manufacturer and we suspect that more than 200,000 devices, representing 4.1 percent of the SSL keys in our dataset, were generated with poor entropy. Any weak keys found to be generated by a device suggests that the entire class of devices may be vulnerable upon further analysis."