david wong

Hey ! I'm David, a security consultant at Cryptography Services, the crypto team of NCC Group . This is my blog about cryptography and security and other related topics that I find interesting.

How to backdoor Diffie-Hellman, lessons learned from the Socat non-prime prime 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)

attack

attack 2

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 =)

Well done! You've reached the end of my post. Now you can leave me a comment :)