How to Backdoor Diffie-Hellman: quick explanation posted August 2016
I've noticed that since I published the How to Backdoor Diffie-Hellman paper I did not post any explanations on this blog. I just gave a presentation at Defcon 24 and the recording should be online in a few months. In the mean time, let me try with a dumbed-down explanation of the outlines of the paper:
I found many ways to implement a backdoor, some are Nobody-But-Us (NOBUS) backdoors, while some are not (I also give some numbers of "security" for the NOBUS ones in the paper).
The idea is to look at a natural way of injecting a backdoor into DH with Pohlig-Hellman:
Here the modulus \(p\) is prime, so we can naturally compute the number of public keys (elements) in our group: \(p-1\). By factoring this number you can also get the possible subgroups. If you have enough small subgroups \(p_i\) then you can use the Chinese Remainder Theorem to stitch together the many partial private keys you found into the real private key.
The problem here is that, if you can do Pohlig-Hellman, it means that the subgroups \(p_i\) are small enough for anyone to find them by factoring \(p-1\).
The next idea is to hide these small subgroups so that only us can use this Pohlig-Hellman attack.
Here the prime \(n\) is not so much a prime anymore. We instead use a RSA modulus \(n = p \times q\). Since \(n\) is not a prime anymore, to compute the number of possible public keys in our new DH group, we need to compute \((p-1)(q-1)\) (the number of elements co-prime to \(n\)). This is a bit tricky and only us, with the knowledge of \(p\) and \(q\) should be able to compute that. This way, under the assumptions of RSA, we know that no-one will be able to factor the number of elements (\((p-1)(q-1)\)) to find out what subgroups there are. And now our small subgroups are well hidden for us, and only us, to perform Pohlig-Hellman.
There is of course more to it. Read the paper :)
In your paper section 5, you mention that
'As with our previous method, we could use much larger factors of around 100 bits to avoid any powerful adversaries and have a agreeable 2^51 computations on average to solve the discrete logarithm problem in these large subgroup'
My understanding of this paragraph is that setting p_big, q_big to 100 bits primes to defense Pollard's p - 1 Algorithm, and using Pollard's Rho Algorithm gives us about 2^51 computations which is agreeable.
But 2^51 = 10^16 computations are kind of large, aren't it?
it is large, but in the realm of what's do-able for a normal consumer
Ok, thanks for replying.
Not familiar with how fast computers can run XD
I only know that my computer can run about 10^8 computations a second.
But I got the idea.
Because Pollard's p - 1 has complexity roughly O(B), and Pohlig Hellman has complexity O(sqrt(B)), which is much faster.
When the number is big, Pollard's p - 1 is hard to do but do-able, and Pohlig Hellman is a piece of cake.
When the number is huge, Pohlig Hellman is hard to do but do-able, and Pollard's p - 1 will be impossible.
leave a comment...