Various memory allocations inefficiencies prevents real use case scenarios

[evilaliv3]

Scrypt is an algorithm designed cause lots of memory allocations by itself, but it seems that the current scrypt-async-js design contains a lot of additional memory allocations inefficiencies that prevent to use it in the real with the suggested LogN=20 that was proposed in 2009 as the right LogN for file encryption.

https://www.tarsnap.com/scrypt/scrypt-slides.pdf

For example running Scrypt with LogN=20 on Chrome seems to allocate more than 2GB for a sigle run;

This is due to the fact of various variable allocations inside loops and mix javascript sintaxes that could be avoided like:

• new Array inside functions when the variable could be allocated one time outside
• return [x, y, z] inside functions reallocating every time a new array for the return

[dchest]

In theory, these allocations should be killed by garbage collector early, keeping only the result of PBKDF2_HMAC_SHA256_OneIter, but yeah, practically they probably do it later. I'd approach this differently, by rewriting all SHA256 and most importantly HMAC/PBKDF2 (e.g. like in fast-sha-256) to use preallocated arrays. Let me take a stab at it sometime next week.

[dchest]

So I counted allocations by manually inserting counters into code, and it's approximately 40K for all temporary arrays in SHA and PBKDF. Not great, but also not something to worry about if you ask for 1 GiB (logN=20, r=8), and these can all be collected early by GC except for 1K used in computation (if r=8). I wonder what's up with 2 GB that you got. Did you use r=8?

[anri-asaturov]

@dchest btw I've noticed that V8 GC can wait with executing collection cycle in case there is plenty RAM and CPU is really busy, might be related.

[evilaliv3]

@dchest: yes i confirm that i was using r=8;

what do you suggest for a logN=20 to be performed even on a low budget android phone? do you think that could be feasible? What would be the estimated RAM requirement for the r requirement that you suggest by the current allocations we have?

it would would be probably really great to implement a profiling of the library and publish the results obtained. we could even do a small whitepaper on that showing what you were able to implement in JS and describing the results and possible use case applications!

\cc @fpietrosanti

thank you so much!

[fpietrosanti]

Some internal function can be moved to WebCrypto API, to leverage native code?

[dchest]

I think logN=20, r=8 is too high for phones (1 GiB RAM if we count only the intended allocations), it will probably crash many phones, which don't have enough RAM. I'd use maximum 256 MiB (logN=18, r=8) on phones, or even lower on low-budget phones (but don't go lower than 16 MiB). As for r (block size for blockMix function), there's no reason to change it to something other than 8 right now, so consider it a fixed parameter and then adjust logN accordingly (bytes of memory = 128 * r * 2^logN).

[dchest]

@fpietrosanti no #9 (comment) (can be done, but mostly useless)

[evilaliv3]

We could not use logn<20 because we need a secure derivation used for file encryption so at least we will try it work with r=1 given the fact that is the only parameter we could play on. In our encryption schema the scrypt result is used as passphrase for Pgp key and cant be changed depending on the client The library has no issue with r=1 right?

[dchest]

No no no, you have it completely backwards. r is a block size parameter, N is memory-CPU cost parameter. With logN=20, r=1 you'll use 128 MiB of memory, the same as logN=17, r=8, but you'll make it worse with respect to memory latency, so it's not an improvement. r should be your fixed parameter, and logN is something that you can play with. If you don't believe me, take a look at the orignal scrypt encryption utility code: r is fixed there to 8, N is calculated based on maximum memory in the system, and p is calculated based on the number of CPUs:

https://github.com/Tarsnap/scrypt/blob/master/lib/scryptenc/scryptenc.c#L104

There's no such thing as inability to use smaller N because you need file encryption — if you meant the recommended parameters from scrypt paper — they are what they are, recommended parameters. If your system can't use larger N, you make it smaller. (One good way to figure it out is to measure system parameters, but it's impossible to do this in JavaScript and, as you say, in your system.)

(To answer your question: yes, the library accepts any valid r)

[dchest]

[evilaliv3]

understood! thank you so much @dchest for the clarification.