How does NSA break SSL?

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.

3 Likes

Fascinating. It’s really eye-opening how vulnerable routers can be, even if the manufacturer puts its best foot forward. For example, here’s a vulnerability my friend uncovered where routers with FPGAs can be compromised at even the hardware level. https://😾😾😾.fm/ (aka Thrangrycat)

Yes… he really did use emojis for the disclosure name :slight_smile:

2 Likes