Re: [Cfrg] CFRG feedback on signing with secp256k1 curve

[Dan Brown <[e-mail]>]

Hi Mike,

Well, secp256k1 has cofactor 1, same as NIST P256. So it does not map to Montgomery or Edwards form, and may be more prone to side channel attacks. Offhand I don't have references, but I think they can be found.

It has also special structure: j-invariant 0 ‎and efficient endomorphism. There is no known attack on ECDLP for this feature, but the consensus is that it may be riskier than a less special curve. Again, I could probably find refs. It is implicit in that NIST did not recommend it.

Gallant-Lambert-Vanstone found a way to speed up Pollard rho attacks on ECDLP given an efficient endomorphism, but the speedup for secp256k1 would be very little, maybe *2, i.e. 1 bit of security, but don't quote me.

Menezes-Okamoto-Vanstone attacked various special curves, including supersingular curves with j=0, but secp256k1 is not affected. Nonetheless, the shared feature of j=0 with an MOV-attacked curve, is an informal red flag, aka early warning sign, aka crack in the concrete.

Indeed, in 1985, Miller suggested using special curves, but also cautioned they could be risky.

Despite the consensus about the risk of special curves, they have been proposed for their other benefits. Pairing curves are special too, but secp256k1 does not have a pairing. Yet others have proposed special curves for their speed. Koblitz, Koblitz and Menezes suggested special curves might better survive a collapse in regular curves.

That all said, I'm not aware of a specific study of secp256k1. If none exist, then it's a bit odd.

Well, I hope that helps. I can try to figure the exact references later.

Best regards,

Dan

From: Mike Jones
Sent: Monday, June 11, 2018 8:03 PM
To: [e-mail]
Subject: [Cfrg] CFRG feedback on signing with secp256k1 curve


Dear CFRG,

You’ll recall that the “secp256k1” elliptic curve is described by Dan Brown and Certicom in “SEC 2: Recommended Elliptic Curve Domain Parameters” http://www.secg.org/sec2-v2.pdf (the same document that described the secp256r1 curve – a.k.a., P-256).

I recently wrote  https://tools.ietf.org/html/draft-jones-webauthn-secp256k1-00<https://tools.ietf..org/html/draft-jones-webauthn-secp256k1-00> with a very specific and narrow purpose: to register JOSE and COSE curve identifiers for the SECG secp256k1 elliptic curve and associated algorithm identifiers for signing.   This curve is already being used by FIDO UAF, the W3C Verifiable Claims interest group, and several blockchain projects.  I want to get standard identifiers registered so these projects can use standards-based, rather than ad-hoc, cryptographic representations.  A path forward for this document is being discussed at [e-mail]<mailto:[e-mail]>.

As part of the SECDISPATCH evaluation, Ekr had suggested that I ask the CFRG for references to security analyses of secp256k1.  No matter what you or I may think of Blockchain, because Blockchain is using secp256k1 and is under tremendous scrutiny, it’s my assumption that if major security flaws were known, people would be widely talking about them.  But I’d like to replace my assumption with an actual security analysis or two and thoughts from the CFRG, if possible.

                                                       Thanks,
                                                       -- Mike