A potential backdoor in Dual_EC_DRBG – Elliptic Curves
8.4.4 A potential backdoor in Dual_EC_DRBG
Dual_EC_DRBG is a pseudorandom number generator based on elliptic curve cryptography. From 2006 to 2014, it was among the algorithms officially recommended by NIST in their Special Publication 800-90A Random Number Generation Using Deterministic Random Bit Generators. In 2014, NIST withdraw the algorithm based on substantial suspicion in the cryptographic community that the algorithm contained a cryptographic backdoor inserted by NSA, the authors of the algorithm.
Even before its official publication, numerous renowned cryptographers voiced concerns about Dual_EC_DRBG’s security because the algorithm’s design lends itself to a backdoor insertion. More importantly, the absence of a backdoor could only be verified by the algorithm’s designers.
Figure 8.9 shows a generic architecture of a pseudorandom number generator. Initially, the internal, secret state s is seeded using a truly random seed s0, for example, the sequence of the computer mouse coordinates, the time between the keyboard taps or the hard disk latency. From there on, state s is used as input into a cryptographically secure hash function h() to produce pseudorandom numbers r.
The hash function h is deterministic. Given a constant (or repeating) state s, it would therefore produce identical output r. To avoid this, function g(s) – for example, a second hash function – is used to update state s. If the value of s was s0 in the current iteration, the value for the next iteration would be g(s0).
Obviously, if Eve knew the value of s, she could predict every future r because she could compute every subsequent state g(s) and, knowing that state, every subsequent output r = h(g(s)). Fortunately, because h is a cryptographically secure hash function, it is computationally infeasible for Eve to reverse it. Hence, Eve cannot reconstruct s from r.
Figure 8.9: Basic architecture of a pseudorandom number generator
Figure 8.10 shows the architecture of the Dual_EC_DRBG pseudorandom number generator.
Analogous to the generic architecture in Figure 8.9, a truly random seed s0 is initially used to seed the internal, secret state s. Next, the algorithm multiplies an elliptic curve point P by s to obtain an intermediate value r. Finally, to produce a pseudorandom number, Dual_EC_DRBG multiplies a second elliptic curve point Q by r and outputs the x coordinate of the resulting point rQ, the 16 most significant bits being discarded [165].
Figure 8.10: Architecture of the Dual_EC_DRBG pseudorandom number generator
To break Dual_EC_DRBG, Eve must compute r given rQ (we can neglect the fact that she does not know the 16 most significant bits of rQ because 16 bits can be easily brute-forced). Computing r from rQ is equivalent to solving ECDLP, and we learned earlier in this chapter that solving ECDLP for cryptographically secure elliptic curves is computationally hard.
As a result, operation rQ can be in principle viewed as a one-way function, making it impossible for Eve to determine Dual_EC_DRBG’s secret internal state s from its output rQ. However, this only holds if the points P and Q were chosen randomly.
For the Dual_EC_DRBG specification in NIST’s Special Publication 800-90A, no explanation was given how its designers at NSA generated P and Q. As an example, based on what is publicly known, no NUMS numbers were used. Without such assurance, there is a risk of the following cryptographic backdoor. Assume that P and Q were chosen such that:
for some secret number e known only to Dual_EC_DRBG designers. If this is the case and Eve, being one of the algorithm’s designers, knows that secret e, then she can compute:
Because e(rQ) is associative, Eve can express it as r(eQ). Because P = eQ, Eve can compute:
thereby obtaining the secret internal state s. With the knowledge of s, Eve can calculate every subsequent pseudorandom number rQ and every subsequent internal state s.
While there is no definitive proof that Dual_EC_DRBG contains the above backdoor, the classified NSA files leaked by Edward Snowden in 2013 revealed the existence of a clandestine NSA operation codenamed BULLRUN whose aim was to break the encryption of online communication by inserting vulnerabilities into encryption systems and IT equipment. Based on Snowden’s leaked files, the New York Times reported that the NSA deliberately became the sole editor of the Dual_EC_DRBG standard and concluded that the standard indeed contained a backdoor.