Proposing wasm-crypto.js - a fast cipher suite for JS runtimes

[tanx]

tl;dr - This is a a collection of lessons learned from implementing OpenPGP.js v2.0 and a thought experiment of how a future WebAssembly based cipher suite compiled from a well tested C library could look like

OpenPGP.js cipher redundancy today

We've made huge progress from a performance standpoint in the current OpenPGP.js v2.x release. The new release uses Uint8Arrays throughout the library and integrates asm.js implementations for SHA-1, SHA-256, and AES. We also use node.js's native crypto module for these ciphers as well as the native WebCrypto apis for RSA key generation.

This makes the current release very fast for common use cases, but also introduces different code paths and duplicate cipher dependencies to the library. For example we currently use three different SHA libraries (jsSHA, Rusha and asmCrypto). For AES we use two different AES implementations: asmCrypto for integrity protected packets (CFB in non-resync mode) and our old implementation for non integrity protected packets (CFB in resync mode).

For future ECC support we could integrate WebCrypto/Node.js apis that implement NIST curves. But DJB's Curve25519 is not supported by either api. We would need to cross compile a C implementation to WebAssembly/asm.js (probably Google's curve25519-donna also used by the Signal Chrome App).

The problems with using WebCrypto apis

The W3C has specified a WebCryptography api that surface native cryptography shipping in browser’s TLS stacks to JavaScript developers. Browser support is quite good but there are a few problems:

• IE 11 implements an old version of the spec, without Promises (fixed in Edge)
• Safari/Webkit implements another old version of the spec (with Promises), but this one behaves differently than Chrome and Firefox
• No browser currently implements AES-CFB mode
• Even if browsers implement CFB mode, they would likely not implement OpenPGP’s resync mode (which might be OK as modern PGP implementations use integrity protected packets)
• RSASSA-PKCS1-v1_5 only supports sign/verify not encrypt/decrypt
• Only SHA-1, SHA-256, SHA-384 and SHA-512 are supported. Not SHA-224, MD5 and RIPE-MD
• Only NIST curves are supported. Not Curve25519.

You could rightfully argue that some of these ciphers are old and insecure. So it’s good that the WebCrypto apis do not support them. But the OpenPGP specification requires them in order to decrypt/read old messages. Even worse, the WebCrypto apis cannot be used at all for OpenPGP's AES and RSA encryption, due to lack of AES-CFB and RSASSA-PKCS1-v1_5 encrypt/decrypt ... some of the most performance intensive code.

To sum things up, the current state of using multiple apis/ciphers for different platforms and waiting for browser vendors to implement ciphers required for OpenPGP is unsatisfactory to say the least. In the end we will still need to fall back to JS ciphers to offer cross-platform compatability.

A proposal for a unified WebAssembly cipher suite

Brendan Eich pointed out that all major browser vendors are currently working on WebAssembly for their JavaScript engines and since node uses V8, we can expect it to be available widely for all of our current target platforms in 2016/2017:

https://twitter.com/brendaneich/status/707760398968053761

Compiling ciphers from a well tested C library like OpenSSL (or another, which ever offers all of our required ciphers) would allow us to replace our redundant cipher libs with one library and remove our dependency on native apis for various runtimes that offer incomplete cipher support.

We’d have a cipher suite, that is…

• Feature complete (AES, 3DES, CFB mode, RSA, all SHA hashes, MD5, RIPE-MD, …)
• The same on all platforms
• Almost as fast as native (WASM can reach 2x native performance)
• Memory safe … this should not be underestimated

We could still drop down to native apis in OpenPGP.js if the overhead is minimal and the performance difference is big enough, but by default for every platform would use the same fast and well tested cipher suite. Runtimes that do not yet support WebAssembly could fall back to asm.js by using the wasm polyfill which generates asm.js from wasm bytecode.

How to approach this in baby steps

1. Create a new npm-module/github-repo called wasm-crypto.js that compiles well tested ciphers (probably from OpenSSL’s) to WebAssembly/asm.js. The wasm-crypto.js library would provide a build toolchain for compiling C code as well as a thin, well documented api layer and unit tests.
2. Replace OpenPGP.js's current ciphers one by one. We could start with something simple like replacing our three SHA libs with the SHA implementation provided by OpenSSL. This would serve as a proof of concept and give us some insight into this approach.
3. If the proof of concept is successful we could invite other web crypto project's to contribute their required ciphers into one unified cipher suite for the web. Much like OpenSSL today for native apps.

