5
$\begingroup$

From what I read, the backdoor in Dual_EC_DRBG operates by using related $P$ and $Q$ points.

Did I understand the idea correctly?

Dual_EC_DRBG works by multiplying the $P$ point with the seed initially, and then using the $x$-coordinate of the previous resulting point (let's call that $S$) instead of the seed (that value is named $s$).

The $x$-coordinate of the current point is then multiplied by the $Q$ point, to act as an one-way function and prevent the ability to produce more bits knowing one output value.

Let's call the resulting point $R$. Its $x$-coordinate (called $r$) is then truncated and output.

Does the backdoor work the following way?

Assuming $Q = P \cdot x$ and $R = Q \cdot s = (P \cdot x) \cdot s$

(and that x is known to the adversary)

it should be possible to calculate $S = P \cdot s$, which would allow to continue generating bits since the output:

$$S = R \cdot x^{-1} \pmod n)$$

Is that true?

$\endgroup$
6
$\begingroup$

Not quite, but you're close. I will write $[n]A$ for scalar multiplication of the point $A$ on the curve in question by the scalar $n$, as is more typical notation, and I will write $x(A)$ for the least nonnegative integer representative of the $x$ coordinate of $A$.

Let $E/k$ be an elliptic curve over the field $k$, and $P$ and $Q$ be two $k$-rational points of large prime order.

The initial state is a bit string interpreted as an integer $s_0$. The $i^\mathit{th}$ state $s_i$ and output $r_i$ are given by \begin{align*} s_i &= x([s_{i - 1}]P), \\ r_i &= x([s_i]Q). \end{align*} If $P = [d]Q$ for some integer $d$, then $$s_{i + 1} = x([s_i]P) = x([s_i][d]Q) = x([d][s_i]Q) = x([d] x^{-1}(r_i)),$$ where $x^{-1}(r_i)$ is one of the two possible points with $x$ coordinate $r_i$.

Finding $d$ given $P$ and $Q$ is intractable in a curve for which the ECDLP is hard, but the nation-state adversary influencing cryptography standards could have picked $P$ and $d$ and then computed $Q$ from them.

You, too, can create your own Dual_EC_DRBG back door in the privacy of your own living room! However, you probably can't get FIPS certification if you do that—and if anyone catches you at it outside your living room, you may fall afoul of US Patent 8,396,213 on how to design a key escrow euphemism for a back door. And by design they can't distinguish whether you generated your own $P$ and $Q$ at random or picked $Q$ and $d$ first and then computed $P$ from them for a key escrow system, saving $d$ somewhere secure like a sticky note on your monitor.

So merely using base points other than the standard ones may be a violation of US patent law. (Caveat: I may be a vulture, like many attorneys, but I have not passed the bar, and I am certainly not your patent vulture.)

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Actually, you don't need to be a nation-state adversary to pick $P$ and $d$ and compute $Q$ from them.... $\endgroup$ – poncho Sep 14 '17 at 21:42
  • $\begingroup$ @poncho: I clarified how you and the nation-state adversary and P and Q and Dan Brown's patent are all potentially related. $\endgroup$ – Squeamish Ossifrage Sep 15 '17 at 3:37
  • $\begingroup$ @SqueamishOssifrage - I've conducted some experiments with Dual_EC_DRBG in Sage and the way described in my (edited since your answer) question works. $\endgroup$ – Mark Sep 17 '17 at 14:35
  • $\begingroup$ @Mark: The reason I said ‘not quite’ is that the Dual_EC_DRBG outputs are $x$ coordinates, not the points themselves. What I called $d$ is what you called $x^{-1}$, which is confusing when the coordinate is also called $x$. $\endgroup$ – Squeamish Ossifrage Sep 17 '17 at 15:50
  • 2
    $\begingroup$ @PaulUszak: You'll note I did emphasize that it's a US patent, and that the violation might be of US patent law. The issue is not that there are no non-US programs of note (really? Guess I should tell all my Japanese, Indian, Middle Eastern, African, European, Latin American, Australian, Central Asian, Siberian, and Canadian software engineering colleagues that they've never written anything of note), but that the US is a big rich market that most tech companies don't want to rule out up front. $\endgroup$ – Squeamish Ossifrage Sep 17 '17 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.