How to backdoor Diffie-Hellman, lessons learned from the Socat non-prime prime posted February 2016

The socat thingy created some interest in my brain and I'm now wondering how to build a NOBUS (Nobody But Us) backdoor inside Diffie-Hellman and how to reverse it if it's not a proper NOBUS.

Ways to do that is to imagine how the DH non-prime modulus could have been generated to allow for a backdoor. For it to be a NOBUS it should not easily be factorable, but for it to allow a Pohlig-Hellman attack it must have a B-smooth order with B small enough for the adversary to compute the discrete log in a subgroup of order B.

I'm currently summing up my research in the open on a github repo: How to backdoor Diffie-Hellman, lessons learned from the Socat non-prime prime. If anyone is interested in any parts of this research (factorizing the modulus, thinking of ways to build the backdoored modulus, ...) please shoot me a message :)

If you go on the github repository you will see an already working proof of concept that explains each of the steps (generation, attack)

This proof of concept underlines one of the ways the malicious committer could have generated the non-prime modulus \(p = p_1 p_2\) with both \(p_i\) primes such that \(p_i - 1\) are smooth. The attack works, but I'm thinking about ways of reversing such a non-prime modulus that would disable the NOBUS property of the backdoor. Spoiler alert: Pollard's p-1 factorization algorithm.

Anyway, if you're interested in contributing to that research, or if you have any comments that could be useful, please shoot me a message =)