Dual_EC_DRBG

Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criticism, including a potential backdoor, for seven years it was one of the four (now three) CSPRNGs standardized in NIST SP 800-90A as originally published circa June 2006, until it was withdrawn in 2014.An elliptic curve random number generator avoids escrow keys by choosing a point Q on the elliptic curve as verifiably random. Intentional use of escrow keys can provide for back up functionality. The relationship between P and Q is used as an escrow key and stored by for a security domain. The administrator logs the output of the generator to reconstruct the random number with the escrow key. Another alternative method for preventing a key escrow attack on the output of an ECRNG, shown in Figures 3 and 4 is to add a truncation function to ECRNG to truncate the ECRNG output to approximately half the length of a compressed elliptic curve point. Preferably, this operation is done in addition to the preferred method of Figure 1 and 2, however, it will be appreciated that it may be performed as a primary measure for preventing a key escrow attack. The benefit of truncation is that the list of R values associated with a single ECRNG output r is typically infeasible to search. For example, for a 160-bit elliptic curve group, the number of potential points R in the list is about 280, and searching the list would be about as hard as solving the discrete logarithm problem. The cost of this method is that the ECRNG is made half as efficient, because the output length is effectively halved.1. Dual_EC_DRBG, as specified in NIST SP 800-90A and ANSI X9.82-3, allows an alternative choice of constants P and Q. As far as I know, the alternatives do not admit a known feasible backdoor. In my view, it is incorrect to imply that Dual_EC_DRBG always has a backdoor, though I admit a wording to qualify the affected cases may be awkward.The Dual EC DRBG algorithm is only available to third party developers via the Cryptographic APIs on the platform. In the case of the Cryptographic API, it is available if a 3rd party developer wished to use the functionality and explicitly designed and developed a system that requested the use of the API.A Trojan is really, really big. You can’t say that was a mistake. It’s a massive piece of code collecting keystrokes. But changing a bit-one to a bit-two is probably going to be undetected. It is a low conspiracy, highly deniable way of getting a backdoor. So there’s a benefit to getting it into the library and into the product. Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criticism, including a potential backdoor, for seven years it was one of the four (now three) CSPRNGs standardized in NIST SP 800-90A as originally published circa June 2006, until it was withdrawn in 2014. Weaknesses in the cryptographic security of the algorithm were known and publicly criticised well before the algorithm became part of a formal standard endorsed by the ANSI, ISO, and formerly by the National Institute of Standards and Technology (NIST). One of the weaknesses publicly identified was the potential of the algorithm to harbour a kleptographic backdoor advantageous to those who know about it—the United States government's National Security Agency (NSA)—and no-one else. In 2013, The New York Times reported that documents in their possession but never released to the public 'appear to confirm' that the backdoor was real, and had been deliberately inserted by the NSA as part of its Bullrun decryption program. In December 2013, a Reuters news article alleged that in 2004, before NIST standardized Dual_EC_DRBG, NSA paid RSA Security $10 million in a secret deal to use Dual_EC_DRBG as the default in the RSA BSAFE cryptography library, which resulted in RSA Security becoming the most important distributor of the insecure algorithm. RSA responded that they 'categorically deny' that they had ever knowingly colluded with the NSA to adopt an algorithm that was known to be flawed, saying 'we have never kept relationship a secret'. Sometime before its first known publication in 2004, a possible kleptographic backdoor was discovered with the Dual_EC_DRBG's design, with the design of Dual_EC_DRBG having the unusual property that it was theoretically impossible for anyone but Dual_EC_DRBG's designers (NSA) to confirm the backdoor's existence. Bruce Schneier concluded shortly after standardization that the 'rather obvious' backdoor (along with other deficiencies) would mean that nobody would use Dual_EC_DRBG. The backdoor would allow NSA to decrypt for example SSL/TLS encryption which used Dual_EC_DRBG as a CSPRNG. Members of the ANSI standard group, to which Dual_EC_DRBG was first submitted, were aware of the exact mechanism of the potential backdoor and how to disable it, but did not take sufficient steps to unconditionally disable the backdoor or to widely publicize it. The general cryptographic community was initially not aware of the potential backdoor, until Dan Shumow and Niels Ferguson's publication, or of Certicom's Daniel R. L. Brown and Scott Vanstone's 2005 patent application describing the backdoor mechanism. In September 2013, The New York Times reported that internal NSA memos leaked by Edward Snowden indicated that the NSA had worked during the standardization process to eventually become the sole editor of the Dual_EC_DRBG standard, and concluded that the Dual_EC_DRBG standard did indeed contain a backdoor for the NSA. As response, NIST stated that 'NIST would not deliberately weaken a cryptographic standard.'According to the New York Times story, the NSA spends $250 million per year to insert backdoors in software and hardware as part of the Bullrun program. A Presidential advisory committee subsequently set up to examine NSA's conduct recommended among other things that the US government 'fully support and not undermine efforts to create encryption standards'. In April 21, 2014, NIST withdrew Dual_EC_DRBG from its draft guidance on random number generators recommending 'current users of Dual_EC_DRBG transition to one of the three remaining approved algorithms as quickly as possible.' The stated purpose of including the Dual_EC_DRBG in NIST SP 800-90A is that its security is based on computational hardness assumptions from number theory. A mathematical security reduction proof can then prove that as long as the number theoretical problems are hard, the random number generator itself is secure. However, the makers of Dual_EC_DRBG did not publish a security reduction for Dual_EC_DRBG, and it was shown soon after the NIST draft was published that Dual_EC_DRBG was indeed not secure, because it output too many bits per round. The output of too many bits (along with carefully chosen elliptic curve points P and Q) is what makes the NSA backdoor possible, because it enables the attacker to revert the truncation by brute force guessing. The output of too many bits was not corrected in the final published standard, leaving Dual_EC_DRBG both insecure and backdoored. In many other standards, constants which are meant to be arbitrary are chosen by the nothing up my sleeve number principle, where they are derived from pi or similar mathematical constants in a way that leaves little room for adjustment. However, Dual_EC_DRBG did not specify how the default P and Q constants were chosen, possibly because they were constructed by NSA to be backdoored. Because the standard committee were aware of the potential for a backdoor, a way for an implementer to choose their own secure P and Q were included. But the exact formulation in the standard was written such that use of the alleged backdoored P and Q was required for FIPS 140-2 validation, so the OpenSSL project chose to implement the backdoored P and Q, even though they were aware of the potential backdoor and would have preferred generating their own secure P and Q. New York Times would later write that NSA had worked during the standardization process to eventually become the sole editor of the standard. A security proof was later published for Dual_EC_DRBG by Daniel R.L. Brown and Kristian Gjøsteen, showing that the generated elliptic curve points would be indistinguishable from uniformly random elliptic curve points, and that if fewer bits were output in the final output truncation, and if the two elliptic curve points P and Q were independent, and if three problems were shown to be hard (only one of which is generally accepted as being hard), then Dual_EC_DRBG is secure. The proof relied on the assumption that three problems were hard: the decisional Diffie–Hellman assumption (which is generally accepted to be hard), and two newer problems which are not generally accepted to be hard: the truncated point problem, and the x-logarithm problem. Dual_EC_DRBG was quite slow compared to many alternative CSPRNGs (which don't have security reductions), but Daniel R.L. Brown argues that the security reduction makes the slow Dual_EC_DRBG a valid alternative (assuming implementors disable the obvious backdoor). Note that Daniel R.L. Brown works for Certicom, the main owner of elliptic curve cryptography patents, so there may be a conflict of interest in promoting an EC CSPRNG.