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.
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!
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...
- 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 ClientI 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.
- 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.
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