Here's a description of page 182 of "Guide to Elliptic Curve Cryptography" by Hankerson, Menezes and Vanstone. Here's a quote from that page:
The main observation in invalid-curve attacks is that the usual formulae for adding points on an elliptic curve $E$ defined over $\mathbb F_q$ do not involve the coefficient $b$ (see §3.1.2). Thus, if $E'$ is any elliptic curve defined over $\mathbb F_q$ whose reduced Weierstrass equation differs from $E$’s only in the coefficient $b$, then the addition laws for $E'$ and $E$ are the same. Such an elliptic curve $E'$ is called an invalid curve relative to $E$.
Suppose now that $A$ does not perform public key validation on points it receives in the one-pass ECDH protocol. The attacker $B$ selects an invalid curve $E'$ such that $E'(\mathbb F_q)$ contains a point $R$ of small order $l$, and sends $R$ to $A$. $A$ computes $K=dR$ and $k = KDF(R)$. As with the small subgroup attack, when $A$ sends $B$ a message $m$ and its tag $t=MAC_k(m)$, $B$ can determine $d_l = d \bmod l$. By repeating the attack with points $R$ (on perhaps different invalid curves) of relatively prime orders, $B$ can eventually recover $d$.
I am having a problem understanding one aspect of invalid-curve attacks: given some curve $E$, how does one finds an invalid curve $E'$ ($E$ and $E'$ have same parameters except for coefficient $b$) and a small-order point $R$ on $E'(\mathbb F_q)$? Is there an efficient algorithm for finding curves with small order points?
I would appreciate an example showing how to find such a curve $E'$ and a point $R$ for some "popular" $E$ (e.g. one of the NIST curves).