curve.n missing _move method in proto

[benediamond]

In short weierstrass curves, the member curve.n is missing _move from its prototype:

var BN = require('bn.js')
var EC = require('elliptic')

var curve = new EC.ec('secp256k1'); // e.g.---same problem for other curves

curve.n._move // undefined
new BN(curve.n.toString(16), 16)._move // defined

If n is then used to initialize a reduction context, calling redNeg causes _move to drop, which leads to crashes:

var q = BN.red(curve.n) // bad
var temp = new BN(1234).toRed(q)
temp.redNeg()._move // undefined
temp.redNeg().redMul(temp) // crashes

and yet,

var q = BN.red(new BN(curve.n.toString(16), 16))
var temp = new BN(1234).toRed(q)
temp.redNeg()._move // now defined
temp.redNeg().redMul(temp) // this works

Here is the stacktrace:

TypeError: a.umod(...)._forceRed(...)._move is not a function
    at Red.imod (/Users/benediamond/node_modules/bn.js/lib/bn.js:3190:36)
    at Red.mul (/Users/benediamond/node_modules/bn.js/lib/bn.js:3254:17)
    at BN.redMul (/Users/benediamond/node_modules/elliptic/node_modules/bn.js/lib/bn.js:2883:21)

This issue only happens when bn.js version v5.0.0 is used! elliptic version is 6.5.0. @fanatid

[benediamond]

@StuartH1

[benediamond]

@indutny if you could take a look at this as well...?

[indutny]

Does this happen during some API call? What's the test case?

[benediamond]

The minimal working example is as indicated in the original post.

Indeed, curve.n is a natural argument with which to initialize a reduction context—in order to conduct modular computation in the exponent.

Turns out that calling redNeg on any such exponent will lead to crashes.