N.B. This is just thinking out loud and there are probably many pitfalls and issues along the way that I'm not yet seeing. So please let me know what you think.

thanks,
Tankred

[tanx]

Experimental support for WebAssembly has landed in Chrome, Firefox & a build of Edge

http://v8project.blogspot.co.uk/2016/03/experimental-support-for-webassembly.html

[tanx]

Ryan Sleevi of Google and others have given some interesting feedback:

https://twitter.com/tankredhase/status/711022750136143873

Specifically we should not focus on optimizing old/busted ciphers. But rather invest in modern primitives like AES-GCM that are supported natively by WebCrypto, in order to be able to deprecate JS cipher requirements in OpenPGP.js altogether. Having given this some thought, I tend to agree and would close this issue in favor of #421.

[toberndo]

I'm still in favor of the wasm path. Curve25519 is currently not supported in the Web Crypto API and also for the compression algorithms wasm would bring us close to native performance.

[tanx]

Yeah. As long as there is no native alternative I agree. Curve25519 and compression are obvious choices. Although it probably makes sense to do each in its own git/npm module so other projects can reuse/patch them.

See also #26 (comment)

But for AES-CFB/SHA-1/SHA-256 we already use asm.js primitives. To my knowledge WASM has no runtime advantages over asm.js, only more efficient bytecode format for smaller download and faster AOT compilation. That makes a huge difference when you compile a game engine written in C/C++ to the web. For small ciphers asm.js is probably good enough i.e. the performance gain from asm.js to wasm probably does not justify the investment.

RSA encrypt/decrypt is probably the only "legacy cipher" that justifies optimization in the short term. FYI asmCrypto implements RSA already. We would just need to add that to out build target in asmCrypto-lite and replace our old JSBN based code. --> seperate github issue?

In the longterm I agree with Ryan Sleevi that we should invest in modern crypto like ECC/AES-GCM that is readily available in native apis.

[toberndo]

For small ciphers asm.js is probably good enough i.e. the performance gain from asm.js to wasm
probably does not justify the investment.

Sounds reasonable. Also asm.js is backward compatible

RSA encrypt/decrypt is probably the only "legacy cipher" that justifies optimization in the short term.
FYI asmCrypto implements RSA already. We would just need to add that to out build target in
asmCrypto-lite and replace our old JSBN based code. --> seperate github issue?

Looks like rsa-pkcs-v1.5 is not implemented in https://github.com/vibornoff/asmcrypto.js
In general I think it would be good to find a well maintained typed array replacement for JSBN.
When choosing a new RSA implementation we need to check that we don't get a regression with issues fixed after the last security audit like 9f23c6a

[tanx]

Looks like rsa-pkcs-v1.5 is not implemented in https://github.com/vibornoff/asmcrypto.js

In general I think it would be good to find a well maintained typed array replacement for JSBN.
When choosing a new RSA implementation we need to check that we don't get a regression with issues fixed after the last security audit like 9f23c6a

Agreed. Create an issue for asm.js RSA?

Also, I feel like we should maybe create a roadmap for OpenPGP.js v3.0 with ECC, lib-modularization, asm.js optimizations, and GCM coming to mind. That way outsiders can see where we're headed, making it easier to contribute a task.

—
You are receiving this because you modified the open/close state.
Reply to this email directly or view it on GitHub

[tanx]

@toberndo @bartbutler @evilaliv3 I created a really simple roadmap. Since everyone is really eager to get ECC I put that in v3.0. Other things that came up are in v4.0. totally up for debate though:

https://github.com/openpgpjs/openpgpjs/milestones

[shlomi-schwartz]

What is the status of this proposal (wasm part)?

[tjad]

I'd like to know too please.

[bartbutler]

It's a a holding pattern at the moment. Lots of performance improvements went into OpenPGP.js 3 but we haven't been able to look at much beyond the 3.0 milestones yet.

[bitjson]

For anyone subscribed to this issue looking for a specific WASM implementation – the bitcoin-ts library now provides a WebAssembly version of secp256k1, and both single-pass and incremental versions of ripemd160, sha256, sha512, and sha1. (As a tree-shakable es6 module with TypeScript types.)

Interestingly enough, if your use case includes lots of small hashes, you may find the WASM implementation is significantly faster than the built-in Crypto.subtle API:

More benchmarks are here.

[twiss]

Could you perhaps also compare to asmcrypto.js? That's what we're currently using, and last I tested was significantly faster than hash.js and Rusha.

[bitjson]

@twiss thanks for the idea! Done: https://github.com/bitjson/bitcoin-ts/wiki/Benchmarks

