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

From: Mike Jones <[email-masked]>
Date: Tue, 12 Jun 2018 00:03:10 +0000

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 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 [email-masked]<mailto:[email-masked]>.

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

---

From: Dan Brown <[email-masked]>
Date: Tue, 12 Jun 2018 02:36:56 +0000

Hi Mike,
To clarify 2 points on my role,
secp256k1 appeared in version 1.0 of SEC2, ‎and I had no part in designing the curve or in writing version 1.0 of SEC2. I believe the design and writing was a group effort, of Gallant, Lambert, Vanstone, Qu, Blake-Wilson, and others.
By the time of SEC2 version 2.0, I had become the editor for SEC2, due to personnel changes, and was listed as the contact in the update. It was still a group effort back then, so many people were involved in the decision to keep the various that were kept.
Also, AFAIK, P-256 was described by NIST before it was added to SEC2.
Best regards,
Dan

From: Mike Jones
Sent: Monday, June 11, 2018 8:03 PM
To: [email-masked]
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 [email-masked]<mailto:[email-masked]>.

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

---

From: denis bider <[email-masked]>
Date: Wed, 13 Jun 2018 00:33:32 -0500

Tangential note:

In SSH, RFC 5656 defines a standard algorithm identifier format for ECDSA
and ECDH using any curve that has an OID. I'm not aware of many other
implementations, but exactly because of the reasoning you point out
(Bitcoin is a huge target), since 2014, Bitvise SSH Server and SSH Client
have supported secp256k1 in SSH under the following algorithm names:

Key exchange:

ecdh-sha2-1.3.132.0.10

Public key authentication (server or client):

ecdsa-sha2-1.3.132.0.10

On Mon, Jun 11, 2018 at 7:03 PM, Mike Jones <
Michael.Jones=[email-masked]> wrote:

> 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 [email-masked].
>
>
>
> 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
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 13 Jun 2018 08:45:31 +0000

Mike Jones <Michael.Jones=[email-masked]> writes:

>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

It's worse than that: Because of Blockchain, secp256k1 is under tremendous
scrutiny, and anyone finding a weakness is highly motivated *not* to talk
about it.  

secp256k1 is the curve I'd least want to use because it's such a massive
target for highly-motivated attackers.

Peter.

---

From: Dan Brown <[email-masked]>
Date: Wed, 13 Jun 2018 13:25:07 +0000

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

Dear CFRG,

                                                       Thanks,
                                                       -- Mike