1
$\begingroup$

The answerer has commented that scrypt's memory use is "only a function of r". $\:$ However, he has
not addressed my argument that it also depends on N, in one of my comments from over 5 days ago.


I had somehow gotten the impression that scrypt offered a separate memory-factor in addition
to its main work-factor. $\:$ However, the (original?) scrypt paper does not have such a parameter.

Do any implementations of scrypt offer a way to limit
its memory usage without that limiting its runtime?

Looking at that paper, I see that there would be an obvious way to do so: in the definition of
ROMix (on page 6), add an input M and replace the instances of N in steps 2 and 7 with M.
Alternatively, one could replace those two Ns with max(M,N) and replace
the N in step 6 with max(N,(2*N)-M), or with something similar to that.

$\endgroup$

2 Answers 2

1
$\begingroup$

Definition 4: The key derivation function scrypt is defined as scrypt(P, S, N, r, p, dkLen) = MFcryptHMAC SHA256,SMixr(P, S, N, p, dkLen)

The limits on the size of p and dkLen exist as a result of a corresponding limit on the length of key produced by PBKDF.

Users of scrypt can tune the parameters N, r, and p according to the amount of memory and computing power available, the latency-bandwidth product of the memory subsystem, and the amount of parallelism desired; at the current time, taking r = 8 and p = 1 appears to yield good results, but as memory latency and CPU parallelism increase it is likely that the optimum values for both r and p will increase. Note also that since the computations of SMix are independent, a large value of p can be used to increase the computational cost of scrypt without increasing the memory usage; so we can expect scrypt to remain useful even if the growth rates of CPU power and memory capacity diverge.

Source.

This SO answer elaborates on the factors more clearly.

$N$: General work factor, iteration count.
$r$: blocksize in use for underlying hash; fine-tunes the relative memory-cost.
$p$: parallelization factor; fine-tunes the relative cpu-cost.

Source.

If you want to increase memory hardness, raise r. This will also raise execution time, so you might want to lower N at the same time.

$\endgroup$
8
  • $\begingroup$ Wait a minute here. $\:$ It looks to me as if runtime and memory usage are both proportional to $\:N\hspace{-0.03 in}\cdot\hspace{-0.04 in}r\:$, $\hspace{.63 in}$ via ROMix and its hash H. $\:$ If that's correct, then those parameters don't actually let $\hspace{1.44 in}$ one limit memory usage independently of runtime. $\;\;\;$ $\endgroup$
    – user991
    Aug 22, 2013 at 22:49
  • $\begingroup$ @RickyDemer Do you really believe you can increase memory usage without increasing runtime without decreasing the runtime of something non-memory related? Be honest with yourself here. $\endgroup$
    – orlp
    Aug 23, 2013 at 12:14
  • $\begingroup$ @RickyDemer Nope. Memory usage is only a function of $r$. nightcracker, I'm not sure what your point is. $\endgroup$
    – Nick ODell
    Aug 23, 2013 at 17:26
  • $\begingroup$ What am I missing in the following argument? $\:$ "scrypt calls MFcrypt, MFcrypt calls SMix$_r$ (p times in parallel), SMix$_r$ calls ROMix, ROMix makes a table of N values of its hash (which is BlockMix$_{Salsa20/8,r}$), $\;\;$ all of which must be stored simultaneously. $\:$ Thus memory usage scales linearly with N." $\hspace{.98 in}$ $\endgroup$
    – user991
    Aug 23, 2013 at 17:47
  • 1
    $\begingroup$ @RickyDemer If you run multiple computations in parallel, the memory multiplies with the number of those instances, but if you run them sequentially it does not. You should set the memory parameter so that your total RAM can support all your CPU cores. Once you increase the parallelism parameter beyond your CPU cores, only the runtime increases. $\endgroup$ Sep 28, 2013 at 9:11
1
$\begingroup$

If you're using node, node scrypt does this much nicer than your standard Nrp parameters:

scrypt.params(maxtime, maxmem, maxmemfrac, function(err, scryptParameters) {
   // scryptParameters contains the standard Nrp generated based on your inputs
});

This way you can control your parameters in a much more understandable way, putting limits on how much cpu time to use, how much memory to use, and the maximum percentage of your available memory to use.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.