4
$\begingroup$

I have been examining the scrypt paper, and I noted the claims in table 1.

For 10 random ASCII characters, the cost at that time for scrypt set to $(2^{14}, 8, 1)$ is estimated to be $175T/yr.

Can formulae for equivalent year cost be constructed to determine the parameters as functions of time since those tests were performed?

Improve this question
$\endgroup$
  • $\begingroup$ Those tests were performed in 2009, from what I remember, so Moore's law has not yet much touched those numbers. $\endgroup$ – Reid Jun 23 '14 at 14:29
  • 1
    $\begingroup$ @Reid Based on my inexperience, it seems reasonable to assume that they are approximately 1/4 as strong as they were. The js library I'm using requires much higher parameters to achieve 3.8 seconds. Thank you for taking your time on my question! $\endgroup$ – user7024 Jun 23 '14 at 14:33
4
$\begingroup$

Can formulae for equivalent year cost be constructed to determine the parameters as functions of time since those tests were performed?

Yes, but you have to make a lot of assumptions. First, though, note that the paper says:

We caution again that these values are very approximate [...] Nevertheless, we believe that the estimates presented here are useful for the purpose of comparing different key derivation functions.

The estimates are not necessarily very accurate as absolute values, but only in relation to each other. They are based on numbers from 2002.

That said, there are three parameters to tweak in scrypt: $N$, $r$ and $p$. Increasing $p$ increases only the computational cost. Increasing $r$ or $N$ also increases memory use. The effect of $p$ is easiest to estimate:

Doubling $p$ doubles the time taken per try, so the attacker needs twice as many devices to calculate the same number of hashes in a year, so the attack cost doubles.

Now how much cheaper has computing power become since 2002?

  • A 2002 Northwood P4 had 55 million transistors while a 2014 Haswell i7 has 1.4 billion. That's about a 25x increase.
  • The 2002 130nm process could put about 0.38 million transistors on a square mm, while the 2014 22nm process can put 7.9 million. That's about a 20x increase.
  • The "doubles every two years" version of Moore's law implies a 64x increase.

Conservatively, then, you could increase $p$ from 1 to e.g. 64 to account for the increased performance/\$ potential, but that would likely increase the time it takes significantly, at least unless your implementation is parallelized (for $p>1$ the different SMix invocations can be calculated in parallel).

Increasing $N$ would be even better, because of the increased memory use – not only would the attacker need twice as many devices, but each of those would be more expensive as well. However, the effect of that is more difficult to estimate. Additionally, that may not be doable in a low memory environment, like mobile or in the browser.

In practice, I think a better approach is to set a target time and find the highest numbers you can use and still make a target time.

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you very much again otus for sharing your excellent knowledge! $\endgroup$ – user7024 Jun 23 '14 at 15:44
  • $\begingroup$ "r" should only be increased to reflect increases in the memory latency-bandwidth product of the machine on which you will be using Scrypt. Too small, and your machine will not be as efficient at Scrypt as a potential attacker could be. Too large, and a potential attacker could user slower, cheaper memory than you. "N" and "p" are the only parameters that should be adjusted to increase costs to an attacker otherwise, with preference to N (if possible) for the reasons given in this answer. $\endgroup$ – Nick Bauer Nov 23 '15 at 17:11
  • 1
    $\begingroup$ @NickBauer, yes, there is an optimal $r$ to use, but I would not expect it to necessarily be the default one, so that would be one to potentially tweak. Still, you are correct, so I'm fixing the suggestion. $\endgroup$ – otus Nov 23 '15 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy