This repo contains some research I'm currently doing on the Socat backdoor:

• everything to generate parameters for a DH backdoor

• contains everything to generate the attack on both Socat and Openssl (still not fully working)

• is a (now old) proof of concept (generation + small subgroup attack)

• contains work on reversing the backdoor in the old 1024bits socat modulus and checking the security of the new 2048bits one.

• hopefuly soon it will be full with estimations on Pohlig-Hellman and Pollard Rho

• wannabe whitepaper

• github/test_DHparams contains a tool to check your Diffie-Hellman parameters (is the modulus long enough? Is it a safe prime? ...)

Also, this page is getting long so here's a table of content:

1. Socat? What?
2. Human Error
3. How to implement a NOBUS backdoor
4. How to reverse socat's non prime modulus
5. How is the attacker using the backdoor
6. What about socat's new prime modulus?
7. Resources

On February 1st 2016, a security advisory was posted to Openwall by a Socat developer: Socat security advisory 7 - Created new 2048bit DH modulus

In the OpenSSL address implementation the hard coded 1024 bit DH p parameter was not prime. The effective cryptographic strength of a key exchange using these parameters was weaker than the one one could get by using a prime p. Moreover, since there is no indication of how these parameters were chosen, the existence of a trapdoor that makes possible for an eavesdropper to recover the shared secret from a key exchange that uses them cannot be ruled out.
A new prime modulus p parameter has been generated by Socat developer using OpenSSL dhparam command.
In addition the new parameter is 2048 bit long.

This is a pretty weird message with a Juniper feeling to it.

Socat's README tells us that you can use their free software to setup an encrypted tunnel for data transfer between two peers.

Looking at the commit logs you can see that they used a 512 bits Diffie-Hellman modulus until last year (2015) january when it was replaced with a 1024 bits one.

Socat did not work in FIPS mode because 1024 instead of 512 bit DH prime is required. Thanks to Zhigang Wang for reporting and sending a patch.

The person who pushed the commit is Gerhard Rieger who is the same person who fixed it a year later. In the comment he refers to an Oracle employee at the time who has yet to comment on his mistake. It also seems like his github account and his personnal websites were deleted the day this security advisory was published.

This research's goal is to understand how this could possibly be a backdoor. And more particularly, a Nobody-but-us one (NOBUS). Here are the objectives of this research:

• Build a proof of concept of such a NOBUS backdoor
• check if we can reverse the socat backdoor to use it ourselve
• Try to answer the question: "does it look like a backdoor?"

How likely is it a human error?

• I've tried reversing the hex array representation of the modulus to see if the developer made a mistake, but nothing.

• Someone proposed something weird that I didn't understand. If someone wants to help me here.

There seem to be different ways, with different consequences, to do that. backdoor_generator/backdoor_generator.sage allows you to generate backdoored DH parameters according to these different techniques, the explanations are in the source as well as the README there.

There is also a working proof of concept in PoC.sage that implements one way of doing it:

It creates a non-prime modulus p = p_1 * p_2 with p_i primes, such that p_i - 1 are smooth. Since the order of the group will be (p_1 - 1)(p_2 - 1) (smooth) and known only to the malicious person who generated p, Pohlig-Hellman (passive) or a Small Subgroup Confinment attack (active) can be used to recover the private key.

In the proof of concept the small subgroup attack is implemented instead of Pohlig-Hellman just because it seemed easier to code. They are relatively equivalent except that in practice an ephemeral key is used which makes small subgroup attacks not practical.

Note that these issues should not arrise if the DH parameters were generated properly, that is the order and subgroups orders should be known. If the prime is a safe prime, you don't need to do anything. If it is not, it might be that the order of the group (p-1) is smooth, this is a bad idea but nonetheless you can verify that the public key received lies in the correct subgroup by raising it to the power of the subgroup. See rfc2785 for more information.

The proof of concept is a step by step explanation of what's happening. Above you can see the generation of the backdoored modulus, bellow you can see the attack tacking place and recovering discrete logs of each of the subgroups

To run it yourself you will need Sage. You can also use an online version of it a cloud.sagemath.com.

from what we learned in implementing such a backdoor, we will see how we can reverse it to use it ourselves.

