scrypt hashing

[ghost]

There is supposedly fast scrypt javascript implementation available at https://github.com/dchest/scrypt-async-js

Maybe it's worth looking if it's good replacement/addition for pbkdf2 which easypasswords uses currently.

[palant]

Yes, I have been considering scrypt, there are some good implementations available. The main concern here are mobile devices (Firefox Mobile and eventually an Android app). While these should still perform reasonably well with PBKDF2 given native WebCrypto, the same likely isn't going to be true for scrypt. If we want to switch algorithms it would make sense to do this at the same time as #47, but I'd need to do some measurements first.

[palant]

So far I could find four usable scrypt implementations:

• https://github.com/tonyg/js-scrypt: extremely fast in Firefox, not quite so in Chrome but still good. Downside: huge script file (1.2 MB).
• https://github.com/ricmoo/scrypt-js: extremely slow.
• https://github.com/cryptocoinjs/scryptsy: extremely slow in Firefox; sort of fine in Chrome, but still much slower than the fastest implementations.
• https://github.com/dchest/scrypt-async-js: only 20% behind js-scrypt in Firefox, same performance in Chrome.

It seems that scrypt-async is the gold standard. Given the performance I see, 2^14 is the highest cost factor we could use - 2^15 would already be a stretch. This isn't too great given that this paper from 2009 already recommends this exact cost factor. That was eight years ago and as far as PBKDF2 goes our cost factor is considerably above the suggestion in this paper (hard to compare SHA1 and SHA256 unfortunately).

Another consideration is memory usage. I wonder what users will say about Easy Passwords producing memory usage spikes of 16 MB (cost factor 2^14) or more (if we manage to find a more efficient scrypt implementation, ideally we could have 2^16 which requires 64 MB).

[palant]

I actually went up to 2¹⁵ (and 32 MB memory usage) for scrypt in my tests, this is fairly close to the load currently produced by PBKDF2 after all. On my laptop, the expected delays are in the area of 0.2 seconds - fairly consistent for Firefox, Chrome and even Edge. On a four years old Android 4.1 tablet things are quite different. The default browser is hopeless, it is way too outdated, so I've tested in Firefox and Chrome:

• scrypt performance is quite consistent between Firefox and Chrome: around 2.8 seconds for js-scrypt and 1.8 seconds for scrypt-async.
• Native WebCrypto implementation of PBKDF2 needs 2.3 seconds on Firefox and 1.2 seconds on Chrome. asmCrypto is even slightly faster on Firefox (2.2 seconds) but considerably slower on Chrome (4.5 seconds).

So it seems that using scrypt-async would work. It performs well on desktop, so that we won't have a noticeable difference. And on mobile people are expecting multi-seconds delays I guess, so 1.8 seconds shouldn't be too bad. And whether people will accept 32 MB memory usage - I guess see that...

[ghost]

Personally I don't see 32MB memory as problem since modern browsers consume already about 1GB on slight load and with all those sandboxes and containerization this number will go up. Even on mobile there should be plenty of memory available. I wonder how modern android performs.

I've found one more scrypt implementation https://github.com/EtherDream/WebScrypt most documentation is in Chinese but maybe it's worth to test it.

Also just for curiosity there is something like this https://github.com/antelle/argon2-browser

[palant]

Nice one. The API of WebScrypt is somewhat weird but it is considerably faster than scrypt-async. On desktop I get 0.13 seconds instead of 0.2, on the tablet 1 second in Chrome. For some reason, in Firefox I get 4.8 seconds however.

This doesn't make a whole lot of sense because I also tested everything on Moto G4 Play now (not a high-end phone but considerably newer). With scrypt-async I get 1.6 seconds on Chrome and 2 seconds on Firefox, WebScrypt completes in barely more than 1 second on both - no disadvantage for Firefox here.

And then there is a "tiny" issue: there is no license information in the WebScrypt repository.

[ghost]

I've found webscrypt author announcement with some explanations. Unfortunately he wasn't active recently. I hope we will hear something from him.

[palant]

We can always go with scrypt-async if he doesn't react. The important thing is: scrypt implementations in the browser can still be improved. So looking into where scrypt-async can be optimized might be a better investment.

[palant]

I created dchest/scrypt-async-js#34 and the author pointed out yet another alternative: https://github.com/StableLib/stablelib. With this pull request the performance isn't too far behind WebScrypt any more. While WebScrypt author reacted and added a license, I'm thinking about using StableLib regardless. The issue with WebScrypt is, it has the entire algorithm implemented in asm.js - and asm.js cannot do "slightly more than 32 MB of memory," one has to allocate 64 MB then. So it has twice the memory usage compared to StableLib.

[palant]

