In December of 2015, Juniper Networks announced a vulnerability in their encryption algorithm and a master password within the firewalls of their software, ScreenOS. This is significant because of the use of Juniper routers in the US government, which is a speculated motivation behind the attack. In this paper, we aim to identify how these attacks were crafted and what the implications of these attacks could mean for Juniper’s customers. Though the attack on Juniper’s Dual EC algorithm is clear through Juniper’s flawed code, there is some ambiguity over who implemented the attack, when the attack was implemented and what their motivations are. With the announcement, Juniper released a patch for both vulnerabilities, however the extent of the aftermath of the attack is still unknown.
Media coverage of the Juniper hack was convinced that the culprits were nation-state attackers who had all of the U.S. government’s secrets at their whim. Within a day of Juniper’s official statement detailing the vulnerabilities, four nations- Russia, UK, China, Israel - were held in suspicion as possible attackers, though there was little to no evidence of this. Coverage including the involvement of the FBI and DHS was hailed as evidence of a foreign attack, although many of this is speculation merely based on the fact of their involvement and not by any direct statements from the agency. Actual reports of the extent of the hack have not been released.
Following more details of the hack, Juniper was harshly criticized for using Dual EC DRBG, Dual Elliptic Curve Deterministic Random Bit Generator, in their software even though it was long known to be a weak encryption. The NSA also suffered backlash because of evidence by Snowden confirming that NSA engineered a backdoor in Dual EC, which was a brainchild between the NSA and NIST as a standard in encryption. Juniper was also accused of implementing the Dual EC backdoor in conjunction with the NSA, hurting the integrity of their software despite their claims against the accusations.
Dual EC 101
Before discussing the vulnerability exploited in Dual EC, we must first discuss the technical details surrounding the Dual EC pseudorandom number generator. Dual EC is constructed on top of Elliptic Curve Cryptography, which as the name implies, is done using an Elliptic Curve over a finite field. Sparing the extensive mathematical definitions of Elliptic Curves over finite fields, the three basic constraints for the curve itself are that it follows the form Y^2 = X^3 + ax + b, the determinant, 4a^3 + 27b^2, is not equal to 0, and it has a “point at infinity”. What is important to note is that we are able to construct a group structure over the curve, where the group operator is something analogous to addition. To explain this better, take any two arbitrary points on the curve, say A and B. Applying the group operator A + B, we will be able to get a third point on the curve, -R, which we can just flip to get the point R, denoting that as A + B = R.
So why is this important, and what exactly was the vulnerability in Dual EC that was exploited? In Dual EC, we note that there are several “public” variables, that do not matter if they are known. Specifically, these are the elliptic curve, and two distinct points on the curve, P and Q. However, it is important to note that while Q is publicly known, the way it is generated is unknown. With this information in mind, let us consider the discrete log problem. To explain what this problem is, we will take a look at the Diffie Hellman Key exchange protocol. In Diffie Hellman, consider the following: given some generator/variable g, and some output y computed as g^x = y, find the value x such that g^x = y. The security of the key exchange algorithm is based on the hardness of the problem, and solving the problem would break the underlying security of the algorithm. Now, jumping back to Elliptic curve cryptography, here the discrete log problem is given P and some output Q, calculated as eP = Q, it is hard to find e such that eP = Q. Note that this is over elliptic curves and it is not as simple as just dividing both sides by P to find e. Again, like Diffie Hellman, the security of Elliptic curve cryptography is based on the hardness of this discrete log problem, and if someone were able to solve it, would break many of the overarching schemes. In other words, being able to find how exactly Q was generated, or knowing what exactly e is, would break many of the constructs on top of Elliptic curve cryptography.
Juniper implemented their system to follow the following pipeline: Dual EC, which is insecure, would generate a random seed value after 1000 outputs/blocks generated from the ANSI X9.17 PRNG, pseudorandom number generator. The seed value would be fed into ANSI X9.17, which is proven to be secure, which would generate random values for IKE, Internet Key Exchange. However, during the prng_ressed() function call inside the source code,(displayed below), the variable prng_output_index is reset to 32 instead of 0. As such, the statement inside the for loop: prng_output_index <= 0x1F, fails to be met and thus the code inside is never executed (0x1F is 31 in decimal). As a result, the PRNG that is outputting random numbers to IKE is Dual EC not ANSI X9.17. If the code did not have such a bug in it, the pipeline would have been secure.
But in 2007, Shumow and Ferguson, two researchers from Microsoft, noted that if the discrete logarithm problem could be solved, e.g the value e were known, then seeing the output of Dual EC, or at least 30 bytes of the output would be sufficient to recover the internal state of Dual EC and predict any future output of the PRNG. In the disassembled binaries, a hard coded master password was found. This gave access to the attackers to change the value of Q to something they generated, therefore also knowing the value of e. Even without the password, statically analyzing the output would provide enough information to recover the internal state of Dual EC.
Exploiting the Dual EC vulnerability and using the hardcoded backdoor, an attacker could have initiated the following attack, (displayed below). They would log into ScreenOS via the hardcoded backdoor, most likely using ssh, and gain admin access to the system. Inside the system, they would modify Q to a non-random number such that they know what eP evaluates to. This limits the number of unknown variables to the initial state only. Now each time Dual EC outputs to IKE, the attacker can see the raw outputs of Dual EC and exploit the vulnerability.
As the IKE protocol is similar to TLS, we will use TLS as an example to explain how the attacker can deduce the internal state of the Dual EC algorithm and generate the future outputs from Dual EC. (Please note that IKE is a two phase protocol, the first is a Diffie–Hellman key exchange, and the second is a nonce exchange). In TLS, the server outputs the random values: x of gx and the server random. Since x is hard to figure out given the problem of discrete logs, the attacker will ignore this output and use the server random. The server random is a encrypted, raw output of size 32 bytes from Dual EC, which fits the minimum criteria of the vulnerability where the attacker needs to know at least 30 bytes of an output. During each of the outputs of Dual EC, its internal state is incremented each time (using the equation below where S is the state) in a deterministic fashion. Using the vulnerability, the attacker can narrow the current state to 3 different possibilities. Let’s say the value outputted by these 3 possible states is X’0, X’1, X’2 respectively. During the next handshake, the attacker can passively obtain the value of gx, and g since it is public, and check whether gx’0 or gx’1 or gx’2 is equal to gx. Thus, the attacker knows which of the three states is equal to the current state.
The question now stands, what could Juniper have done better? For one, Juniper should not use the Dual EC DRBG algorithm. It’s output is biased and thus fails the to be a ‘random’ generator. The most important characteristic of a pseudorandom/random generator is that it’s output be ‘truly’ random meaning that given the input and the output, someone could not determine what the next output would be because to he/she, it is random. Dual EC DRBG, however, produces a biased output and as proven previously knowing at least 30 bytes, it’s easy to predict the internal state of Dual EC thus determining how the value is generated. In addition to this, Juniper needs to fix the part in the code that skips over using ANSI entirely thus using a deterministic output vs. a non-deterministic one for IKE. Whether Juniper hardcoded the password into the machine code or whether a hacker discovered it remains unclear. In any case, a password should never be hardcoded.
The (Potential) Attackers
To add some more uncertainty into the picture, there are a couple suspicions as to whom the hackers behind this attack(s) are. In most of the articles concerning the hack, there was a document attached released by Snowden between the NSA and Britain. It listed a number of flaws/potential vulnerabilities that Juniper had that Britain was considering exploiting. None of these flaws, however, included the hacks described in this post. In addition, the articles listed the attackers as Russia and NSA instead of Britain. Thus, there is no concrete evidence that either country partnered with NSA just strong speculations. (There is also the theory that Russia went ahead and did the hack themselves). Regardless of which country approached NSA, both had common enemies: Pakistan, Yemen, India and China all whom which used Juniper’s screenOS. Going to the NSA with their discoveries would simply make clear that their attack isn’t meant to be against the U.S. If Britain/Russia could go forward with the hack, NSA would have access to the intercepted traffic as well. Being that NSA has been surrounded by controversy and claims that include their spying on everyone, including American governments, it’s no surprise that they would put U.S. government information at risk as well.
Once the hack was discovered, U.S. government scrambled to find how many federal agencies were at risk of espionage. Soon after, the worry spread to other companies, like Cisco and Fortnet, leading them to patch flaws that were exploited by hack that was potentially associated with NSA. Companies and investors lost trust in Juniper which hit the company when their stock dropped by 10%. In the end, Juniper was one of many companies whose vulnerabilities were exploited. We’ll never know what companies do or don’t have a backdoor in their software. All we can do as users of these systems is protect ourselves as much as we can: complex passwords, secure encryption algorithms and being wise in where we put our information. No matter how safe and secure a company claims to be, every system or software has some flaw that can be exploited. The important thing is to take the proper measurements and be ready for when an attack does happen.
https://theintercept.com/2015/12/23/juniper-firewalls-successfully-targeted-by-nsa-and-gchq/ (detailed + NSA/Britain document)