Do we always choose a generator of prime order for ECDH? If yes, then why?

Question

I am looking at the description of Weil MOV Attack from the Vanstone, Menezes Book (Guide to Elliptic Curve Cryptograpy)

Suppose now that the prime order $n$ of $P \in E(F_q)$ satisfies $gcd(n,q) = 1$. Let $k$ be the smallest positive integer such that $q^k \equiv 1 \pmod n$, the integer $k$ is the multiplicative order of $q$ modulo $n$ and therefore is a divisor of $n − 1$. Since $n$ divides $q^k − 1$, the multiplicative group ${F^\star}_{q^k}$ of the extension field $F_{q^k}$ has a unique subgroup $G$ of order $n$. The Weil pairing attack constructs an isomorphism from $\langle P \rangle$ to $G$ when the additional constraint $n \nmid (q − 1)$ is satisfied

So the $MOV$ attack would work only if the $ECDH$ problem is of the kind $nG = R$ with $G$ a point of prime order. So for $ECDH$, do we always chose a generator of prime order. If so, why?

So there seems to be 4 conditions which need to be satisfied for the MOV attack to work

• Prime order of Generator.
• The order of the generator is coprime to the order of the Field
• The order of the genarator does not divide $(q − 1)$
• Small embedding degree

So even if you do have a small embedding degree what would be probability that the $MOV$ attack would be applicable. A lot of different conditions need to be satisfied - i.e. you could choose a small embedding degree as long as one of the other conditions aren't satisfied.

Answer 1

In broad generality we can solve the discrete logarithm $nG=R$ problem for a point of order $m$ by solving for $n\pmod q$ for every prime power that divides $m$ and combining them with the Chinese remainder theorem.

Generically we can solve the component discrete logarithm problem modulo $q=p^t$ with $O(tp^{1/2})$ work using methods such as Pollard's kangaroo.

However for especially badly chosen primes where one of the primes dividing $n$ divides the underlying field characteristics (so that the Smart/Semaev anomalous curve attack applies), or where there is a small embedding degree for that prime (so that the MOV attack applies), the value $n\pmod q$ can be recovered in work sub exponential in $p$. This applies whether $q=n$ or whether there is a cofactor.

The small embedding degree would always make this component of the discrete logarithm very easy to recover so that the hardness of the overall discrete logarithm is dependent on the other primes. At this point one might as well simply work outside the subgroup generated by the prime power with small embedding degree.

The choice to use a generator of prime order is one of efficiency. For, say, 128-bits of security while not leaking any information about $n$, we would want every prime factor of the order of the generator to be 256-bits in size and neither anomalous nor of low embedding degree. We could do this with a case where the order of the generator is the product of two 256-bit primes, but then we would need an underlying field of at least 512-bits and be passing around similarly sized coordinates as public keys. By only using one prime we can work with the smallest possible underlying field while having the appropriate level of security.