I have been looking at the scrypt hashing algorithm and am confused as to why the N value, which determines the overall cost, is limited to powers of two. There are only 3 things that the N value actually affects

  1. The amount of times to mix with salsa (via two loops with N being the count)
  2. The amount of memory required to compute a hash
  3. And one seemingly minor portion of mixing:

The mixing that relies on N is this:

for (i = 0; i < N; i++) {
    j = 32 * (X[16] & (N-1));
    for (k = 0; k < 32; k++)
        X[k] ^= V[j + k];
    xor_salsa8(&X[0], &X[16]);
    xor_salsa8(&X[16], &X[0]);

Would using N values that aren't a power of two compromise this mixing in some way?


The operation:

X[16] & (N-1)

is really, mathematically speaking: $$ X[16] \mathrm{\ mod\ } N $$ With a generic $N$, this operation must be done with an actual division, which is expensive; some CPU types don't provide it, and for CPU which do provide it (e.g. x86), it is quite slow (for instance, for 32-bit operands on an Intel Core2, division latency is 40 cycles). This would raise the computational cost by a non-negligible amount; correspondingly, it would decrease the memory hardness of scrypt (since, for a given CPU budget, it would be able to do less memory accesses).

However, when $N$ is a power of 2, the modulo can be done with a simple bitwise "AND", which is a matter of a single clock cycle.

  • $\begingroup$ ((UInt64)X[16] * N) >> 32 has similar properties and is relatively cheap on many CPUs. For example on x86 the high word of a 32x32 multiplication ends up in an second register as byproduct of the standard multiplication and thus is easy to compute. $\endgroup$ – CodesInChaos Apr 20 '14 at 16:08
  • $\begingroup$ It turns out upon further inspection that this is not the only modification that would need to be made. The X[16] bit was an optimized version of Integrify. Without it being N being a power of two, my understanding is that this is not accurate. However, I can't quite understand the paper well enough to implement it myself and can not find a reference implementation with arbitrary N value support $\endgroup$ – Earlz Apr 22 '14 at 1:04

Your Answer

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

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