7
$\begingroup$

As we all know for discussion of Dual_EC_DBRG, the point on an elliptic curve Q can be calculated from P and some (large) integer d

$Q = dP$

And we know that knowledge of Q and P is not sufficient to be able to compute d efficiently.

My understanding

I've been hoping to explain why, and I believe that they answer is that when computing dP, one doesn't have to perform d - 1 additions, but instead can make use of the fact that you can calculate $\{2P, 4P, 8P, \dots, mP\}$ where m is the smallest power of 2 greater than or equal to $d/2$. That set of points can be calculated with $\left\lceil\log_2 d\right\rceil -1$ additions. And then to compute $dP$ we will need an addition for every 1-bit in d.

So in worst case, computing $dP$ requires $2\log_2 d$ additions. But this short cut is not available for computing d from P and Q, and so the number of additions (subtractions) is closer to d itself.

Is this close to being a useful understanding?

$\endgroup$
  • 1
    $\begingroup$ Are you trying to understand how the Dual_EC_DRBG backdoor works? I could add some ref to my answer or try to explain a little more.. $\endgroup$ – ddddavidee Dec 28 '15 at 10:07
9
$\begingroup$

Computing $d$ given $P$ and $Q$, with $Q = dP$ is known as the "elliptic curve discrete logarithm problem" and is considered to be infeasible under some hypothesis. The security of Elliptic Curves Cryptography is based exactly on the ability to compute the point multiplication and the intractability of the inverse operation: given two points find out the discrete operand $d$. The difficulty of the problem is given by the size of the elliptic curves.

One (of the best) algorithm to compute the discrete logarithm, Silver–Pohlig–Hellman algorithm, has complexity $O(\sqrt n)$ where $n$ is the order of the elliptic curve, but it is very efficient in the case of $n$ smooth (product of small integer). This is also the reason you don't want to have a curve with a smooth number as order.

The first part of your question shows a standard way to compute the point multiplication using the binary expansion of the multiplicand. It is usually known as "double and add" and corresponds to the "square and multiply algorithm".

If you're trying to understand how the backdoor in the Dual_EC_DRBG works you should read this answer to the question Explaining weakness of Dual EC DRBG to wider audience?. Roughly the $P$ and $Q$ used in the standard are generated in an unknown way. So, if NSA knows the $d$ scalar such that $Q = dP$ they can compute some values and synchronize with the generator. If you implement the same algorithm using two (provable) random points, the backdoor disappears. Usually a provable way to generate a point is to hash some not random english strings (as the US Constitution or the Shakespear's work or the Star Wars The Force Awakens original script, or ...) and use this output to generate the point.

