Improve performance by using WebCrypto API?

[fpietrosanti]

Hi, i was wondering if the performance of this scrypt implementation cannot be improved by leveraging existing WebCrypto API primitives (https://www.chromium.org/blink/webcrypto)

I don't know, from a performance profiling perspective how does the library behave, but in WebCrypto API there are those ones that maybe suitable for use in scrypt-async:

• SHA256 https://dvcs.w3.org/hg/webcrypto-api/raw-file/tip/spec/Overview.html#sha
• PBKDF2 https://dvcs.w3.org/hg/webcrypto-api/raw-file/tip/spec/Overview.html#pbkdf2
• HMAC https://dvcs.w3.org/hg/webcrypto-api/raw-file/tip/spec/Overview.html#hmac

Do you think it does make sense as a possible significant performance improvement of the library?

Maybe would it make sense to customize scrypt algorithm itself in order to maximize it's use of Native code when run in an HTML5 browser?

[dchest]

The performance of PBKDF2 as used in scrypt mostly doesn't matter (that's why I implemented them in a simple way instead of the more performant, like in https://github.com/dchest/fast-sha256-js), since the hot part of computation is in Salsa20/8 and memory copying/xoring. It would make sense to use WebCrypto primitives for modern implementation, but I try to keep compatibility with older IE versions, and don't want to put a lot of, so to speak, #ifdefs (we have one already: https://coveralls.io/files/682307335#L363). On the other hand, it would probably make sense to use WebCrypto for WebWorker-based implementation (I'll review and comment on that PR later).

[fpietrosanti]

How much do you think, a webcryto based performance improvement, would bring in % of speeding it up?

At GlobaLeaks, where we don't have the backward compatibility limitations due to the use of window.crypto for RNG for OpenPGP.js use, we could be interested to do it, if it's expect to deliver some significant performance improvement.

Fabio

[dchest]

Not sure exactly, but with high enough N, r parameters, it would be in a single digits if not smaller. Try running a Chrome profiler and see the % it takes for PBKDF2.

FYI, lots of browsers implemented window.crypto.getRandomValues before any other APIs from that standard, so last time I checked full WebCrypto with PBKDF2 is still not widely implemented.

[fpietrosanti]

Our use in GlobaLeaks by @evilaliv3 does number crunching for 5-10seconds because we need to key-stretch a 16digits pin.

From tour profiling, our of 530ms of computation we can desume that: +20% is spent in "Anonymous function" 9% on SalsaXOR 30% is spent on mixing functions ~1% in SHA256 ~1% in PBKDF

Some point of brainstorming:

• are there any operation done "within" the block/smixing functions that could leverage WebCrypto API or abusing other new HTML5 API like WebGL?
• are there anything to be optimized inside the "anonymous functions" occupying so much time? Can we make those functions to be shown in the profiler?
• Is the use of SalsaXOR something with very specific cryptographic properties of salsa for scrypt or it could be re-implemented using AES-GCM function available from webcrypto?

[dchest]

1. I don't know WebGL, so I'm not competent enough to answer this question. There's https://github.com/Kukunin/webgl-scrypt if you want to try it.
2. I think this may be interruptions caused by a small interruptStep. If you set it to something like 1<<30, it won't interrupt computations. This is what I wanted to to for WebWorker implementation: since it doesn't need interruptions, as it's running on a separate thread, I'd like to make it synchronous.
3. Check out scrypt paper: https://www.tarsnap.com/scrypt/scrypt.pdf

BlockMix is best used with a hash which is fast while not possessing excess internal parallelism.

AES would be a bad choice because it's slow and it's very good for hardware (read: attacker) optimizations. I don't think there's anything in WebCrypto which would be more suitable.

[evilaliv3]

i confirm that i do not find the pbkdf2 fully implemented not in chromium (Version 41.0.2272.118 Built on 8.0, running on Debian 8.0 (64-bit)) nor in icewasel.

1. @fpietrosanti i don't think it would be good to use the https://github.com/Kukunin/webgl-scrypt that is really tricky.
2. yep i've verified and its due to the interruptStep. i think it would be good to use the 0 to skip totally the setTimeout that even with a low timing is really resource expensive.

[fpietrosanti]

@evilalive Well, reducing this "anonymous function" to the bare minimum, means impacting a possibly 20% overhead with your WebWorker hacking.

@dchest Thanks for the pointer, going to ask the developer of WebGL-scrypt if he think that there could be some very specific WebGL function only for the mixing functions.

In the meantime i opened this topic for discussion on cryptography mailing list at randombit as a way to stimulate such discussions: http://lists.randombit.net/pipermail/cryptography/2015-May/007234.html

[fpietrosanti]

Btw regarding possible use of WebGL i read abstract of a paper optimizing AES with a 10x performance http://link.springer.com/chapter/10.1007%2F978-3-319-02726-5_20 compared to pure JS implementation.

[dchest]

To optionally get rid of interruptStep, I'm thinking of making some arguments to scrypt completely optional, and adjusting how it behaves based on passed types.

• scrypt(password, salt, logN, r, dkLen, interruptStep, callback, [encoding])
• scrypt(password, salt, logN, r, dkLen, callback, [encoding]) -> uses the default interruptStep of 1000 (good for old IE, so that it won't show "script is too slow" alert)
• scrypt(password, salt, logN, r, dkLen, [encoding]) -> returns value instead of passing it to callback

Thus, if you do not pass callback, you will get the synchronous behavior.

[evilaliv3]

@dchest i've quite finished to write a patch for the interruptStep. in my idea that static setting is not useful at all: 1) one will use web workers when available in browsers. 2) in case web workers are not available the static setting can be replaced nu a dynamic one in wich we increment/decrement the step based on the computation of let's say 1ms. (this 1ms if a random number here, to be tuned)

i will be back with the patch for 2 in an hour or little more.

[dchest]

@evilaliv3 will it work in IE6 (I'm sorry)? :-) I think it throws the error not based on running time, but based on the amount of executed instructions, so unfortunately, I don't think dynamic adjusting will work.

[evilaliv3]

but right now it's not managed also by your code, or i'm wrong? wit the current fixed value (with a default of 1000) the chosen setting would

• work well on the average pc, but who will define the average pc of it's audience?
• work bad in good pc (e.g., on mine it takes 900ms for a computation that would take 300ms removing the set timeout)
• work bad on very low pc where the browser would raise an exception anyway for too long run execution.
• work bad on very low pc where the 1000 value will go anyway in exception for too much execution time.

what do you think?

[dchest]

There's no average PC for IE: it interprets a fixed amount of instructions on any PC, and throws error if it's over the limit. I found the value by trial and error, but unfortunately I don't actually remember if it was the default 1000 or something else (I'll have to check my notes).

I think mobile Safari also had problems with long-running scripts, but it checked for running time, not the number of instructions.

The point of making scrypt-async-js was exactly to avoid apparent hanging and "slow script" errors in every browser: I think there were other implementations of scrypt available, but they were unusable for real-life client-side execution due to this. That's why setTimeout is here, and that's why the name has async in it :) (So your last two points are avoided).

The problem with dynamic setting of interruptStep is that you don't know when the particular browser will show a slow script error: it will only report it to the user, not the script. However, the WebWorker implementation can avoid all this stuff, so if you're targeting only modern browsers, it will work better.

[evilaliv3]

i see, thanks.

why you have not integrated the webworker? is there something you would like we implement before accepting it?

[dchest]

I first want to make the changes I wrote about here: https://github.com/dchest/scrypt-async-js/issues/9#issuecomment-98678202 (soon, in a day or so), and then see how to use the third described way of calling in a worker. Also, I'd like to avoid Promise, as it's available only on the newest versions (http://caniuse.com/#search=Promise), but workers are available earlier. Finally, maybe after the changes, it would be worth just to document how to use it in a worker instead of providing our own implementation.

[evilaliv3]

there are no problem in using the third in a worker. and rightly lets try to avoid Promise. i will take a look in this direction too

[jedie]

I didn't want to open a new issues. Hope that's ok.

What's about the performance of this scrypt implementation compared with https://github.com/tonyg/js-scrypt/ ?

[fpietrosanti]

@jedie It would be lovely if you could arrange a small project like that to compare, performance wise, different scrypt libraries on different browsers. :-)