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

On Wed, Jun 13, 2018 at 9:25 AM Dan Brown <danibrown@blackberry.com> wrote:

> 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.
>

Here's study that looks at secp256k1 in ECDSA in OpenSSL, which claims to
recover private keys in 200 signatures using side channels.

https://eprint.iacr.org/2014/161.pdf

(To be fair: I haven't looked deep enough to tell whether it's an
implementation issue or an inherent issue with the curve.)

--Richard

>
> 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: *cfrg@irtf.org
> *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 secdispatch@ietf.org.
>
>
>
> 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
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>