Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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. $\;\;\;$ –  Ricky Demer Aug 22 '13 at 22:49
    
@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. –  nightcracker Aug 23 '13 at 12:14
    
@RickyDemer Nope. Memory usage is only a function of $r$. nightcracker, I'm not sure what your point is. –  Nick ODell Aug 23 '13 at 17:26
    
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}$ –  Ricky Demer Aug 23 '13 at 17:47
    
@nightcracker : $\;\;\;$ No, but I do believe that I can decrease memory usage without significantly $\hspace{.37 in}$ changing the runtime. $\:$ In fact, I believe the last sentence in my post gives a way to do that. $\hspace{.82 in}$ –  Ricky Demer Aug 23 '13 at 18:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.