NSA could put undetectable “trapdoors” in millions of crypto keys
Researchers have devised a way to place undetectable backdoors in the cryptographic keys that protect websites, virtual private networks, and Internet servers. The feat allows hackers to passively decrypt hundreds of millions of encrypted communications as well as cryptographically impersonate key owners.
The technique is notable because it puts a backdoor—or in the parlance of cryptographers, a “trapdoor”—in 1,024-bit keys used in the Diffie-Hellman key exchange. Diffie-Hellman significantly raises the burden on eavesdroppers because it regularly changes the encryption key protecting an ongoing communication. Attackers who are aware of the trapdoor have everything they need to decrypt Diffie-Hellman-protected communications over extended periods of time, often measured in years. Knowledgeable attackers can also forge cryptographic signatures that are based on the widely used digital signature algorithm.
As with all public key encryption, the security of the Diffie-Hellman protocol is based on number-theoretic computations involving prime numbers so large that the problems are prohibitively hard for attackers to solve. The parties are able to conceal secrets within the results of these computations. A special prime devised by the researchers, however, contains certain invisible properties that make the secret parameters unusually susceptible to discovery. The researchers were able to break one of these weakened 1,024-bit primes in slightly more than two months using an academic computing cluster of 2,000 to 3,000 CPUs.