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.
I figured that the culprit was WebCrypto being asynchronous. This isn’t normally an issue, unless you have to do around 250 thousands HMAC operations — sending input data to another thread and receiving result for each single one of them. There is no way to call WebCrypto API in a synchronous fashion, not even from a web worker. Which means that using WebCrypto API in this way makes no sense here and pure JavaScript implementations would be faster.
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.
I got into this one step after another so that I only thought about existing implementations when I was already done. Turns out, their performance isn’t too impressive, for whatever reason. I found four existing pure-JavaScript implementations of the PBKDF2-HMAC-SHA1 algorithm: SJCL, forge, crypto-browserify and crypto-js. Out of those, crypto-js turned out to be so slow that I couldn’t even measure its performance. As this paper indicates, its PBKDF2 implementation slows down massively as the number of iterations increases, this goes beyond linear.
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:
The implementation I added as fallback in Easy Passwords now performs consistently well in all browsers, never needing more than twice the time of native implementations. The other pure-JavaScript implementations are at least factor three slower, always taking more than a second to derive a single password. For some reason they seem particularly slow in Edge, with crypto-browserify even taking around a minute for one operation.
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.
Comments
Does it provide same security as native version? Also I think it shouldn’t be available in any circumstances for firefox since there is built in PBKDF2 and user has to be certain that it’s actually used. Security and simplicity should prevail against compromises and fallbacks.
It’s the same algorithm, it produces the same results for the same input – there are unit tests ensuring that. So security isn’t affected in any way. At the moment, the fallback isn’t used on Firefox (unless you do something weird that disables native PBKDF2 support which is actually possible). However, seeing how well asmCrypto works I consider using it for everything – already because having only one code path is simpler and more reliable than a major path and fallbacks.
I don’t know myself but security people go ballistic about using window.crypto.randomBytes() and nothing else. https://paragonie.com/blog/2016/05/how-generate-secure-random-numbers-in-various-programming-languages#js-csprng
Any custom implementations could have their weak spots. I don’t like the idea about changing something which works only because some microsoft crap didn’t implement current standards again.
Good random numbers are very important when generating encryption keys, this is irrelevant for Easy Passwords. The only weak spot I can think of here are potential buffer overflows and similar edge conditions. But even if you take away the fact that the data is largely supplied by the user himself, we aren’t running native code here – it’s JavaScript. You can compromise the memory of a single asm.js script but all you can potentially achieve that way is generating a broken password for the manipulated input. Easy Passwords currently spins up a new worker for each password generated, so no other operations can be affected.
Ok, I’ll trust you :) Keep up the good work!
FYI: critique of deterministic pwd managers like easy: https://tonyarcieri.com/4-fatal-flaws-in-deterministic-password-managers https://twitter.com/bascule/status/801120682373328897
Nope, that’s about very basic password managers. Easy Passwords saves a state, this addresses the first two issues. It’s a very simple state however, one that you can print out as a paper backup. This state can also be synced without being concerned about security issues – it is worthless without knowing the master password (I am currently working on automatic sync functionality). Easy Passwords also uses a combined approach, it can store legacy password – these will be encrypted with an individual key derived from your master password (that’s issue #3).
The last issue is valid of course, you better don’t lose your master password. How would that happen however? It’s not like you reuse that password elsewhere. By far most likely scenario IMHO is a malware infestation on your computer. Problem is, if your computer is compromised then no password manager will save you. It doesn’t matter whether the malware only needs to get your master password or whether it needs to copy your password vault as well. It can easily do either, and it can even collect your passwords as they are being entered on the web – without even knowing where these are stored.
I agree that easypass already solved those issues unfortunately the message there is: deterministic = bad and it looks that everyone agrees which doesn’t look good for easypass popularity. I think there is still one valid point – plaintext metadata. It’s not crucial for security but somewhat privacy issue ( especially with online syncing involved). Shouldn’t it be encrypted same way as legacy passwords? I think there is no benefit for the user having ability to access them without masterpasss. If there is no downside of it please consider it for future verions of easypass.
Well, everybody agreeing is just the regular filter bubble :). I obviously disagree. Deterministic password generation can be bad if implemented incorrectly (which is sadly the usual case), but with proper crypto to back it up the disadvantage compared to your encrypted password storage is purely theoretical.
As to plaintext metadata, it’s not really a disadvantage as long as that data is on your computer – you have your regular browsing history there as well. In fact, being able to print it is actually a huge advantage – not sure about you but I am very concerned about losing my data in a hard drive crash, and with data as important as my passwords I’m not even inclined to trust backups (no, I don’t have the time to verify integrity of my backups on a regular basis, just like most people). So having that piece of paper around and knowing that I can easily restore all my passwords as long as I have it is quite a relief.
As to sync functionality, there is an important reason why the metadata is going to be synced without encryption – I’m sure that you want sync to always work in background, not just when you unlocked Easy Passwords with your master password. If encryption were required, the extension wouldn’t be able to perform a sync as long as it doesn’t know your master password.
And it isn’t such a huge privacy issue as it would seem. The data isn’t being uploaded to some server I own. The sync functionality will rather use your Dropbox or Google Drive account. So the only parties being able to access it will be you (isn’t it nice to verify what Easy Passwords stores there?) and the provider. And I assume that you already trust either Dropbox or Google with data that is much more private than that list of websites and account names.
Side-note: mind entering a valid email address or leaving it out completely when commenting? If you enter an email address the blog will try to notify you about my response and I get a bounce back.
I think you could still print it after providing masterpass but not before.
Also is syncing encrypted files different that syncing plaintext files? Those files aren’t heavy so it’s not much for transfer here. I think masterpass isn’t needed for syncing encrypted or not. I assume that legacy passwords are synced too so you will sync encrypted metadata + encrypted legacy password instead of plaintext metadata + encrypted legacy passwords.
Personally I wouldn’t put unencrypted files in any online storage because of potential breach, leak or account steal.
Syncing isn’t merely a download&replace operation. What if you have two devices and are adding passwords on both of them? It would be quite a pity if the upload from one device kicked out the password you added on another. So a sync using means download, then merge, then upload. And possibly even a retry if another device uploaded changes in between.
With some effort this could probably be done with encrypted data as well, but that encrypted data would have to be structured in order to allow merging. It would need some serious security evaluation to make sure that this structure doesn’t allow any conclusions about the data. What’s worse, it would considerably increase the number of decryption operations that the extension needs to perform – meaning that key derivation might become too slow for a responsive UI and you would need to reduce the number of rounds. All in all seems completely unjustified given the potential risks.
Virtually every non-deterministic password manager has sync option of encrypted data available so those issues should have common solutions. I don’t think decrypting data is necessary. I wonder if extension-side sync is needed at all when users can (or already do) syncing on their own alongside other files with dropbox, owncloud etc.
i think encrypted metadata is important as it contains all those usernames…what about encrypting metadata by default then switch to plaintext if sync is enabled (if it ever be avalaible)?