I used the results from this blog post (actual results) to estimate what affordable contemporary hardware is capable of. It seems that this configuration is capable of calculating 100k hashes per second given our current PBKDF2-HMAC-SHA1 configuration. Estimating performance of scrypt(2¹⁵, 8, 1) is more complicated because it isn't clear how the significantly higher memory requirements would affect it. But even if I ignore that effect completely and look at computing power only, I get 14k hashes per second. So changing algorithms is certainly worth it, particularly with StableLib calculating scrypt hashes faster than WebCrypto is currently calculating PBKDF2 hashes on both Firefox and Chrome.

[palant]

There is also some concern about cryptocurrencies such as LiteCoin making specialized scrypt cracking hardware affordable. There is indeed this monster for example selling for something like $4k. In theory, it could produce 2 million hashes per second with our parameters, that would be quite bad. Luckily, it would most definitely fail on the memory requirements. LiteCoin is based on scrypt(2¹⁰) which requires merely 1 MB of memory per hashing operation. I couldn't find any real description of the 288 ASIC chips used there but I assume that each of these has no more than 1 MB of SRAM available. Judging by the prices listed on Digi-Key, putting 32 MB of memory into each chip would require considerably more expensive hardware (never mind the cost of developing such hardware, since it doesn't seem to exist yet). And having the chips talk to DRAM would introduce considerable latencies and slow them down similarly to how memory access becomes a bottleneck for GPUs.

[ghost]

Yeah, scrypt memory constraint should piss-off all that evil monsters 😄 . According to below article scrypt with memory usage below 4MB is worse than bcrypt but with our 32MB it's meaningless.
https://blog.ircmaxell.com/2014/03/why-i-dont-recommend-scrypt.html

Do you have any plans for transition yet? I assume easypasswords have to support both algorithms for foreseeable future to keep compatibility. Existing users would end up with having old passwords hashed with pbkdf2 and new with scrypt so maybe additional metadata like type:scrypt type:pbkdf2 is needed.

Also I wonder if scrypt cost parameter should be customizable. It will allow users for further hardening their passwords and for longer term it will free you from reassessing if current cost is still sufficient or not. Downsides of this is that users could put some crazy values which will create unstability. Also as this addons is named easypasswords it shouldn't be cluttered with much configurations. Maybe it's better to stay with hardcoded parametres, I don't know.

[palant]

I mistakenly said above that Litecoin requires 1 MB of memory for a hash operation. I forgot to account for the different r parameter, the actual memory requirement is merely 128 kB. So the ASIC chips of the Litecoin mining hardware probably have much less memory available to them than I thought.

According to below article scrypt with memory usage below 4MB is worse than bcrypt but with our 32MB it's meaningless.

The article is quite confusing, especially when it comes to the conclusions. Trading computing power for memory is definitely a concern however. For example, if the monster hardware actually had 1 MB of SRAM per chip then it could in theory fit the calculation in that memory while "only" increasing processing requirements by factor 32. Then it would still be able to produce 60k hashes per second, meaning that it would be considerably faster than the eight GPU system measured by Jeff Atwood, while also being significantly cheaper. Of course, if the chips have merely 128 kB of memory, then they would only turn out 8k hashes per second - still not too bad but definitely less of a concern.

Do you have any plans for transition yet? I assume easypasswords have to support both algorithms for foreseeable future to keep compatibility. Existing users would end up with having old passwords hashed with pbkdf2 and new with scrypt so maybe additional metadata like type:scrypt type:pbkdf2 is needed.

We currently have type: "generated", there will be type: "generated2" for the new algorithm. For now the old passwords will stay, so we'll need to indicate "Using Easy Passwords 1.x algorithm" for them on the "All Passwords" list. Also, we'll need a way to mark a password as "Using Easy Passwords 1.x algorithm" when new passwords are entered, so that people can recover their passwords (e.g. from paper backup).

This is only going to be a transitional period however, and the wording will have to make clear that replacing old passwords is recommended. At some point we'll drop support for the old algorithm, all remaining passwords will be converted to legacy (stored) passwords automatically.

Also I wonder if scrypt cost parameter should be customizable.

No, overwhelming users with configuration options that they cannot hope to understand definitely isn't the idea. At some point in future we'll need to increase the cost parameter of course, maybe even switch to a better algorithm - it depends on advances in scrypt cracking hardware. We'll handle this transition in the same way PBKDF2 to scrypt transition will be handled.

[palant]

This has been implemented on the crypto-update branch now. I'll leave the issue open until the branch is merged, #47 needs to land for that along with a notification screen explaining the changes. As long as #47 isn't resolved, stored passwords will still use PBKDF2 to derive the encryption key.

[ghost]

Great work! I'll be waiting for this.

[ghost]

There was discussion in golang about recommended scrypt parameters and conclusion is same as yours (N=15, r=8, p=1)
golang/go#22082 (comment)
https://go-review.googlesource.com/c/crypto/+/67070
https://blog.filippo.io/the-scrypt-parameters/

[palant]

The branch has been merged. There are a few issues to be addressed before release still but we should have a release soon.