Researchers have discovered a method for creating encryption backdoors that could be used by attacks to passively...
-- and undetectably -- decrypt communications and improperly sign data.
The researchers described how to construct -- and exploit -- prime numbers used by cryptographic algorithms like the Diffie-Hellman key exchange and the Digital Signature Algorithm (DSA) that can be factored with limited computing resources available in a modern academic setting, rather than the hundreds of millions of dollars of custom equipment that a government-level adversary would use. These crafted primes provide an attacker with what amounts to an undetectable encryption backdoor against 1024-bit keys, a length that has long been thought to be vulnerable only to brute-force attack by a government-level attacker.
In the paper, "A kilobit hidden SNFS discrete logarithm computation," researchers Joshua Fried and Nadia Heninger, both of the University of Pennsylvania, and Pierrick Gaudry and Emmanuel Thomé, both with the French Institute for Research in Computer Science and Automation, wrote that their "computations show that trapdoored primes are entirely feasible with current computing technology." The encryption trapdoor in the prime can be turned into an encryption backdoor, as long as the attacker is able to force targets to use that prime.
"A trapdoored prime means that it is much less expensive for an attacker who knows the trapdoor to solve the discrete logarithm problem modulo that prime," Heninger, assistant professor in the Computer and Information Science department at the University of Pennsylvania, told SearchSecurity by email. "An attacker who can solve the discrete logarithm problem can decrypt communications that were encrypted using Diffie-Hellman key exchange, or forge signatures using the DSA algorithm."
The danger arises from the ubiquity of widely used primes. For example, the Apache 2.2 server includes the hard-coded "group parameters" -- which include a large, difficult-to-factor prime number -- that are used to generate strong keys. Standard Diffie-Hellman group parameters are also specified in RFC 5114, "Additional Diffie-Hellman Groups for Use with IETF Standards," and are widely used as the basis for generating encryption keys.
The problem, according to Heninger, is that "[t]here is no known feasible way to detect a backdoor of the type we constructed in a prime that someone gives you.
"The concern we're raising here is that the hard-coded Apache parameter comes with no proof that it is not malicious," Heninger wrote. "We're not saying that we think the Apache prime is backdoored; it's just a prominent example of a prime that we cannot verify. So, a powerful attacker could generate a malicious prime and get it incorporated into a standard or widely used [library] as the default, and then be able to decrypt traffic as desired."
"Good cryptographic practice recommends that publicly agreed parameters must be 'verifiably random,'" the paper reads, though while some standardized cryptographic data is verifiably random, this is not always the case. The authors note, "RFC 5114 specifies a number of groups for use with Diffie-Hellman, and states that the parameters were drawn from NIST test data, but neither the NIST test data nor RFC 5114 itself contain the seeds used to generate the finite field parameters."
Countermeasures to protect against the possibility that an attacker is leveraging this flaw, according to Heninger, include using elliptic curve cryptography, using keys of at least 2048-bit length, or using "a verifiable randomness procedure as documented in FIPS 186 to generate their primes, and publish the seeds."
Find out more about issues raised around the integrity of Diffie-Hellman key exchange
Read about why CIA Director John Brennan thinks encryption backdoors won't affect U.S. businesses