Score:2

Is the STARK Curve a SafeCurve?

in flag

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?

kelalaka avatar
in flag
Not clear that why that $G$ is selected, nothing-up-in-my-sleeve number?
oberstet avatar
in flag
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?
kelalaka avatar
in flag
Yes, that's it.
oberstet avatar
in flag
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 ..
poncho avatar
my flag
@kelalaka: actually, it's provable that specific $G$ is as strong as any other generator in that curve.
kelalaka avatar
in flag
@poncho strong in the sense of who? Maybe the creator generated a log table as much as possible for themself and still going. Well, when considering the size of the curve, their advantage will not more than negligible, however, it is still considered that one should give the reason as pointed on the (overhyped?) safetycurves. Why not the first $x$ as in Curve25519? In the end, We know that the nothing-up-in-my sleeve number is physiological .
poncho avatar
my flag
@kelalaka: in the strong sense that, if you can solve the DLog (or CDH) problem with that specific $G$, you can solve the DLog (or CDH) problem with any generator. This is in contrast to (say) the EC equation itself; maybe they had a specific weakness with $A=1$ curves in mind? Probable: no; on the other hand, we don't have any proof.
kelalaka avatar
in flag
@poncho yes, I know that we can convert any dlog base to another base to solve there. What I want to say, the may implemented a massive dlog index and way before anybody, then even this case, their advantage is negligible against the other attackers. Yes, for $A=1$, we don't know. This and other reason to consider this curve _somewhat rigid_ Small $A$ can reduces some computation, that all I know. Thanks, again.
poncho avatar
my flag
@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...
Score:3
in flag
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.

oberstet avatar
in flag
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": https://electriccoin.co/blog/people-behind-zcash-technology-daira-hopwood-engineer-and-protocol-designer/ https://github.com/daira
kelalaka avatar
in flag
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.
kelalaka avatar
in flag
later, I'll look for the others if I can...
oberstet avatar
in flag
fwiw, here are some more fragments of my digging: I _think_ the family of curves is called "Barreto-Naehrig (BN)" https://eprint.iacr.org/2010/429.pdf. I could not find the specific parameters of the STARK curve in https://neuromancer.sk/std/bn / https://tools.ietf.org/id/draft-kasamatsu-bncurves-01.html. zCash (a different project from Starkware), which the Starkware guys hinted at, historically used BN254, but switched to BLS12-381 in 2017 https://github.com/zcash/zcash/issues/2502 https://cp4space.hatsya.com/2020/12/27/barreto-naehrig-curves-and-cryptographic-pairings/
poncho avatar
my flag
"The twist ... has the same cardinality implies the same security"; is the order a twist a prime? If not, that implies that the twist has lower security
kelalaka avatar
in flag
@poncho I've found the twist has the same cardinality. You can check with my code. I wondering that part, since I've not seen a curve like this.
kelalaka avatar
in flag
@poncho and the $G$ is clearly not on the twist of the curve, too.
poncho avatar
my flag
The cardinality of a curve plus the cardinality of its twist always sum to $2p+2$; this can be seen because, for any possible x coordinate, it corresponds to two points on the curve, or to two points on the twist, or one point on both (if $y=0$, which doesn't happen on this curve). Add in the two points of infinity (one on the curve, one on the twist), and you're there. The only way this can happen is if the order of the curve is $p+1$, which is not the case for this curve.
kelalaka avatar
in flag
@poncho that is true, that I did not checked that. I'll delete that part until it resolved.
kelalaka avatar
in flag
@poncho thanks, I don't know why $d=5$ is not working, I've solved the issue with quadratic_twist of the SageMath, though that is way slower.
kelalaka avatar
in flag
@oberstet It cannot be BN curve since $p \equiv 1 \bmod 4$, the BN curves requires that $p \equiv 3 \bmod 4$
oberstet avatar
in flag
uh, right. I guess I was looking too hard for an "official/proper curve name";) btw, as suggested, I've DM'ed Daria Hopwood (above) via Keybase and included a link to the post here. Let's see.
Ariel avatar
cn flag
Re "nothing up my sleeve", the [generator](https://github.com/starkware-libs/starkex-resources/blob/44a15c7d1bdafda15766ea0fc2e0866e970e39c1/crypto/starkware/crypto/signature/signature.py#L50) is the second point in this [array](https://github.com/starkware-libs/starkex-resources/blob/44a15c7d1bdafda15766ea0fc2e0866e970e39c1/crypto/starkware/crypto/signature/pedersen_params.json#L25), which is generated from the digits of $\pi$.
kelalaka avatar
in flag
@Ariel thanks for the links.
oberstet avatar
in flag
@Ariel thanks! I could verify that: the `nothing_up_my_sleeve_gen.py` script indeed uses Pi to compute G, and the JSON file is exactly the output of the script https://gist.github.com/oberstet/35b55f21a73a94fb1d1c13f4d6dd5323 https://github.com/starkware-libs/starkex-resources/blob/44a15c7d1bdafda15766ea0fc2e0866e970e39c1/crypto/starkware/crypto/signature/nothing_up_my_sleeve_gen.py#L56
Dan Carmon avatar
us flag
@kelalaka $d=5$ didn't work because 5 _is_ a quadratic residue modulo $p$ (easy to check $p \equiv 1 \pmod 5$). You could take $d=3$ instead, which is a non-residue since $p \equiv 5 \pmod {12}$.
kelalaka avatar
in flag
@DanCarmon uh. My QR calculation had a mistake then. Thanks. I'll check both again...
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.