Date: Mon, 25 Nov 2013 15:05:46 +0400 From: Solar Designer <solar@...nwall.com> To: crypt-dev@...ts.openwall.com Subject: increasing scrypt SMix 1st loop AT cost Hi, Attached is a program that simulates scrypt's SMix with its original two loops, as well as 3 possible revisions of the first loop (thus a total of four code versions). The revisions are less friendly to TMTO, so should only be used when easy and efficient TMTO is not desired (for the defender's own use). loop1_pow2 increases SMix's total area-time cost for the attacker to 4/3 of original (that is, by one third). In practice, the increase is likely higher since this also makes TMTO less efficient (and as we've discussed before, an attacker with ASIC would actually want to use TMTO with classic scrypt). The revised first loop's AT cost is calculated as (1/2)^2 + (1/4)^2 + (1/8)^2 ..., which for large N approaches 1/3. loop1_mod increases SMix's total area-time cost for the attacker to 1.5 of original, similarly without consideration of its effect on TMTO yet. However, it has certain maybe-drawbacks compared to loop1_pow2: the distribution of j's is farther away from uniform (it is uniform for any given i, but not across all i's) and fewer different V_j's are being accessed total. These are in addition to drawbacks of the integer division itself: depends on chosen size of X (beyond bits in N-1), somewhat slow, not constant time, slightly non-uniform when size of X is not a lot larger than log2(N). loop1_wrap is similar to loop1_mod, but it replaces the modulo division with a custom function I came up with, which has both pros and cons. Currently my preference is loop1_pow2 (this is what I have in our scrypt-derived development tree). Program output: classic B' = 292735ce775aaef5 t_cost = 2097152 at_cost1 = 1073741824 at_cost2 = 549755813888 at_cost = 550829555712 at_cost1/t = 512 at_cost2/t = 262144 at_cost/t = 262656 total: nhits=663284 (63.26%) mhits=9 loop1_pow2 loop1: nhits=595349 (56.78%) mhits=10 B' = d9247fb08f9e807c t_cost = 2097152 at_cost1 = 183251937963 at_cost2 = 549755813888 at_cost = 733007751851 at_cost1/t = 87381 at_cost2/t = 262144 at_cost/t = 349525 total: nhits=882412 (84.15%) mhits=13 loop1_wrap loop1: nhits=456640 (43.55%) mhits=24 B' = b7283d0ff61c6599 t_cost = 2097152 at_cost1 = 274877644800 at_cost2 = 549755813888 at_cost = 824633458688 at_cost1/t = 131072 at_cost2/t = 262144 at_cost/t = 393216 total: nhits=830413 (79.19%) mhits=24 loop1_mod loop1: nhits=524257 (50.00%) mhits=21 B' = 2365d32db26bfc21 t_cost = 2097152 at_cost1 = 274877644800 at_cost2 = 549755813888 at_cost = 824633458688 at_cost1/t = 131072 at_cost2/t = 262144 at_cost/t = 393216 total: nhits=855632 (81.60%) mhits=22 For nhits, higher is better (more V elements were read from). For mhits, lower is better (suggests we're closer to uniform distribution, although indeed there's no guarantee from just looking at this value). I've also tried compressing sequences of j's with gzip and comparing the compressed sizes, I actually looked at lists of j's sorted by hit count, and I similarly tested many other possible definitions of wrap(). Alexander View attachment "sim-at.c" of type "text/x-c" (4319 bytes)
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.