Re: [Cfrg] Bad and Rigid Curve (Rigid << NUMS)

Resending, because I received a version from CFRG with an empty text.

Let p=2^127-1.
Define a curve by y^2 = x^3 + x.
Note that this is a Montgomery curve over a Mersenne prime.
There appears to be little room for manipulation, so it seems rigid.
I presume this curve is quite speedy and side-channel resistant because of its similarity to Curve25519.

Now let's imagine being back at a time before the Pollard rho [P], Pohlig-Hellman [PH], and Menezes-Okamoto-Vanstone [MOV] attacks were published.  These attacks were eventually discovered, so it is quite possible that our adversary discovers them before we do.  Perhaps the adversary is also the one proposing these curves to us, saying "Don't worry, you don't have to trust us, this curve is rigid, and we could not have manipulated it."

The purpose of this convoluted back-in-time exercise is to provide model of today's value of rigidity against possible secret attacks.

Since we do not yet know about [P], we would think that exhaustive search is the best attack, and think that solving the DLP in this curve requires about 2^128 operations.  But:

If our adversary knows the [P] attack, then s/he can solve the DLP in 2^64 steps.
If our adversary knows the [MOV] attack, then s/he can use pairings and map this DLP into the field GF(p^2), and use an index calculus, which to be considerably faster than 2^128 steps.
If our adversary knows the [PH] attack, then s/he can exploit the curve order 2^128, and solve the DLP in something like 128 group operations. 

Aside: the reason that the [MOV] and [PH] attacks work with this curve is because it is supersingular due to a theorem p = 3 mod 4, which implies the curve has order p+1 = 2^128.  Actually, it's elementary to verify the order by noting that if nonzero x admits a y solution, then -x does not, because -1 is a quadratic non-residue mod p, which shows that the order is p+1: the point at infinity, the point (0,0), and a two points (x,y), (x,-y) for each of the (p-1)/2 sets of the form {x,-x}.

To find this curve, I relied on half-remembering the relevant number-theoretic results, and then used Wikipedia (and Menezes's thesis and Silverman's text) to remind me about the details of the theorem above, whose details I had forgotten.  In other words, I did not run any computations, and instead relied upon a basic knowledge base.  So, it would have been super-easy for an adversary to find this curve, and quite natural for a benevolent person not knowing the three attacks and seeking a rigid curve to propose this particular curve.  I presume somebody with a better understanding of EC theory using and better computational tools could find more sophisticated bad and rigid curves.

Anyway, the rigidity of this curve would not have helped prevent any of three major attacks on the DLP.    (Sorry: I did not also arrange the SASS attack, but it seems incompatible with the MOV attack.)

My interpretation of this bad and rigid curve is that rigidity does not buy us the NUMS property (or whatever better name you want). So, we should not overestimate the value of rigidity.  Rather, we should be placing much more emphasis on the maturity of cryptanalysis.  More precisely, I think rigidity helps only to the extent that secret attacks require the adversary to use trial-and-error curve selection, but trial-and-error attacks are not the only kind of attacks possible.

Now some comparisons to other curve selections:

If we honestly self-selected a random curve (or pseudorandom curve with a rigid seed) in the sense of y^2 = x^3 + Rx + x, where R is some rigid random value, we would have resisted the [MOV] with high probability, fared slightly better against [PH], but not any better against [P].  So, randomness has provided extra protection against a sparse attack, but we still have needed to rely on good cryptanalysis to resist dense attacks like [P] and [PH].

If we had honestly selected a different rigid curve such as the curves defined by y^2 = x^3 + 1 or y^2 = x^3 + x^2 + x (though minutely less rigid) then I expect we would fared just as well as the random curve above.  Enthusiasts might try counting the points on these curves to see if they resist [PH] better than a random curve.  If so, I argue heuristically, that would have just been a fluke, not a basis for recommending special curves.  This also shows how minute differences in rigidity can make or break the curve.

If the adversary was selecting the curve and only knew about the [MOV] attack, then the adversary would presumably suggest y^2 = x^3 + x and not y^2 = x^3 + x^2 + x (unless the latter is also supersingular). In particular, the adversary could have something up his/her sleeve, the [P], [PH], or [MOV] attack, when proposing a rigid curve. So, as I said above, rigidity is definitely less than nothing-up-my-sleeve (NUMS).

If the adversary was also selecting the curve but using the pseudorandom method (with a free seed like P256) and knew about the [MOV] attack, s/he would have a harder time searching for a random R to make [MOV] work.  This seems hard to me: I don't know how to find R, or even R exists, unless R is common.   My current understanding is that about p/12 values of R should exist but that these R could belong GF(p^2) instead of GF(p). This suggests that there's a heuristic that 1/12 chance of an R existing in GF(p).  Even after finding R, how does one find a pre-image of one's pseudorandom function?  If the seed to the pseudorandom function could be made sufficiently rigid, then it should be even harder.

I agree that rigidity's value of thwarting trial-and-error search seems very appealing because of the potential trial-and-error attack on P256.  But just because it would stop a possible P256 attack, it won't stop all NUMS attacks on special curves. So, overall, I would recommend combining rigidity with some form of pseudorandomness, since pseudorandomness seems to force the adversary to use trial-and-error (in the space over which pseudorandom function is applied).

Best regards,

--Dan

> -----Original Message-----
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Dan Brown
> Sent: Thursday, August 07, 2014 1:32 PM
> To: cfrg@irtf.org
> Subject: [Cfrg] Bad and Rigid Curve (Rigid << NUMS)
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg