This repo contains some research I'm currently doing on the Socat backdoor.
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 Zhigang Wang, an Oracle employee at the time who has yet to comment on his mistake.
This research tries to understand how this could be a backdoor. And more particularly, a NOBUS one (Nobody But Us). Here are the objectives of this research:
- Build a proof of concept of such a NOBUS backdoor
- In failures of building NOBUS backdoors, check if I can use the socat backdoor
- Try to answer: "does it look like a backdoor?"
How likely is it a human error?
- I've tried reversing the prime to see if the developer made a mistake, but nothing.
- Someone proposed "Swap each 4-byte section or 8-byte section as though someone messed up endian conversion." It turns out that both these cases are not primes.
I won't write an explanation of these attacks here, but they are the reason why a non-prime modulus could be a NOBUS backdoor.
If a backdoor allowing such attacks was generated with a prime modulus, then anyone could reveal the order (by computing modulus - 1) and see if it is smooth by simply factoring it (and then take advantage of the backdoor).
There is a working proof of concept in PoC.sage that implements one way of doing it (I expect more ways to generate backdoored primes)
It creates a non-prime modulus p = p_1 * p_2 with p_i primes, such that
p_i - 1 is 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 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 and such small subgroup attacks are not that 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 (and used to verify that the public key received lies in the correct 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.
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] (i) 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 (ii) The probability that the second-largest prime factor of n is <= x^{0.2117} is about 1/2 (iii) 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).)
let's replace x by (1 << 1024) - 1 = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137215
this gives us:
A new order has been generated, but we know nothing about its order. This doesn't sound good and this section should explain why (from a backdoor point of view) and explain how we can try to reverse it...
The above shows that the new modulus was not generated as p = 2q + 1 (a Sophie Germain prime, also known as safe prime).
EDIT: But wait. Actually it was. When I do /2 it converts the number to a rational whereas is_prime works on integers. It fails silently (which is a bad behavior). So the q is indeed "probably" a prime:
proof.arithmetic(False)
is_prime(q) #-> TrueThe research stops here in this section.