6
$\begingroup$

I would like to implement a protocol using elliptic curves. I'm thinking of using MIRACL so using curves in their Weierstrass form is preferable as it they are supported by this framework.

I don't want to start picking random curves, so I am looking at the available safe curves. None of the curves is in Weierstrass form however. Do you have any suggestions for such curves? Even curves with low security, such as 80 bit curves are welcome.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ You can use Curve25519 as per this answer. $\endgroup$
    – SEJPM
    Sep 26, 2015 at 17:06
  • $\begingroup$ Thanks for this. I also found this post which is very useful $\endgroup$
    – absinthe_minded
    Sep 26, 2015 at 19:45
  • 1
    $\begingroup$ Most of the advantages of safe curves only apply if you use Mongomery or (twisted) Edwards form for computation. Or do you just want to use Weierstrass form for easy prototyping with MIRACL and then switch to another form for production use? $\endgroup$
    – CodesInChaos
    Sep 28, 2015 at 14:50
  • $\begingroup$ At the current stage I want to use them for a prototype and say that I use this curves which are known as secure even if they do not perform as they are expected to. It's more like a proof of concept. Indeed, using the original form of these curves would give me a significant performance boost, but this will be done at a later stage, if so. $\endgroup$
    – absinthe_minded
    Sep 30, 2015 at 8:44

3 Answers 3

Reset to default
2
$\begingroup$

Bernstein and Lange regard any curve in Weierstraß form as "not safe" because they assume, implementers of ECC with these curves will make stupid mistakes. You can see a more detailed discussion on this point here:Safety of ECC-point addition.

So you should pick a subset of their criteria if you want the Weierstraß form(I don't see any reason not to). IMHO the most important criterion is that their creation was "stiff" i.e. there was no unexplained way to fill degrees of freedom in the creation process. The NIST curves do not fullfill this criterion. They somehow fell from heaven and the community is suspicious. You might use the "stiffly" created ECC-brainpool elliptic curves(up to 512 bit), or my stiffly created curves ECC-curves_anders (up to 1024 bit).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 'Rigid' is the word they use. $\endgroup$
    – otus
    Oct 2, 2015 at 10:20
0
$\begingroup$

I am not clear about the categorisation of safe and non-safe curves on this site.

But the "unsafe" curves of Nist, Brainpool and Certicom are used in electronic passports , the new german id card , etc.

So, I would simply stick to that curves and forget the fancy "safe" curves.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I wouldn't say fancy Curve25519 as it is being standardized. However, the arguments that the site has are not unfair (see here. $\endgroup$
    – absinthe_minded
    Sep 26, 2015 at 21:28
  • 3
    $\begingroup$ Well, calling them "the" safe curves is a bit of an exaggeration. So maybe stick to something more neutral such as "the Bernstein curves". $\endgroup$
    – Circonflexe
    Oct 29, 2015 at 18:40
  • $\begingroup$ @Circonflexe What do you think about twist insecurity for Brainpool curves that DJB has mentioned here: safecurves.cr.yp.to/twist.html. How big this threat is in your view? $\endgroup$
    – Oleg Gryb
    Nov 1, 2015 at 17:43
0
$\begingroup$

Nobody including DJB has proved that Brainpool curves are not safe. The only relative weakness that has been mentioned in the safe curves wiki was related to twist security, which includes according to this wiki things like "invalid curves", but those are more implementations issues than something attributed to a curve's properties, e.g. if you always validate point-on-curve condition in your protocol, "invalid curve" attack won't be possible.

Unlike in NIST case, Brainpool's constant generation method is clearly defined and doesn't leave any room for manipulations. In NIST case a method of a seed generation has never been disclosed, which has made some people (including me) nervous after DUAL_EC_DRBG exploit had been disclosed.

The disadvantage of Brainpool curves compare to the NIST ones is that the former couldn't be optimized, which makes them about two times slower than the optimized implementation of NIST's curves, but peace of mind is more important than optimization here.

In regard of DJB's "safe curves", an apparent disadvantage is that a group of researchers that work with them is smaller than that for more traditional curves defined by the short Weierstrass equation. It means that declared "safety" might not live too long as more researchers start looking at them in details.

Bottom line, you should be perfectly safe with Brainpool curves and they are in the short Weierstrass form, which is what you're looking for.

UPDATE

Check this one as well. It's related to "safe"/"not safe" discussion. A timing attack on Curve25519 is described there. It's based on a flaw in a EC point multiplication implementation, so the curve creators could say that it's an implementation problem. At the same time, they claim that other curves are not safe because it's very difficult to implement them right. Well, judging from the provided link implementing Curve25519 right is not easy either :)

Improve this answer
$\endgroup$
6
  • $\begingroup$ The point of the SafeCurves criteria is to highlight design decisions that encourage vulnerable protocols and implementations. It's true that you can thwart invalid-curve attacks on protocols using Brainpool curves by paying additional cost—in computation and in engineering complexity—for point validation, but you can safely use Curve25519 in faster and simpler protocols that don't need the point validation. $\endgroup$
    – Squeamish Ossifrage
    May 26, 2018 at 0:04
  • $\begingroup$ The Montgomery form of Curve25519 enables faster and simpler x-restricted scalar multiplication than curves with no Montgomery form for which implementors are confronted with a choice of (a) fast variable-time arithmetic with branches and incomplete addition formulas, or (b) slow constant-time arithmetic with branch elimination or the Brier–Joye ladder. Whatever form, you need to compute multiplication in the coordinate field, and it is well-known that fast integer multiplication is a possible source of leaks—but that's common to all prime curves, so it's not a criterion to discriminate on. $\endgroup$
    – Squeamish Ossifrage
    May 26, 2018 at 0:11
  • $\begingroup$ No, design decisions don't encourage anything here. Implementors always have a choice to do or not to do things like "point on curve validation" (e.g. OpenSSL does). At the same time, when implementors chose to use common EC arithmetics, which is prone to timing attacks, curves that are claimed to be safe, become vulnerable as well. Faster and simpler - maybe. Safer they are not, and rsearchers should really stop claiming that. $\endgroup$
    – Oleg Gryb
    May 27, 2018 at 0:25
  • $\begingroup$ Here is one example in regard of "faster" vs. "safer". There is optimized arithmetics available for NIST P256, which can be enabled by re-compiling OpenSSL with a special flag. In my experiments the optimization made it almost 50% faster. However, since it has never been explained how a seed for a co-efficient 'b' has been generated, "verified random" criteria is not met, and that's why my choice would be a Brainpool curve. This is where safety really kicks in: speed vs. a possibility of "first person attack". What you chose depends on your mindset, risk profile and risk tolerance. $\endgroup$
    – Oleg Gryb
    May 27, 2018 at 0:51
  • $\begingroup$ You can botch protocol design and implementation with any curve. Each curve failing a SafeCurves criterion is harder or_slower_ to use safely in protocol design and implementation than a curve that passes, all else being equal. Optimized NIST P-256 arithmetic vs. unoptimized NIST P-256 is beside the point. Fast and secure Montgomery ladder, vs. a choice of fast or secure short Weierstrass arithmetic, is what's relevant. Simple and secure validation-free x-restricted DH with twist security, vs. simple or secure without twist security. $\endgroup$
    – Squeamish Ossifrage
    May 27, 2018 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.