Dual_EC_DRBG
Dual_EC_DRBG, formally known as the Dual Elliptic Curve Deterministic Random Bit Generator, is a pseudorandom number generator that produces deterministic bit sequences from an initial seed through iterative elliptic curve point multiplications and coordinate extractions on a fixed curve over the finite field \mathbb{F}_p with p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1.[1] The algorithm maintains an internal state s_k, updated as s_k = g_P(s_{k-1}) where g_P(x) = X(P^x \mod p) extracts the x-coordinate of the elliptic curve point P^x, and generates 32-byte outputs r_k = g_Q(s_k) with g_Q(x) = t(X(Q^x)) applying a truncation t(x) = x \mod 2^{16} to the x-coordinate of Q^x.[1] Standardized by NIST in Special Publication 800-90A in 2006 as one of four approved DRBGs, it was proposed by the National Security Agency (NSA) using NSA-generated parameters including the curve equation y^2 = x^3 - 3x + b with specific b and points P, Q \in E(\mathbb{F}_p).[2] Despite its inclusion in standards like ANSI X9.82 and adoption in commercial products such as RSA BSAFE and Juniper ScreenOS, Dual_EC_DRBG exhibited inefficiencies, producing output at only about 4 bytes per elliptic curve operation compared to hundreds for alternatives, and early cryptanalyses revealed statistical biases in truncated outputs.[3] In 2007, Microsoft researchers David Shumow and Niels Ferguson publicly demonstrated a kleptographic vulnerability: if Q = d \cdot P for a secret discrete logarithm d, an attacker knowing d can predict all future outputs from merely 32 consecutive bytes of prior output, effectively backdooring the generator while preserving forward security for users lacking d.[1] The NSA's selection of P and Q—where such a relation plausibly holds given computational infeasibility for outsiders to verify without d—combined with the algorithm's underperformance and resistance to parameter replacement in some implementations, fueled suspicions of deliberate sabotage.[1] Following 2013 disclosures from Edward Snowden's leaks confirming NSA efforts to undermine it and subsequent analyses, NIST deprecated Dual_EC_DRBG in 2014, recommending its removal from products due to unmitigated backdoor risks.[2][4]History
Origins and Development
The Dual_EC_DRBG, or Dual Elliptic Curve Deterministic Random Bit Generator, was developed by the National Security Agency (NSA) in the early 2000s as a pseudorandom number generator based on elliptic curve cryptography.[1] [5] The algorithm leverages point multiplication on two generator points, P and Q, on a specific elliptic curve over a finite field to produce output bits from an initial seed, aiming to provide deterministic randomness suitable for cryptographic applications.[6] It was first publicly presented on July 19–22, 2004, at a NIST workshop on random number generation in Gaithersburg, Maryland, where Don Johnson of Entrust delivered the talk titled "Number Theoretic DRBG," describing the core mechanism despite NSA origins.[1] [7] The presentation outlined the generator's reliance on the difficulty of the elliptic curve discrete logarithm problem, with fixed curve parameters and points selected for 128-bit security strength.[6] NSA personnel contributed to the design but did not present, reflecting the agency's role in advancing number-theoretic approaches amid broader NIST efforts to standardize deterministic random bit generators (DRBGs).[1] Following the workshop, the algorithm appeared in the June 2004 draft of ANSI X9.82, a financial services standard for random number generation, proposed alongside other DRBG candidates like those based on hash functions and block ciphers.[1] NIST incorporated it into the December 16, 2005, draft of Special Publication 800-90, co-authored by Elaine Barker and John Kelsey, which included four DRBG options for federal use; public comments were solicited until February 1, 2006.[1] Despite early cryptanalytic concerns—such as biases noted by Kristin Gjøsteen in 2005—the mechanism advanced to finalization in NIST SP 800-90 on June 25, 2006, and was adopted in ANSI X9.82 Part 3 and ISO/IEC 18031:2005.[1] [5] This development occurred parallel to U.S. advocacy for its inclusion in international standards, amid NSA's push for elliptic curve-based primitives in cryptographic protocols.[1]Standardization Process
The Dual_EC_DRBG algorithm was proposed by the National Security Agency (NSA) and integrated into cryptographic standards through collaborative efforts involving the American National Standards Institute (ANSI), the National Institute of Standards and Technology (NIST), and subsequently the International Organization for Standardization (ISO). The ANSI X9.82 project, focused on random number generation for financial services, commenced in 1998 under the Accredited Standards Committee X9, with the NSA contributing the Dual_EC_DRBG mechanism around 2003.[8] A draft of ANSI X9.82 incorporating Dual_EC_DRBG was released in June 2004, following its presentation at a NIST workshop in July 2004, though public review was limited due to the standard's paywalled access.[1] The standard was finalized as ANSI X9.82 Part 3 in 2007, designating Dual_EC_DRBG as one of several approved deterministic random bit generators (DRBGs).[8] Parallel to ANSI efforts, NIST incorporated Dual_EC_DRBG into its Special Publication 800-90, "Recommendation for Random Number Generation Using Deterministic Random Bit Generators," with a draft released on December 15, 2005, and public comments solicited until February 2006. NIST standardized it in June 2006 as one of four DRBG options, alongside Hash_DRBG, HMAC_DRBG, and CTR_DRBG, citing the NSA's existing implementations and the need for FIPS 140-2 validation compatibility.[8] During this period, concerns emerged, including Microsoft's 2005 identification of potential trapdoor vulnerabilities in the algorithm's elliptic curve points P and Q, and statistical bias observations in output distributions noted by reviewers in 2006.[1] Despite these, the algorithm retained its default NSA-generated parameters, with optional provisions added for user-generated alternatives. The U.S. delegation influenced ISO standardization by directing adoption of ANSI X9.82 elements into ISO/IEC 18031:2005, "Information technology — Security techniques — Random bit generation," which included Dual_EC_DRBG.[1] Subsequent revisions addressed specific issues: NIST SP 800-90 was updated in March 2007 to add backtracking resistance via an additional step in the generation process, and further revised in 2008 and 2012 to refine reseeding and instantiation procedures without altering the core Dual_EC mechanism.[8] These standards emphasized implementation flexibility, but the NSA's persistent advocacy for inclusion—despite identified biases and efficiency drawbacks compared to other DRBGs—drew scrutiny from cryptographers during workshops and comment periods.[1]Key Events Timeline
Technical Description
Algorithm Overview
The Dual_EC_DRBG is a deterministic random bit generator designed to produce pseudorandom bits from an initial seed, relying on the computational difficulty of the elliptic curve discrete logarithm problem for its security. It operates over NIST-recommended elliptic curves P-256, P-384, or P-521, each defined by the equation y^2 = x^3 - 3x + b in the finite field \mathbb{F}_p, where p is a large prime and b is a curve-specific constant. For the P-256 curve, p = \mathtt{ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551}_{16} and b = \mathtt{5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b}_{16}. The algorithm uses two fixed points P and Q on the curve E(\mathbb{F}_p), with P generating a large prime-order subgroup of order n.[12] The internal state consists of an integer s such that $1 \leq s < n. Initialization derives s from seed material (entropy input, nonce, and optional personalization string) using the derivation function Hash_df to produce a value of length seedlen bits (e.g., 256 for P-256), interpreted as an integer modulo n. A reseed counter is set to 0.[12] Bit generation proceeds iteratively: for each block, compute r = X(s \cdot Q), where \cdot denotes scalar multiplication on the elliptic curve and X extracts the x-coordinate as an integer in [0, p-1]. The output block is the rightmost outlen bits of r (outlen = 240 for P-256). The state is then updated as s \leftarrow X(s \cdot P). This loop repeats, concatenating output blocks, until the requested number of bits is obtained or a maximum per-request limit is reached (e.g., $2^19 bits for P-256). Additional input can be incorporated by XORing it into s before computing r. Reseeding periodically refreshes s using new entropy.[12] The functions effectively define g_P(s) = X(s \cdot P) for state update and g_Q(s) as the truncated X(s \cdot Q) for output, with truncation selecting the lower-order bits to match outlen. The design assumes that predicting future outputs from past ones is as hard as solving the discrete logarithm relating P and Q.[12]
Mathematical Foundations
The Dual_EC_DRBG relies on the hardness of the elliptic curve discrete logarithm problem (ECDLP) within the additive group of rational points E(\mathbb{F}_p) on a specific elliptic curve E over the prime finite field \mathbb{F}_p, where p = \mathtt{ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551}_{16}.[1] The curve follows the Weierstrass form y^2 = x^3 - 3x + b \mod p, with the coefficient b = \mathtt{5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b}_{16}. These parameters define a curve suitable for approximately 128 bits of security under the ECDLP assumption, where computing the discrete logarithm d such that Q = d \cdot P for points P, Q \in E(\mathbb{F}_p) is computationally infeasible without knowledge of d.[1] Fixed points P and Q on E(\mathbb{F}_p) act as the primary parameters for pseudorandom generation, with P serving as a base point and Q derived as a multiple of P. Their coordinates are: \begin{aligned} P_x &= \mathtt{6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296}_{16}, \\ P_y &= \mathtt{4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5}_{16}, \\ Q_x &= \mathtt{c97445f45cdef9f0d3e05e1e585fc297235b82b5be8ff3efca67c59852018192}_{16}, \\ Q_y &= \mathtt{b28ef557ba31dfcbdd21ac46e2a91e3c304f44cb87058ada2cb815151e610046}_{16}. \end{aligned} Scalar multiplication in the group uses the standard elliptic curve point doubling and addition formulas, yielding points whose x-coordinates provide the raw material for state transitions and outputs. The core functions g_P and g_Q map an input scalar x \in \{0, 1, \dots, p-1\} to elements of \mathbb{F}_p via x-coordinate extraction after scalar multiplication: g_P(x) = X(x \cdot P) and g_Q(x) = t(X(x \cdot Q)), where X denotes the x-coordinate of the resulting point (represented as an integer in [0, p-1]) and t applies truncation by discarding the least significant 16 bits of that integer.[1] The generator iterates by updating the internal state s_k = g_P(s_{k-1}) from an initial seed-derived s_0 and producing output blocks r_k = g_Q(s_k), with each r_k further processed into bit strings of requested length by taking the most significant bits from the truncated value. This construction assumes that the x-coordinates behave pseudorandomly under the ECDLP, though the minimal truncation in t limits provable security bounds.[1]Operational Mechanics
The Dual_EC_DRBG maintains an internal state s, a 256-bit integer representing a scalar for elliptic curve operations on the NIST P-256 curve defined over the finite field \mathbb{F}_p where p = \mathtt{ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551}_{16}, with equation y^2 = x^3 - 3x + b and b = \mathtt{5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b}_{16}. The fixed generator points are P and Q with coordinates: \begin{aligned} P_x &= \mathtt{6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296}_{16}, \\ P_y &= \mathtt{4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5}_{16}, \\ Q_x &= \mathtt{c97445f45cdef9f0d3e05e1e585fc297235b82b5be8ff3efca67c59852018192}_{16}, \\ Q_y &= \mathtt{b28ef557ba31dfcbdd21ac46e2a91e3c304f44cb87058ada2cb815151e610046}_{16}. \end{aligned} To generate pseudorandom bits, the algorithm proceeds as follows in each iteration:- Compute the elliptic curve point U = s \cdot P via scalar multiplication.
- Extract the x-coordinate r = X(U), interpreted as an integer in [0, p-1].
- For output generation, compute the point V = r \cdot Q and extract t = X(V).
- The output block consists of the 240 most significant bits of t, obtained by truncating the 16 least significant bits: \lfloor t / 2^{16} \rfloor.
- For state update, compute the point W = r \cdot P and set the new state s = X(W).