$\endgroup$
  • $\begingroup$ Thank you very much. I am aiming to write a description of one aspect of the Dual EC backdoor, and am focusing on the contrast between the two Juniper backdoors. With the authentication one, once it was discovered that everyone has that "back door key", but with the Dual EC one, only the creator of the new Q has the key, even though P and Q are known. $\endgroup$ – Jeffrey Goldberg Dec 28 '15 at 15:36
  • 1
    $\begingroup$ I suggest to read this blog post too blog.cryptographyengineering.com/2015/12/… $\endgroup$ – ddddavidee Dec 28 '15 at 15:42
  • 1
    $\begingroup$ Matthew Green is a major source for me on all things Dual_EC. (Despite the fact that I've lost count of the number of times he's written "this will be the last thing I write about Dual_EC_DBRG". $\endgroup$ – Jeffrey Goldberg Dec 28 '15 at 19:18
6
$\begingroup$

And we know that knowing of $Q$ and $P$ is sufficient to be able to compute $d$ efficiently.

I think you meant "knowing $P$ and $d$ we can compute $Q$ efficiently. That's the DLP as stated in your previous answer.

I think it's more intuitive to work in $\mathbb{Z}_p^*$ and in this group you might reframe the DLP question as this: "given some generator $g$ for the group $\mathbb{Z}_p^*$, what's the difference between computing $g^d$ for some known $d$ as opposed to just computing $g^k$ for each $k \in \{1, \ldots, p-1\}$?"

In terms of complexity we measure operations in terms of bits of input required. It turns out we have a good algorithm for exponentiation called exponentiation by squaring. The cost of calculating the exponent is explained on that page - in essence, to compute $x^n$ we need $\log_2 n$ square operations and $O(\log_2 n)$ multiplications - that is, at most $\log_2 n$ operations on bits. Considering that squaring approximately doubles digits and considering multiplication to cost $O(d^k)$ operations for some constant $k$ the page comes up with a bound. The complexity they give is:

$$O((n\log_2(x))^{k})$$

i.e. polynomial in terms of bits.

A naive way to solve the DLP is to compute $g^k$ for each $k \in \{2, \ldots, p-1\}$. For this we simply need repeated multiplications modulo $p$ as we can hold the last value. As before, the cost is $O(d^k)$ for two $d$-digit numbers. In terms of bits, the order of the group is $b=\log_2(p)$. Then we need $O(2^b b^k)$ multiplications, in terms of bits, assuming all integers take $b$ bits and are prefixed with zero.

Another way to think of this is that the maximum space required to represent a prime $p$ is $b$ bits and our algorithm must touch each element in this space - $2^b$ elements.

There are of course some important caveats to this - there are better algorithms than trial multiplication and depending on the group they might be fatal for crypto purposes. But essentially that's it.

This is expanded upon in the answers to "Why is the discrete logarithm problem assumed to be hard?" (not by me).

The double and add method follows the same principle - the cost in bits of an operation for a known coefficient $d$ can be expressed in some polynomial form, while evaluating every possible multiple of the generator (and thus the entire group) is significantly more costly as the size of the group increases such that no polynomial time algorithm is known. In EC, we tend to operate over a cyclic subgroup of the group of points under point addition such that every point is a generator.


Additional extras you didn't ask for but since your previous answer mentioned it :) Let's go back to the $\mathbb{Z}_*^p$ group for this. A number is $B$-smooth if it can be completely factored into primes less than a given $B$. For example the order of $\mathbb{Z}_{181}^*$ is $180 = 2^2 \cdot 3^2 \cdot 5$ and this is say 7-Smooth. We can use this property to use the index calculus algorithm to (more) efficiently (than brute force) compute the DLP. Or as your first answer mentions, any other algorithm relying on this property.

We defend against this by choosing a "safe prime" or a strong prime i.e. one such that $2p+1$ where $p$ is prime. This means the order of such a group is $2p$ and as such there is a large prime order subgroup order $p$ (group contains subgroups of order factors of the order of the group by lagrange).

There is a very important difference between the group of points on an elliptic curve and the multiplicative group of integers modulo $p$ - there is a corresponding integer ring in which unique factorisation into primes holds. We have no such equivalent in elliptic curve group. See this question: Trying to better understand the failure of the Index Calculus for ECDLP Consequently our groups need not be as large (we no longer need a large prime order subgroup).

As a further aside, an excellent article on Dual_EC_DRBG is this proof of concept which works with C/OpenSSL. Maths included.

$\endgroup$
  • $\begingroup$ Thank you very much. Yes, there was a "not" missing from my original statement (now corrected). Oddly enough, I find I have stronger (better?) intuitions GDLP on elliptic curves than on $\mathbb{Z}_p$. I think it is because with elements of $\mathbb{Z}_p$ I can't help think of it a well-ordered. I get confused and misled by the similarity to ordinary arithmetic. But addition on ECs forces me to think about the Group properties in a more distilled form. I was at Usenix Security where that PoC was presented. Here I'm focusing on the GDLP on ECs, instead of the how to use the back door. $\endgroup$ – Jeffrey Goldberg Dec 28 '15 at 19:54
  • $\begingroup$ @JeffreyGoldberg no worries, I figured as much as the rest of your Q seemed to assume this. I agree, the similarity can definitely trip you up, I just find it easier to produce examples in this form. $\endgroup$ – diagprov Dec 28 '15 at 20:19
  • $\begingroup$ Another reason for sticking with EC when trying to explain the GDLP to a lay audience is that I can ignore multiplication. (Indeed, I'm forced to.) And by showing point addition on a curve over the reals, I can draw pictures instead of writing lots of algebraic expressions. $\endgroup$ – Jeffrey Goldberg Dec 28 '15 at 22:54
2
$\begingroup$

For computing $Q=dP$ we have a "NAF" methods that are more faster than logarithmic methods. Fore more detail you can see "guide to elliptic curve". Also for computing $d$ from $Q=dP$, the method that commonly use is pollard-rho method. This method is based on birthday paradox attack and be-able to solve discrete logarithm in $O(\sqrt p)$ which $p$ is a biggest divisor of order of elliptic curve. For practical use of this method you can use of MAGMA computational Algebra system which is the powerful program of pure math especially in elliptic curves. This program be-able to find $d$ in a second time for the order $1-80$ bit.

$\endgroup$
  • $\begingroup$ In his answer, @dddavidee pointed to the Silver-Pohlig-Hellman algorithm for computing the discrete log instead of Pollard's rho. Now you said that Pollard's rho is "commonly used" while ddddavidee said "One (of the best) ... S-P-H algorithm". Both appear to offer a worst case of $\mathop{O}(\sqrt{n})$, so I'm guessing that there are just a lot of finicky details involved in choosing among them. Is that largely correct? $\endgroup$ – Jeffrey Goldberg Dec 28 '15 at 23:12
  • 1
    $\begingroup$ Pollard's rho attack is a probabilistic method that be-able to find $d$ with probability greater than $1/2$. In Pohlig-Hellman algorithm we convert one discrete log problem to other discrete log problem.I think that in the program such as the MAGMA at first Pohlig-Hellman method check and if this attack unable to find $d$ then program use of parallelized Pollard's rho attack. For more detail you can see documentation of MAGMA or "handbook of elliptic and hyper elliptic curves". $\endgroup$ – Meysam Ghahramani Dec 28 '15 at 23:32

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.