As I mentioned previously, an efficient PBKDF2 implementation is absolutely essential for Easy Passwords in order to generate passwords securely. So when I looked into Microsoft Edge and discovered that it chose to implement WebCrypto API but not the PBKDF2 algorithm this was quite a show-stopper. I still decided to investigate the alternatives, out of interest.
First of all I realized that Edge’s implementation of the WebCrypto API provides the HMAC algorithm which is a basic building block for PBKDF2. With PBKDF2 being a relatively simple algorithm on top of HMAC-SHA1, why not try to implement it this way? And so I implemented a fallback that would use HMAC if PBKDF2 wasn’t supported natively. It worked but there was a “tiny” drawback: generating a single password took 15 seconds on Edge, with Firefox not being significantly faster either.
So I went one step further. HMAC again is fairly simple, and the only non-trivial part here is SHA1. The Rusha project offers a very fast SHA1 implementation so I went with this one. And I realized that my 250 thousands HMAC operations were mostly hashing the same data: the first block of each hashing operation was derived from the secret key, always the same data. So I hacked Rusha so that it would allow me to pre-process this block and save the resulting state. HMAC would then restore the state and only hash the variable part of the input on top of it.
This implementation got the time down to 1.5 seconds on Edge — still not great but almost an acceptable delay for the user interface. And profiling made it obvious that the performance could still be improved: most time was being spent converting between big-endian and low-endian numbers. The issue is that SHA1 input is considered a sequence of big-endian numbers. With the calculation using low-endian numbers internally on almost every platform a fairly expensive conversion is necessary. And then the hashing result would be available as five low-endian numbers, yet for a proper byte representation of the SHA1 hash these need to be converted to big-endian again.
With PBKDF2 you are usually hashing the result of the previous hashing operation however. Converting that result from low-endian to big-endian only to perform the reverse conversion on the input is a complete waste. So I implemented a shortcut that allowed hashing the result of the previous hashing operation efficiently, without any conversion. While at it, I’ve thrown away most Rusha code since I was only using its high-performance core at that point anyway. And that change brought the password derivation time down to below 0.5 seconds on Edge. On Firefox the calculation even completes in 0.3 seconds which is very close to the 0.2 seconds needed by the native implementations on Firefox and Chrome.
Was it worth it? This implementation makes Edge a platform that can be realistically supported by Easy Passwords — but there are still lots of other issues to fix for that. But at least I updated the online version of the password generator which no longer relies on WebCrypto, meaning that it will work in any browser with typed arrays support — I even tested it in Internet Explorer 11 and it was still very fast.
As to the others, you can test them yourself if you like (on browsers without native PBKDF2 support the first test will error out so you need to click the tests individually there). The following graph sums up my results:
Edit: Shortly after writing all this I found asmCrypto that uses asm.js consistently. Guess what — its performance is on par with the native implementations and in Firefox it’s even significantly faster than that (around 0.1 seconds)! Thanks for reading up on my wasted effort.