1051509 - Add parameters for secp256k1 to NSS

Status: RESOLVED WONTFIX

(NSS :: Libraries, defect, P5)

Description

[Dave Huseby [:huseby]]

NSS is only missing the parameters for the secp256k1 curve used in bitcoin.  This should be a trivial patch.

Comment 1

[Ryan Sleevi]

Considering that WebCrypto does not define secp256k1, the subject of the bug seems misleading.

That's not to say there wouldn't be benefit, but not for WebCrypto, not right now.
(And given the timing issues that exist with a naive implementation of secp256k1, probably not as simple a patch as suggested)

Comment 2

[Dave Huseby [:huseby]]

Attachment: secp256k1.patch

And it was trivial.  From cr.yp.to curve pages I found the following...

order:
115792089237316195423570985008687907852837564279074904382605163141518161494337
= 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
= 2^256 - 432420386565659656852420866394968145599 

prime:
115792089237316195423570985008687907853269984665640564039457584007908834671663
= 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
= 2^256 - 2^32 - 977 

equation:
y^2 = x^3+0x+7 
so a is 0 and b is 7

base point:
(55066263022277343669578718895168534326250603453777594175500187360389116729240,
32670510020758816978083085130507043184471273380659243275938904335757337482424)
= (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8) 

cofactor:
1

Comment 3

[Dave Huseby [:huseby]]

You are correct Ryan, here's the patch to add the secp256k1 parameters to NSS.  I adjusted the title accordingly.

Comment 4

[Ryan Sleevi]

https://eprint.iacr.org/2014/161.pdf for why I think this is a bad idea as proposed.

Anyone wanting to implement secp256k1 bears the burden of proof to understand the math and demonstrate appropriate mitigation for timing attacks. Otherwise, its just introducing new potential bugs with real adverse effects. Most libraries have done a dedicated 256k1 implementation to mitigate these types of attacks.

Comment 5

[eric]

+1 for this patch, especially if it enables support for the curve in the `<keygen>` element.

Comment 6

[Ryan Sleevi]

(In reply to eric from comment #5)
> +1 for this patch, especially if it enables support for the curve in the
> `<keygen>` element.

No, it does not and will not.

Comment 7

[Dave Huseby [:huseby]]

Do you think the timing attacks are specific to each curve, or do you feel that they are specific to the implementation of the general function?  Because if it is specific to the general function, then I assume that NSS must have already solved the problem.

Comment 8

[Ryan Sleevi]

Note that NSS has multiple implementations - there is the general function, but there are optimized versions for the primary curves used by NSS. So it's not fair to assume that NSS has solved it in general, especially if the majority of platforms are using hand-coded assembly or optimized implementations for the curve. That's why I indicated that the burden of proof lies on the patch requester to review the available literature and consider the implementation strategy employed by NSS as it relates to the curve.

Recall that the previous paper I listed, with regards to OpenSSL's implementation, arose precisely because of the same implementation strategy - curve optimized implementations for specific curves that avoided timing issues present in the generic function relative to other curve parameters and their implementation strategies.

Comment 9

[Dave Huseby [:huseby]]

I was trying to go through the NSS history to find the code but I'm not very good with Mercurial anymore.  Wasn't there a time when all of the curves in ecl-curve.h were implemented?  I'm pretty sure there's a branch somewhere that has all of the implementations.  Anyway, that's probably a bad implementation that predates all of the timing attack research.

So what you're suggesting is that if i want to add secp256k1, at the very least, I should do a specialized function for that curve that has all of the side-channel attack prevention found in something like the lib256k1 implementation?

Comment 10

[Ryan Sleevi]

(In reply to Dave Huseby [:huseby] from comment #9)
> I was trying to go through the NSS history to find the code but I'm not very
> good with Mercurial anymore.  Wasn't there a time when all of the curves in
> ecl-curve.h were implemented?  I'm pretty sure there's a branch somewhere
> that has all of the implementations.  Anyway, that's probably a bad
> implementation that predates all of the timing attack research.
> 

Correct

> So what you're suggesting is that if i want to add secp256k1, at the very
> least, I should do a specialized function for that curve that has all of the
> side-channel attack prevention found in something like the lib256k1
> implementation?

Or ensure the generalized function is resistent to timing attacks. Since this is hard for generalized functions, it might be easier to create a specialized version.

However, that latter point "found in something like the lib256k1 implementation" - it's necessary for licensing compliance etc that the code be appropriately licensable under the terms of the MPL/GPL/LGPL tri-license :)

You would likely find the discussion on https://github.com/bitcoin/secp256k1/issues/238 useful