9x slower than jsbn

[wyoung]

I'm using an npm library which is based on jsbn. This pairing works together quite well, but it's been difficult to work with due to the jsbn library's thin documentation, especially around its ctor, which has a screwy parameter interface.

I therefore went searching for replacements and found your library. I was excited to see that it's got docs, its ctor makes more sense than that of jsbn, it's getting updates, it implements a nearly drop-in compatible interface, and on top of all of that it acts as a polyfill for a feature that will appear in JS platforms that are still in my future. (Alas!) This thing is dripping awesomesauce!

Then I benchmarked it. On my tests here, it's about 9x slower than jsbn.

I'll accept some slowdown to get the above features, but not that much. With jsbn, a key element of the calculation takes about a tenth of a second, which means it adds a barely noticeable delay to the user. Multiplying that delay by 10 makes the delay actually annoying.

I'm filing this issue along with the tests below in case there's a way you can substantially speed up this library short of delegating to native BigInt, perhaps by swiping ideas from jsbn. Native BigInt will be great, but I probably won't be able to depend on it until about a year or so from now, when it's in a sufficiently large fraction of the browsers my customers use.

Thanks!

Simple Node test case:

const srpc = require('secure-remote-password/client');
require('benchmark').Suite().add('calcM1', function() {
    const s = 0xDEADBEEF.toString(16); // jsbn needs hex string, not Number!
    const I = 'username';
    const P = 'password';
    srpc.deriveSession(
        '1f7befaaf479d8339995bdaa5892906a98e56fe6fc73f29d69e55fbe6da8a038',
        '645dada978654c53e94cc92bff45f06c3ef0c3ed9e6d9079bd70a971dfd20b8df1facda9bc0cb536630aded9805451d1f263823c5eca83a566f7c4d5d32bd0f147952b70c4be179db085027a3f1f0fbbccb9589d81fef4584572d968a11d312f88dfbf153bda58f34c7636772a7e2cbf7e7c22d44d94b1424d14b3cf731763e10c7f0e4c7389f1bb5aee7cd499788f059b36a7291252364545a7bdf425dc2594c7c5abb4eab2e8b6423b12f8cef7015cc520d5dedea7f75602b6a7d797943d5a415dd1846aefa719a1fe0b07334c09bff11c2b46e2587b2a03f1cec5aacfc3e5ef3a703d45f0ff92d4638d95a9bfdc2cf82e0276892209156c552c38a12f09e6',
        s, I, srpc.derivePrivateKey(s, I, P));
}).on('cycle', function(e) {
    console.log(String(e.target));
}).run();

Install the required modules with:

$ npm install secure-remote-password benchmark big-integer

Run it as-is above, then apply this trivial diff to convert the secure-remote-password module to use your big-integer module and run it again:

--- node_modules/secure-remote-password/lib/srp-integer.js~0       2019-05-01 18:15:44.240901888 -0600
+++ node_modules/secure-remote-password/lib/srp-integer.js 2019-05-01 18:15:17.890837371 -0600
@@ -2,7 +2,7 @@
 
 const padStart = require('pad-start')
 const randomHex = require('crypto-random-hex')
-const { BigInteger } = require('jsbn')
+const bigInt = require('big-integer')
 
 const kBigInteger = Symbol('big-integer')
 const kHexLength = Symbol('hex-length')
@@ -57,13 +57,13 @@
 }
 
 SRPInteger.fromHex = function (input) {
-  return new SRPInteger(new BigInteger(input, 16), input.length)
+  return new SRPInteger(bigInt(input, 16), input.length)
 }
 
 SRPInteger.randomInteger = function (bytes) {
   return SRPInteger.fromHex(randomHex(bytes))
 }
 
-SRPInteger.ZERO = new SRPInteger(new BigInteger('0'), null)
+SRPInteger.ZERO = new SRPInteger(bigInt.zero, null)
 
 module.exports = SRPInteger

On CentOS 7, which includes Node 6.16.0, I get 10.92 iterations per second with the jsbn based implementation and 1.22 ops/sec with bigInt.

On a macOS system running Node 11.14.0 from Homebrew, I get 18.21 ops/sec with the jsbn implementation and 58.67 with bigInt, which sounds great until you realize that it's because Node 11.14 includes native big integer support. If I hack your library code to set supportsNativeBigInt to false, the benchmark result drops to 2.15 ops/sec here, only slightly better than on the CentOS 7 system, percentage-wise.

I'm tempted to rely on native BigInt support, but I worry that I've got a lot of users that won't have it yet, and they'll have a bad user experience.

[peterolson]

I haven't looked at it carefully yet, but my guess is that the performance difference comes from parsing hex input. From what I understand, jsbn internally uses base representation that is a power of 2, while this library internally uses a base representation that is a power of 10.

This means that jsbn will have a significant advantage in parsing hexadecimal input, and this library will have a significant advantage in parsing decimal input. Unfortunately it's a tradeoff, and I can't think of a simple way to make both fast at the same time. I decided to optimize for decimal since I figured it would be a more common use case (I can't say for sure if that's true or not), but that means this library can't really compete with other libraries that optimize for powers of 2.

[ex3ndr]

Not really, in my tests i has nothing with hex parsing. modPow operation is simply super slow.

[cyan-2048]

modPow very slow indeed! it takes 20 seconds to complete (for browsers that don't support native BigInt)

[cyan-2048]