(As a workaround, you can always use new BN(curve.n.toString(16), 16) instead, as in the example. Shouldn't be necessary though.)

[benediamond]

In other words, the test case is

var q = BN.red(curve.n)
var temp = new BN(1234).toRed(q)
temp.redNeg().redMul(temp) // shouldn't crash

[indutny]

I think the problem is happening because elliptic uses bn.js@4 and you're using the latest bn.js .

[indutny]

cc @fanatid @calvinmetcalf : should we update bn.js in elliptic? What issues could it cause in browserify-crypto?

[fanatid]

Problem is that new version of bn.js have _move while elliptic still uses bn.js@4.
Fore reference, _move was introduced in indutny/bn.js#178

I started check modules which used by crypto-browserify and where bn.js is used. But then I though, even if package ok with bn.js@4 it does not matter, it would be better update to bn.js@5 because if we update only elliptic bundling code (browserify/webpack/etc) which uses crypto-browserify will cause adding 2 different major bn.js versions.
If you ok with updating browserify-sign, browserify-rsa, elliptic, bn.js, create-ecdh, diffie-hellman, miller-rabin, public-encrypt I can submit PR's.

I also found that some package uses deprecated Buffer API (new Buffer), should be this updated too? Buffer.from was added from node 5.10, I do not think that older versions should be supported.

[fanatid]

@calvinmetcalf @indutny are you okay with updating bn.js everywhere to version 5?

[indutny]

I'm more than happy with this, as long as there is a coordination with crypto-browserify. cc @jprichardson

[jprichardson]

I'm in full support 👍

[fanatid]

Great, I'll add it to my list.

List of packages for update (in order for update):

• create-ecdh fix(deprecation): use Buffer.from instead of constructor browserify/createECDH#13 bump bn.js to 5.0.0 browserify/createECDH#15
• diffie-hellman switch to safe-buffer browserify/diffie-hellman#31 bump bn to 5.0.0 browserify/diffie-hellman#32
• public-encrypt Update bn.js to address Buffer constructor deprecation browserify/publicEncrypt#20
• miller-rabin Update bn.js to address Buffer constructor deprecation miller-rabin#11
• browserify-rsa Address Buffer constructor deprecation browserify/browserify-rsa#12 bump bn.js to 5.0.0 browserify/browserify-rsa#13
• asn1.js Buffer constructor runtime deprecation - this package emits a warning on Node 10 asn1.js#102 Use Buffer.(from|alloc) instead of deprecated Buffer API asn1.js#103 fix: address buffer constructor deprecation asn1.js#116 bump bn.js to 5.0.0 asn1.js#118
• browserify-sign Fix buffer deprecation. browserify/browserify-sign#45 bump bn.js to 5.0.0 browserify/browserify-sign#47
• elliptic Update bn.js to address Buffer deprecation #197 bump bn.js to 5.0.0 #210

`yarn why bn.js` output:

=> Found "[email protected]"
info Reasons this module exists
   - "browserify#crypto-browserify#create-ecdh" depends on it
   - Hoisted from "browserify#crypto-browserify#create-ecdh#bn.js"
   - Hoisted from "browserify#crypto-browserify#diffie-hellman#bn.js"
   - Hoisted from "browserify#crypto-browserify#public-encrypt#bn.js"
   - Hoisted from "browserify#crypto-browserify#browserify-sign#bn.js"
   - Hoisted from "browserify#crypto-browserify#diffie-hellman#miller-rabin#bn.js"
   - Hoisted from "browserify#crypto-browserify#browserify-sign#browserify-rsa#bn.js"
   - Hoisted from "browserify#crypto-browserify#browserify-sign#elliptic#bn.js"
   - Hoisted from "browserify#crypto-browserify#browserify-sign#parse-asn1#asn1.js#bn.js"

[fanatid]

Another question before move on, because indutny/asn1.js#103
Should packages still use safe-buffer? If packages will be updated to Buffer.from should it be major version bump?
Personally, I think that safe-buffer is not required anymore. New versions should be semver-major.
cc @ChALkeR

[ChALkeR]

I think that it's not required, support for Node.js < 4.5 could be just dropped.

[benediamond]

hi all (@fanatid)—any update on this? thank you!

[fanatid]

Oh, I forgot about this issue during long vacation. I'll revisit it shortly and try make some progress. Sorry.

[benediamond]

great, thanks, please keep posted.

[fanatid]

I added extra function (which still called in BN#_move), but this resolve issue immediately with new release of bn.js. This will be faster than upgrade all packages with bn.js as dependency.
@benediamond can you test it? (new version with workaround not released [only PR right now indutny/bn.js/pull/236], so test will be little tricky)

[fanatid]

Submitted PR's to all packages for update bn.js to 5.0.0. Only bn.js update, but I propose release minor bump instead patch for updated packages.
I left safe-buffer, did not touch new Buffer, because otherwise there will be more burden. Every updated package will require proper engines field and major-bump with update next dependent packages.

[benediamond]

hi @fanatid sorry for the delay! it's a bit tricky to test this, because elliptic imports its own BN.js...? PR looks good though, big thanks for this.

[fanatid]

@benediamond I published [email protected] with workaround (indutny/bn.js#238). Should work now.

[benediamond]

@fanatid excellent! i can confirm that the issue is fixed. feel free to close.

[fanatid]

Found another issue related with different versions:

const BN = require('bn.js') // 5.1.1
const EC = require('elliptic').ec // 6.5.2

const ec = new EC('secp256k1')
const ecparams = ec.curve

console.log(new BN(42).toRed(BN.red('k256')).redSqr())
console.log(new BN(42).toRed(ecparams.red).redSqr())

<BN-R: 6e4>
/home/kirill/tmp/node_modules/elliptic/node_modules/bn.js/lib/bn.js:2975
      r.strip();
        ^

TypeError: r.strip is not a function
    at K256.ireduce (/home/kirill/tmp/node_modules/elliptic/node_modules/bn.js/lib/bn.js:2975:9)
    at Red.imod (/home/kirill/tmp/node_modules/elliptic/node_modules/bn.js/lib/bn.js:3147:39)
    at Red.mul (/home/kirill/tmp/node_modules/elliptic/node_modules/bn.js/lib/bn.js:3211:17)
    at Red.sqr (/home/kirill/tmp/node_modules/elliptic/node_modules/bn.js/lib/bn.js:3219:17)
    at BN.redSqr (/home/kirill/tmp/node_modules/bn.js/lib/bn.js:2996:21)
    at Object.<anonymous> (/home/kirill/tmp/bnjs-t.js:8:44)
    at Module._compile (internal/modules/cjs/loader.js:1139:30)
    at Object.Module._extensions..js (internal/modules/cjs/loader.js:1159:10)
    at Module.load (internal/modules/cjs/loader.js:988:32)
    at Function.Module._load (internal/modules/cjs/loader.js:896:14)

Related with indutny/bn.js#105

[collincusce]

Hey I came here because I'm getting the r.strip error as well.

 FAIL  tests/apis/ava/keychain.test.ts (5.154s)
  AssetsKeyPair
    ✕ Creation Empty (403ms)

  ● AssetsKeyPair › Creation Empty

    TypeError: r.strip is not a function



      at K256.ireduce (node_modules/elliptic/node_modules/bn.js/lib/bn.js:2975:9)
      at Red.imod (node_modules/elliptic/node_modules/bn.js/lib/bn.js:3147:39)
      at Red.mul (node_modules/elliptic/node_modules/bn.js/lib/bn.js:3211:17)
      at BN.redMul (node_modules/bn.js/lib/bn.js:2984:21)
      at JPoint.eqXToP (node_modules/elliptic/lib/elliptic/curve/short.js:909:36)
      at EC.verify (node_modules/elliptic/lib/elliptic/ec/index.js:191:12)
      at AssetsKeyPair.verify (src/apis/ava/keychain.ts:2440:17)
      at Object.<anonymous> (tests/apis/ava/keychain.test.ts:15:19)

from code:

/**
     * Verifies that the private key associated with the provided public key produces the signature associated with the given message.
     * 
     * @param msg The message associated with the signature
     * @param sig The signature of the signed message
     * 
     * @returns True on success, false on failure
     */
    verify = (msg:Buffer, sig:Buffer):boolean => { 
        let sigObj:elliptic.ec.SignatureOptions = this._sigFromSigBuffer(sig);
        return ec.verify(msg, sigObj, this.keypair);
    }

    /**
     * @ignore
     */
    protected _sigFromSigBuffer = (sig:Buffer):elliptic.ec.SignatureOptions => {
        let r:BN = new BN(bintools.copyFrom(sig, 0, 32));
        let s:BN = new BN(bintools.copyFrom(sig, 32, 64));
        let recoveryParam:number = bintools.copyFrom(sig, 64, 65).readUIntBE(0, 1);
        let sigOpt = {
            r:r,
            s:s,
            recoveryParam:recoveryParam
        };
        return sigOpt;
    }

[fanatid]

Hi @collincusce
As workaround you can get BN from elliptic: https://github.com/cryptocoinjs/secp256k1-node/blob/v4.0.0/lib/elliptic.js#L8
i.e. you will need remove bn.js as direct dependency and use bn.js from elliptic.
At least this is working solution right now.

[collincusce]

Thanks! Thoughts on using this library (which is a wrapper) instead? https://github.com/cryptocoinjs/secp256k1-node

[rawr51919]

I'll be working on fixing this issue via

• crypto-browserify https://github.com/crypto-browserify/crypto-browserify/pull/200
• diffie-hellman Fixed deprecation warnings and updated dependencies browserify/diffie-hellman#35
• publicEncrypt Update dependencies and fix Travis CI builds browserify/publicEncrypt#22
• createECDH Update dependencies and fix Travis CI builds browserify/createECDH#18
• browserify-sign Updated dependencies and fixed crypto-browserify Travis CI builds browserify/browserify-sign#63
• browserify-rsa Update dependencies, fixed crypto-browserify Travis CI builds, and added ppc64le browserify/browserify-rsa#15
• miller-rabin Updated dependencies, added Travis CI builds, and fixed constructor errors miller-rabin#12
• asn1.js Updated dependencies asn1.js#126
• elliptic Update dependencies #246

This supersedes the PRs made by @fanatid in comment #191 (comment). This in turn also fixes https://github.com/crypto-browserify/crypto-browserify/issues/187. The strip() issue discussed earlier was also fixed in indutny/bn.js#239, so no need to worry about these updates and PRs.