scrypt TMTO in numbers

[Solar Designer <solar@openwall.com>]

Hi,

To have a baseline for various scrypt TMTO defeaters and attacks on
them, which I posted about to crypt-dev recently, I implemented the
obvious TMTO for the original scrypt (as a patch to crypto_scrypt-ref.c)
and obtained some actual numbers for the TMTO applied to computation of:

scrypt("pleaseletmein", "SodiumChloride", 16384, 8, 1)

(That's one of the test vectors from the scrypt paper.)

Here they are:

TMTO = 0 comp = 32768 memmax = 16384 memavg = 12288.25 avg/max = 0.750 atavg = 403M atmax = 537M
TMTO = 2 comp = 41018 memmax = 8192 memavg = 6556.12 avg/max = 0.800 atavg = 269M atmax = 336M
TMTO = 3 comp = 49187 memmax = 5462 memavg = 4552.37 avg/max = 0.833 atavg = 224M atmax = 269M
TMTO = 4 comp = 57348 memmax = 4096 memavg = 3511.04 avg/max = 0.857 atavg = 201M atmax = 235M
TMTO = 8 comp = 90500 memmax = 2048 memavg = 1862.71 avg/max = 0.910 atavg = 169M atmax = 185M
TMTO = 10 comp = 106940 memmax = 1639 memavg = 1513.48 avg/max = 0.923 atavg = 162M atmax = 175M
TMTO = 16 comp = 156396 memmax = 1024 memavg = 970.42 avg/max = 0.948 atavg = 152M atmax = 160M
TMTO = 32 comp = 286860 memmax = 512 memavg = 497.41 avg/max = 0.971 atavg = 143M atmax = 147M
TMTO = 64 comp = 547180 memmax = 256 memavg = 252.18 avg/max = 0.985 atavg = 138M atmax = 140M
TMTO = 100 comp = 841080 memmax = 164 memavg = 162.41 avg/max = 0.990 atavg = 137M atmax = 138M

Explanation:

"TMTO" is the time-memory tradeoff factor - how much we want to reduce
the maximum memory usage.  Zero means original scrypt algorithm, without
taking advantage of any TMTO.  (TMTO = 1 would produce the same results
via a different code path.)

"comp" is the amount of computation, as measured in BlockMix calls.

"memmax" and "memavg" are the maximum and average memory usage,
respectively.  With these scrypt parameters (r = 8, p = 1), they happen
to be in kilobytes, which is handy.  The average is across BlockMix
calls, assuming that a constant time elapses between the calls.

"avg/max" is the ratio of average to maximum memory usage.  Without
TMTO, it is 3/4.  This means that an attacker capable of reallocating
memory between multiple parallel scrypt instances may reduce their total
memory needs to 3/4 of max (and thereby fit 4/3 more scrypt cores per
ASIC, etc.) by optimally (de)synchronizing their operation.  At higher
TMTO settings, this ratio approaches 1, thereby making this possible
optimization nearly useless.

"atavg" and "atmax" are the area-time costs as estimated using average
memory usage (with the optimization described above) and using maximum
memory usage (without that optimization).  These costs do not include
the area consumed by the crypto core itself (they're based on cost of
memory only), so they're reasonably accurate only as long as the memory
usage stays reasonably high.

These tests confirm that asymptotically there's a 4x reduction in
area-time as compared to naive non-TMTO implementation (always
allocating the maximum needed memory per scrypt core).  At TMTO = 100,
we get 537M / 138M = 3.89 times reduction in area-time.

They also confirm that with many cores it is possible to reduce the
per-core memory usage to 3/4 of max when not exploiting the TMTO, and
that this optimization becomes nearly useless at high TMTO factors.
Asymptotically, there's a 3x reduction in area-time as compared to
optimally (de)synchronized multi-core non-TMTO implementation.
At TMTO = 100, we get 403M / 137M = 2.94 times reduction in area-time.

It is important to note that these numbers include cost of both loops in
SMix, whereas the proofs and cost estimates in the scrypt paper were
based on the second loop only.  However, for practical purposes I prefer
to consider both loops at once.

It is clear that attackers with ASICs benefit from the TMTO, albeit up
to "a constant factor".  Thus, modifications of scrypt to defeat the
TMTO (to some extent) may help not only against GPUs, but also against
ASICs (which scrypt was designed to protect against, unlike GPUs).

I am going to continue posting about possible incompatible changes to
scrypt (thus, deviating from scrypt) to crypt-dev only.  I made this
posting to the scrypt list as well because the numbers above are for
scrypt proper (a modified implementation of it producing same results,
as verified against test vectors).

This is nothing new/unexpected, but I thought some of you could find
this useful to get a better feeling of how the scrypt TMTO behaves.

Alexander