The mission of the US' National Institute of Standards and Technology, NIST, is to create technical and measurement standards to make US manufacturing and industry more competitive.

In 1987, the Computer Security Act tasked NIST (then known as the National Bureau of Standards, NBS) with the creation of computer standards to ensure the security of federal computer systems. The best known standard that came from this work is probably the Advanced Encryption Standard (AES) algorithm. NIST held a competition between 1997 and 2000 to pick a symmetric cipher (that is, one where the same key is used for both encryption and decryption). The winner of the competition was Belgian algorithm Rijndael, and accordingly, Rijndael is known as AES.

The CSA explicitly required NIST to seek the advice and guidance of the National Security Agency when creating these standards. The NSA is, after all, where the government's cryptography experts work, and once upon a time, the organization was pretty helpful in this area. Before the CSA, the NSA had helped develop old NBS standards. In the 1970s, NBS created a standard for AES's predecessor, called the Data Encryption Standard (DES).

The DES algorithm was (officially) developed by IBM after NBS solicited proposals for its encryption standard. At the time, there was concern over certain aspects of the algorithm's design. In particular, the algorithm defines various mappings between numbers, called S-boxes. Put one number into the S-box, get another one out. At the time, the NSA was accused of having tampered with the mappings that these S-boxes described, when the S-boxes the algorithm's designers originally chose were replaced without explanation after government consultations.

In the 1990s, a new technique of analyzing and attacking encryption algorithms, called differential cryptanalysis, was developed. It turns out that DES' susceptibility to cryptanalysis depends on the mappings defined by the S-boxes. The S-boxes that the government had specified in DES turned out to be resistant to this kind of attack. It was later revealed that IBM's researchers had discovered differential cryptanalysis and told NSA about it. Rather than undermining the algorithm, NSA had used the technique to shore up DES to improve its security, then kept it secret.

A change in mission?

However, documents leaked by Edward Snowden suggest that the NSA's influence can be rather less than helpful. The Guardian says that secret documents confirm that the NSA "has been introducing weaknesses into security standards." Specifically, a NIST-approved standard from 2006 was functionally edited solely by the NSA.

Neither The Guardian nor the New York Times is specific about exactly which spec was weakened by the NSA, but it's widely believed to be one called Special Publication 800-90.

SP 800-90 specifies four different algorithms for securely generating pseudorandom numbers. Each of the four algorithms is based on a different cryptographic technique, on the basis that if the underlying technique is secure, then it makes sense to use that same technique in other applications where security is useful.

Three of the algorithms (based on hashing, encryption, and HMAC) were uncontroversial. The fourth, named Dual_EC_DRBG and based on elliptic curve encryption, raised eyebrows. The algorithm was extremely slow, and the random numbers it produced were flawed: they had a detectable bias, with some numbers slightly favored over others.

With these issues, the obvious response would be to exclude it, but it was kept in at the NSA's insistence. The agency argued that Dual_EC_DRBG was worth including because of its theoretical basis: it should be difficult to predict the numbers the algorithm will generate as long as the elliptic curve discrete logarithm problem remained difficult to solve. SP 800-90 also had an appendix that included an optional technique for addressing the bias issue.

Soon after SP 800-90 was published, however, a bigger problem was found. Just as with DES, the Dual_EC_DRBG algorithm includes certain parameters that have to be chosen by the algorithm designer. For DES, the parameters define the S-box mappings. For Dual_EC_DRBG, they define the elliptic curve and a chosen point on that curve. In 2007, two Microsoft researchers presented a paper that described an attack on Dual_EC_DRBG. What these researchers discovered was that the point and the curve were related to one another by another number. If that other number was known then an attacker could examine the random numbers generated by the algorithm, and subsequently predict the numbers that would be generated in the future.

This in turn means that any algorithm that used those random numbers could be compromised. We saw a similar attack recently, when a bad random number generator in Android allowed the theft of $5,700 of bitcoins.

At the time, the researchers were unsure of what their findings meant. The rationale for choosing the particular parameters that Dual_EC_DRBG specifies isn't known, and it was possible that the algorithm's designers didn't know the number relating the point to the curve.

Without knowledge of that number, it isn't possible to predict the numbers generated. It's also not possible to easily work backwards: if the designers of Dual_EC_DRBG don't know it, then nobody else can readily determine it either (or at least, they can't determine it without solving the elliptic curve discrete logarithm problem). And similar to the bias issue, SB 800-90 includes an optional way to generate new parameters rather than using the ones included in the spec, so even if the algorithm's designers do know the magic number, the algorithm can still be used securely.

Nonetheless, at the time the concern was raised that the NSA had put a backdoor in the standard.

With the revelation that the NSA has, in fact, worked to undermine the security of specifications, it seems highly likely that the NSA does know how the numbers are related, and so could predict random numbers generated by Dual_EC_DRBG.

If the NSA did indeed insert a backdoor into SP 800-90, it was a peculiar effort. Of the 401 validated implementations of SP 800-90, only 66 even implement the algorithm. While implementations of it do exist in common software—Microsoft added it to Windows Vista Service Pack 1, for example, and it can be found in OpenSSL and many Java libraries too—its slow performance means that it isn't ever likely to be a popular choice. Combined with the concerns about bias—known before the SP 800-90 was finalized—and the worries about NSA backdooring, and users are likely to be few and far between.

As such, it all seems to be a bit pointless. Unlike NSA's secretive work on DES—which made the algorithm better—the secretive work presumed to have taken place on SP 800-90 has probably made it a little bit worse. Money well spent? Not really.