Hide a weakness in ECC by choosing the prime or one of the curve coefficients

Question

Suppose you are given a value $c$. Can you find a prime $p$ and an integer $b$ such that the elliptic curve

$$E: y^2 \equiv x^3 -3x + b \pmod p$$

is cryptographically weak? You need to choose $p,b$ so that all of the following restrictions also hold:

1. $p$ has some desired size (say, 256 bits)

2. $1 < b < p$ and $1 < c < p$

3. $b^2 c \equiv -27 \pmod p$

4. the order $n$ of the curve is a prime number

By cryptographically weak, I mean that the discrete log problem is easy on the curve (or that some other standard cryptographic assumption is false).

Is there any known way to do this? Is there a procedure to find $p,b$ (as a function of $c$) satisfying all these conditions, where the procedure succeeds with non-negligible probability (say, probability $\ge 1/10^{12}$)? Or, is there a proof or heuristic argument that doing so is likely to be impossible?

Basically, this amounts to asking whether there's any way to ensure that the resulting elliptic curve has a non-trivial probability of being cryptographically weak, given ability to choose some (but not all) of the curve parameters.

(For instance, maybe you could choose $b$ however you like, factor $b^2c+27$, select an appropriate divisor as $p$, and hope that the resulting curve is vulnerable to some particular attack; or who knows what. Your choice of strategy.)

Motivation: If this problem has a solution, then it means that the NSA could have hidden a backdoor in the NIST-recommended elliptic curves (specifically, the P-xxx curves). Thus, it has implications for how much trust we can put in the those standard curves.

Answer 1

Bernstein and Lange says that there has been no progress for prime-field elliptic curves since about 1999, when the NIST curves were chosen. No large class of weak curves were known then, and no large class is known now.

Some small classes are known, (as Neves says) the curves with small embedding degree and the anomalous curves (order $n$ equals the prime $p$), but all of these were known back then (though not all of them by everyone in 1985, the MOV attack was a real attack, and the anomalous curves were an attempt to block the MOV attack, I think). So these classes are hard to hit at random, and are easily detected anyway.

The problem of embedding trapdoors in elliptic curves has been studied by Edlyn Teske, but she uses curves over extension fields, not prime fields. (Her techniques rely on it being hard to find isogenies between curves, but it is possible to find curves with isogenies. You choose one curve over an extension field that is secure, another that is not secure, and an isogeny between them. The isogeny is the trapdoor and allows you to move the DLOG instance from one curve to the other. The extension field attacks this relies on do not apply to NIST's extension field curves, as far as I know.)