Constructing the Dual EC backdoor

Unless you've been living under the rock for the past couple of weeks then you've probably heard of the Dual EC backdoor in Juniper devices. Matthew Green wrote an awesome blog post, and Checkoway et al gave a nice update on the backdoor at Real World Crypto 2016. If you haven't read these links please do now, I'll wait.

The backdoor is the knowledge of $d$ such that $dQ$ = $P$, where $P$ and $Q$ are the two constants in Dual EC. Someone asked me how NSA can find such a $d$, and it took me a while to figure it out so I thought I'd share with you all.

Note that $P$ is not a random point, but it's the standard generator defined for the P-256 curve. That means unless NSA had been planning for the Dual EC backdoor since the 1990s when the P-256 curve was defined, they couldn't just take a random $Q$, and multiply it with a random $d$ to obtain $P$.

What NSA might have done was to generate a random $d$, then use the extended Euclidean algorithm to find $e$ such that $de \equiv 1 \pmod{n}$ where $n$ is the number of points on the P-256 curve (also known as the order of the curve). Such an $e$ always exists, because $n$ is a prime number. Then $Q = eP$ satisfying $dQ = deP = P$. Quan Nguyen showed me that the same trick can be used to figure out $P$, given $n$ and $nP$ (which I thought was a much difficult problem).

The extended Euclidean algorithm together with the Chinese Remainder Theorem are the two most powerful cryptanalysis tools ever. I've seen countless systems broken because the designers weren't aware of these algorithms. Whenever analyzing or designing a new system, ask yourself if you can break it using these simple tricks, and you'll be surprised that most of the times the answer is yes.

By the way here's my (conspiracy) theory of what happened to Juniper. In 2008 for whatever reason Juniper decided to use Dual EC. Perhaps they wanted to get certified so that they could sell to the US government. They did their homework, found the alleged backdoor, which was discovered in 2007. They decided to replace the default $Q$ with their home-brew value. I think the bug in the PRNG and the increasing of nonces to 32 bytes were honest mistakes. If these changes were unauthorized, Juniper would have counted them as another backdoor, but they didn't. Fast forward to 2012, NSA wanted to hack someone which uses some Juniper device. They were furious that Juniper wasn't using their default $Q$, and decided to hack Juniper to change $Q$. They didn't want to use the default $Q$, because they knew the backdoor would be discovered eventually, and using said value would be a smoking gun confirming that NSA was the perpetrator and the alleged backdoor in Dual EC is real.