The National Security Agency has a long history of putting backdoors into encryption mechanisms. As an example, it was known that the NSA put backdoors into router equipment made by Cisco. In this post, I briefly explain one possible way that NSA could break SSL.

The NSA did contribute to the NIST suite of pseudo-random number generators which was the Dual Elliptic Curve Deterministic Random Generator. The Dual_EC_DRBG specifies a particular cyclic curve, and it specifies a particular pair of points, but it does not state how those given points were generated. This standard was specified in a NIST standard called SP 800-90A.

In the following you can see how the Dual_EC_DRBG works:

r_i←number(s_i P)

s_(i+1)←number(r_i P)

Output(bitstring(r_i Q))

In this algorithm, we have a given point P, and we have some seed value s_0, and after the first and second scalar multiplications, we convert the output point on the curve to a number. Note that P = eQ for some e, and finding e would require solving the elliptic curve version of the discrete logarithm problem, but the generator (possibly NSA) of P and Q could know the value of e. In that case, if the NSA could observe just one output from this sequence, then the NSA could simply multiply the output which is r_i Q to e and the result will be r_i e Q = r_i P, and it means the NSA could compute s_(i+1), and consequently the rest of the outputs and break the secrecy of the Dual_EC_DRBG.

Now the main question is how NSA could break SSL. The start phase of SSL protocol is SSL handshake which parties exchange a master secret, and then the master secret will be used for encrypting further communication by using symmetric cryptography. The point is in generating the master secret the Dual_EC_DRBG was being used, and if the NSA could break the secrecy of the Dual_EC_DRBG, then it means the secrecy of the master secret would be under an attack as well.