NSA-style agency could install 'trapdoors' in many cryptographic keys - study
A 1,024-bit prime — used in 22 percent of the top 200,000 HTTPS-protected websites, according to SSL Pulse — can be broken with a special discrete logarithm computation, essentially placing a undetectable backdoor, or "trapdoor," in a cryptographic key, allowing for decryption, according to researchers at the University of Pennsylvania and the Université de Lorraine in France.
The researchers said a trapdoor in a 1,024-bit key that protects encrypted communications is feasible for well-resourced hackers, especially those working with top-notch computing technology. This would implicate mainly state institutions like the US National Security Agency.
Documents released in 2013 by intelligence contractor Edward Snowden revealed that the NSA seeks to attack encryption standards across the internet. Documents on an NSA program codenamed "Bullrun" showed that the US government penetrated encryption securities through the use of “supercomputers, technical trickery, court orders and behind-the-scenes persuasion."
"The Snowden documents have raised some serious questions about backdoors in public key cryptography standards," Nadia Heninger, a University of Pennsylvania researcher and co-author of the report, told Ars Technica. "We are showing that trapdoored primes that would allow an adversary to efficiently break 1,024-bit keys are completely feasible."
It took the research team "a little over two months" to break a weakened 1,024-bit key using "an academic cluster" of 2,000 to 3,000 CPUs.
Two years after Snowden revelations exposed "Bullrun," Heninger and others published research posting that the NSA could break powerful encryption. Getting past 1024-bit primes would require a machine that costs a few hundred million dollars, they wrote, yet that supercomputer would still only be able to crack about one 1024-bit prime a year. A well-funded and determined institution like the NSA could fit the bill.
Since 2010, the National Institute for Standards and Technology has recommended using keys of at least 2,048 bits, though 1,024-bit keys are still common, Ars Technica wrote.