Looks like asmcrypto.js really underperforms for smaller inputs, but starts to outperform for inputs of >1MB.

A sampling of the results for sha256:

browser: sha256: hash a 32-byte input

hash.js x 270,121 ops/sec ±0.92% (64 runs sampled)
bitcoin-ts x 253,430 ops/sec ±0.25% (64 runs sampled)
crypto.subtle x 15,178 ops/sec ±5.02% (53 runs sampled)
asmcrypto.js x 4,263 ops/sec ±4.08% (54 runs sampled)

Fastest is hash.js

browser: sha256: hash a 100-byte input

bitcoin-ts x 177,468 ops/sec ±1.20% (63 runs sampled)
hash.js x 164,577 ops/sec ±0.22% (64 runs sampled)
crypto.subtle x 10,692 ops/sec ±4.31% (41 runs sampled)
asmcrypto.js x 4,192 ops/sec ±2.29% (25 runs sampled)

Fastest is bitcoin-ts

browser: sha256: hash a 1000-byte input

bitcoin-ts x 37,884 ops/sec ±1.87% (63 runs sampled)
hash.js x 26,529 ops/sec ±1.46% (60 runs sampled)
crypto.subtle x 10,109 ops/sec ±3.17% (49 runs sampled)
asmcrypto.js x 3,677 ops/sec ±5.85% (49 runs sampled)

Fastest is bitcoin-ts

browser: sha256: hash a 10000-byte input

crypto.subtle x 7,716 ops/sec ±3.37% (41 runs sampled)
bitcoin-ts x 4,299 ops/sec ±2.23% (26 runs sampled)
hash.js x 3,208 ops/sec ±0.21% (64 runs sampled)
asmcrypto.js x 3,018 ops/sec ±1.74% (20 runs sampled)

Fastest is crypto.subtle

browser: sha256: incrementally hash a 32MB input in 1MB chunks

asmcrypto.js x 3.55 ops/sec ±0.19% (13 runs sampled)
bitcoin-ts x 1.43 ops/sec ±1.35% (8 runs sampled)
hash.js x 0.61 ops/sec ±1.62% (6 runs sampled)

Fastest is asmcrypto.js

node: sha256: hash a 32-byte input

bcoin x 624,000 ops/sec ±2.56% (83 runs sampled)
hash.js x 351,590 ops/sec ±0.87% (92 runs sampled)
bitcoin-ts x 232,430 ops/sec ±1.40% (86 runs sampled)
node.js native x 224,557 ops/sec ±4.77% (81 runs sampled)
asmcrypto.js x 2,537 ops/sec ±2.84% (60 runs sampled)

Fastest is bcoin

node: sha256: hash a 100-byte input

bcoin x 420,771 ops/sec ±5.44% (74 runs sampled)
node.js native x 208,342 ops/sec ±4.46% (81 runs sampled)
hash.js x 191,333 ops/sec ±1.68% (87 runs sampled)
bitcoin-ts x 169,389 ops/sec ±2.14% (84 runs sampled)
asmcrypto.js x 2,586 ops/sec ±3.60% (60 runs sampled)

Fastest is bcoin

node: sha256: hash a 1000-byte input

bcoin x 183,676 ops/sec ±2.41% (81 runs sampled)
node.js native x 131,335 ops/sec ±3.34% (83 runs sampled)
bitcoin-ts x 45,486 ops/sec ±0.75% (86 runs sampled)
hash.js x 32,043 ops/sec ±0.58% (90 runs sampled)
asmcrypto.js x 2,603 ops/sec ±2.25% (66 runs sampled)

Fastest is bcoin

node: sha256: hash a 10000-byte input

bcoin x 27,889 ops/sec ±1.26% (87 runs sampled)
node.js native x 26,013 ops/sec ±1.75% (89 runs sampled)
bitcoin-ts x 5,247 ops/sec ±3.23% (91 runs sampled)
hash.js x 3,465 ops/sec ±1.11% (90 runs sampled)
asmcrypto.js x 2,248 ops/sec ±2.08% (76 runs sampled)

Fastest is bcoin

node: sha256: incrementally hash a 32MB input in 1MB chunks

node.js native x 9.41 ops/sec ±0.50% (27 runs sampled)
asmcrypto.js x 3.56 ops/sec ±1.44% (13 runs sampled)
bitcoin-ts x 1.72 ops/sec ±0.98% (9 runs sampled)
hash.js x 0.53 ops/sec ±0.49% (6 runs sampled)

Fastest is node.js native