Trial division (testing every small primes up to a certain limit) has already found two small factors: 271 and 13,597. The last factor is still a composite of 1002 bits (302 digits) that we'll call C302 (C for Composite).

I tested if the generator (2) has order 271-1 or 13,597-1 or (271-1)*(13,597-1). But no.

Pollard's p-1 factorization algorithm should work fine for finding factors p if p-1 is smooth.

The records people have reached with this algorithm is to factor a ~200bits composite which largest factor was a 50bits and other factors under 30bits (with B1=10^10 and B2 =10^15).

But an attacker could have easily chosen factors of p-1 and q-1 to be of size > 50bits which would have canceled any possibility of Pollard's p-1 to factor p or q. He could have also added two 60 bits factors to void the B2 bound as well.

Another very good algorithm at factoring is the Elliptic Curve Method or ECM, that only depends on the size of the smallest factor.

The records found factors of size 276bits. This is again a problem if the backdoored modulus is composed of two 512bits primes.

The Quadratic Sieve, or QS algorithm running-time depends on the modulus's size, best for numbers under 400-500bits, and so is out of reach for our big 1024bits modulus.

Then, at some predetermined point where ECM is less likely to find a factor over time than the time taken to run a sieve method, you switch from ECM to the sieve method, which is SIQS below ~100 digits and NFS above 100 digits. These sieve methods are different in that they take a fixed amount of time for a given input number, and are guaranteed* to produce a factorization at the end. (Dubslow)

Finally the General Number Field Sieve, or the GNFS algorithm, which works according to the size of the entire modulus and not its factors, has a record of factoring 768bits in 2009. That might be our best bet, although the modulus is still too big for us to try. In the Logjam paper last year could be read that the NSA might have the capacity to do it.

Q: What are the chances that if this was non-prime was a mistake, it generated factors large enough so that no one can reverse it?

A: From Handbook of Applied Cryptography fact 3.7:

Let n be chosen uniformly at random form the interval [1, x]

1. if 1/2 <= a <= 1, then the probability that the largest prime factor of n is <= x^a is approximately 1+ ln(a). Thus, for example, the probability than n has a prime factor > sqrt(x) is ln(2) ~= 0.69
2. The probability that the second-largest prime factor of n is <= x^{0.2117} is about 1/2
3. The expected total number of prime factors of n is ln ln x + O(1). (If n = mult(p_i^{e_i}), the total number of prime factors of n is sum(e_i).)

This means three things:

1. item socat's 1024 bit composite modulus n probability to have a prime factor greater than 512 bits is ~0.69.
2. the probability that the second-largest prime factor of n is smaller than 217 bits is 1/2.
3. The total number of prime factor of n is expected to be 7 (we already have 2).

217 bits is feasible to find with ECM (maybe with p-1 factorization algorithm)

Note: More info can be found in backdoor_generator/README.md.

1. The attacker knows the factorization of the modulus
2. That means he knows the factorization of the order
3. He can compute the discrete logarithm in each subgroup and re-combine them to the real discrete logarithm (Pohlig-Hellman). This can be done passively with PH, or actively (small subgroup confinment attack) by sending points of different subgroup instead of computing them with PH.

How does he compute the Discrete Logarithm?

Most records use the NFS algorithm to compute the DLOG. The best so far is modulo 596 bits. Logjam did tackle a 512 bits as well.

But there exists faster and easier to use algorithms that work in O(sqrt(modulus)) like Pollard Rho or Baby-Step-Giant-Step. That means in a subgroup of prime order 64bits, these algorithms would compute a discrete logarithm in ~2^32 operations.

Note: In our proof of concept PoC.sage, the subgroups are so small (<20bits) that the naive approach of testing all powers of the generator is fast enough to compute the discrete logarithm of all the subgroups.

A new order has been generated, but we know nothing about its order: checking it with test_DHparams we confirm that it is a safe prime (2q + 1) so its order is implicit (2q).

on Socat:

• Thai Duong's blogpost
• crypto stackexchange's post
• reddit's thread
• metzdowd's discussion

on Backdoors:

• Paper keys under doomarts
• Surreptitiously Weakening Cryptographic Systems