2015-06-26

BusyBeaver and the state of near-native code in browsers

Curious how cryptography performs in asm.js vs. Google Native Client? Check it out for yourself:
A description of my path to these examples follows.



I was impressed recently with what I read about Google Native Client, which is embedded in Chrome, and Firefox's asm.js and Emscripten. I was further impressed by how I can play Prince of Persia in my browser, and it works via DOSBox inside JavaScript, and it's actually perfectly playable, aside from key lag. :-)

I've recently been working on BusyBeaver, a new password hashing, key derivation, and proof of work function. Existing commonly used password hashing approaches suffer from extreme brute forcing susceptibility on hardware as widely available as an AMD GPU. BusyBeaver is my attempt to improve upon PBKDF2 and scrypt in its resistance to optimization via execution on a GPU, FPGA, or most anything other than the intended usage platform - a 64-bit, general purpose CPU.

It seems I've done a decent enough job with BusyBeaver, as far as resisting GPU optimization is concerned, so I had the idea to see if I can use Emscripten, or Google Native Client, to have it run in browsers. It would, after all, be useful to a website that wants to offload the CPU cost of rigorous password hashing to the person who is intended to benefit from it — the user.

Oh boy.

Well, first of all, I was able to get BusyBeaver to compile with Emscripten, and it does run in Firefox, IE, and Chrome... in descending order of performance. It will become clear why I say this.

It takes a while for this to execute, but... BAM!



The test vectors run! And they are correct! Yay!

Note that this is an achievement in its own right. This is C++ code, compiled without modification into JavaScript, and it runs in a browser. That's pretty awesome.

But. There are buts.
  • The native EXE compiled with GCC is 100 kB. With Visual Studio 2013, it's 210 kB. With Emscripten, the .js file is 700 kB. Yikes. That's a lot of bandwidth to pay for a key derivation function.
  • In Firefox, the module loads in 150 ms on my computer. That's thanks to the SpiderMonkey optimizations for asm.js. It's probably much more on mobiles... But those run Chrome or Safari.
  • In Firefox, an execution of BusyBeaver with 50,000 operations, which takes about 6 ms in native code, runs for... 500 ms. Mmmm... okay. I guess that asm.js's claims of a factor of 2 slowdown over native compilation with clang are circumstantial, or hyperbolic, or clang must really suck.
  • Even so, I guess the figures in Firefox could work in practice. But how about Chrome?
  • In Chrome, the page is still loading...
  • Okay, so Chrome takes about 30 seconds to load the test page and run one execution of BusyBeaver. Once the page is loaded, subsequent runs take about 2 seconds. Sigh. Clearly, Chrome developers didn't implement the JavaScript optimizations for asm.js that Firefox did - which I guess is because they favor their Native Client.
  • Hey, how about IE? Well, would you look at that. The page loads in about 8 seconds, and then subsequent executions take about 4 seconds each. Not too much different from Chrome; just with a different - in this case better - initial analysis vs. subsequent performance tradeoff.
  • In Chrome on my Samsung Galaxy S4, the script took 311 seconds to load. It then took 13 seconds to calculate a subsequent digest.

Google Native Client

I also adapted BusyBeaver for Google Native Client. Results?
  • The portable executable compiles to 100 kB. Compare to 700 kB with Emscripten.
  • A single digest is calculated in 10 ms. Compare to 500 ms with Firefox and asm.js.
In my opinion - asm.js has:
  • no readability, compatibility, or safety advantage over a portable binary format; and is
  • an order of magnitude less efficient, both in performance and code size.
If you're going to have something as sophisticated as Emscripten, and a proposed standard like asm.js, why not just adopt a proper binary format?

Until then, we have statements like these, coming from Mozilla and Opera:
  • "NaCl seems to be 'yearning for the bad old days, before the web', to paraphrase Tim Berners-Lee."
    -- Håkon Wium Lie, Opera CTO
  • "We don't want to go back to a place where it's just binary delivery over the internet. We've seen people try to do it before."
    -- Chris Blizzard, Mozilla
:-/

3 comments:

Boris Kolar said...

There's new initiative - WebAssembly: http://moduscreate.com/webassembly-explained/

Some tech details: https://github.com/WebAssembly/design/blob/master/AstSemantics.md

denis bider said...

Well, good thing they finally seem to be working on it.

Check out my most recent update to the article. I've implemented a version for Google Native Client. In Chrome, it executes in 10 ms, compared to Firefox's 500.

I sure hope WebAssembly ends up being more like PNaCl, and less like asm.js. asm.js sucks.

denis bider said...

I'm fearful that WebAssembly is going to suck:

"Will WebAssembly make JavaScript faster? Short answer: yes (load time) and no (execution time)."

I'm not seeing a load time problem with the asm.js version of BusyBeaver. I'm seeing an execution time problem - 500 milliseconds per digest is fifty times slower than performance with Google Native Client.