Date: Thu, 21 Mar 2013 11:55:58 +0400 From: Solar Designer <solar@...nwall.com> To: scrypt@...snap.com, crypt-dev@...ts.openwall.com Subject: scrypt TMTO in numbers 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
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.