david wong

Hey! I'm David, cofounder of zkSecurity and the author of the Real-World Cryptography book. I was previously a crypto architect at O(1) Labs (working on the Mina cryptocurrency), before that I was the security lead for Diem (formerly Libra) at Novi (Facebook), and a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.

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:

prime backdoor

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.

CM-HSO

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

Well done! You've reached the end of my post. Now you can leave a comment or read something else.

Comments

OAlienO

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?

david

it is large, but in the realm of what's do-able for a normal consumer

OAlienO

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...