Editor's note (11/16/15): Following the terrorist attacks in Paris on November 13 and the ensuing debate about counterterrorism efforts and encrypted communications, Scientific American is republishing the following article.
In the three months since Edward Snowden began his whistle-blowing campaign against the National Security Agency (NSA) the former government contractor has exposed the agency’s massive online eavesdropping efforts and attempts to circumvent encryption used to secure digital communications. The latest allegations indicate the NSA manipulated and weakened a cryptography standard the National Institute of Standards and Technology (NIST) had issued several years ago.
As a result, NIST last week publicly discouraged tech companies from using that cryptographic approach and promised to give the public an opportunity to weigh in on a revised standard. The fix may not be all that difficult—the tainted part of the standard is a highly inefficient algorithm that security experts identified as a problem long ago. In fact, the biggest mystery, those experts say, is why the NSA thought any company or government agency would willingly use that particular algorithm to protect their data. “It certainly wasn’t inserted into the standard with the intention of making an efficient algorithm available to the community,” says Ari Juels, chief scientist of computer storage provider EMC’s RSA security division.
The NIST Special Publication 800-90 cryptography standard includes four different algorithms—called “deterministic random bit generators,” or DRBGs—for encoding data. The algorithm included at the NSA’s behest—Dual Elliptic Curve Deterministic Random Bit Generation, or Dual_EC_DRBG—is vulnerable to tampering and could allow the agency to build in a so-called backdoor it could use to determine the values that the algorithm generated, essentially neutering its effectiveness to keep information secret, according to documents Snowden leaked to the New York Times, The Guardian and ProPublica.
The NSA orchestrated essentially a “kleptographic” attack on anyone entrusting their data to the Dual_EC_DRBG algorithm, which would intentionally leak data through a cryptographic backdoor, Juels says. “Security analysts and programmers have been writing and testing kleptographic systems since 1996, but you would be hard-pressed to find one in actual use, until now,” he adds.
NIST’s job is to develop standards and guidelines to protect federal information and data systems, and industry often follows its recommendations for its own technology. “Reopening the discussion over this standard is likely a face-saving move for NIST,” Juels says. “They presumably could have just jettisoned this algorithm, but that might have looked worse than soliciting public input.”
Computer scientists for years suspected that such a backdoor existed in Dual_EC_DRBG. Security researchers from Eindhoven University of Technology in the Netherlands noted in May 2006 that the algorithm was insecure and that an attack against it was easy enough to launch on “an ordinary PC”. The following year two Microsoft engineers flagged Dual_EC_DRBG as potentially containing a backdoor (pdf), although they stopped short of accusing NIST and the NSA of inserting it there intentionally.
NIST denies the accusations, pointing out on its Web site that the agency is “required by statute” to consult with the NSA and stating, “NIST would not deliberately weaken a cryptographic standard.”*
Yet that is exactly what appears to have happened. Documents provided by Snowden show the spy agency played a crucial role in writing the standard that NIST is now cautioning against using, the New York Times reported. NIST published the cryptography standard in 2006, and the International Organization for Standardization (ISO) later adopted it for its 163 member countries.
Despite Dual_EC_DRBG’s known flaws, prominent tech companies including Microsoft, Cisco, Symantec and RSA include the algorithm in their product’s cryptographic libraries primarily because they need it to be eligible for government contracts, cryptographer Bruce Schneier says. It is up to the private sector companies that buy these products to decide whether to enable the algorithm, something they are unlikely to do in the case of Dual_EC_DRBG, according to RSA’s Juels.
Snowden’s latest revelations may leave NIST and the NSA somewhat red-faced, but they do not damage cryptography’s credibility overall as a security measure, says Paul Kocher, founder, president and chief scientist of Cryptography Research, a designer of data, computer and network security systems. Efforts to use a backdoor as a means of defeating cryptography indicate the basic technology is still formidable. “There’s really nothing that impacts the fundamental mathematics underpinning encryption here,” he adds.
Buggy software and flawed operating systems still pose a far greater threat to data security and Internet privacy. The real issue is the government’s credibility. “This sort of a thing is a big deal from a political perspective,” Kocher says. “You expect that the government will produce security standards with pure intent. When that line’s crossed, even if it’s not in a widely used program, that’s obviously troubling.”
*Editor's Note (9/18/13): This sentence was edited after posting. The original stated that NIST only initially denied that it deliberately weakened a cryptographic standard. NIST indicated to Scientific American that it stands by its statement that it would not deliberately weaken it.