2
$\begingroup$

SafeCurves defines criterias for choosing safe curves in elliptic-curve cryptography.

STARK Curve defines a Stark-friendly elliptic curve that can be used with ECDSA.

I was wondering: Is the STARK Curve a SafeCurve?

$\endgroup$
9
  • 1
    $\begingroup$ Not clear that why that $G$ is selected, nothing-up-in-my-sleeve number? $\endgroup$
    – kelalaka
    Jan 14 at 23:17
  • $\begingroup$ Not sure I get what you mean (I'm not an EC expert) - do you mean the specific Generator point used in the ECDSA scheme the STARK Curve web site defines might be specifically selected by Starkware (the authors) so that a hidden/covert backdoor opens in the curve? $\endgroup$
    – oberstet
    Jan 14 at 23:23
  • 1
    $\begingroup$ Yes, that's it. $\endgroup$
    – kelalaka
    Jan 14 at 23:24
  • $\begingroup$ ok, thanks! makes sense, and this is definitely a question I am going to dig down. it is also a question - not the one I asked, but a very good one obviously;) even if the general curve form is safe (if that is possible to say), the specific parameters might not result in a safe concrete curve .. $\endgroup$
    – oberstet
    Jan 14 at 23:28
  • 1
    $\begingroup$ @kelalaka: "What I want to say, the may implemented a massive dlog index and way before anybody"; this is true independent of how they selected $G$; hence having a non-NUMS value doesn't make it any more likely... $\endgroup$
    – poncho
    2 days ago
3
$\begingroup$
The conclusion

The STARK Curve seems a reasonable choice for ECDSA.

The STARK Curve

The STARK Curve defined over $\mathbb{F}_p$ with $p = 2^{251} + 17*2^{192} +1$ with the short Weierstrass equation

$$y^2 = x^3 + A x + B$$

with

  • $A = 1$, and
  • $B = 3141592653589793238462643383279502884197169399375105820974944592307816406665$
Details from the given parameters
  • The order of the curve group ( numbner of points) is $n = \#E(\mathbf{F}_p )$ is $n= 3618502788666131213697322783095070105526743751716087489154079457884512865583$

    And this is a prime number indication that

    • Every element except the identity ( $\mathcal{O})$ can be a generator. The nothing-in-my-sleeve number of this curve (thanks to Aria for pointing), comes from the $\pi$.

      So Starks has Somewhat rigidness at least for now.

      In the end, the nothing-in-my-sleeve number is rather physiological.

    • Co-factor is $h=1$ this means that there is no Montgomery representation of the curve, as a result, there is no fast Montgomery ladder (requires an element of order 2, i.e. 2|co-factor), Joyce ladder is still possible with slower performance. In ECDSA this is helpful in the calculation of $[k]G$ since only $x$ coordinate is used.

    • There is no small group attack to consider, though this is not a problem for legitimate users of ECDSA. If the users are not legitimate then they can use this to double-spend coins as did in Curv25519 however this is not the case for the STARK curve.

    • The curve group is isomorphic to $\mathbb{Z_n}$

  • The $n$ has 252-bit binary representation and this implies it has around $126$-bit security against the best classical discrete logarithm problems.

  • The size of the curve gives no collision of $k$ if a good random number generator is used. If one still fears this one can use deterministic ECDSA given in rfc-6979.

  • Twist security ( not related to ECDSA); the quadratic twist of this curve is $$y^2 = x^3 + 5^2*x +B*5^3$$ *

    • The cardinality of the twist = "618502788666131213697322783095070105623107215331596699973092056135872020481"
    • The factors of the twist group = "499669 * 26023817775804638430931 * 278275836047110893120702478691334736277272165979" and this gives around 158 bit security. Moderate level.
  • And, we have $2*p+2 = Ord(E) + Ord(\text{E_quaratic_twist})$

  • $n \neq p$ therefore it is not an anomalous curve where the discrete log can be solved quickly.

SageMath Code
a = 1
b = 3141592653589793238462643383279502884197169399375105820974944592307816406665
p = 2^251 + 17*2^192 +1

E = EllipticCurve(GF(p), [0,0,0,a,b])

print(E)
Et = E.quadratic_twist()
print(Et)

print("E abelian =", E.abelian_group())
print("E twist a = ", Et.abelian_group())

card = E.cardinality()
cardEt = Et.cardinality()

print("cardinality E       =",card)
print("cardinality E twist =",card)


print("factors E   ",factor(card))
print("factors Et ",factor(cardEt))

#Generator part not for the quadratic twist.
#G = E(874739451078007766457464989774322083649278607533249481151382481072868806602,152666792071518830868575557812948353041420400780739481342941381225525861407)
#n = G.order()
#print("Generator order =", n)

print(log(card,2).n()+1)

assert(2*p+2 == card + cardEt)

*The quadratic twist formed with QNR 5, unfortunately, it did not work as intended. Thanks to Poncho to point out this. I keep the equation so that one can see the problem. Instead, I've used quadratic_twist function of SageMath that quite slow.

$\endgroup$
15
  • $\begingroup$ Fantastic=) Thanks so much for your deep dive analysis of some cryptographic properties of the STARK curve. Not that I really understand the details;) But I guess it checks (some of) the 11 flags for SafeCurves as in the overview table there. Anyways, I tried to dig down choice of G, asked a guy from Starkware: "For the choice of generator, I don’t remember. ... For question you can ask Daira Hopwood from ZCash": electriccoin.co/blog/… github.com/daira $\endgroup$
    – oberstet
    2 days ago
  • 1
    $\begingroup$ 3 from the list is just parameters, the base point is about rigidness, not all related to security. Ladder asks about Montgomery for a constant time, however, Joyce ladder handles this. I'll look for the base point, thanks for pointing. $\endgroup$
    – kelalaka
    2 days ago
  • $\begingroup$ later, I'll look for the others if I can... $\endgroup$
    – kelalaka
    2 days ago
  • 1
    $\begingroup$ @oberstet It cannot be BN curve since $p \equiv 1 \bmod 4$, the BN curves requires that $p \equiv 3 \bmod 4$ $\endgroup$
    – kelalaka
    2 days ago
  • 1
    $\begingroup$ Re "nothing up my sleeve", the generator is the second point in this array, which is generated from the digits of $\pi$. $\endgroup$
    – Ariel
    2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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